123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255 |
- package protocols;
- import java.math.BigInteger;
- import java.util.Arrays;
- import com.oblivm.backend.gc.GCSignal;
- import communication.Communication;
- import gc.GCUtil;
- import oram.Bucket;
- import oram.Forest;
- import oram.Metadata;
- import oram.Tree;
- import oram.Tuple;
- import protocols.struct.Party;
- import protocols.struct.PreData;
- import util.M;
- import util.P;
- import util.Timer;
- import util.Util;
- public class Eviction extends Protocol {
- private int pid = P.EVI;
- public Eviction(Communication con1, Communication con2) {
- super(con1, con2);
- }
- 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(PreData predata, boolean firstTree, byte[] Li, Tuple[] originalPath, Tree OTi, Timer timer) {
- timer.start(pid, M.online_comp);
- if (firstTree) {
- OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new Bucket(originalPath) });
- timer.stop(pid, M.online_comp);
- return;
- }
- int d = OTi.getD();
- int sw = OTi.getStashSize();
- int w = OTi.getW();
- 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(predata.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(predata.evict_E_feKeyPairs[i], pathBuckets[i].getTuples());
- E_labelInputKeys[i] = GCUtil.selectLabelKeys(predata.evict_E_labelKeyPairs[i], pathBuckets[i].getTuples());
- deltaInputKeys[i] = GCUtil.revSelectKeys(predata.evict_deltaKeyPairs[i], predata.evict_delta[i]);
- }
- timer.start(pid, M.online_write);
- con1.write(pid, LiInputKeys);
- con1.write(pid, E_feInputKeys);
- con1.write(pid, E_labelInputKeys);
- con1.write(pid, deltaInputKeys);
- timer.stop(pid, M.online_write);
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- permutetarget.runE();
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- permuteindex.runE();
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- int W = (int) Math.pow(2, logW);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].expand(W);
- pathBuckets[i].permute(predata.evict_delta_p[i]);
- }
- pathBuckets = Util.permute(pathBuckets, predata.evict_pi);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].permute(predata.evict_rho_p[i]);
- }
- pathTuples = Bucket.bucketsToTuples(pathBuckets);
- SSXOT ssxot = new SSXOT(con1, con2, 1);
- pathTuples = ssxot.runE(predata, pathTuples, timer);
- pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
- for (int i = 0; i < d; i++) {
- int[] rho_ivs = Util.inversePermutation(predata.evict_rho_p[i]);
- pathBuckets[i].permute(rho_ivs);
- }
- int[] pi_ivs = Util.inversePermutation(predata.evict_pi);
- pathBuckets = Util.permute(pathBuckets, pi_ivs);
- for (int i = 0; i < d; i++) {
- int[] delta_ivs = Util.inversePermutation(predata.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(pid, M.online_comp);
- }
- public void runD(PreData predata, boolean firstTree, byte[] Li, Tree OTi, Timer timer) {
- timer.start(pid, M.online_comp);
- if (firstTree) {
- timer.start(pid, M.online_read);
- Tuple[] originalPath = con2.readTupleArray(pid);
- timer.stop(pid, M.online_read);
- OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), new Bucket[] { new Bucket(originalPath) });
- timer.stop(pid, M.online_comp);
- return;
- }
- timer.start(pid, M.online_read);
- GCSignal[] LiInputKeys = con1.readGCSignalArray(pid);
- GCSignal[][] E_feInputKeys = con1.readDoubleGCSignalArray(pid);
- GCSignal[][][] E_labelInputKeys = con1.readTripleGCSignalArray(pid);
- GCSignal[][] deltaInputKeys = con1.readDoubleGCSignalArray(pid);
- GCSignal[][] C_feInputKeys = con2.readDoubleGCSignalArray(pid);
- GCSignal[][][] C_labelInputKeys = con2.readTripleGCSignalArray(pid);
- timer.stop(pid, M.online_read);
- int w = OTi.getW();
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- GCSignal[][][] outKeys = predata.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], predata.evict_tiOutKeyHashes[i]).toByteArray(),
- (logW + 7) / 8);
- }
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- int[] target_pp = permutetarget.runD(predata, firstTree, outKeys[0], timer);
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- int[] ti_pp = permuteindex.runD(predata, firstTree, ti_p, w, timer);
- int W = (int) Math.pow(2, logW);
- int[] evict = prepareEviction(target_pp, ti_pp, W);
- SSXOT ssxot = new SSXOT(con1, con2, 1);
- ssxot.runD(predata, evict, timer);
- timer.start(pid, M.online_read);
- Bucket[] pathBuckets = con2.readBucketArray(pid);
- timer.stop(pid, M.online_read);
- OTi.setBucketsOnPath(new BigInteger(1, Li).longValue(), pathBuckets);
- timer.stop(pid, M.online_comp);
- }
- public void runC(PreData predata, boolean firstTree, Tuple[] originalPath, int d, int sw, int w, Timer timer) {
- if (firstTree) {
- timer.start(pid, M.online_write);
- con2.write(pid, originalPath);
- timer.stop(pid, M.online_write);
- return;
- }
- timer.start(pid, 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(predata.evict_C_feKeyPairs[i], pathBuckets[i].getTuples());
- C_labelInputKeys[i] = GCUtil.selectLabelKeys(predata.evict_C_labelKeyPairs[i], pathBuckets[i].getTuples());
- }
- timer.start(pid, M.online_write);
- con2.write(pid, C_feInputKeys);
- con2.write(pid, C_labelInputKeys);
- timer.stop(pid, M.online_write);
- PermuteTarget permutetarget = new PermuteTarget(con1, con2);
- permutetarget.runC(predata, firstTree, timer);
- PermuteIndex permuteindex = new PermuteIndex(con1, con2);
- permuteindex.runC(predata, firstTree, timer);
- int logW = (int) Math.ceil(Math.log(w + 1) / Math.log(2));
- int W = (int) Math.pow(2, logW);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].expand(W);
- pathBuckets[i].permute(predata.evict_delta_p[i]);
- }
- pathBuckets = Util.permute(pathBuckets, predata.evict_pi);
- for (int i = 0; i < d; i++) {
- pathBuckets[i].permute(predata.evict_rho_p[i]);
- }
- pathTuples = Bucket.bucketsToTuples(pathBuckets);
- SSXOT ssxot = new SSXOT(con1, con2, 1);
- pathTuples = ssxot.runC(predata, pathTuples, timer);
- pathBuckets = Bucket.tuplesToBuckets(pathTuples, d, W, W);
- for (int i = 0; i < d; i++) {
- int[] rho_ivs = Util.inversePermutation(predata.evict_rho_p[i]);
- pathBuckets[i].permute(rho_ivs);
- }
- int[] pi_ivs = Util.inversePermutation(predata.evict_pi);
- pathBuckets = Util.permute(pathBuckets, pi_ivs);
- for (int i = 0; i < d; i++) {
- int[] delta_ivs = Util.inversePermutation(predata.evict_delta_p[i]);
- pathBuckets[i].permute(delta_ivs);
- pathBuckets[i].shrink(w);
- }
- pathBuckets[0].expand(Arrays.copyOfRange(originalPath, w, sw));
- timer.start(pid, M.online_write);
- con2.write(pid, pathBuckets);
- timer.stop(pid, M.online_write);
- timer.stop(pid, M.online_comp);
- }
- // for testing correctness
- @Override
- public void run(Party party, Metadata md, Forest forest) {
- System.out.println("Use Retrieve to test Eviction");
- }
- }
|