Eviction.java 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404
  1. package protocols;
  2. import java.util.Arrays;
  3. import com.oblivm.backend.flexsc.CompEnv;
  4. import com.oblivm.backend.gc.GCSignal;
  5. import com.oblivm.backend.gc.regular.GCEva;
  6. import com.oblivm.backend.gc.regular.GCGen;
  7. import com.oblivm.backend.network.Network;
  8. import communication.Communication;
  9. import crypto.Crypto;
  10. import gc.GCRoute;
  11. import gc.GCUtil;
  12. import oram.Bucket;
  13. import oram.Forest;
  14. import oram.Metadata;
  15. import oram.Tree;
  16. import oram.Tuple;
  17. import struct.Party;
  18. import subprotocols.PermuteIndex;
  19. import subprotocols.PermuteTarget;
  20. import subprotocols.SSXOT;
  21. import util.M;
  22. import util.Util;
  23. // TODO: set bucket on path
  24. public class Eviction extends Protocol {
  25. public Eviction(Communication con1, Communication con2) {
  26. super(con1, con2);
  27. online_band = all.Eviction_on;
  28. offline_band = all.Eviction_off;
  29. timer = all.Eviction;
  30. }
  31. private int[] prepareEviction(int[] target, int[] ti, int W) {
  32. int d = ti.length;
  33. int[] evict = new int[W * d];
  34. for (int r = 0; r < d; r++) {
  35. int tupleIndex = r * W + ti[r];
  36. for (int c = 0; c < W; c++) {
  37. int currIndex = r * W + c;
  38. if (currIndex == tupleIndex) {
  39. int targetIndex = target[r] * W + ti[target[r]];
  40. evict[targetIndex] = currIndex;
  41. } else
  42. evict[currIndex] = currIndex;
  43. }
  44. }
  45. return evict;
  46. }
  47. public void runE(boolean firstTree, int[] tupleParam, byte[] Li, Tuple[] originalPath, Tree OTi) {
  48. if (firstTree) {
  49. // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new
  50. // Bucket(originalPath) });
  51. return;
  52. }
  53. timer.start(M.offline_comp);
  54. // GC
  55. int d = OTi.getD();
  56. int sw = OTi.getStashSize();
  57. int w = OTi.getW();
  58. int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
  59. GCSignal[][] evict_LiKeyPairs = GCUtil.genKeyPairs(d - 1);
  60. GCSignal[] LiZeroKeys = GCUtil.getZeroKeys(evict_LiKeyPairs);
  61. GCSignal[][][] evict_E_feKeyPairs = new GCSignal[d][][];
  62. GCSignal[][][] evict_C_feKeyPairs = new GCSignal[d][][];
  63. GCSignal[][] E_feZeroKeys = new GCSignal[d][];
  64. GCSignal[][] C_feZeroKeys = new GCSignal[d][];
  65. GCSignal[][][][] evict_E_labelKeyPairs = new GCSignal[d][w][][];
  66. GCSignal[][][][] evict_C_labelKeyPairs = new GCSignal[d][w][][];
  67. GCSignal[][][] E_labelZeroKeys = new GCSignal[d][w][];
  68. GCSignal[][][] C_labelZeroKeys = new GCSignal[d][w][];
  69. GCSignal[][][] evict_deltaKeyPairs = new GCSignal[d][][];
  70. GCSignal[][] deltaZeroKeys = new GCSignal[d][];
  71. for (int i = 0; i < d; i++) {
  72. evict_E_feKeyPairs[i] = GCUtil.genKeyPairs(w);
  73. evict_C_feKeyPairs[i] = GCUtil.genKeyPairs(w);
  74. E_feZeroKeys[i] = GCUtil.getZeroKeys(evict_E_feKeyPairs[i]);
  75. C_feZeroKeys[i] = GCUtil.getZeroKeys(evict_C_feKeyPairs[i]);
  76. evict_deltaKeyPairs[i] = GCUtil.genKeyPairs(logW);
  77. deltaZeroKeys[i] = GCUtil.getZeroKeys(evict_deltaKeyPairs[i]);
  78. for (int j = 0; j < w; j++) {
  79. evict_E_labelKeyPairs[i][j] = GCUtil.genKeyPairs(d - 1);
  80. evict_C_labelKeyPairs[i][j] = GCUtil.genKeyPairs(d - 1);
  81. E_labelZeroKeys[i][j] = GCUtil.getZeroKeys(evict_E_labelKeyPairs[i][j]);
  82. C_labelZeroKeys[i][j] = GCUtil.getZeroKeys(evict_C_labelKeyPairs[i][j]);
  83. }
  84. }
  85. Network channel = new Network(null, con1);
  86. CompEnv<GCSignal> gen = new GCGen(channel, timer, offline_band, M.offline_write);
  87. GCSignal[][][] outZeroKeys = new GCRoute<GCSignal>(gen, d, w).routing(LiZeroKeys, E_feZeroKeys, C_feZeroKeys,
  88. E_labelZeroKeys, C_labelZeroKeys, deltaZeroKeys);
  89. ((GCGen) gen).sendLastSetGTT();
  90. byte[][][] evict_tiOutKeyHashes = new byte[d][][];
  91. GCSignal[][][] evict_targetOutKeyPairs = new GCSignal[d][][];
  92. for (int i = 0; i < d; i++) {
  93. evict_tiOutKeyHashes[i] = GCUtil.genOutKeyHashes(outZeroKeys[1][i]);
  94. evict_targetOutKeyPairs[i] = GCUtil.recoverOutKeyPairs(outZeroKeys[0][i]);
  95. }
  96. timer.start(M.offline_write);
  97. con2.write(offline_band, evict_C_feKeyPairs);
  98. con2.write(offline_band, evict_C_labelKeyPairs);
  99. con1.write(offline_band, evict_tiOutKeyHashes);
  100. timer.stop(M.offline_write);
  101. // Permutation
  102. int[] evict_pi = Util.randomPermutation(d, Crypto.sr_CE);
  103. byte[][] evict_delta = new byte[d][(logW + 7) / 8];
  104. byte[][] evict_rho = new byte[d][(logW + 7) / 8];
  105. int[][] evict_delta_p = new int[d][];
  106. int[][] evict_rho_p = new int[d][];
  107. for (int i = 0; i < d; i++) {
  108. Crypto.sr_CE.nextBytes(evict_delta[i]);
  109. Crypto.sr_CE.nextBytes(evict_rho[i]);
  110. evict_delta_p[i] = Util.getXorPermutation(evict_delta[i], logW);
  111. evict_rho_p[i] = Util.getXorPermutation(evict_rho[i], logW);
  112. }
  113. timer.stop(M.offline_comp);
  114. ///////////////////////////////////////////////////////////////////
  115. timer.start(M.online_comp);
  116. Tuple[] pathTuples = new Tuple[d * w];
  117. System.arraycopy(originalPath, 0, pathTuples, 0, w);
  118. System.arraycopy(originalPath, sw, pathTuples, w, (d - 1) * w);
  119. Bucket[] pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, w, w);
  120. GCSignal[] LiInputKeys = GCUtil.revSelectKeys(evict_LiKeyPairs, Li);
  121. GCSignal[][] E_feInputKeys = new GCSignal[d][];
  122. GCSignal[][][] E_labelInputKeys = new GCSignal[d][][];
  123. GCSignal[][] deltaInputKeys = new GCSignal[d][];
  124. for (int i = 0; i < d; i++) {
  125. E_feInputKeys[i] = GCUtil.selectFeKeys(evict_E_feKeyPairs[i], pathBuckets[i].getTuples());
  126. E_labelInputKeys[i] = GCUtil.selectLabelKeys(evict_E_labelKeyPairs[i], pathBuckets[i].getTuples());
  127. deltaInputKeys[i] = GCUtil.revSelectKeys(evict_deltaKeyPairs[i], evict_delta[i]);
  128. }
  129. timer.start(M.online_write);
  130. con1.write(online_band, LiInputKeys);
  131. con1.write(online_band, E_feInputKeys);
  132. con1.write(online_band, E_labelInputKeys);
  133. con1.write(online_band, deltaInputKeys);
  134. timer.stop(M.online_write);
  135. PermuteTarget permutetarget = new PermuteTarget(con1, con2);
  136. permutetarget.runE(d, evict_pi, evict_targetOutKeyPairs);
  137. PermuteIndex permuteindex = new PermuteIndex(con1, con2);
  138. permuteindex.runE(w, evict_pi);
  139. int W = (int) Math.pow(2, logW);
  140. for (int i = 0; i < d; i++) {
  141. pathBuckets[i].expand(W);
  142. pathBuckets[i].permute(evict_delta_p[i]);
  143. }
  144. pathBuckets = Util.permute(pathBuckets, evict_pi);
  145. for (int i = 0; i < d; i++) {
  146. pathBuckets[i].permute(evict_rho_p[i]);
  147. }
  148. pathTuples = Bucket.bucketsToTuples(pathBuckets);
  149. SSXOT ssxot = new SSXOT(con1, con2);
  150. pathTuples = ssxot.runE(pathTuples, tupleParam);
  151. pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
  152. for (int i = 0; i < d; i++) {
  153. int[] rho_ivs = Util.inversePermutation(evict_rho_p[i]);
  154. pathBuckets[i].permute(rho_ivs);
  155. }
  156. int[] pi_ivs = Util.inversePermutation(evict_pi);
  157. pathBuckets = Util.permute(pathBuckets, pi_ivs);
  158. for (int i = 0; i < d; i++) {
  159. int[] delta_ivs = Util.inversePermutation(evict_delta_p[i]);
  160. pathBuckets[i].permute(delta_ivs);
  161. pathBuckets[i].shrink(w);
  162. }
  163. pathBuckets[0].expand(Arrays.copyOfRange(originalPath, w, sw));
  164. // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), pathBuckets);
  165. timer.stop(M.online_comp);
  166. }
  167. public void runD(boolean firstTree, int[] tupleParam, byte[] Li, Tree OTi) {
  168. if (firstTree) {
  169. timer.start(M.online_read);
  170. // Tuple[] originalPath = con2.readTupleArrayAndDec();
  171. timer.stop(M.online_read);
  172. // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new
  173. // Bucket(originalPath) });
  174. return;
  175. }
  176. timer.start(M.offline_comp);
  177. // GC
  178. int d = OTi.getD();
  179. int w = OTi.getW();
  180. int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
  181. GCSignal[] LiZeroKeys = GCUtil.genEmptyKeys(d - 1);
  182. GCSignal[][] E_feZeroKeys = new GCSignal[d][];
  183. GCSignal[][] C_feZeroKeys = new GCSignal[d][];
  184. GCSignal[][][] E_labelZeroKeys = new GCSignal[d][w][];
  185. GCSignal[][][] C_labelZeroKeys = new GCSignal[d][w][];
  186. GCSignal[][] deltaZeroKeys = new GCSignal[d][];
  187. for (int i = 0; i < d; i++) {
  188. E_feZeroKeys[i] = GCUtil.genEmptyKeys(w);
  189. C_feZeroKeys[i] = GCUtil.genEmptyKeys(w);
  190. deltaZeroKeys[i] = GCUtil.genEmptyKeys(logW);
  191. for (int j = 0; j < w; j++) {
  192. E_labelZeroKeys[i][j] = GCUtil.genEmptyKeys(d - 1);
  193. C_labelZeroKeys[i][j] = GCUtil.genEmptyKeys(d - 1);
  194. }
  195. }
  196. Network channel = new Network(con1, null);
  197. CompEnv<GCSignal> eva = new GCEva(channel, timer, M.offline_read);
  198. GCRoute<GCSignal> evict_gcroute = new GCRoute<GCSignal>(eva, d, w);
  199. evict_gcroute.routing(LiZeroKeys, E_feZeroKeys, C_feZeroKeys, E_labelZeroKeys, C_labelZeroKeys, deltaZeroKeys);
  200. ((GCEva) eva).receiveLastSetGTT();
  201. eva.setEvaluate();
  202. timer.start(M.offline_read);
  203. byte[][][] evict_tiOutKeyHashes = con1.readTripleByteArrayAndDec();
  204. timer.stop(M.offline_read);
  205. timer.stop(M.offline_comp);
  206. //////////////////////////////////////////////////////////////////////
  207. timer.start(M.online_comp);
  208. timer.start(M.online_read);
  209. GCSignal[] LiInputKeys = con1.readGCSignalArrayAndDec();
  210. GCSignal[][] E_feInputKeys = con1.readDoubleGCSignalArrayAndDec();
  211. GCSignal[][][] E_labelInputKeys = con1.readTripleGCSignalArrayAndDec();
  212. GCSignal[][] deltaInputKeys = con1.readDoubleGCSignalArrayAndDec();
  213. GCSignal[][] C_feInputKeys = con2.readDoubleGCSignalArrayAndDec();
  214. GCSignal[][][] C_labelInputKeys = con2.readTripleGCSignalArrayAndDec();
  215. timer.stop(M.online_read);
  216. GCSignal[][][] outKeys = evict_gcroute.routing(LiInputKeys, E_feInputKeys, C_feInputKeys, E_labelInputKeys,
  217. C_labelInputKeys, deltaInputKeys);
  218. byte[][] ti_p = new byte[deltaInputKeys.length][];
  219. for (int i = 0; i < ti_p.length; i++) {
  220. ti_p[i] = Util.padArray(GCUtil.evaOutKeys(outKeys[1][i], evict_tiOutKeyHashes[i]).toByteArray(),
  221. (logW + 7) / 8);
  222. }
  223. PermuteTarget permutetarget = new PermuteTarget(con1, con2);
  224. int[] target_pp = permutetarget.runD(firstTree, outKeys[0]);
  225. PermuteIndex permuteindex = new PermuteIndex(con1, con2);
  226. int[] ti_pp = permuteindex.runD(firstTree, ti_p, w);
  227. int W = (int) Math.pow(2, logW);
  228. int[] evict = prepareEviction(target_pp, ti_pp, W);
  229. SSXOT ssxot = new SSXOT(con1, con2);
  230. ssxot.runD(evict.length, evict.length, tupleParam, evict);
  231. timer.start(M.online_read);
  232. // Bucket[] pathBuckets = con2.readBucketArrayAndDec();
  233. timer.stop(M.online_read);
  234. // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), pathBuckets);
  235. timer.stop(M.online_comp);
  236. }
  237. public void runC(boolean firstTree, int[] tupleParam, Tuple[] originalPath, int d, int sw, int w) {
  238. if (firstTree) {
  239. timer.start(M.online_write);
  240. // con2.write(online_band, originalPath);
  241. timer.stop(M.online_write);
  242. return;
  243. }
  244. timer.start(M.offline_comp);
  245. // GC
  246. timer.start(M.offline_read);
  247. GCSignal[][][] evict_C_feKeyPairs = con1.readTripleGCSignalArrayAndDec();
  248. GCSignal[][][][] evict_C_labelKeyPairs = con1.readQuadGCSignalArrayAndDec();
  249. timer.stop(M.offline_read);
  250. // Permutation
  251. int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
  252. int[] evict_pi = Util.randomPermutation(d, Crypto.sr_CE);
  253. byte[][] evict_delta = new byte[d][(logW + 7) / 8];
  254. byte[][] evict_rho = new byte[d][(logW + 7) / 8];
  255. int[][] evict_delta_p = new int[d][];
  256. int[][] evict_rho_p = new int[d][];
  257. for (int i = 0; i < d; i++) {
  258. Crypto.sr_CE.nextBytes(evict_delta[i]);
  259. Crypto.sr_CE.nextBytes(evict_rho[i]);
  260. evict_delta_p[i] = Util.getXorPermutation(evict_delta[i], logW);
  261. evict_rho_p[i] = Util.getXorPermutation(evict_rho[i], logW);
  262. }
  263. timer.stop(M.offline_comp);
  264. ///////////////////////////////////////////////////////////////
  265. timer.start(M.online_comp);
  266. Tuple[] pathTuples = new Tuple[d * w];
  267. System.arraycopy(originalPath, 0, pathTuples, 0, w);
  268. System.arraycopy(originalPath, sw, pathTuples, w, (d - 1) * w);
  269. Bucket[] pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, w, w);
  270. GCSignal[][] C_feInputKeys = new GCSignal[d][];
  271. GCSignal[][][] C_labelInputKeys = new GCSignal[d][][];
  272. for (int i = 0; i < d; i++) {
  273. C_feInputKeys[i] = GCUtil.selectFeKeys(evict_C_feKeyPairs[i], pathBuckets[i].getTuples());
  274. C_labelInputKeys[i] = GCUtil.selectLabelKeys(evict_C_labelKeyPairs[i], pathBuckets[i].getTuples());
  275. }
  276. timer.start(M.online_write);
  277. con2.write(online_band, C_feInputKeys);
  278. con2.write(online_band, C_labelInputKeys);
  279. timer.stop(M.online_write);
  280. PermuteTarget permutetarget = new PermuteTarget(con1, con2);
  281. permutetarget.runC(firstTree, d, evict_pi);
  282. PermuteIndex permuteindex = new PermuteIndex(con1, con2);
  283. permuteindex.runC(firstTree, w, evict_pi, evict_rho);
  284. int W = (int) Math.pow(2, logW);
  285. for (int i = 0; i < d; i++) {
  286. pathBuckets[i].expand(W);
  287. pathBuckets[i].permute(evict_delta_p[i]);
  288. }
  289. pathBuckets = Util.permute(pathBuckets, evict_pi);
  290. for (int i = 0; i < d; i++) {
  291. pathBuckets[i].permute(evict_rho_p[i]);
  292. }
  293. pathTuples = Bucket.bucketsToTuples(pathBuckets);
  294. SSXOT ssxot = new SSXOT(con1, con2);
  295. pathTuples = ssxot.runC(pathTuples, tupleParam);
  296. pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
  297. for (int i = 0; i < d; i++) {
  298. int[] rho_ivs = Util.inversePermutation(evict_rho_p[i]);
  299. pathBuckets[i].permute(rho_ivs);
  300. }
  301. int[] pi_ivs = Util.inversePermutation(evict_pi);
  302. pathBuckets = Util.permute(pathBuckets, pi_ivs);
  303. for (int i = 0; i < d; i++) {
  304. int[] delta_ivs = Util.inversePermutation(evict_delta_p[i]);
  305. pathBuckets[i].permute(delta_ivs);
  306. pathBuckets[i].shrink(w);
  307. }
  308. pathBuckets[0].expand(Arrays.copyOfRange(originalPath, w, sw));
  309. timer.start(M.online_write);
  310. // con2.write(online_band, pathBuckets);
  311. timer.stop(M.online_write);
  312. timer.stop(M.online_comp);
  313. }
  314. @Override
  315. public void run(Party party, Metadata md, Forest[] forest) {
  316. System.out.println("Use PIRRetrieve to test Eviction");
  317. }
  318. @Override
  319. public void run(Party party, Metadata md, Forest forest) {
  320. }
  321. }