rdpf.tcc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326
  1. // Templated method implementations for rdpf.hpp
  2. // Create a StreamEval object that will start its output at index start.
  3. // It will wrap around to 0 when it hits 2^depth. If use_expansion
  4. // is true, then if the DPF has been expanded, just output values
  5. // from that. If use_expansion=false or if the DPF has not been
  6. // expanded, compute the values on the fly. If xor_offset is non-zero,
  7. // then the outputs are actually
  8. // DPF(start XOR xor_offset)
  9. // DPF((start+1) XOR xor_offset)
  10. // DPF((start+2) XOR xor_offset)
  11. // etc.
  12. template <typename T>
  13. StreamEval<T>::StreamEval(const T &rdpf, address_t start,
  14. address_t xor_offset, size_t &aes_ops,
  15. bool use_expansion) : rdpf(rdpf), aes_ops(aes_ops),
  16. use_expansion(use_expansion), counter_xor_offset(xor_offset)
  17. {
  18. depth = rdpf.depth();
  19. // Prevent overflow of 1<<depth
  20. if (depth < ADDRESS_MAX_BITS) {
  21. indexmask = (address_t(1)<<depth)-1;
  22. } else {
  23. indexmask = ~0;
  24. }
  25. start &= indexmask;
  26. counter_xor_offset &= indexmask;
  27. // Record that we haven't actually output the leaf for index start
  28. // itself yet
  29. nextindex = start;
  30. if (use_expansion && rdpf.has_expansion()) {
  31. // We just need to keep the counter, not compute anything
  32. return;
  33. }
  34. path.resize(depth);
  35. pathindex = start;
  36. path[0] = rdpf.get_seed();
  37. for (nbits_t i=1;i<depth;++i) {
  38. bool dir = !!(pathindex & (address_t(1)<<(depth-i)));
  39. bool xor_offset_bit =
  40. !!(counter_xor_offset & (address_t(1)<<(depth-i)));
  41. path[i] = rdpf.descend(path[i-1], i-1,
  42. dir ^ xor_offset_bit, aes_ops);
  43. }
  44. }
  45. template <typename T>
  46. typename T::node StreamEval<T>::next()
  47. {
  48. if (use_expansion && rdpf.has_expansion()) {
  49. // Just use the precomputed values
  50. typename T::node leaf =
  51. rdpf.get_expansion(nextindex ^ counter_xor_offset);
  52. nextindex = (nextindex + 1) & indexmask;
  53. return leaf;
  54. }
  55. // Invariant: in the first call to next(), nextindex = pathindex.
  56. // Otherwise, nextindex = pathindex+1.
  57. // Get the XOR of nextindex and pathindex, and strip the low bit.
  58. // If nextindex and pathindex are equal, or pathindex is even
  59. // and nextindex is the consecutive odd number, index_xor will be 0,
  60. // indicating that we don't have to update the path, but just
  61. // compute the appropriate leaf given by the low bit of nextindex.
  62. //
  63. // Otherwise, say for example pathindex is 010010111 and nextindex
  64. // is 010011000. Then their XOR is 000001111, and stripping the low
  65. // bit yields 000001110, so how_many_1_bits will be 3.
  66. // That indicates (typically) that path[depth-3] was a left child,
  67. // and now we need to change it to a right child by descending right
  68. // from path[depth-4], and then filling the path after that with
  69. // left children.
  70. //
  71. // When we wrap around, however, index_xor will be 111111110 (after
  72. // we strip the low bit), and how_many_1_bits will be depth-1, but
  73. // the new top child (of the root seed) we have to compute will be a
  74. // left, not a right, child.
  75. uint64_t index_xor = (nextindex ^ pathindex) & ~1;
  76. nbits_t how_many_1_bits = __builtin_popcount(index_xor);
  77. if (how_many_1_bits > 0) {
  78. // This will almost always be 1, unless we've just wrapped
  79. // around from the right subtree back to the left, in which case
  80. // it will be 0.
  81. bool top_changed_bit =
  82. !!(nextindex & (address_t(1) << how_many_1_bits));
  83. bool xor_offset_bit =
  84. !!(counter_xor_offset & (address_t(1) << how_many_1_bits));
  85. path[depth-how_many_1_bits] =
  86. rdpf.descend(path[depth-how_many_1_bits-1],
  87. depth-how_many_1_bits-1,
  88. top_changed_bit ^ xor_offset_bit, aes_ops);
  89. for (nbits_t i = depth-how_many_1_bits; i < depth-1; ++i) {
  90. bool xor_offset_bit =
  91. !!(counter_xor_offset & (address_t(1) << (depth-i-1)));
  92. path[i+1] = rdpf.descend(path[i], i, xor_offset_bit, aes_ops);
  93. }
  94. }
  95. bool xor_offset_bit = counter_xor_offset & 1;
  96. typename T::node leaf = rdpf.descend(path[depth-1], depth-1,
  97. (nextindex & 1) ^ xor_offset_bit, aes_ops);
  98. pathindex = nextindex;
  99. nextindex = (nextindex + 1) & indexmask;
  100. return leaf;
  101. }
  102. // Additive share of the scaling value M_as such that the high words
  103. // of the leaf values for P0 and P1 add to M_as * e_{target}
  104. template <>
  105. inline std::tuple<RegAS,RegAS,RegAS> RDPFTriple::scaled_value<RegAS>() const {
  106. return std::make_tuple(dpf[0].scaled_sum, dpf[1].scaled_sum,
  107. dpf[2].scaled_sum);
  108. }
  109. // XOR share of the scaling value M_xs such that the high words
  110. // of the leaf values for P0 and P1 XOR to M_xs * e_{target}
  111. template <>
  112. inline std::tuple<RegXS,RegXS,RegXS> RDPFTriple::scaled_value<RegXS>() const {
  113. return std::make_tuple(dpf[0].scaled_xor, dpf[1].scaled_xor,
  114. dpf[2].scaled_xor);
  115. }
  116. // Get the bit-shared unit vector entry from the leaf node
  117. template <>
  118. inline std::tuple<RegXS,RegXS,RegXS> RDPFTriple::unit<RegXS>(node leaf) const {
  119. return std::make_tuple(
  120. dpf[0].unit_bs(std::get<0>(leaf)),
  121. dpf[1].unit_bs(std::get<1>(leaf)),
  122. dpf[2].unit_bs(std::get<2>(leaf)));
  123. }
  124. // Get the additive-shared unit vector entry from the leaf node
  125. template <>
  126. inline std::tuple<RegAS,RegAS,RegAS> RDPFTriple::unit<RegAS>(node leaf) const {
  127. return std::make_tuple(
  128. dpf[0].unit_as(std::get<0>(leaf)),
  129. dpf[1].unit_as(std::get<1>(leaf)),
  130. dpf[2].unit_as(std::get<2>(leaf)));
  131. }
  132. // Get the XOR-shared scaled vector entry from the leaf ndoe
  133. template <>
  134. inline std::tuple<RegXS,RegXS,RegXS> RDPFTriple::scaled<RegXS>(node leaf) const {
  135. return std::make_tuple(
  136. dpf[0].scaled_xs(std::get<0>(leaf)),
  137. dpf[1].scaled_xs(std::get<1>(leaf)),
  138. dpf[2].scaled_xs(std::get<2>(leaf)));
  139. }
  140. // Get the additive-shared scaled vector entry from the leaf node
  141. template <>
  142. inline std::tuple<RegAS,RegAS,RegAS> RDPFTriple::scaled<RegAS>(node leaf) const {
  143. return std::make_tuple(
  144. dpf[0].scaled_as(std::get<0>(leaf)),
  145. dpf[1].scaled_as(std::get<1>(leaf)),
  146. dpf[2].scaled_as(std::get<2>(leaf)));
  147. }
  148. // Additive share of the scaling value M_as such that the high words
  149. // of the leaf values for P0 and P1 add to M_as * e_{target}
  150. template <>
  151. inline std::tuple<RegAS,RegAS> RDPFPair::scaled_value<RegAS>() const {
  152. return std::make_tuple(dpf[0].scaled_sum, dpf[1].scaled_sum);
  153. }
  154. // XOR share of the scaling value M_xs such that the high words
  155. // of the leaf values for P0 and P1 XOR to M_xs * e_{target}
  156. template <>
  157. inline std::tuple<RegXS,RegXS> RDPFPair::scaled_value<RegXS>() const {
  158. return std::make_tuple(dpf[0].scaled_xor, dpf[1].scaled_xor);
  159. }
  160. // Get the bit-shared unit vector entry from the leaf node
  161. template <>
  162. inline std::tuple<RegXS,RegXS> RDPFPair::unit<RegXS>(node leaf) const {
  163. return std::make_tuple(
  164. dpf[0].unit_bs(std::get<0>(leaf)),
  165. dpf[1].unit_bs(std::get<1>(leaf)));
  166. }
  167. // Get the additive-shared unit vector entry from the leaf node
  168. template <>
  169. inline std::tuple<RegAS,RegAS> RDPFPair::unit<RegAS>(node leaf) const {
  170. return std::make_tuple(
  171. dpf[0].unit_as(std::get<0>(leaf)),
  172. dpf[1].unit_as(std::get<1>(leaf)));
  173. }
  174. // Get the XOR-shared scaled vector entry from the leaf ndoe
  175. template <>
  176. inline std::tuple<RegXS,RegXS> RDPFPair::scaled<RegXS>(node leaf) const {
  177. return std::make_tuple(
  178. dpf[0].scaled_xs(std::get<0>(leaf)),
  179. dpf[1].scaled_xs(std::get<1>(leaf)));
  180. }
  181. // Get the additive-shared scaled vector entry from the leaf node
  182. template <>
  183. inline std::tuple<RegAS,RegAS> RDPFPair::scaled<RegAS>(node leaf) const {
  184. return std::make_tuple(
  185. dpf[0].scaled_as(std::get<0>(leaf)),
  186. dpf[1].scaled_as(std::get<1>(leaf)));
  187. }
  188. // I/O for RDPFs
  189. template <typename T>
  190. T& operator>>(T &is, RDPF &rdpf)
  191. {
  192. is.read((char *)&rdpf.seed, sizeof(rdpf.seed));
  193. rdpf.whichhalf = get_lsb(rdpf.seed);
  194. uint8_t depth;
  195. // Add 64 to depth to indicate an expanded RDPF
  196. is.read((char *)&depth, sizeof(depth));
  197. bool read_expanded = false;
  198. if (depth > 64) {
  199. read_expanded = true;
  200. depth -= 64;
  201. }
  202. assert(depth <= ADDRESS_MAX_BITS);
  203. rdpf.cw.clear();
  204. for (uint8_t i=0; i<depth; ++i) {
  205. DPFnode cw;
  206. is.read((char *)&cw, sizeof(cw));
  207. rdpf.cw.push_back(cw);
  208. }
  209. if (read_expanded) {
  210. rdpf.expansion.resize(1<<depth);
  211. is.read((char *)rdpf.expansion.data(),
  212. sizeof(rdpf.expansion[0])<<depth);
  213. }
  214. value_t cfbits = 0;
  215. is.read((char *)&cfbits, BITBYTES(depth));
  216. rdpf.cfbits = cfbits;
  217. is.read((char *)&rdpf.unit_sum_inverse, sizeof(rdpf.unit_sum_inverse));
  218. is.read((char *)&rdpf.scaled_sum, sizeof(rdpf.scaled_sum));
  219. is.read((char *)&rdpf.scaled_xor, sizeof(rdpf.scaled_xor));
  220. return is;
  221. }
  222. // Write the DPF to the output stream. If expanded=true, then include
  223. // the expansion _if_ the DPF is itself already expanded. You can use
  224. // this to write DPFs to files.
  225. template <typename T>
  226. T& write_maybe_expanded(T &os, const RDPF &rdpf,
  227. bool expanded = true)
  228. {
  229. os.write((const char *)&rdpf.seed, sizeof(rdpf.seed));
  230. uint8_t depth = rdpf.cw.size();
  231. assert(depth <= ADDRESS_MAX_BITS);
  232. // If we're writing an expansion, add 64 to depth
  233. uint8_t expanded_depth = depth;
  234. bool write_expansion = false;
  235. if (expanded && rdpf.expansion.size() == (size_t(1)<<depth)) {
  236. write_expansion = true;
  237. expanded_depth += 64;
  238. }
  239. os.write((const char *)&expanded_depth, sizeof(expanded_depth));
  240. for (uint8_t i=0; i<depth; ++i) {
  241. os.write((const char *)&rdpf.cw[i], sizeof(rdpf.cw[i]));
  242. }
  243. if (write_expansion) {
  244. os.write((const char *)rdpf.expansion.data(),
  245. sizeof(rdpf.expansion[0])<<depth);
  246. }
  247. os.write((const char *)&rdpf.cfbits, BITBYTES(depth));
  248. os.write((const char *)&rdpf.unit_sum_inverse, sizeof(rdpf.unit_sum_inverse));
  249. os.write((const char *)&rdpf.scaled_sum, sizeof(rdpf.scaled_sum));
  250. os.write((const char *)&rdpf.scaled_xor, sizeof(rdpf.scaled_xor));
  251. return os;
  252. }
  253. // The ordinary << version never writes the expansion, since this is
  254. // what we use to send DPFs over the network.
  255. template <typename T>
  256. T& operator<<(T &os, const RDPF &rdpf)
  257. {
  258. return write_maybe_expanded(os, rdpf, false);
  259. }
  260. // I/O for RDPF Triples
  261. // We never write RDPFTriples over the network, so always write
  262. // the DPF expansions if they're available.
  263. template <typename T>
  264. T& operator<<(T &os, const RDPFTriple &rdpftrip)
  265. {
  266. write_maybe_expanded(os, rdpftrip.dpf[0], true);
  267. write_maybe_expanded(os, rdpftrip.dpf[1], true);
  268. write_maybe_expanded(os, rdpftrip.dpf[2], true);
  269. nbits_t depth = rdpftrip.dpf[0].depth();
  270. os.write((const char *)&rdpftrip.as_target.ashare, BITBYTES(depth));
  271. os.write((const char *)&rdpftrip.xs_target.xshare, BITBYTES(depth));
  272. return os;
  273. }
  274. template <typename T>
  275. T& operator>>(T &is, RDPFTriple &rdpftrip)
  276. {
  277. is >> rdpftrip.dpf[0] >> rdpftrip.dpf[1] >> rdpftrip.dpf[2];
  278. nbits_t depth = rdpftrip.dpf[0].depth();
  279. rdpftrip.as_target.ashare = 0;
  280. is.read((char *)&rdpftrip.as_target.ashare, BITBYTES(depth));
  281. rdpftrip.xs_target.xshare = 0;
  282. is.read((char *)&rdpftrip.xs_target.xshare, BITBYTES(depth));
  283. return is;
  284. }
  285. // I/O for RDPF Pairs
  286. // We never write RDPFPairs over the network, so always write
  287. // the DPF expansions if they're available.
  288. template <typename T>
  289. T& operator<<(T &os, const RDPFPair &rdpfpair)
  290. {
  291. write_maybe_expanded(os, rdpfpair.dpf[0], true);
  292. write_maybe_expanded(os, rdpfpair.dpf[1], true);
  293. return os;
  294. }
  295. template <typename T>
  296. T& operator>>(T &is, RDPFPair &rdpfpair)
  297. {
  298. is >> rdpfpair.dpf[0] >> rdpfpair.dpf[1];
  299. return is;
  300. }