dpfgen.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391
  1. struct dpfP2
  2. {
  3. __m128i root;
  4. __m128i CW[32];
  5. uint8_t cwt_L[32];
  6. uint8_t cwt_R[32];
  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. uint8_t random_value;
  19. arc4random_buf(&random_value, sizeof(uint8_t));
  20. target_share_read[i][j] = random_value;//rand();
  21. target_share_read[i][j] = target_share_read[i][j] % 2;
  22. //if(party) target_share_read[i][expo-2] = 1;
  23. }
  24. }
  25. }
  26. struct cw_construction
  27. {
  28. __m128i rand_b, gamma_b;
  29. uint8_t bit_b;
  30. };
  31. struct BlindsCW
  32. {
  33. __m128i blinded_message;
  34. uint8_t blinded_bit;
  35. };
  36. struct reconstructioncw
  37. {
  38. __m128i cw;
  39. uint8_t cwbit[2];
  40. };
  41. void compute_CW(cw_construction computecw_array, size_t ind, size_t layer,tcp::socket& sout, __m128i L, __m128i R, uint8_t bit, __m128i & CW, uint8_t &cwt_L, uint8_t &cwt_R)
  42. {
  43. reconstructioncw cwsent, cwrecv;
  44. __m128i rand_b = computecw_array.rand_b; // computecw.rand_b;
  45. __m128i gamma_b = computecw_array.gamma_b; // computecw.gamma_b;
  46. uint8_t bit_b = computecw_array.bit_b; // computecw.bit_b;
  47. uint8_t blinded_bit, blinded_bit_read;
  48. blinded_bit = bit ^ bit_b;
  49. __m128i blinded_L = L ^ R ^ rand_b;
  50. __m128i blinded_L_read;
  51. BlindsCW blinds_sent, blinds_recv;
  52. blinds_sent.blinded_bit = blinded_bit;
  53. blinds_sent.blinded_message = blinded_L;
  54. //exchange blinded shares for OSWAP.
  55. boost::asio::write(sout, boost::asio::buffer(&blinds_sent, sizeof(BlindsCW)));
  56. communication_cost += sizeof(__m128i);
  57. boost::asio::read(sout, boost::asio::buffer(&blinds_recv, sizeof(BlindsCW)));
  58. blinded_bit_read = blinds_recv.blinded_bit;
  59. blinded_L_read = blinds_recv.blinded_message;
  60. cwsent.cw = R ^ gamma_b;
  61. if(bit)
  62. {
  63. cwsent.cw ^= (L ^ R ^ blinded_L_read);
  64. }
  65. if(blinded_bit_read)
  66. {
  67. cwsent.cw ^= rand_b;
  68. }
  69. cwsent.cwbit[0] = get_lsb(L) ^ bit;//advice[0];
  70. cwsent.cwbit[1] = get_lsb(R) ^ bit;//advice[1];
  71. boost::asio::write(sout, boost::asio::buffer(&cwsent, sizeof(cwsent)));
  72. boost::asio::read(sout, boost::asio::buffer(&cwrecv, sizeof(cwrecv)));
  73. communication_cost += sizeof(__m128i);
  74. cwrecv.cw ^= cwsent.cw;
  75. cwrecv.cwbit[0] ^= (cwsent.cwbit[0] ^ 1);
  76. cwrecv.cwbit[1] ^= (cwsent.cwbit[1]);
  77. cwt_L = cwrecv.cwbit[0];
  78. cwt_R = cwrecv.cwbit[1];
  79. CW = cwrecv.cw;
  80. // The following asserts the correctness of ComputeCW
  81. #ifdef DEBUG
  82. uint8_t bit_reconstruction;
  83. boost::asio::write(sout, boost::asio::buffer(&bit, sizeof(bit)));
  84. boost::asio::read(sout, boost::asio::buffer(&bit_reconstruction, sizeof(bit_reconstruction)));
  85. bit_reconstruction = bit ^ bit_reconstruction;
  86. __m128i L_reconstruction;
  87. boost::asio::write(sout, boost::asio::buffer(&L, sizeof(L)));
  88. boost::asio::read(sout, boost::asio::buffer(&L_reconstruction, sizeof(L_reconstruction)));
  89. L_reconstruction = L ^ L_reconstruction;
  90. __m128i R_reconstruction;
  91. boost::asio::write(sout, boost::asio::buffer(&R, sizeof(R)));
  92. boost::asio::read(sout, boost::asio::buffer(&R_reconstruction, sizeof(R_reconstruction)));
  93. R_reconstruction = R ^ R_reconstruction;
  94. __m128i CW_debug;
  95. if(bit_reconstruction != 0)
  96. {
  97. CW_debug = L_reconstruction;
  98. }
  99. else
  100. {
  101. CW_debug = R_reconstruction;
  102. }
  103. assert(CW_debug[0] == CW[0]);
  104. assert(CW_debug[1] == CW[1]);
  105. #endif
  106. }
  107. template<typename node_t, typename prgkey_t>
  108. static inline void traverse(const prgkey_t & prgkey, const node_t & seed, node_t s[2])
  109. {
  110. dpf::PRG(prgkey, clear_lsb(seed, 0b11), s, 2);
  111. } // dpf::expand
  112. /**
  113. * @brief
  114. *
  115. * @param nodes_per_leaf
  116. * @param depth
  117. * @param nbits
  118. * @param nodes_in_interval
  119. * @param prgkey The PRG Key
  120. * @param target_share
  121. * @param socketsPb Array of sockets to write to Pb
  122. * @param socketsP2 Array of sockets to write to P2
  123. * @param from
  124. * @param to
  125. * @param output
  126. * @param _t
  127. * @param final_correction_word the final correction word is written in to this
  128. * @param party Party
  129. * @param socket_no
  130. */
  131. inline void create_dpfs (bool reading, size_t db_nitems, const AES_KEY& prgkey,
  132. uint8_t target_share[64], std::vector<socket_t>& socketsPb, std::vector<socket_t>& socketsP2, const size_t from, const size_t to, __m128i * output, int8_t * _t, __m128i& final_correction_word,
  133. cw_construction computecw_array, dpfP2 * dpf_instance,
  134. bool party, size_t socket_no, size_t ind = 0)
  135. {
  136. const size_t bits_per_leaf = std::is_same<leaf_t, bool>::value ? 1 : sizeof(leaf_t) * CHAR_BIT;
  137. const bool is_packed = (sizeof(leaf_t) < sizeof(node_t));
  138. const size_t nodes_per_leaf = is_packed ? 1 : std::ceil(static_cast<double>(bits_per_leaf) / (sizeof(node_t) * CHAR_BIT));
  139. const size_t depth = std::ceil(std::log2(db_nitems));
  140. const size_t nbits = std::ceil(std::log2(db_nitems));
  141. const size_t nodes_in_interval = db_nitems-1;
  142. __m128i root;
  143. arc4random_buf(&root, sizeof(root));
  144. root = set_lsb(root, party);
  145. const size_t from_node = std::floor(static_cast<double>(from) / nodes_per_leaf);
  146. __m128i * s[2] = {
  147. reinterpret_cast<__m128i *>(output) + nodes_in_interval * (nodes_per_leaf - 1),
  148. s[0] + nodes_in_interval / 2
  149. };
  150. int8_t * t[2] = { _t, _t + nodes_in_interval / 2};
  151. int curlayer = depth % 2;
  152. s[curlayer][0] = root;
  153. t[curlayer][0] = get_lsb(root, 0b01);
  154. __m128i * CW = (__m128i *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(__m128i));
  155. #ifdef VERBOSE
  156. if(ind == 0)
  157. {
  158. std::cout << "root = " << root[0] << " " << root[1] << std::endl;
  159. std::cout << "t[curlayer][0] " << (int) t[curlayer][0] << std::endl;
  160. }
  161. #endif
  162. dpf_instance[ind].root = root;
  163. // cw_construction computecw_array[15];
  164. // boost::asio::read(socketsP2[0], boost::asio::buffer(&computecw_array, 15 * sizeof(computecw_array[0])));
  165. for (size_t layer = 0; layer < depth; ++layer)
  166. {
  167. #ifdef VERBOSE
  168. printf("layer = %zu\n", layer);
  169. #endif
  170. curlayer = 1-curlayer;
  171. size_t i=0, j=0;
  172. auto nextbit = (from_node >> (nbits-layer-1)) & 1;
  173. size_t nodes_in_prev_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer)));
  174. size_t nodes_in_cur_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer-1)));
  175. __m128i L = _mm_setzero_si128();
  176. __m128i R = _mm_setzero_si128();
  177. for (i = nextbit, j = nextbit; j < nodes_in_prev_layer-1; ++j, i+=2)
  178. {
  179. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  180. L ^= s[curlayer][i];
  181. R ^= s[curlayer][i+1];
  182. }
  183. if (nodes_in_prev_layer > j)
  184. {
  185. if (i < nodes_in_cur_layer - 1)
  186. {
  187. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  188. L ^= s[curlayer][i];
  189. R ^= s[curlayer][i+1];
  190. }
  191. }
  192. uint8_t cwt_L, cwt_R;
  193. // Computes the correction word using OSWAP
  194. compute_CW(computecw_array, ind, layer, socketsPb[socket_no], L, R, target_share[layer], CW[layer], cwt_L, cwt_R);
  195. #ifdef DEBUG
  196. if(ind == 0)
  197. {
  198. std::cout << "CW reconstruction = " << CW[layer][0] << " " << CW[layer][1] << std::endl;
  199. std::cout << " cwt_L = " << (int) cwt_L << std::endl;
  200. std::cout << " cwt_R = " << (int) cwt_R << std::endl;
  201. }
  202. #endif
  203. dpf_instance[ind].CW[layer] = CW[layer];
  204. dpf_instance[ind].cwt_L[layer] = cwt_L;
  205. dpf_instance[ind].cwt_R[layer] = cwt_R;
  206. for(size_t j = 0; j < nodes_in_prev_layer; ++j)
  207. {
  208. t[curlayer][2*j] = get_lsb(s[curlayer][2*j]) ^ (cwt_L & t[1-curlayer][j]);
  209. s[curlayer][2*j] = clear_lsb(xor_if(s[curlayer][2*j], CW[layer], !t[1-curlayer][j]), 0b01);
  210. t[curlayer][(2*j)+1] = get_lsb(s[curlayer][(2*j)+1]) ^ (cwt_R & t[1-curlayer][j]);
  211. s[curlayer][(2*j)+1] = clear_lsb(xor_if(s[curlayer][(2*j)+1], CW[layer], !t[1-curlayer][j]), 0b01);
  212. }
  213. }
  214. __m128i Gamma = _mm_setzero_si128();
  215. for (size_t i = 0; i < to + 1; ++i)
  216. {
  217. Gamma[0] += output[i][0]; // the correction word for duoram update
  218. Gamma[1] += output[i][1]; // the correction word for share conversion
  219. }
  220. if(party)
  221. {
  222. Gamma[0] = -Gamma[0]; // the correction word for duoram update
  223. Gamma[1] = -Gamma[1]; // the correction word for share conversion
  224. }
  225. #ifdef DEBUG
  226. boost::asio::write(socketsPb[socket_no + 3], boost::asio::buffer(&Gamma, sizeof(Gamma)));
  227. boost::asio::read(socketsPb[socket_no + 3], boost::asio::buffer(&final_correction_word, sizeof(final_correction_word)));
  228. #endif
  229. final_correction_word = Gamma;
  230. } // create_dpfs
  231. inline void evaluate_dpfs( size_t db_nitems, dpfP2 dpfinstance, const AES_KEY& prgkey, const size_t from, const size_t to,
  232. __m128i * output, int8_t * _t, bool party, size_t ind)
  233. {
  234. const size_t bits_per_leaf = std::is_same<leaf_t, bool>::value ? 1 : sizeof(leaf_t) * CHAR_BIT;
  235. const bool is_packed = (sizeof(leaf_t) < sizeof(node_t));
  236. const size_t nodes_per_leaf = is_packed ? 1 : std::ceil(static_cast<double>(bits_per_leaf) / (sizeof(node_t) * CHAR_BIT));
  237. const size_t depth = std::ceil(std::log2(db_nitems));
  238. const size_t nbits = std::ceil(std::log2(db_nitems));
  239. const size_t nodes_in_interval = db_nitems-1;
  240. __m128i root = dpfinstance.root;
  241. __m128i * CW = (__m128i *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(__m128i));
  242. uint8_t * cwt_L = (uint8_t *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(uint8_t));
  243. uint8_t * cwt_R = (uint8_t *) std::aligned_alloc(sizeof(__m256i), depth * sizeof(uint8_t));
  244. for(size_t j = 0; j < depth; ++j)
  245. {
  246. CW[j] = dpfinstance.CW[j];
  247. cwt_L[j] = dpfinstance.cwt_L[j];
  248. cwt_R[j] = dpfinstance.cwt_R[j];
  249. }
  250. root = set_lsb(root, party);
  251. const size_t from_node = std::floor(static_cast<double>(from) / nodes_per_leaf);
  252. __m128i * s[2] = {
  253. reinterpret_cast<__m128i *>(output) + nodes_in_interval * (nodes_per_leaf - 1),
  254. s[0] + nodes_in_interval / 2
  255. };
  256. int8_t * t[2] = { _t, _t + nodes_in_interval / 2};
  257. int curlayer = depth % 2;
  258. s[curlayer][0] = root;
  259. t[curlayer][0] = get_lsb(root, 0b01);
  260. #ifdef VERBOSE
  261. if(ind == 0)
  262. {
  263. std::cout << "root = " << root[0] << " " << root[1] << std::endl;
  264. std::cout << "t[curlayer][0] " << (int) t[curlayer][0] << std::endl;
  265. }
  266. #endif
  267. for (size_t layer = 0; layer < depth; ++layer)
  268. {
  269. #ifdef VERBOSE
  270. printf("layer = %zu\n", layer);
  271. #endif
  272. curlayer = 1-curlayer;
  273. size_t i=0, j=0;
  274. auto nextbit = (from_node >> (nbits-layer-1)) & 1;
  275. size_t nodes_in_prev_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer)));
  276. size_t nodes_in_cur_layer = std::ceil(static_cast<double>(nodes_in_interval) / (1ULL << (depth-layer-1)));
  277. for (i = nextbit, j = nextbit; j < nodes_in_prev_layer-1; ++j, i+=2)
  278. {
  279. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  280. }
  281. if (nodes_in_prev_layer > j)
  282. {
  283. if (i < nodes_in_cur_layer - 1)
  284. {
  285. traverse(prgkey, s[1-curlayer][j], &s[curlayer][i]);
  286. }
  287. }
  288. #ifdef VERBOSE
  289. if(ind == 0)
  290. {
  291. std::cout << "CW reconstruction = " << CW[layer][0] << " " << CW[layer][1] << std::endl;
  292. std::cout << " cwt_L = " << (int) cwt_L[layer] << std::endl;
  293. std::cout << " cwt_R = " << (int) cwt_R[layer] << std::endl;
  294. }
  295. #endif
  296. for(size_t j = 0; j < nodes_in_prev_layer; ++j)
  297. {
  298. t[curlayer][2*j] = get_lsb(s[curlayer][2*j]) ^ (cwt_L[layer] & t[1-curlayer][j]);
  299. s[curlayer][2*j] = clear_lsb(xor_if(s[curlayer][2*j], CW[layer], !t[1-curlayer][j]), 0b11);
  300. t[curlayer][(2*j)+1] = get_lsb(s[curlayer][(2*j)+1]) ^ (cwt_R[layer] & t[1-curlayer][j]);
  301. s[curlayer][(2*j)+1] = clear_lsb(xor_if(s[curlayer][(2*j)+1], CW[layer], !t[1-curlayer][j]), 0b11);
  302. }
  303. }
  304. } // evaluate_dpfs