dpfgen.h 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676
  1. struct dpfP2
  2. {
  3. __m128i root;
  4. __m128i CW[26];
  5. uint8_t cwt_L[26];
  6. uint8_t cwt_R[26];
  7. };
  8. void generate_random_targets(uint8_t ** target_share_read, size_t n_threads, bool party, size_t expo)
  9. {
  10. for(size_t i = 0; i < n_threads; i++)
  11. {
  12. target_share_read[i] = new uint8_t[64];
  13. }
  14. for(size_t j = 0; j < 64; ++j)
  15. {
  16. for(size_t i = 0; i < n_threads; ++i)
  17. {
  18. srand(3);
  19. uint8_t random_value;
  20. arc4random_buf(&random_value, sizeof(uint8_t));
  21. target_share_read[i][j] = random_value;//rand();
  22. target_share_read[i][j] = 0;//target_share_read[i][j] % 2;
  23. if(party) target_share_read[i][expo-2] = 1;
  24. }
  25. }
  26. }
  27. void write_evalfull_outs_into_a_file(bool party, size_t i, size_t db_nitems, int8_t ** flags, int64_t * outs_, __m128i * final_correction_word)
  28. {
  29. if(!party)
  30. {
  31. char const * p0_filename0;
  32. char tmp[100];
  33. p0_filename0 = "../duoram-online/party0_read_flags_b";
  34. strcpy(tmp, p0_filename0);
  35. strcat(tmp, std::to_string(i).c_str());
  36. int w0 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  37. int written = write(w0, flags[i], db_nitems * sizeof(flags[i][0]));
  38. if(written<0) {
  39. perror("Write error");
  40. }
  41. close(w0);
  42. p0_filename0 = "../duoram-online/party0_read_flags_c";
  43. strcpy(tmp, p0_filename0);
  44. strcat(tmp, std::to_string(i).c_str());
  45. int w1 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  46. written = write(w1, flags[i], db_nitems * sizeof(flags[i][0]));
  47. if(written<0) {
  48. perror("Write error");
  49. }
  50. close(w1);
  51. p0_filename0 = "../duoram-online/party0_read_flags_d";
  52. strcpy(tmp, p0_filename0);
  53. strcat(tmp, std::to_string(i).c_str());
  54. int w2 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  55. written = write(w2, flags[i], db_nitems * sizeof(flags[i][0]));
  56. if(written<0) {
  57. perror("Write error");
  58. }
  59. close(w2);
  60. p0_filename0 = "../duoram-online/party0_write_flags_b";
  61. strcpy(tmp, p0_filename0);
  62. strcat(tmp, std::to_string(i).c_str());
  63. int w4 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  64. written = write(w4, flags[i], db_nitems * sizeof(flags[i][0]));
  65. if(written<0) {
  66. perror("Write error");
  67. }
  68. close(w4);
  69. p0_filename0 = "../duoram-online/party0_write_flags_c";
  70. strcpy(tmp, p0_filename0);
  71. strcat(tmp, std::to_string(i).c_str());
  72. int w5 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  73. written = write(w5, flags[i], db_nitems * sizeof(flags[i][0]));
  74. if(written<0) {
  75. perror("Write error");
  76. }
  77. close(w5);
  78. p0_filename0 = "../duoram-online/party0_write_flags_d";
  79. strcpy(tmp, p0_filename0);
  80. strcat(tmp, std::to_string(i).c_str());
  81. int w6 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  82. written = write(w6, flags[i], db_nitems * sizeof(flags[i][0]));
  83. if(written<0) {
  84. perror("Write error");
  85. }
  86. close(w6);
  87. p0_filename0 = "../duoram-online/party0_write_b";
  88. strcpy(tmp, p0_filename0);
  89. strcat(tmp, std::to_string(i).c_str());
  90. w4 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  91. written = write(w4, outs_, db_nitems * sizeof(outs_[0]));
  92. if(written<0) {
  93. perror("Write error");
  94. }
  95. close(w4);
  96. p0_filename0 = "../duoram-online/party0_write_c";
  97. strcpy(tmp, p0_filename0);
  98. strcat(tmp, std::to_string(i).c_str());
  99. w5 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  100. written = write(w5, outs_, db_nitems * sizeof(outs_[0]));
  101. if(written<0) {
  102. perror("Write error");
  103. }
  104. close(w5);
  105. p0_filename0 = "../duoram-online/party0_write_d";
  106. strcpy(tmp, p0_filename0);
  107. strcat(tmp, std::to_string(i).c_str());
  108. w6 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  109. written = write(w6, outs_, db_nitems * sizeof(outs_[0]));
  110. if(written<0) {
  111. perror("Write error");
  112. }
  113. close(w6);
  114. }
  115. if(party)
  116. {
  117. char const * p0_filename0;
  118. char tmp[100];
  119. p0_filename0 = "../duoram-online/party1_read_flags_b";
  120. strcpy(tmp, p0_filename0);
  121. strcat(tmp, std::to_string(i).c_str());
  122. int w0 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  123. int written = write(w0, flags[i], db_nitems * sizeof(flags[i][0]));
  124. if(written<0) {
  125. perror("Write error");
  126. }
  127. close(w0);
  128. p0_filename0 = "../duoram-online/party1_read_flags_c";
  129. strcpy(tmp, p0_filename0);
  130. strcat(tmp, std::to_string(i).c_str());
  131. int w1 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  132. written = write(w1, flags[i], db_nitems * sizeof(flags[i][0]));
  133. if(written<0) {
  134. perror("Write error");
  135. }
  136. close(w1);
  137. p0_filename0 = "../duoram-online/party1_read_flags_d";
  138. strcpy(tmp, p0_filename0);
  139. strcat(tmp, std::to_string(i).c_str());
  140. int w2 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  141. written = write(w2,flags[i], db_nitems * sizeof(flags[i][0]));
  142. if(written<0) {
  143. perror("Write error");
  144. }
  145. close(w2);
  146. p0_filename0 = "../duoram-online/party1_write_flags_b";
  147. strcpy(tmp, p0_filename0);
  148. strcat(tmp, std::to_string(i).c_str());
  149. int w4 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  150. written = write(w4,flags[i], db_nitems * sizeof(flags[i][0]));
  151. if(written<0) {
  152. perror("Write error");
  153. }
  154. close(w4);
  155. p0_filename0 = "../duoram-online/party1_write_flags_c";
  156. strcpy(tmp, p0_filename0);
  157. strcat(tmp, std::to_string(i).c_str());
  158. int w5 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  159. written = write(w5, flags[i], db_nitems * sizeof(flags[i][0]));
  160. if(written<0) {
  161. perror("Write error");
  162. }
  163. close(w5);
  164. p0_filename0 = "../duoram-online/party1_write_flags_d";
  165. strcpy(tmp, p0_filename0);
  166. strcat(tmp, std::to_string(i).c_str());
  167. int w6 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  168. written = write(w6, flags[i], db_nitems * sizeof(flags[i][0]));
  169. if(written<0) {
  170. perror("Write error");
  171. }
  172. close(w6);
  173. p0_filename0 = "../duoram-online/party1_write_b";
  174. strcpy(tmp, p0_filename0);
  175. strcat(tmp, std::to_string(i).c_str());
  176. w4 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  177. written = write(w4, outs_, db_nitems * sizeof(outs_[0]));
  178. if(written<0) {
  179. perror("Write error");
  180. }
  181. close(w4);
  182. // char const * p0_filename0;
  183. p0_filename0 = "../duoram-online/party1_write_c";
  184. strcpy(tmp, p0_filename0);
  185. strcat(tmp, std::to_string(i).c_str());
  186. w5 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  187. written = write(w5, outs_, db_nitems * sizeof(outs_[0]));
  188. if(written<0) {
  189. perror("Write error");
  190. }
  191. close(w5);
  192. p0_filename0 = "../duoram-online/party1_write_d";
  193. strcpy(tmp, p0_filename0);
  194. strcat(tmp, std::to_string(i).c_str());
  195. w6 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  196. written = write(w6, outs_, db_nitems * sizeof(outs_[0]));
  197. if(written<0) {
  198. perror("Write error");
  199. }
  200. close(w6);
  201. }
  202. if(party)
  203. {
  204. char const * p1_filename0;
  205. char tmp[100];
  206. p1_filename0 = "../duoram-online/FCW1";
  207. strcpy(tmp, p1_filename0);
  208. strcat(tmp, std::to_string(i).c_str());
  209. int w0 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  210. int written = write(w0, &final_correction_word[0][0], sizeof(final_correction_word[0][0]));
  211. if(written<0) {
  212. perror("Write error");
  213. }
  214. close(w0);
  215. }
  216. if(!party)
  217. {
  218. char const * p0_filename0;
  219. char tmp[100];
  220. p0_filename0 = "../duoram-online/FCW0";
  221. strcpy(tmp, p0_filename0);
  222. strcat(tmp, std::to_string(i).c_str());
  223. int w0 = open( tmp, O_WRONLY | O_CREAT, S_IWRITE | S_IREAD);
  224. int written = write(w0, &final_correction_word[0][0], sizeof(final_correction_word[0][0]));
  225. if(written<0) {
  226. perror("Write error");
  227. }
  228. close(w0);
  229. }
  230. }
  231. void compute_CW(tcp::socket& sout, tcp::socket& sin, __m128i L, __m128i R, uint8_t bit, __m128i & CW)
  232. {
  233. struct cw_construction
  234. {
  235. __m128i rand_b, gamma_b;
  236. uint8_t bit_b;
  237. };
  238. cw_construction computecw;
  239. read(sin, boost::asio::buffer(&computecw, sizeof(computecw)));
  240. __m128i rand_b = computecw.rand_b;
  241. __m128i gamma_b = computecw.gamma_b;
  242. uint8_t bit_b = computecw.bit_b;
  243. #ifdef DEBUG
  244. __m128i rand_b2, gamma_b2;
  245. uint8_t bit_b2;
  246. read(sin, boost::asio::buffer(&rand_b2, sizeof(rand_b)));
  247. read(sin, boost::asio::buffer(&gamma_b2, sizeof(gamma_b)));
  248. read(sin, boost::asio::buffer(&bit_b2, sizeof(bit_b)));
  249. assert(rand_b2[0] == rand_b[0]);
  250. assert(rand_b2[1] == rand_b[1]);
  251. assert(gamma_b2[0] == gamma_b[0]);
  252. assert(gamma_b2[1] == gamma_b[1]);
  253. assert(bit_b2 == bit_b);
  254. #endif
  255. uint8_t blinded_bit, blinded_bit_read;
  256. blinded_bit = bit ^ bit_b;
  257. __m128i blinded_L = L ^ R ^ rand_b;
  258. __m128i blinded_L_read;
  259. struct BlindsCW
  260. {
  261. __m128i blinded_message;
  262. uint8_t blinded_bit;
  263. };
  264. BlindsCW blinds_sent, blinds_recv;
  265. blinds_sent.blinded_bit = blinded_bit;
  266. blinds_sent.blinded_message = blinded_L;
  267. boost::asio::write(sout, boost::asio::buffer(&blinds_sent, sizeof(blinds_sent)));
  268. boost::asio::read(sout, boost::asio::buffer(&blinds_recv, sizeof(blinds_recv)));
  269. blinded_bit_read = blinds_recv.blinded_bit;
  270. blinded_L_read = blinds_recv.blinded_message;
  271. __m128i out_ = R ^ gamma_b;//_mm_setzero_si128;
  272. if(bit)
  273. {
  274. out_ ^= (L ^ R ^ blinded_L_read);
  275. }
  276. if(blinded_bit_read)
  277. {
  278. out_ ^= rand_b;
  279. }
  280. __m128i out_reconstruction;
  281. boost::asio::write(sout, boost::asio::buffer(&out_, sizeof(out_)));
  282. boost::asio::read(sout, boost::asio::buffer(&out_reconstruction, sizeof(out_reconstruction)));
  283. out_reconstruction = out_ ^ out_reconstruction;
  284. CW = out_reconstruction;
  285. #ifdef DEBUG
  286. uint8_t bit_reconstruction;
  287. boost::asio::write(sout, boost::asio::buffer(&bit, sizeof(bit)));
  288. boost::asio::read(sout, boost::asio::buffer(&bit_reconstruction, sizeof(bit_reconstruction)));
  289. bit_reconstruction = bit ^ bit_reconstruction;
  290. __m128i L_reconstruction;
  291. boost::asio::write(sout, boost::asio::buffer(&L, sizeof(L)));
  292. boost::asio::read(sout, boost::asio::buffer(&L_reconstruction, sizeof(L_reconstruction)));
  293. L_reconstruction = L ^ L_reconstruction;
  294. __m128i R_reconstruction;
  295. boost::asio::write(sout, boost::asio::buffer(&R, sizeof(R)));
  296. boost::asio::read(sout, boost::asio::buffer(&R_reconstruction, sizeof(R_reconstruction)));
  297. R_reconstruction = R ^ R_reconstruction;
  298. __m128i CW_debug;
  299. if(bit_reconstruction != 0)
  300. {
  301. CW_debug = L_reconstruction;
  302. }
  303. else
  304. {
  305. CW_debug = R_reconstruction;
  306. }
  307. assert(CW_debug[0] == CW[0]);
  308. assert(CW_debug[1] == CW[1]);
  309. #endif
  310. }
  311. template<typename node_t, typename prgkey_t>
  312. static inline void traverse(const prgkey_t & prgkey, const node_t & seed, node_t s[2])
  313. {
  314. dpf::PRG(prgkey, clear_lsb(seed, 0b11), s, 2);
  315. } // dpf::expand
  316. /**
  317. * @brief
  318. *
  319. * @param nodes_per_leaf
  320. * @param depth
  321. * @param nbits
  322. * @param nodes_in_interval
  323. * @param prgkey The PRG Key
  324. * @param target_share
  325. * @param socketsPb Array of sockets to write to Pb
  326. * @param socketsP2 Array of sockets to write to P2
  327. * @param from
  328. * @param to
  329. * @param output
  330. * @param _t
  331. * @param final_correction_word the final correction word is written in to this
  332. * @param party Party
  333. * @param socket_no
  334. */
  335. inline void create_dpfs( size_t db_nitems,
  336. const AES_KEY& prgkey, uint8_t target_share[64], std::vector<socket_t>& socketsPb, std::vector<socket_t>& socketsP2,
  337. const size_t from, const size_t to, __m128i * output, int8_t * _t, __m128i& final_correction_word, bool party, size_t socket_no, size_t ind)
  338. {
  339. const size_t bits_per_leaf = std::is_same<leaf_t, bool>::value ? 1 : sizeof(leaf_t) * CHAR_BIT;
  340. const bool is_packed = (sizeof(leaf_t) < sizeof(node_t));
  341. const size_t nodes_per_leaf = is_packed ? 1 : std::ceil(static_cast<double>(bits_per_leaf) / (sizeof(node_t) * CHAR_BIT));
  342. const size_t depth = std::ceil(std::log2(db_nitems));
  343. const size_t nbits = std::ceil(std::log2(db_nitems));
  344. const size_t nodes_in_interval = db_nitems-1;
  345. __m128i root;
  346. arc4random_buf(&root, sizeof(root));
  347. root = set_lsb(root, party);
  348. const size_t from_node = std::floor(static_cast<double>(from) / nodes_per_leaf);
  349. __m128i * s[2] = {
  350. reinterpret_cast<__m128i *>(output) + nodes_in_interval * (nodes_per_leaf - 1),
  351. s[0] + nodes_in_interval / 2
  352. };
  353. int8_t * t[2] = { _t, _t + nodes_in_interval / 2};
  354. int curlayer = depth % 2;
  355. s[curlayer][0] = root;
  356. t[curlayer][0] = get_lsb(root, 0b01);
  357. __m128i * CW = (__m128i *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(__m128i));
  358. if(ind == 0)
  359. {
  360. std::cout << "root = " << root[0] << " " << root[1] << std::endl;
  361. std::cout << "t[curlayer][0] " << (int) t[curlayer][0] << std::endl;
  362. }
  363. dpfP2 dpf_instance;
  364. dpf_instance.root = root;
  365. for (size_t layer = 0; layer < depth; ++layer)
  366. {
  367. #ifdef VERBOSE
  368. printf("layer = %zu\n", layer);
  369. #endif
  370. curlayer = 1-curlayer;
  371. size_t i=0, j=0;
  372. auto nextbit = (from_node >> (nbits-layer-1)) & 1;
  373. size_t nodes_in_prev_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer)));
  374. size_t nodes_in_cur_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer-1)));
  375. __m128i L = _mm_setzero_si128();
  376. __m128i R = _mm_setzero_si128();
  377. for (i = nextbit, j = nextbit; j < nodes_in_prev_layer-1; ++j, i+=2)
  378. {
  379. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  380. L ^= s[curlayer][i];
  381. R ^= s[curlayer][i+1];
  382. }
  383. if (nodes_in_prev_layer > j)
  384. {
  385. if (i < nodes_in_cur_layer - 1)
  386. {
  387. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  388. L ^= s[curlayer][i];
  389. R ^= s[curlayer][i+1];
  390. }
  391. }
  392. compute_CW(socketsPb[socket_no], socketsP2[socket_no], L, R, target_share[layer], CW[layer]);
  393. uint8_t advice_L = get_lsb(L) ^ target_share[layer];
  394. uint8_t advice_R = get_lsb(R) ^ target_share[layer];
  395. uint8_t cwt_L, cwt_R;
  396. uint8_t advice[2];
  397. uint8_t cwts[2];
  398. advice[0] = advice_L;
  399. advice[1] = advice_R;
  400. boost::asio::write(socketsPb[socket_no+1], boost::asio::buffer(&advice, sizeof(advice)));
  401. boost::asio::read(socketsPb[socket_no+1], boost::asio::buffer(&cwts, sizeof(cwts)));
  402. cwt_L = cwts[0];
  403. cwt_R = cwts[1];
  404. cwt_L = cwt_L ^ advice_L ^ 1;
  405. cwt_R = cwt_R ^ advice_R;
  406. #ifdef DEBUG
  407. if(ind == 0)
  408. {
  409. std::cout << "CW reconstruction = " << CW[layer][0] << " " << CW[layer][1] << std::endl;
  410. std::cout << " cwt_L = " << (int) cwt_L << std::endl;
  411. std::cout << " cwt_R = " << (int) cwt_R << std::endl;
  412. }
  413. #endif
  414. dpf_instance.CW[layer] = CW[layer];
  415. dpf_instance.cwt_L[layer] = cwt_L;
  416. dpf_instance.cwt_R[layer] = cwt_R;
  417. for(size_t j = 0; j < nodes_in_prev_layer; ++j)
  418. {
  419. t[curlayer][2*j] = get_lsb(s[curlayer][2*j]) ^ (cwt_L & t[1-curlayer][j]);
  420. s[curlayer][2*j] = clear_lsb(xor_if(s[curlayer][2*j], CW[layer], !t[1-curlayer][j]), 0b11);
  421. t[curlayer][(2*j)+1] = get_lsb(s[curlayer][(2*j)+1]) ^ (cwt_R & t[1-curlayer][j]);
  422. s[curlayer][(2*j)+1] = clear_lsb(xor_if(s[curlayer][(2*j)+1], CW[layer], !t[1-curlayer][j]), 0b11);
  423. }
  424. }
  425. boost::asio::write(socketsP2[socket_no+1], boost::asio::buffer(&dpf_instance, sizeof(dpfP2)));
  426. __m128i Gamma = _mm_setzero_si128();
  427. for (size_t i = 0; i < to + 1; ++i)
  428. {
  429. Gamma[0] += output[i][0];
  430. Gamma[1] += output[i][1]; // the correction word for share conversion
  431. }
  432. if(party)
  433. {
  434. Gamma[0] = -Gamma[0];
  435. Gamma[1] = -Gamma[1]; // the correction word for share conversion
  436. }
  437. // boost::asio::write(socketsPb[socket_no + 3], boost::asio::buffer(&Gamma, sizeof(Gamma)));
  438. // boost::asio::read(socketsPb[socket_no + 3], boost::asio::buffer(&final_correction_word, sizeof(final_correction_word)));
  439. final_correction_word = Gamma; // final_correction_word + Gamma;
  440. } // dpf::__evalinterval
  441. inline void evaluate_dpfs( size_t db_nitems, dpfP2 dpfinstance, const AES_KEY& prgkey, const size_t from, const size_t to,
  442. __m128i * output, int8_t * _t, __m128i& final_correction_word, bool party,
  443. size_t ind)
  444. {
  445. const size_t bits_per_leaf = std::is_same<leaf_t, bool>::value ? 1 : sizeof(leaf_t) * CHAR_BIT;
  446. const bool is_packed = (sizeof(leaf_t) < sizeof(node_t));
  447. const size_t nodes_per_leaf = is_packed ? 1 : std::ceil(static_cast<double>(bits_per_leaf) / (sizeof(node_t) * CHAR_BIT));
  448. const size_t depth = std::ceil(std::log2(db_nitems));
  449. const size_t nbits = std::ceil(std::log2(db_nitems));
  450. const size_t nodes_in_interval = db_nitems-1;
  451. __m128i root = dpfinstance.root;
  452. __m128i * CW = (__m128i *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(__m128i));
  453. uint8_t * cwt_L = (uint8_t *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(uint8_t));
  454. uint8_t * cwt_R = (uint8_t *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(uint8_t));
  455. for(size_t j = 0; j < depth; ++j)
  456. {
  457. CW[j] = dpfinstance.CW[j];
  458. cwt_L[j] = dpfinstance.cwt_L[j];
  459. cwt_R[j] = dpfinstance.cwt_R[j];
  460. }
  461. root = set_lsb(root, party);
  462. const size_t from_node = std::floor(static_cast<double>(from) / nodes_per_leaf);
  463. __m128i * s[2] = {
  464. reinterpret_cast<__m128i *>(output) + nodes_in_interval * (nodes_per_leaf - 1),
  465. s[0] + nodes_in_interval / 2
  466. };
  467. int8_t * t[2] = { _t, _t + nodes_in_interval / 2};
  468. int curlayer = depth % 2;
  469. s[curlayer][0] = root;
  470. t[curlayer][0] = get_lsb(root, 0b01);
  471. #ifdef VERBOSE
  472. if(ind == 0)
  473. {
  474. std::cout << "root = " << root[0] << " " << root[1] << std::endl;
  475. std::cout << "t[curlayer][0] " << (int) t[curlayer][0] << std::endl;
  476. }
  477. #endif
  478. for (size_t layer = 0; layer < depth; ++layer)
  479. {
  480. #ifdef VERBOSE
  481. printf("layer = %zu\n", layer);
  482. #endif
  483. curlayer = 1-curlayer;
  484. size_t i=0, j=0;
  485. auto nextbit = (from_node >> (nbits-layer-1)) & 1;
  486. size_t nodes_in_prev_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer)));
  487. size_t nodes_in_cur_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer-1)));
  488. for (i = nextbit, j = nextbit; j < nodes_in_prev_layer-1; ++j, i+=2)
  489. {
  490. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  491. }
  492. if (nodes_in_prev_layer > j)
  493. {
  494. if (i < nodes_in_cur_layer - 1)
  495. {
  496. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  497. }
  498. }
  499. #ifdef VERBOSE
  500. if(ind == 0)
  501. {
  502. std::cout << "CW reconstruction = " << CW[layer][0] << " " << CW[layer][1] << std::endl;
  503. std::cout << " cwt_L = " << (int) cwt_L[layer] << std::endl;
  504. std::cout << " cwt_R = " << (int) cwt_R[layer] << std::endl;
  505. }
  506. #endif
  507. for(size_t j = 0; j < nodes_in_prev_layer; ++j)
  508. {
  509. t[curlayer][2*j] = get_lsb(s[curlayer][2*j]) ^ (cwt_L[layer] & t[1-curlayer][j]);
  510. s[curlayer][2*j] = clear_lsb(xor_if(s[curlayer][2*j], CW[layer], !t[1-curlayer][j]), 0b11);
  511. t[curlayer][(2*j)+1] = get_lsb(s[curlayer][(2*j)+1]) ^ (cwt_R[layer] & t[1-curlayer][j]);
  512. s[curlayer][(2*j)+1] = clear_lsb(xor_if(s[curlayer][(2*j)+1], CW[layer], !t[1-curlayer][j]), 0b11);
  513. }
  514. }
  515. __m128i Gamma = _mm_setzero_si128();
  516. for (size_t i = 0; i < to + 1; ++i)
  517. {
  518. Gamma[0] += output[i][0];
  519. Gamma[1] += output[i][1]; // the correction word for share conversion
  520. }
  521. if(party)
  522. {
  523. Gamma[0] = -Gamma[0];
  524. Gamma[1] = -Gamma[1]; // the correction word for share conversion
  525. }
  526. final_correction_word = Gamma; // final_correction_word + Gamma;
  527. } // dpf::__evalinterval