123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136 |
- #include "duoram.hpp"
- #include "shapes.hpp"
- template <>
- RegAS Duoram<RegAS>::Shape::basic_binary_search(RegAS &target)
- {
- if (this->shape_size == 0) {
- RegAS zero;
- return zero;
- }
-
-
- address_t padsize = 1;
- nbits_t depth = 0;
- while (padsize <= this->shape_size) {
- padsize *= 2;
- ++depth;
- }
- Duoram<RegAS>::Pad P(*this, tio, yield, padsize);
-
- RegAS index;
- index.set(this->tio.player() ? 0 : (1<<(depth-1))-1);
-
-
- while (depth > 0) {
-
- RegAS val = P[index];
-
- CDPF cdpf = tio.cdpf(this->yield);
- auto [lt, eq, gt] = cdpf.compare(this->tio, this->yield,
- val-target, tio.aes_ops());
- if (depth > 1) {
-
-
-
-
-
-
- RegAS uncond;
- uncond.set(tio.player() ? 0 : address_t(1)<<(depth-2));
- RegAS cond;
- cond.set(tio.player() ? 0 : address_t(1)<<(depth-1));
- RegAS condprod;
- mpc_flagmult(this->tio, this->yield, condprod, lt, cond);
- index -= uncond;
- index += condprod;
- } else {
-
-
-
-
-
-
- RegAS cond;
- cond.set(tio.player() ? 0 : 1);
- RegAS condprod;
- mpc_flagmult(this->tio, this->yield, condprod, lt, cond);
- index += condprod;
- }
- --depth;
- }
- return index;
- }
- template <>
- RegXS Duoram<RegAS>::Shape::binary_search(RegAS &target)
- {
- if (this->shape_size == 0) {
- RegXS zero;
- return zero;
- }
-
-
- address_t padsize = 1;
- nbits_t depth = 0;
- while (padsize <= this->shape_size) {
- padsize *= 2;
- ++depth;
- }
- Duoram<RegAS>::Pad P(*this, tio, yield, padsize);
-
- address_t mid = (1<<(depth-1))-1;
- RegAS val = P[mid];
-
- CDPF cdpf = tio.cdpf(this->yield);
- auto [lt, eq, gt] = cdpf.compare(this->tio, this->yield,
- val-target, tio.aes_ops());
- if (depth == 1) {
-
-
-
-
-
- RegXS ret;
- ret.xshare = lt.bshare;
- return ret;
- }
- auto oidx = P.oblivindex(depth-1);
- oidx.incr(lt);
- --depth;
- while(depth > 0) {
-
-
-
-
-
-
-
-
-
-
-
-
- Duoram<RegAS>::Stride S(P, tio, yield, (1<<(depth-1))-1, 1<<depth);
- RegAS val = S[oidx];
- CDPF cdpf = tio.cdpf(this->yield);
- auto [lt, eq, gt] = cdpf.compare(this->tio, this->yield,
- val-target, tio.aes_ops());
- oidx.incr(lt);
- --depth;
- }
- return oidx.index();
- }
|