123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407 |
- package protocols;
- import java.util.Arrays;
- import com.oblivm.backend.flexsc.CompEnv;
- import com.oblivm.backend.gc.GCSignal;
- import com.oblivm.backend.gc.regular.GCEva;
- import com.oblivm.backend.gc.regular.GCGen;
- import com.oblivm.backend.network.Network;
- import communication.Communication;
- import crypto.Crypto;
- import gc.GCRoute;
- import gc.GCUtil;
- import oram.Bucket;
- import oram.Forest;
- import oram.Metadata;
- import oram.Tree;
- import oram.Tuple;
- import struct.Party;
- import subprotocols.PermuteIndex;
- import subprotocols.PermuteTarget;
- import subprotocols.SSXOT;
- import util.M;
- import util.P;
- import util.Util;
- // TODO: set bucket on path
- public class Eviction extends Protocol {
- int pid = P.EVI;
- public Eviction(Communication con1, Communication con2) {
- super(con1, con2);
- online_band = all.online_band[pid];
- offline_band = all.offline_band[pid];
- timer = all.timer[pid];
- }
- private int[] prepareEviction(int[] target, int[] ti, int W) {
- int d = ti.length;
- int[] evict = new int[W * d];
- for (int r = 0; r < d; r++) {
- int tupleIndex = r * W + ti[r];
- for (int c = 0; c < W; c++) {
- int currIndex = r * W + c;
- if (currIndex == tupleIndex) {
- int targetIndex = target[r] * W + ti[target[r]];
- evict[targetIndex] = currIndex;
- } else
- evict[currIndex] = currIndex;
- }
- }
- return evict;
- }
- public void runE(boolean firstTree, int[] tupleParam, byte[] Li, Tuple[] originalPath, Tree OTi) {
- if (firstTree) {
- // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new
- // Bucket(originalPath) });
- return;
- }
- timer.start(M.offline_comp);
- // GC
- int d = OTi.getD();
- int sw = OTi.getStashSize();
- int w = OTi.getW();
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- GCSignal[][] evict_LiKeyPairs = GCUtil.genKeyPairs(d - 1);
- GCSignal[] LiZeroKeys = GCUtil.getZeroKeys(evict_LiKeyPairs);
- GCSignal[][][] evict_E_feKeyPairs = new GCSignal[d][][];
- GCSignal[][][] evict_C_feKeyPairs = new GCSignal[d][][];
- GCSignal[][] E_feZeroKeys = new GCSignal[d][];
- GCSignal[][] C_feZeroKeys = new GCSignal[d][];
- GCSignal[][][][] evict_E_labelKeyPairs = new GCSignal[d][w][][];
- GCSignal[][][][] evict_C_labelKeyPairs = new GCSignal[d][w][][];
- GCSignal[][][] E_labelZeroKeys = new GCSignal[d][w][];
- GCSignal[][][] C_labelZeroKeys = new GCSignal[d][w][];
- GCSignal[][][] evict_deltaKeyPairs = new GCSignal[d][][];
- GCSignal[][] deltaZeroKeys = new GCSignal[d][];
- for (int i = 0; i < d; i++) {
- evict_E_feKeyPairs[i] = GCUtil.genKeyPairs(w);
- evict_C_feKeyPairs[i] = GCUtil.genKeyPairs(w);
- E_feZeroKeys[i] = GCUtil.getZeroKeys(evict_E_feKeyPairs[i]);
- C_feZeroKeys[i] = GCUtil.getZeroKeys(evict_C_feKeyPairs[i]);
- evict_deltaKeyPairs[i] = GCUtil.genKeyPairs(logW);
- deltaZeroKeys[i] = GCUtil.getZeroKeys(evict_deltaKeyPairs[i]);
- for (int j = 0; j < w; j++) {
- evict_E_labelKeyPairs[i][j] = GCUtil.genKeyPairs(d - 1);
- evict_C_labelKeyPairs[i][j] = GCUtil.genKeyPairs(d - 1);
- E_labelZeroKeys[i][j] = GCUtil.getZeroKeys(evict_E_labelKeyPairs[i][j]);
- C_labelZeroKeys[i][j] = GCUtil.getZeroKeys(evict_C_labelKeyPairs[i][j]);
- }
- }
- Network channel = new Network(null, con1);
- CompEnv<GCSignal> gen = new GCGen(channel, timer, offline_band, M.offline_write);
- GCSignal[][][] outZeroKeys = new GCRoute<GCSignal>(gen, d, w).routing(LiZeroKeys, E_feZeroKeys, C_feZeroKeys,
- E_labelZeroKeys, C_labelZeroKeys, deltaZeroKeys);
- ((GCGen) gen).sendLastSetGTT();
- byte[][][] evict_tiOutKeyHashes = new byte[d][][];
- GCSignal[][][] evict_targetOutKeyPairs = new GCSignal[d][][];
- for (int i = 0; i < d; i++) {
- evict_tiOutKeyHashes[i] = GCUtil.genOutKeyHashes(outZeroKeys[1][i]);
- evict_targetOutKeyPairs[i] = GCUtil.recoverOutKeyPairs(outZeroKeys[0][i]);
- }
- timer.start(M.offline_write);
- con2.write(offline_band, evict_C_feKeyPairs);
- con2.write(offline_band, evict_C_labelKeyPairs);
- con1.write(offline_band, evict_tiOutKeyHashes);
- timer.stop(M.offline_write);
- // Permutation
- int[] evict_pi = Util.randomPermutation(d, Crypto.sr_CE);
- byte[][] evict_delta = new byte[d][(logW + 7) / 8];
- byte[][] evict_rho = new byte[d][(logW + 7) / 8];
- int[][] evict_delta_p = new int[d][];
- int[][] evict_rho_p = new int[d][];
- for (int i = 0; i < d; i++) {
- Crypto.sr_CE.nextBytes(evict_delta[i]);
- Crypto.sr_CE.nextBytes(evict_rho[i]);
- evict_delta_p[i] = Util.getXorPermutation(evict_delta[i], logW);
- evict_rho_p[i] = Util.getXorPermutation(evict_rho[i], logW);
- }
- timer.stop(M.offline_comp);
- ///////////////////////////////////////////////////////////////////
- timer.start(M.online_comp);
- Tuple[] pathTuples = new Tuple[d * w];
- System.arraycopy(originalPath, 0, pathTuples, 0, w);
- System.arraycopy(originalPath, sw, pathTuples, w, (d - 1) * w);
- Bucket[] pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, w, w);
- GCSignal[] LiInputKeys = GCUtil.revSelectKeys(evict_LiKeyPairs, Li);
- GCSignal[][] E_feInputKeys = new GCSignal[d][];
- GCSignal[][][] E_labelInputKeys = new GCSignal[d][][];
- GCSignal[][] deltaInputKeys = new GCSignal[d][];
- for (int i = 0; i < d; i++) {
- E_feInputKeys[i] = GCUtil.selectFeKeys(evict_E_feKeyPairs[i], pathBuckets[i].getTuples());
- E_labelInputKeys[i] = GCUtil.selectLabelKeys(evict_E_labelKeyPairs[i], pathBuckets[i].getTuples());
- deltaInputKeys[i] = GCUtil.revSelectKeys(evict_deltaKeyPairs[i], evict_delta[i]);
- }
- timer.start(M.online_write);
- con1.write(online_band, LiInputKeys);
- con1.write(online_band, E_feInputKeys);
- con1.write(online_band, E_labelInputKeys);
- con1.write(online_band, deltaInputKeys);
- timer.stop(M.online_write);
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- permutetarget.runE(d, evict_pi, evict_targetOutKeyPairs);
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- permuteindex.runE(w, evict_pi);
- int W = (int) Math.pow(2, logW);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].expand(W);
- pathBuckets[i].permute(evict_delta_p[i]);
- }
- pathBuckets = Util.permute(pathBuckets, evict_pi);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].permute(evict_rho_p[i]);
- }
- pathTuples = Bucket.bucketsToTuples(pathBuckets);
- SSXOT ssxot = new SSXOT(con1, con2);
- pathTuples = ssxot.runE(pathTuples, tupleParam);
- pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
- for (int i = 0; i < d; i++) {
- int[] rho_ivs = Util.inversePermutation(evict_rho_p[i]);
- pathBuckets[i].permute(rho_ivs);
- }
- int[] pi_ivs = Util.inversePermutation(evict_pi);
- pathBuckets = Util.permute(pathBuckets, pi_ivs);
- for (int i = 0; i < d; i++) {
- int[] delta_ivs = Util.inversePermutation(evict_delta_p[i]);
- pathBuckets[i].permute(delta_ivs);
- pathBuckets[i].shrink(w);
- }
- pathBuckets[0].expand(Arrays.copyOfRange(originalPath, w, sw));
- // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), pathBuckets);
- timer.stop(M.online_comp);
- }
- public void runD(boolean firstTree, int[] tupleParam, byte[] Li, Tree OTi) {
- if (firstTree) {
- timer.start(M.online_read);
- // Tuple[] originalPath = con2.readTupleArrayAndDec();
- timer.stop(M.online_read);
- // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new
- // Bucket(originalPath) });
- return;
- }
- timer.start(M.offline_comp);
- // GC
- int d = OTi.getD();
- int w = OTi.getW();
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- GCSignal[] LiZeroKeys = GCUtil.genEmptyKeys(d - 1);
- GCSignal[][] E_feZeroKeys = new GCSignal[d][];
- GCSignal[][] C_feZeroKeys = new GCSignal[d][];
- GCSignal[][][] E_labelZeroKeys = new GCSignal[d][w][];
- GCSignal[][][] C_labelZeroKeys = new GCSignal[d][w][];
- GCSignal[][] deltaZeroKeys = new GCSignal[d][];
- for (int i = 0; i < d; i++) {
- E_feZeroKeys[i] = GCUtil.genEmptyKeys(w);
- C_feZeroKeys[i] = GCUtil.genEmptyKeys(w);
- deltaZeroKeys[i] = GCUtil.genEmptyKeys(logW);
- for (int j = 0; j < w; j++) {
- E_labelZeroKeys[i][j] = GCUtil.genEmptyKeys(d - 1);
- C_labelZeroKeys[i][j] = GCUtil.genEmptyKeys(d - 1);
- }
- }
- Network channel = new Network(con1, null);
- CompEnv<GCSignal> eva = new GCEva(channel, timer, M.offline_read);
- GCRoute<GCSignal> evict_gcroute = new GCRoute<GCSignal>(eva, d, w);
- evict_gcroute.routing(LiZeroKeys, E_feZeroKeys, C_feZeroKeys, E_labelZeroKeys, C_labelZeroKeys, deltaZeroKeys);
- ((GCEva) eva).receiveLastSetGTT();
- eva.setEvaluate();
- timer.start(M.offline_read);
- byte[][][] evict_tiOutKeyHashes = con1.readTripleByteArrayAndDec();
- timer.stop(M.offline_read);
- timer.stop(M.offline_comp);
- //////////////////////////////////////////////////////////////////////
- timer.start(M.online_comp);
- timer.start(M.online_read);
- GCSignal[] LiInputKeys = con1.readGCSignalArrayAndDec();
- GCSignal[][] E_feInputKeys = con1.readDoubleGCSignalArrayAndDec();
- GCSignal[][][] E_labelInputKeys = con1.readTripleGCSignalArrayAndDec();
- GCSignal[][] deltaInputKeys = con1.readDoubleGCSignalArrayAndDec();
- GCSignal[][] C_feInputKeys = con2.readDoubleGCSignalArrayAndDec();
- GCSignal[][][] C_labelInputKeys = con2.readTripleGCSignalArrayAndDec();
- timer.stop(M.online_read);
- GCSignal[][][] outKeys = evict_gcroute.routing(LiInputKeys, E_feInputKeys, C_feInputKeys, E_labelInputKeys,
- C_labelInputKeys, deltaInputKeys);
- byte[][] ti_p = new byte[deltaInputKeys.length][];
- for (int i = 0; i < ti_p.length; i++) {
- ti_p[i] = Util.padArray(GCUtil.evaOutKeys(outKeys[1][i], evict_tiOutKeyHashes[i]).toByteArray(),
- (logW + 7) / 8);
- }
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- int[] target_pp = permutetarget.runD(firstTree, outKeys[0]);
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- int[] ti_pp = permuteindex.runD(firstTree, ti_p, w);
- int W = (int) Math.pow(2, logW);
- int[] evict = prepareEviction(target_pp, ti_pp, W);
- SSXOT ssxot = new SSXOT(con1, con2);
- ssxot.runD(evict.length, evict.length, tupleParam, evict);
- timer.start(M.online_read);
- // Bucket[] pathBuckets = con2.readBucketArrayAndDec();
- timer.stop(M.online_read);
- // OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), pathBuckets);
- timer.stop(M.online_comp);
- }
- public void runC(boolean firstTree, int[] tupleParam, Tuple[] originalPath, int d, int sw, int w) {
- if (firstTree) {
- timer.start(M.online_write);
- // con2.write(online_band, originalPath);
- timer.stop(M.online_write);
- return;
- }
- timer.start(M.offline_comp);
- // GC
- timer.start(M.offline_read);
- GCSignal[][][] evict_C_feKeyPairs = con1.readTripleGCSignalArrayAndDec();
- GCSignal[][][][] evict_C_labelKeyPairs = con1.readQuadGCSignalArrayAndDec();
- timer.stop(M.offline_read);
- // Permutation
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- int[] evict_pi = Util.randomPermutation(d, Crypto.sr_CE);
- byte[][] evict_delta = new byte[d][(logW + 7) / 8];
- byte[][] evict_rho = new byte[d][(logW + 7) / 8];
- int[][] evict_delta_p = new int[d][];
- int[][] evict_rho_p = new int[d][];
- for (int i = 0; i < d; i++) {
- Crypto.sr_CE.nextBytes(evict_delta[i]);
- Crypto.sr_CE.nextBytes(evict_rho[i]);
- evict_delta_p[i] = Util.getXorPermutation(evict_delta[i], logW);
- evict_rho_p[i] = Util.getXorPermutation(evict_rho[i], logW);
- }
- timer.stop(M.offline_comp);
- ///////////////////////////////////////////////////////////////
- timer.start(M.online_comp);
- Tuple[] pathTuples = new Tuple[d * w];
- System.arraycopy(originalPath, 0, pathTuples, 0, w);
- System.arraycopy(originalPath, sw, pathTuples, w, (d - 1) * w);
- Bucket[] pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, w, w);
- GCSignal[][] C_feInputKeys = new GCSignal[d][];
- GCSignal[][][] C_labelInputKeys = new GCSignal[d][][];
- for (int i = 0; i < d; i++) {
- C_feInputKeys[i] = GCUtil.selectFeKeys(evict_C_feKeyPairs[i], pathBuckets[i].getTuples());
- C_labelInputKeys[i] = GCUtil.selectLabelKeys(evict_C_labelKeyPairs[i], pathBuckets[i].getTuples());
- }
- timer.start(M.online_write);
- con2.write(online_band, C_feInputKeys);
- con2.write(online_band, C_labelInputKeys);
- timer.stop(M.online_write);
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- permutetarget.runC(firstTree, d, evict_pi);
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- permuteindex.runC(firstTree, w, evict_pi, evict_rho);
- int W = (int) Math.pow(2, logW);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].expand(W);
- pathBuckets[i].permute(evict_delta_p[i]);
- }
- pathBuckets = Util.permute(pathBuckets, evict_pi);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].permute(evict_rho_p[i]);
- }
- pathTuples = Bucket.bucketsToTuples(pathBuckets);
- SSXOT ssxot = new SSXOT(con1, con2);
- pathTuples = ssxot.runC(pathTuples, tupleParam);
- pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
- for (int i = 0; i < d; i++) {
- int[] rho_ivs = Util.inversePermutation(evict_rho_p[i]);
- pathBuckets[i].permute(rho_ivs);
- }
- int[] pi_ivs = Util.inversePermutation(evict_pi);
- pathBuckets = Util.permute(pathBuckets, pi_ivs);
- for (int i = 0; i < d; i++) {
- int[] delta_ivs = Util.inversePermutation(evict_delta_p[i]);
- pathBuckets[i].permute(delta_ivs);
- pathBuckets[i].shrink(w);
- }
- pathBuckets[0].expand(Arrays.copyOfRange(originalPath, w, sw));
- timer.start(M.online_write);
- // con2.write(online_band, pathBuckets);
- timer.stop(M.online_write);
- timer.stop(M.online_comp);
- }
- @Override
- public void run(Party party, Metadata md, Forest[] forest) {
- System.out.println("Use PIRRetrieve to test Eviction");
- }
- @Override
- public void run(Party party, Metadata md, Forest forest) {
- }
- }
|