#ifndef __DPF_HPP__
#define __DPF_HPP__
#include
#include "prg.hpp"
// We have two major kinds of distributed point functions (DPFs): ones
// used for random-access memory (RDPFs) and ones used for comparisons
// (CDPFs). The major differences:
//
// RDPFs are of depth r in order to obliviously access a memory of size
// 2^r. They are created jointly by P0 and P1, with O(r) communication,
// but O(2^r) local computation. They can output bit shares of a
// single-bit unit vector, word-sized additive shares of a unit vector,
// XOR shares of a scaled unit vector, or additive shares of a scaled
// unit vector. They are typically used by evaluating _all_ 2^r leaves.
// All of the 2^r leaves have to be computed at creation time, anyway,
// so you can choose to store an "expanded" version of them that just
// records those precomputed values, making them much faster to use in
// the online phase, at the cost of storage and memory (and the time it
// takes to just read them from disk, particular on rotational media).
//
// CDPFs are only used to compare VALUE_BITS-bit values (typically
// VALUE_BITS = 64), and can only output bit shares of a single-bit unit
// vector. This allows for an optimization where the leaf nodes of the
// DPF (which are 128 bits wide) can subsume the last 7 levels of the
// tree, so the CDPF is actually of height VALUE_BITS-7 (typically 57).
// They are never used to expand all leaves, since that's way too large,
// nor could P0 and P1 jointly compute them in the way they compute
// RDPFs. On the other hand, P2 never sees these CDPFs in the online
// phase, so P2 can just create them and send the halves to P0 and P1 at
// preprocessing time. They are very cheap to create, store, and send
// over the network (in the preprocessing phase), and evaluate (in the
// online phase); all of these are O(VALUE_BITS-7), somewhat abusing O()
// notation here.
struct DPF {
// The type of nodes
using node = DPFnode;
// The 128-bit seed
DPFnode seed;
// Which half of the DPF are we?
bit_t whichhalf;
// correction words
std::vector cw;
// correction flag bits: the one for level i is bit i of this word
value_t cfbits;
// The seed
inline node get_seed() const { return seed; }
// Descend from a node at depth parentdepth to one of its children
// whichchild = 0: left child
// whichchild = 1: right child
//
// Cost: 1 AES operation
inline DPFnode descend(const DPFnode &parent, nbits_t parentdepth,
bit_t whichchild, size_t &aes_ops) const;
};
// Descend from a node at depth parentdepth to one of its children
// whichchild = 0: left child
// whichchild = 1: right child
inline DPFnode DPF::descend(const DPFnode &parent, nbits_t parentdepth,
bit_t whichchild, size_t &aes_ops) const
{
DPFnode prgout;
bool flag = get_lsb(parent);
prg(prgout, parent, whichchild, aes_ops);
if (flag) {
DPFnode CW = cw[parentdepth];
bit_t cfbit = !!(cfbits & (value_t(1)<