123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349 
 #include <bsd/stdlib.h> // arc4random_buf
 #include "bitutils.hpp"
 #include "cdpf.hpp"
 // Generate a pair of CDPFs with the given target value
 //
 // Cost:
 // 4*VALUE_BITS  28 = 228 local AES operations
 std::tuple<CDPF,CDPF> CDPF::generate(value_t target, size_t &aes_ops)
 {
 CDPF dpf0, dpf1;
 const nbits_t depth = VALUE_BITS  7;
 // Pick two random seeds
 arc4random_buf(&dpf0.seed, sizeof(dpf0.seed));
 arc4random_buf(&dpf1.seed, sizeof(dpf1.seed));
 // Ensure the flag bits (the lsb of each node) are different
 dpf0.seed = set_lsb(dpf0.seed, 0);
 dpf1.seed = set_lsb(dpf1.seed, 1);
 dpf0.whichhalf = 0;
 dpf1.whichhalf = 1;
 dpf0.cfbits = 0;
 dpf1.cfbits = 0;
 dpf0.as_target.randomize();
 dpf1.as_target.ashare = target  dpf0.as_target.ashare;
 dpf0.xs_target.randomize();
 dpf1.xs_target.xshare = target ^ dpf0.xs_target.xshare;
 // The current node in each CDPF as we descend the tree. The
 // invariant is that cur0 and cur1 are the nodes on the path to the
 // target at level curlevel. They will necessarily be different,
 // and indeed must have different flag (low) bits.
 DPFnode cur0 = dpf0.seed;
 DPFnode cur1 = dpf1.seed;
 nbits_t curlevel = 0;
 while(curlevel < depth) {
 // Construct the two (uncorrected) children of each node
 DPFnode left0, right0, left1, right1;
 prgboth(left0, right0, cur0, aes_ops);
 prgboth(left1, right1, cur1, aes_ops);
 // Which way lies the target?
 bool targetdir = !!(target & (value_t(1)<<((depth+7)curlevel1)));
 DPFnode CW;
 bool cfbit = !get_lsb(left0 ^ left1 ^ right0 ^ right1);
 bool flag0 = get_lsb(cur0);
 bool flag1 = get_lsb(cur1);
 // The last level is special
 if (curlevel < depth1) {
 if (targetdir == 0) {
 // The target is to the left, so make the correction word
 // and bit make the right children the same and the left
 // children have different flag bits.
 // Recall that descend will apply (only for the party whose
 // current node (cur0 or cur1) has the flag bit set, for
 // which exactly one of the two will) CW to both children,
 // and cfbit to the flag bit of the right child.
 CW = right0 ^ right1 ^ lsb128_mask[cfbit];
 // Compute the current nodes for the next level
 // Exactly one of these two XORs will fire, so afterwards,
 // cur0 ^ cur1 = left0 ^ left1 ^ CW, which will have low bit
 // 1 by the definition of cfbit.
 cur0 = xor_if(left0, CW, flag0);
 cur1 = xor_if(left1, CW, flag1);
 } else {
 // The target is to the right, so make the correction word
 // and bit make the left children the same and the right
 // children have different flag bits.
 CW = left0 ^ left1;
 // Compute the current nodes for the next level
 // Exactly one of these two XORs will fire, so similar to
 // the above, afterwards, cur0 ^ cur1 = right0 ^ right1 ^ CWR,
 // which will have low bit 1.
 DPFnode CWR = CW ^ lsb128_mask[cfbit];
 cur0 = xor_if(right0, CWR, flag0);
 cur1 = xor_if(right1, CWR, flag1);
 }
 } else {
 // We're at the last level before the leaves. We still want
 // the children not in the direction of targetdir to end up
 // the same, but now we want the child in the direction of
 // targetdir to also end up the same, except for the single
 // target bit. Importantly, the low bit (the flag bit in
 // all other nodes) is not special, and will in fact usually
 // end up the same for the two DPFs (unless the target bit
 // happens to be the low bit of the word; i.e., the low 7
 // bits of target are all 0).
 // This will be a 128bit word with a single bit set, in
 // position (target & 0x7f).
 uint8_t loc = (target & 0x7f);
 DPFnode target_set_bit = _mm_set_epi64x(
 loc >= 64 ? (uint64_t(1)<<(loc64)) : 0,
 loc >= 64 ? 0 : (uint64_t(1)<<loc));
 if (targetdir == 0) {
 // We want the right children to be the same, and the
 // left children to be the same except for the target
 // bit.
 // Remember for exactly one of the two parties, CW will
 // be applied to the left and CWR will be applied to the
 // right.
 CW = left0 ^ left1 ^ target_set_bit;
 DPFnode CWR = right0 ^ right1;
 dpf0.leaf_cwr = CWR;
 dpf1.leaf_cwr = CWR;
 } else {
 // We want the left children to be the same, and the
 // right children to be the same except for the target
 // bit.
 // Remember for exactly one of the two parties, CW will
 // be applied to the left and CWR will be applied to the
 // right.
 CW = left0 ^ left1;
 DPFnode CWR = right0 ^ right1 ^ target_set_bit;
 dpf0.leaf_cwr = CWR;
 dpf1.leaf_cwr = CWR;
 }
 }
 dpf0.cw.push_back(CW);
 dpf1.cw.push_back(CW);
 dpf0.cfbits = (value_t(cfbit)<<curlevel);
 dpf1.cfbits = (value_t(cfbit)<<curlevel);
 ++curlevel;
 }
 return std::make_tuple(dpf0, dpf1);
 }
 // Generate a pair of CDPFs with a random target value
 //
 // Cost:
 // 4*VALUE_BITS  28 = 228 local AES operations
 std::tuple<CDPF,CDPF> CDPF::generate(size_t &aes_ops)
 {
 value_t target;
 arc4random_buf(&target, sizeof(target));
 return generate(target, aes_ops);
 }
 // Get the leaf node for the given input. We don't actually use
 // this in the protocol, but it's useful for testing.
 DPFnode CDPF::leaf(value_t input, size_t &aes_ops) const
 {
 nbits_t depth = cw.size();
 DPFnode node = seed;
 input >>= 7;
 for (nbits_t d=0;d<depth1;++d) {
 bit_t dir = !!(input & (value_t(1)<<(depthd1)));
 node = descend(node, d, dir, aes_ops);
 }
 // The last layer is special
 bit_t dir = input & 1;
 node = descend_to_leaf(node, dir, aes_ops);
 return node;
 }
 // Compare the given additively shared element to 0. The output is
 // a triple of bit shares; the first is a share of 1 iff the
 // reconstruction of the element is negative; the second iff it is
 // 0; the third iff it is positive. (All as two'scomplement
 // VALUE_BITbit integers.) Note in particular that exactly one of
 // the outputs will be a share of 1, so you can do "greater than or
 // equal to" just by adding the greater and equal outputs together.
 // Note also that you can compare two RegAS values A and B by
 // passing AB here.
 //
 // Cost:
 // 1 word sent in 1 message
 // 2*VALUE_BITS  14 = 114 local AES operations
 std::tuple<RegBS,RegBS,RegBS> CDPF::compare(MPCTIO &tio, yield_t &yield,
 RegAS x, size_t &aes_ops)
 {
 // Reconstruct S = targetx
 // The server does nothing in this protocol
 if (tio.player() < 2) {
 RegAS S_share = as_target  x;
 tio.iostream_peer() << S_share;
 yield();
 RegAS peer_S_share;
 tio.iostream_peer() >> peer_S_share;
 value_t S = S_share.ashare + peer_S_share.ashare;
 // After that one singleword exchange, the rest of this
 // algorithm is entirely a local computation.
 return compare(S, aes_ops);
 } else {
 yield();
 }
 // The server gets three shares of 0 (which is not a valid output
 // for the computational players)
 RegBS lt, eq, gt;
 return std::make_tuple(lt, eq, gt);
 }
 // You can call this version directly if you already have S = targetx
 // reconstructed. This routine is entirely local; no communication
 // is needed.
 //
 // Cost:
 // 2*VALUE_BITS  14 = 114 local AES operations
 std::tuple<RegBS,RegBS,RegBS> CDPF::compare(value_t S, size_t &aes_ops)
 {
 RegBS gt, eq;
 // Now we're going to simultaneously descend the DPF tree for the
 // values S and T = S + 2^63. Note that the 1 values of V (see the
 // explanation of the algorithm in cdpf.hpp) are those values
 // _strictly_ larger than S and smaller than T (noting they can
 // "wrap around" 2^64). In level 1 of the tree, the paths to S and
 // T will necessarily be at the two different children of the root
 // seed, but they could be in either order. From then on, they will
 // proceed in lockstep, either both going left, or both going right.
 // If they both go left, we also compute the flag for the right
 // sibling on the S path (which will be the XOR of the left sibling
 // and the parent), and add it to the gt flag. If they both go
 // right, we also include the left sibling on the T path (which will
 // be the XOR of the right sibling and the parent), and add it to
 // the gt flag. When we hit the leaves, the gt flag will account
 // for all of the complete leaf nodes strictly greater than S and
 // strictly less than T. Then we just have to pull out the parity
 // of the appropriate bits in the two leaf nodes containing S and T
 // respectively to complete the computation of gt, and also to get
 // the single bit eq.
 nbits_t curlevel = 0;
 const nbits_t depth = VALUE_BITS  7;
 DPFnode Sparent = seed;
 DPFnode Tparent = seed;
 // The top level is the only place where the paths to S and T go
 // in different directions.
 bool Sdir = !!(S & (value_t(1)<<63));
 DPFnode Snode = descend(Sparent, curlevel, Sdir, aes_ops);
 DPFnode Tnode = descend(Tparent, curlevel, !Sdir, aes_ops);
 curlevel = 1;
 // Invariant: Snode is the node on level curlevel on the path to
 // S, and Tnode is the node on level curlevel on the path to
 // T = S + 2^63. Sparent and Tparent are the parents of Snode and
 // Tnode respectively.
 // The last level is special, so terminate the loop 1 before the end
 while(curlevel < depth1) {
 Sdir = !!(S & (value_t(1)<<((depth+7)curlevel1)));
 Sparent = Snode;
 Tparent = Tnode;
 Snode = descend(Sparent, curlevel, Sdir, aes_ops);
 Tnode = descend(Tparent, curlevel, Sdir, aes_ops);
 ++curlevel;
 if (Sdir == 0) {
 // They both went left; include the right child of
 // Sparent in the gt computation
 gt ^= get_lsb(Sparent) ^ get_lsb(Snode);
 } else {
 // Theye both went right; include the left child of
 // Tparent in the gt computation
 gt ^= get_lsb(Tparent) ^ get_lsb(Tnode);
 }
 }
 // Now we're at the level just above the leaves. If we go left,
 // include *all* the bits (not just the low bit) of the right child
 // of Sparent (which will be the flag bit of Sparent XORed with the
 // parity of all the bits of Snode), and if we go right, include all
 // the bits of the left child of Tnode (which will be the flag bit
 // of Tparent XORed with the parity of all the bits of Tnode).
 Sdir = !!(S & (value_t(1)<<((depth+7)curlevel1)));
 Sparent = Snode;
 Tparent = Tnode;
 Snode = descend_to_leaf(Sparent, Sdir, aes_ops);
 Tnode = descend_to_leaf(Tparent, Sdir, aes_ops);
 ++curlevel;
 if (Sdir == 0) {
 // They both went left; include the right child of
 // Snode in the gt computation
 gt ^= get_lsb(Sparent) ^ parity(Snode);
 } else {
 // They're both going right; include the left child of
 // Tnode in the gt computation
 gt ^= get_lsb(Tparent) ^ parity(Tnode);
 }
 // Now Snode and Tnode are the leaves containing S and T
 // respectively. Pull out the bit in Snode for S itself into eq,
 // and all the higher bits into gt. Also pull out the bits strictly
 // below that for T in Tnode into gt.
 nbits_t Spos = S & 0x7f;
 eq.bshare = bit_at(Snode, Spos);
 gt ^= parity_above(Snode, Spos);
 gt ^= parity_below(Tnode, Spos);
 // Once we have gt and eq (which cannot both be 1), lt is just 1
 // exactly if they're both 0.
 RegBS lt;
 lt.bshare = whichhalf ^ eq.bshare ^ gt.bshare;
 return std::make_tuple(lt, eq, gt);
 }
 // You can call this version directly if you already have S = targetx
 // reconstructed. This routine is entirely local; no communication
 // is needed. This function is identical to compare, above, except that
 // it only computes what's needed for the eq output.
 //
 // Cost:
 // VALUE_BITS  7 = 57 local AES operations
 RegBS CDPF::is_zero(value_t S, size_t &aes_ops)
 {
 RegBS eq;
 // We' descend the DPF tree for the values S.
 // Invariant: Snode is the node on level curlevel on the path to
 // S.
 nbits_t curlevel = 0;
 const nbits_t depth = VALUE_BITS  7;
 DPFnode Snode = seed;
 bool Sdir = !!(S & (value_t(1)<<63));
 Snode = descend(Snode, curlevel, Sdir, aes_ops);
 curlevel = 1;
 // The last level is special
 while(curlevel < depth1) {
 Sdir = !!(S & (value_t(1)<<((depth+7)curlevel1)));
 Snode = descend(Snode, curlevel, Sdir, aes_ops);
 ++curlevel;
 }
 // Now we're at the level just above the leaves. If we go left,
 // include *all* the bits (not just the low bit) of the right
 // child of Snode, and if we go right, include all the bits of
 // the left child of Tnode.
 Sdir = !!(S & (value_t(1)<<((depth+7)curlevel1)));
 Snode = descend_to_leaf(Snode, Sdir, aes_ops);
 ++curlevel;
 // Now Snode is the leaf containing S. Pull out the bit in Snode
 // for S itself into eq.
 nbits_t Spos = S & 0x7f;
 eq.bshare = bit_at(Snode, Spos);
 return eq;
 }
