duoram.tcc 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757
  1. // Templated method implementations for duoram.hpp
  2. #include <stdio.h>
  3. #include "cdpf.hpp"
  4. // Pass the player number and desired size
  5. template <typename T>
  6. Duoram<T>::Duoram(int player, size_t size) : player(player),
  7. oram_size(size), p0_blind(blind), p1_blind(peer_blinded_db) {
  8. if (player < 2) {
  9. database.resize(size);
  10. blind.resize(size);
  11. peer_blinded_db.resize(size);
  12. } else {
  13. p0_blind.resize(size);
  14. p1_blind.resize(size);
  15. }
  16. }
  17. // For debugging; print the contents of the Duoram to stdout
  18. template <typename T>
  19. void Duoram<T>::dump() const
  20. {
  21. for (size_t i=0; i<oram_size; ++i) {
  22. if (player < 2) {
  23. printf("%04lx %016lx %016lx %016lx\n",
  24. i, database[i].share(), blind[i].share(),
  25. peer_blinded_db[i].share());
  26. } else {
  27. printf("%04lx %016lx %016lx\n",
  28. i, p0_blind[i].share(), p1_blind[i].share());
  29. }
  30. }
  31. printf("\n");
  32. }
  33. // Enable or disable explicit-only mode. Only using [] with
  34. // explicit (address_t) indices are allowed in this mode. Using []
  35. // with RegAS or RegXS indices will automatically turn off this
  36. // mode, or you can turn it off explicitly. In explicit-only mode,
  37. // updates to the memory in the Shape will not induce communication
  38. // to the server or peer, but when it turns off, a message of the
  39. // size of the entire Shape will be sent to each of the server and
  40. // the peer. This is useful if you're going to be doing multiple
  41. // explicit writes to every element of the Shape before you do your
  42. // next oblivious read or write. Bitonic sort is a prime example.
  43. template <typename T>
  44. void Duoram<T>::Shape::explicitonly(bool enable)
  45. {
  46. if (enable == true) {
  47. explicitmode = true;
  48. } else if (explicitmode == true) {
  49. explicitmode = false;
  50. // Reblind the whole Shape
  51. int player = tio.player();
  52. if (player < 2) {
  53. for (size_t i=0; i<shape_size; ++i) {
  54. auto [ DB, BL, PBD ] = get_comp(i);
  55. BL.randomize();
  56. tio.iostream_server() << BL;
  57. tio.iostream_peer() << (DB + BL);
  58. }
  59. yield();
  60. for (size_t i=0; i<shape_size; ++i) {
  61. auto [ DB, BL, PBD ] = get_comp(i);
  62. tio.iostream_peer() >> PBD;
  63. }
  64. } else {
  65. yield();
  66. for (size_t i=0; i<shape_size; ++i) {
  67. auto [BL0, BL1] = get_server(i);
  68. tio.iostream_p0() >> BL0;
  69. tio.iostream_p1() >> BL1;
  70. }
  71. }
  72. }
  73. }
  74. // For debugging or checking your answers (using this in general is
  75. // of course insecure)
  76. // This one reconstructs the whole database
  77. template <typename T>
  78. std::vector<T> Duoram<T>::Shape::reconstruct() const
  79. {
  80. int player = tio.player();
  81. std::vector<T> res;
  82. res.resize(duoram.size());
  83. // Player 1 sends their share of the database to player 0
  84. if (player == 1) {
  85. tio.queue_peer(duoram.database.data(), duoram.size()*sizeof(T));
  86. } else if (player == 0) {
  87. tio.recv_peer(res.data(), duoram.size()*sizeof(T));
  88. for(size_t i=0;i<duoram.size();++i) {
  89. res[i] += duoram.database[i];
  90. }
  91. }
  92. // The server (player 2) does nothing
  93. // Players 1 and 2 will get an empty vector here
  94. return res;
  95. }
  96. // This one reconstructs a single database value
  97. template <typename T>
  98. T Duoram<T>::Shape::reconstruct(const T& share) const
  99. {
  100. int player = tio.player();
  101. T res;
  102. // Player 1 sends their share of the value to player 0
  103. if (player == 1) {
  104. tio.queue_peer(&share, sizeof(T));
  105. } else if (player == 0) {
  106. tio.recv_peer(&res, sizeof(T));
  107. res += share;
  108. }
  109. // The server (player 2) does nothing
  110. // Players 1 and 2 will get 0 here
  111. return res;
  112. }
  113. // Function to set the shape_size of a shape and compute the number of
  114. // bits you need to address a shape of that size (which is the number of
  115. // bits in sz-1). This is typically called by subclass constructors.
  116. template <typename T>
  117. void Duoram<T>::Shape::set_shape_size(size_t sz)
  118. {
  119. shape_size = sz;
  120. // Compute the number of bits in (sz-1)
  121. // But use 0 if sz=0 for some reason (though that should never
  122. // happen)
  123. if (sz > 1) {
  124. addr_size = 64-__builtin_clzll(sz-1);
  125. addr_mask = address_t((size_t(1)<<addr_size)-1);
  126. } else {
  127. addr_size = 0;
  128. addr_mask = 0;
  129. }
  130. }
  131. // Constructor for the Flat shape. len=0 means the maximum size (the
  132. // parent's size minus start).
  133. template <typename T>
  134. Duoram<T>::Flat::Flat(Duoram &duoram, MPCTIO &tio, yield_t &yield,
  135. size_t start, size_t len) : Shape(*this, duoram, tio, yield)
  136. {
  137. size_t parentsize = duoram.size();
  138. if (start > parentsize) {
  139. start = parentsize;
  140. }
  141. this->start = start;
  142. size_t maxshapesize = parentsize - start;
  143. if (len > maxshapesize || len == 0) {
  144. len = maxshapesize;
  145. }
  146. this->len = len;
  147. this->set_shape_size(len);
  148. }
  149. // Bitonic sort the elements from start to start+(1<<depth)-1, in
  150. // increasing order if dir=0 or decreasing order if dir=1. Note that
  151. // the elements must be at most 63 bits long each for the notion of
  152. // ">" to make consistent sense.
  153. template <typename T>
  154. void Duoram<T>::Flat::bitonic_sort(address_t start, nbits_t depth, bool dir)
  155. {
  156. if (depth == 0) return;
  157. if (depth == 1) {
  158. osort(start, start+1, dir);
  159. return;
  160. }
  161. // Recurse on the first half (increasing order) and the second half
  162. // (decreasing order) in parallel
  163. run_coroutines(this->yield,
  164. [&](yield_t &yield) {
  165. Flat Acoro = context(yield);
  166. Acoro.bitonic_sort(start, depth-1, 0);
  167. },
  168. [&](yield_t &yield) {
  169. Flat Acoro = context(yield);
  170. Acoro.bitonic_sort(start+(1<<(depth-1)), depth-1, 1);
  171. });
  172. // Merge the two into the desired order
  173. butterfly(start, depth, dir);
  174. }
  175. // Internal function to aid bitonic_sort
  176. template <typename T>
  177. void Duoram<T>::Flat::butterfly(address_t start, nbits_t depth, bool dir)
  178. {
  179. if (depth == 0) return;
  180. if (depth == 1) {
  181. osort(start, start+1, dir);
  182. return;
  183. }
  184. // Sort pairs of elements half the width apart in parallel
  185. address_t halfwidth = address_t(1)<<(depth-1);
  186. std::vector<coro_t> coroutines;
  187. for (address_t i=0; i<halfwidth;++i) {
  188. coroutines.emplace_back([&, i](yield_t &yield) {
  189. Flat Acoro = context(yield);
  190. Acoro.osort(start+i, start+i+halfwidth, dir);
  191. });
  192. }
  193. run_coroutines(this->yield, coroutines);
  194. // Recurse on each half in parallel
  195. run_coroutines(this->yield,
  196. [&](yield_t &yield) {
  197. Flat Acoro = context(yield);
  198. Acoro.butterfly(start, depth-1, dir);
  199. },
  200. [&](yield_t &yield) {
  201. Flat Acoro = context(yield);
  202. Acoro.butterfly(start+halfwidth, depth-1, dir);
  203. });
  204. }
  205. // Assuming the memory is already sorted, do an oblivious binary
  206. // search for the largest index containing the value at most the
  207. // given one. (The answer will be 0 if all of the memory elements
  208. // are greate than the target.) This Flat must be a power of 2 size.
  209. // Only available for additive shared databases for now.
  210. template <>
  211. RegAS Duoram<RegAS>::Flat::obliv_binary_search(RegAS &target)
  212. {
  213. nbits_t depth = this->addr_size;
  214. // Start in the middle
  215. RegAS index;
  216. index.set(this->tio.player() ? 0 : 1<<(depth-1));
  217. // Invariant: index points to the first element of the right half of
  218. // the remaining possible range
  219. while (depth > 0) {
  220. // Obliviously read the value there
  221. RegAS val = operator[](index);
  222. // Compare it to the target
  223. CDPF cdpf = tio.cdpf(this->yield);
  224. auto [lt, eq, gt] = cdpf.compare(this->tio, this->yield,
  225. val-target, tio.aes_ops());
  226. if (depth > 1) {
  227. // If val > target, the answer is strictly to the left
  228. // and we should subtract 2^{depth-2} from index
  229. // If val <= target, the answer is here or to the right
  230. // and we should add 2^{depth-2} to index
  231. // So we unconditionally subtract 2^{depth-2} from index, and
  232. // add (lt+eq)*2^{depth-1}.
  233. RegAS uncond;
  234. uncond.set(tio.player() ? 0 : address_t(1)<<(depth-2));
  235. RegAS cond;
  236. cond.set(tio.player() ? 0 : address_t(1)<<(depth-1));
  237. RegAS condprod;
  238. RegBS le = lt ^ eq;
  239. mpc_flagmult(this->tio, this->yield, condprod, le, cond);
  240. index -= uncond;
  241. index += condprod;
  242. } else {
  243. // If val > target, the answer is strictly to the left
  244. // If val <= target, the answer is here or to the right
  245. // so subtract gt from index
  246. RegAS cond;
  247. cond.set(tio.player() ? 0 : 1);
  248. RegAS condprod;
  249. mpc_flagmult(this->tio, this->yield, condprod, gt, cond);
  250. index -= condprod;
  251. }
  252. --depth;
  253. }
  254. return index;
  255. }
  256. // Oblivious read from an additively shared index of Duoram memory
  257. template <typename T>
  258. Duoram<T>::Shape::MemRefAS::operator T()
  259. {
  260. T res;
  261. Shape &shape = this->shape;
  262. shape.explicitonly(false);
  263. int player = shape.tio.player();
  264. if (player < 2) {
  265. // Computational players do this
  266. RDPFTriple dt = shape.tio.rdpftriple(shape.yield, shape.addr_size);
  267. // Compute the index offset
  268. RegAS indoffset = dt.as_target;
  269. indoffset -= idx;
  270. // We only need two of the DPFs for reading
  271. RDPFPair dp(std::move(dt), 0, player == 0 ? 2 : 1);
  272. // The RDPFTriple dt is now broken, since we've moved things out
  273. // of it.
  274. // Send it to the peer and the server
  275. shape.tio.queue_peer(&indoffset, BITBYTES(shape.addr_size));
  276. shape.tio.queue_server(&indoffset, BITBYTES(shape.addr_size));
  277. shape.yield();
  278. // Receive the above from the peer
  279. RegAS peerindoffset;
  280. shape.tio.recv_peer(&peerindoffset, BITBYTES(shape.addr_size));
  281. // Reconstruct the total offset
  282. auto indshift = combine(indoffset, peerindoffset, shape.addr_size);
  283. // Evaluate the DPFs and compute the dotproducts
  284. StreamEval ev(dp, indshift, 0, shape.tio.aes_ops());
  285. for (size_t i=0; i<shape.shape_size; ++i) {
  286. auto L = ev.next();
  287. // The values from the two DPFs
  288. auto [V0, V1] = dp.unit<T>(L);
  289. // References to the appropriate cells in our database, our
  290. // blind, and our copy of the peer's blinded database
  291. auto [DB, BL, PBD] = shape.get_comp(i);
  292. res += (DB + PBD) * V0.share() - BL * (V1-V0).share();
  293. }
  294. shape.yield();
  295. // Receive the cancellation term from the server
  296. T gamma;
  297. shape.tio.iostream_server() >> gamma;
  298. res += gamma;
  299. } else {
  300. // The server does this
  301. RDPFPair dp = shape.tio.rdpfpair(shape.yield, shape.addr_size);
  302. RegAS p0indoffset, p1indoffset;
  303. shape.yield();
  304. // Receive the index offset from the computational players and
  305. // combine them
  306. shape.tio.recv_p0(&p0indoffset, BITBYTES(shape.addr_size));
  307. shape.tio.recv_p1(&p1indoffset, BITBYTES(shape.addr_size));
  308. auto indshift = combine(p0indoffset, p1indoffset, shape.addr_size);
  309. // Evaluate the DPFs to compute the cancellation terms
  310. T gamma0, gamma1;
  311. StreamEval ev(dp, indshift, 0, shape.tio.aes_ops());
  312. for (size_t i=0; i<shape.shape_size; ++i) {
  313. auto L = ev.next();
  314. // The values from the two DPFs
  315. auto [V0, V1] = dp.unit<T>(L);
  316. // shape.get_server(i) returns a pair of references to the
  317. // appropriate cells in the two blinded databases
  318. auto [BL0, BL1] = shape.get_server(i);
  319. gamma0 -= BL0 * V1.share();
  320. gamma1 -= BL1 * V0.share();
  321. }
  322. // Choose a random blinding factor
  323. T rho;
  324. rho.randomize();
  325. gamma0 += rho;
  326. gamma1 -= rho;
  327. // Send the cancellation terms to the computational players
  328. shape.tio.iostream_p0() << gamma0;
  329. shape.tio.iostream_p1() << gamma1;
  330. shape.yield();
  331. }
  332. return res; // The server will always get 0
  333. }
  334. // Oblivious update to an additively shared index of Duoram memory
  335. template <typename T>
  336. typename Duoram<T>::Shape::MemRefAS
  337. &Duoram<T>::Shape::MemRefAS::operator+=(const T& M)
  338. {
  339. Shape &shape = this->shape;
  340. shape.explicitonly(false);
  341. int player = shape.tio.player();
  342. if (player < 2) {
  343. // Computational players do this
  344. RDPFTriple dt = shape.tio.rdpftriple(shape.yield, shape.addr_size);
  345. // Compute the index and message offsets
  346. RegAS indoffset = dt.as_target;
  347. indoffset -= idx;
  348. auto Moffset = std::make_tuple(M, M, M);
  349. Moffset -= dt.scaled_value<T>();
  350. // Send them to the peer, and everything except the first offset
  351. // to the server
  352. shape.tio.queue_peer(&indoffset, BITBYTES(shape.addr_size));
  353. shape.tio.iostream_peer() << Moffset;
  354. shape.tio.queue_server(&indoffset, BITBYTES(shape.addr_size));
  355. shape.tio.iostream_server() << std::get<1>(Moffset) <<
  356. std::get<2>(Moffset);
  357. shape.yield();
  358. // Receive the above from the peer
  359. RegAS peerindoffset;
  360. std::tuple<T,T,T> peerMoffset;
  361. shape.tio.recv_peer(&peerindoffset, BITBYTES(shape.addr_size));
  362. shape.tio.iostream_peer() >> peerMoffset;
  363. // Reconstruct the total offsets
  364. auto indshift = combine(indoffset, peerindoffset, shape.addr_size);
  365. auto Mshift = combine(Moffset, peerMoffset);
  366. // Evaluate the DPFs and add them to the database
  367. StreamEval ev(dt, indshift, 0, shape.tio.aes_ops());
  368. for (size_t i=0; i<shape.shape_size; ++i) {
  369. auto L = ev.next();
  370. // The values from the three DPFs
  371. auto [V0, V1, V2] = dt.scaled<T>(L) + dt.unit<T>(L) * Mshift;
  372. // References to the appropriate cells in our database, our
  373. // blind, and our copy of the peer's blinded database
  374. auto [DB, BL, PBD] = shape.get_comp(i);
  375. DB += V0;
  376. if (player == 0) {
  377. BL -= V1;
  378. PBD += V2-V0;
  379. } else {
  380. BL -= V2;
  381. PBD += V1-V0;
  382. }
  383. }
  384. } else {
  385. // The server does this
  386. RDPFPair dp = shape.tio.rdpfpair(shape.yield, shape.addr_size);
  387. RegAS p0indoffset, p1indoffset;
  388. std::tuple<T,T> p0Moffset, p1Moffset;
  389. // Receive the index and message offsets from the computational
  390. // players and combine them
  391. shape.tio.recv_p0(&p0indoffset, BITBYTES(shape.addr_size));
  392. shape.tio.iostream_p0() >> p0Moffset;
  393. shape.tio.recv_p1(&p1indoffset, BITBYTES(shape.addr_size));
  394. shape.tio.iostream_p1() >> p1Moffset;
  395. auto indshift = combine(p0indoffset, p1indoffset, shape.addr_size);
  396. auto Mshift = combine(p0Moffset, p1Moffset);
  397. // Evaluate the DPFs and subtract them from the blinds
  398. StreamEval ev(dp, indshift, 0, shape.tio.aes_ops());
  399. for (size_t i=0; i<shape.shape_size; ++i) {
  400. auto L = ev.next();
  401. // The values from the two DPFs
  402. auto V = dp.scaled<T>(L) + dp.unit<T>(L) * Mshift;
  403. // shape.get_server(i) returns a pair of references to the
  404. // appropriate cells in the two blinded databases, so we can
  405. // subtract the pair directly.
  406. shape.get_server(i) -= V;
  407. }
  408. }
  409. return *this;
  410. }
  411. // Oblivious sort with the provided other element. Without
  412. // reconstructing the values, *this will become a share of the
  413. // smaller of the reconstructed values, and other will become a
  414. // share of the larger.
  415. //
  416. // Note: this only works for additively shared databases
  417. template <> template <typename U,typename V>
  418. void Duoram<RegAS>::Flat::osort(const U &idx1, const V &idx2, bool dir)
  419. {
  420. // Load the values in parallel
  421. RegAS val1, val2;
  422. run_coroutines(yield,
  423. [&](yield_t &yield) {
  424. Flat Acoro = context(yield);
  425. val1 = Acoro[idx1];
  426. },
  427. [&](yield_t &yield) {
  428. Flat Acoro = context(yield);
  429. val2 = Acoro[idx2];
  430. });
  431. // Get a CDPF
  432. CDPF cdpf = tio.cdpf(yield);
  433. // Use it to compare the values
  434. RegAS diff = val1-val2;
  435. auto [lt, eq, gt] = cdpf.compare(tio, yield, diff, tio.aes_ops());
  436. RegBS cmp = dir ? lt : gt;
  437. // Get additive shares of cmp*diff
  438. RegAS cmp_diff;
  439. mpc_flagmult(tio, yield, cmp_diff, cmp, diff);
  440. // Update the two locations in parallel
  441. run_coroutines(yield,
  442. [&](yield_t &yield) {
  443. Flat Acoro = context(yield);
  444. Acoro[idx1] -= cmp_diff;
  445. },
  446. [&](yield_t &yield) {
  447. Flat Acoro = context(yield);
  448. Acoro[idx2] += cmp_diff;
  449. });
  450. }
  451. // The MemRefXS routines are almost identical to the MemRefAS routines,
  452. // but I couldn't figure out how to get them to be two instances of a
  453. // template. Sorry for the code duplication.
  454. // Oblivious read from an XOR shared index of Duoram memory
  455. template <typename T>
  456. Duoram<T>::Shape::MemRefXS::operator T()
  457. {
  458. Shape &shape = this->shape;
  459. shape.explicitonly(false);
  460. T res;
  461. int player = shape.tio.player();
  462. if (player < 2) {
  463. // Computational players do this
  464. RDPFTriple dt = shape.tio.rdpftriple(shape.yield, shape.addr_size);
  465. // Compute the index offset
  466. RegXS indoffset = dt.xs_target;
  467. indoffset -= idx;
  468. // We only need two of the DPFs for reading
  469. RDPFPair dp(std::move(dt), 0, player == 0 ? 2 : 1);
  470. // Send it to the peer and the server
  471. shape.tio.queue_peer(&indoffset, BITBYTES(shape.addr_size));
  472. shape.tio.queue_server(&indoffset, BITBYTES(shape.addr_size));
  473. shape.yield();
  474. // Receive the above from the peer
  475. RegXS peerindoffset;
  476. shape.tio.recv_peer(&peerindoffset, BITBYTES(shape.addr_size));
  477. // Reconstruct the total offset
  478. auto indshift = combine(indoffset, peerindoffset, shape.addr_size);
  479. // Evaluate the DPFs and compute the dotproducts
  480. StreamEval ev(dp, 0, indshift, shape.tio.aes_ops());
  481. for (size_t i=0; i<shape.shape_size; ++i) {
  482. auto L = ev.next();
  483. // The values from the two DPFs
  484. auto [V0, V1] = dp.unit<T>(L);
  485. // References to the appropriate cells in our database, our
  486. // blind, and our copy of the peer's blinded database
  487. auto [DB, BL, PBD] = shape.get_comp(i);
  488. res += (DB + PBD) * V0.share() - BL * (V1-V0).share();
  489. }
  490. shape.yield();
  491. // Receive the cancellation term from the server
  492. T gamma;
  493. shape.tio.iostream_server() >> gamma;
  494. res += gamma;
  495. } else {
  496. // The server does this
  497. RDPFPair dp = shape.tio.rdpfpair(shape.yield, shape.addr_size);
  498. RegXS p0indoffset, p1indoffset;
  499. shape.yield();
  500. // Receive the index offset from the computational players and
  501. // combine them
  502. shape.tio.recv_p0(&p0indoffset, BITBYTES(shape.addr_size));
  503. shape.tio.recv_p1(&p1indoffset, BITBYTES(shape.addr_size));
  504. auto indshift = combine(p0indoffset, p1indoffset, shape.addr_size);
  505. // Evaluate the DPFs to compute the cancellation terms
  506. T gamma0, gamma1;
  507. StreamEval ev(dp, 0, indshift, shape.tio.aes_ops());
  508. for (size_t i=0; i<shape.shape_size; ++i) {
  509. auto L = ev.next();
  510. // The values from the two DPFs
  511. auto [V0, V1] = dp.unit<T>(L);
  512. // shape.get_server(i) returns a pair of references to the
  513. // appropriate cells in the two blinded databases
  514. auto [BL0, BL1] = shape.get_server(i);
  515. gamma0 -= BL0 * V1.share();
  516. gamma1 -= BL1 * V0.share();
  517. }
  518. // Choose a random blinding factor
  519. T rho;
  520. rho.randomize();
  521. gamma0 += rho;
  522. gamma1 -= rho;
  523. // Send the cancellation terms to the computational players
  524. shape.tio.iostream_p0() << gamma0;
  525. shape.tio.iostream_p1() << gamma1;
  526. shape.yield();
  527. }
  528. return res; // The server will always get 0
  529. }
  530. // Oblivious update to an XOR shared index of Duoram memory
  531. template <typename T>
  532. typename Duoram<T>::Shape::MemRefXS
  533. &Duoram<T>::Shape::MemRefXS::operator+=(const T& M)
  534. {
  535. Shape &shape = this->shape;
  536. shape.explicitonly(false);
  537. int player = shape.tio.player();
  538. if (player < 2) {
  539. // Computational players do this
  540. RDPFTriple dt = shape.tio.rdpftriple(shape.yield, shape.addr_size);
  541. // Compute the index and message offsets
  542. RegXS indoffset = dt.xs_target;
  543. indoffset -= idx;
  544. auto Moffset = std::make_tuple(M, M, M);
  545. Moffset -= dt.scaled_value<T>();
  546. // Send them to the peer, and everything except the first offset
  547. // to the server
  548. shape.tio.queue_peer(&indoffset, BITBYTES(shape.addr_size));
  549. shape.tio.iostream_peer() << Moffset;
  550. shape.tio.queue_server(&indoffset, BITBYTES(shape.addr_size));
  551. shape.tio.iostream_server() << std::get<1>(Moffset) <<
  552. std::get<2>(Moffset);
  553. shape.yield();
  554. // Receive the above from the peer
  555. RegXS peerindoffset;
  556. std::tuple<T,T,T> peerMoffset;
  557. shape.tio.recv_peer(&peerindoffset, BITBYTES(shape.addr_size));
  558. shape.tio.iostream_peer() >> peerMoffset;
  559. // Reconstruct the total offsets
  560. auto indshift = combine(indoffset, peerindoffset, shape.addr_size);
  561. auto Mshift = combine(Moffset, peerMoffset);
  562. // Evaluate the DPFs and add them to the database
  563. StreamEval ev(dt, 0, indshift, shape.tio.aes_ops());
  564. for (size_t i=0; i<shape.shape_size; ++i) {
  565. auto L = ev.next();
  566. // The values from the three DPFs
  567. auto [V0, V1, V2] = dt.scaled<T>(L) + dt.unit<T>(L) * Mshift;
  568. // References to the appropriate cells in our database, our
  569. // blind, and our copy of the peer's blinded database
  570. auto [DB, BL, PBD] = shape.get_comp(i);
  571. DB += V0;
  572. if (player == 0) {
  573. BL -= V1;
  574. PBD += V2-V0;
  575. } else {
  576. BL -= V2;
  577. PBD += V1-V0;
  578. }
  579. }
  580. } else {
  581. // The server does this
  582. RDPFPair dp = shape.tio.rdpfpair(shape.yield, shape.addr_size);
  583. RegXS p0indoffset, p1indoffset;
  584. std::tuple<T,T> p0Moffset, p1Moffset;
  585. // Receive the index and message offsets from the computational
  586. // players and combine them
  587. shape.tio.recv_p0(&p0indoffset, BITBYTES(shape.addr_size));
  588. shape.tio.iostream_p0() >> p0Moffset;
  589. shape.tio.recv_p1(&p1indoffset, BITBYTES(shape.addr_size));
  590. shape.tio.iostream_p1() >> p1Moffset;
  591. auto indshift = combine(p0indoffset, p1indoffset, shape.addr_size);
  592. auto Mshift = combine(p0Moffset, p1Moffset);
  593. // Evaluate the DPFs and subtract them from the blinds
  594. StreamEval ev(dp, 0, indshift, shape.tio.aes_ops());
  595. for (size_t i=0; i<shape.shape_size; ++i) {
  596. auto L = ev.next();
  597. // The values from the two DPFs
  598. auto V = dp.scaled<T>(L) + dp.unit<T>(L) * Mshift;
  599. // shape.get_server(i) returns a pair of references to the
  600. // appropriate cells in the two blinded databases, so we can
  601. // subtract the pair directly.
  602. shape.get_server(i) -= V;
  603. }
  604. }
  605. return *this;
  606. }
  607. // Explicit read from a given index of Duoram memory
  608. template <typename T>
  609. Duoram<T>::Shape::MemRefExpl::operator T()
  610. {
  611. Shape &shape = this->shape;
  612. T res;
  613. int player = shape.tio.player();
  614. if (player < 2) {
  615. res = std::get<0>(shape.get_comp(idx));
  616. }
  617. return res; // The server will always get 0
  618. }
  619. // Explicit update to a given index of Duoram memory
  620. template <typename T>
  621. typename Duoram<T>::Shape::MemRefExpl
  622. &Duoram<T>::Shape::MemRefExpl::operator+=(const T& M)
  623. {
  624. Shape &shape = this->shape;
  625. int player = shape.tio.player();
  626. // In explicit-only mode, just update the local DB; we'll sync the
  627. // blinds and the blinded DB when we leave explicit-only mode.
  628. if (shape.explicitmode) {
  629. if (player < 2) {
  630. auto [ DB, BL, PBD ] = shape.get_comp(idx);
  631. DB += M;
  632. }
  633. return *this;
  634. }
  635. if (player < 2) {
  636. // Computational players do this
  637. // Pick a blinding factor
  638. T blind;
  639. blind.randomize();
  640. // Send the blind to the server, and the blinded value to the
  641. // peer
  642. shape.tio.iostream_server() << blind;
  643. shape.tio.iostream_peer() << (M + blind);
  644. shape.yield();
  645. // Receive the peer's blinded value
  646. T peerblinded;
  647. shape.tio.iostream_peer() >> peerblinded;
  648. // Our database, our blind, the peer's blinded database
  649. auto [ DB, BL, PBD ] = shape.get_comp(idx);
  650. DB += M;
  651. BL += blind;
  652. PBD += peerblinded;
  653. } else if (player == 2) {
  654. // The server does this
  655. // Receive the updates to the blinds
  656. T p0blind, p1blind;
  657. shape.tio.iostream_p0() >> p0blind;
  658. shape.tio.iostream_p1() >> p1blind;
  659. // The two computational parties' blinds
  660. auto [ BL0, BL1 ] = shape.get_server(idx);
  661. BL0 += p0blind;
  662. BL1 += p1blind;
  663. }
  664. return *this;
  665. }