Ryan Henry
0d22946a0e
Ship the TLS mesh, composer, Beaver/Yao/leaf MPC, prep/online paths, apps, and docs so the tree is pushable before elevating share_expr, security_mode, and prep resume. Co-authored-by: Cursor <cursoragent@cursor.com>
40 KiB
A guided tour of libdpf++
This page is a map of the library in plain words. It shows short code, then points you to the full manuals when you want more. To choose which object to build, follow [which DPF](@ref which_dpf).
[TOC]
What problem does this solve?
Imagine a big table of zeros, with one non-zero cell at a secret place. You want two helpers to hold that table. Each helper gets a small key, not the whole table. Neither helper learns where the non-zero cell is. Together, their answers add up to the true table.
That secret table is a point function.
A distributed point function (DPF) is a way to share it with short keys.
libdpf++ builds those keys and evaluates them quickly in C++17.
People use DPFs for private lookup (PIR), multi-party computation (MPC), and other privacy tools. This tree also ships the network and MPC stack those protocols need: TLS party sessions, RoundSink rounds, Beaver / Yao / arithmetic shares on leaf values, composition, leveled run logs, and paper-cost statistics. That map is [Network, parties, and MPC](@ref network_and_mpc); logging and CSVs are [Logging, statistics, and experiments](@ref experiment_costs). See also the [ideal functionalities](@ref ideal_functionalities) for what each protocol is allowed to learn.
Prior work
Elette Boyle, Niv Gilboa, and Yuval Ishai gave the point-function keys this library generates, and the later sections name Jack Doerner and abhi shelat, Xiaojie Guo, Kang Yang, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, and Zheli Liu, and the other authors, next to the construction they described. The [bibliography](@ref bibliography) lists each paper once.
Your first DPF
Include one header. Build a key for each of two parties. Evaluate at a point. Open the two shares.
#include "dpf.hpp"
const std::uint8_t alpha = 42; // secret index
const std::uint64_t beta = 7; // secret payload
auto [k0, k1] = dpf::make_dpf(alpha, beta);
auto y0 = *dpf::eval_point(k0, alpha);
auto y1 = *dpf::eval_point(k1, alpha);
std::uint64_t opened = dpf::reconstruct(y0, y1); // 7
Leaf outputs open with subtraction: share0 - share1.
Comparison outputs open with addition: share0 + share1.
dpf::reconstruct picks the right rule from the share types.
Try next
- Full example: [eval_point.cpp](@ref evaluation/eval_point.cpp)
- Eval manual: [Evaluating DPFs](@ref evaluation)
- Key API: [dpf_key.hpp](@ref dpf/dpf_key.hpp)
The feature zoo
The list on the home page is the short version. Here is the full map.
Inputs: where the secret point lives
The input type is the type of the index alpha.
Shorter inputs mean shorter keys and faster walks.
| Kind | What it is for | Go deeper |
|---|---|---|
uintN_t / intN_t |
Widths 8, 16, 32, 64 | [Input types](@ref input_types) |
| 128-bit integers | Big domains | [extended types](@ref input_types) |
modint<N> / modintN_t |
Unsigned residue mod 2^N |
[modint.hpp](@ref dpf/modint.hpp) |
xint<N> / xintN_t |
XOR ring of width N |
[xor_wrapper.hpp](@ref dpf/xor_wrapper.hpp) |
dpf::bitstring<N> |
Opaque bit strings | [bitstring.hpp](@ref dpf/bitstring.hpp) |
dpf::keyword / keyword2 |
Dictionary keys, ranked patterns | [keyword2.hpp](@ref dpf/keyword2.hpp) |
grotto::fixedpoint |
Fixed-point domain | [fixedpoint.hpp](@ref grotto/fixedpoint.hpp) |
wildcard_value<Input> |
Secret index assigned later | [wildcard.hpp](@ref dpf/wildcard.hpp) |
| Custom types | Your own domain | [custom input rules](@ref custom_input_types) |
using X = dpf::modint<20>; // domain size 2^20
auto [k0, k1] = dpf::make_dpf(X{1000}, std::uint64_t{1});
// same index: 1000_u20
Width literals sit next to those types: 100_u12 (modint), 7_x12
(xint), dpf::literals::operator""_bitstring, and 1.5_fixed16 through
_fixed64. dpf::bit, dpf::twobit, dpf::nyble, and dpf::gf2 through
dpf::gf264 are outputs, not domains. See [Input types](@ref input_types).
Outputs: what sits at that point
The output type is the group element at alpha.
Many outputs can share one leaf when they fit.
| Kind | Group | Go deeper |
|---|---|---|
uintN_t / intN_t / modint<N> |
Additive | [Output types](@ref output_types) |
xint<N> / xor_wrapper |
Word XOR | [xor_wrapper.hpp](@ref dpf/xor_wrapper.hpp) |
dpf::bit |
One XOR bit, packed | [bit.hpp](@ref dpf/bit.hpp) |
dpf::twobit |
Z/4Z, packed 2-bit lanes | [twobit.hpp](@ref dpf/twobit.hpp) |
dpf::nyble |
Z/16Z, packed nibbles | [nyble.hpp](@ref dpf/nyble.hpp) |
gf2 … gf264 |
GF(2^k), XOR add, field multiply | [gf2.hpp](@ref dpf/gf2.hpp) |
dpf::bitstring |
XOR string | [bitstring.hpp](@ref dpf/bitstring.hpp) |
grotto::fixedpoint |
Fixed-point raw word | [fixedpoint.hpp](@ref grotto/fixedpoint.hpp) |
dpf::vec<T, N> |
N lanes, no carry between them |
[vec.hpp](@ref dpf/vec.hpp) |
dpf::wildcard_value<T> |
Fill later | [wildcard.hpp](@ref dpf/wildcard.hpp) |
field64 / field128 |
Prime fields | [field64.hpp](@ref dpf/field64.hpp) |
fp61 |
Field for 3-party DPFs | [fp61.hpp](@ref dpf/fp61.hpp) |
p256 / p256_scalar |
Curve and order | [p256.hpp](@ref dpf/p256.hpp) |
| Typed shares | (2,2) additive and subtractive, (3,3) additive, (2,3) replicated, (K,N) Shamir | [secret_share.hpp](@ref dpf/secret_share.hpp), [shamir.hpp](@ref dpf/shamir.hpp) |
auto [k0, k1] = dpf::make_dpf(
std::uint8_t{12},
dpf::wildcard_value<std::uint32_t>{});
// assign the payload later; eval before assign throws
Shamir shares are shamir::share<T, Party, K, N>. Any K of N open the
constant term. (2,3) is shamir_share. The fields are fp61 and gf2n.
For gf2n, N must be less than 2^k. make_dpf3 uses the (2,3) case
on fp61. examples/mwe/shamir.cpp deals a (3,5) secret in fp61 and a
(2,3) secret in gf28.
Packed output literals are 1_bit, 2_twobit, and 10_nyble.
dpf::vec<T, N> is N lanes of an ordinary output with no carry between
lanes; the construction is on [Output types](@ref output_types).
Assigning a wildcard leaf is
[leaf_nodes](@ref wildcard_assign): compute_and_get_blinded_output_share,
compute_and_get_leaf_share, reconstruct_correction_word, or
async_assign_leaf over a socket. The socket path is two rounds, one
output-width share each way per round. The Beaver triple on the slot
is preprocessing from keygen. assign_cmp rewrites n words locally
and sends nothing.
Many leaves and prefix slots
One key can carry several payloads.
dpf::at<N>(value) plants a value on a public prefix of length N.
That is an incremental DPF: one path can read an ancestor and a leaf.
auto [k0, k1] = dpf::make_dpf(
std::uint8_t{0x2a},
dpf::at<4>(std::uint8_t{5}), // high nibble
std::uint8_t{9}); // full leaf, prefix 8
auto hi = *dpf::eval_point(dpf::out<0, 4>, k0, std::uint8_t{0x2a});
auto leaf = *dpf::eval_point(dpf::out<1, 8>, k0, std::uint8_t{0x2a});
// one payload per listed prefix; idpf(y0, y1) is prefixes 1, 2, ...
auto [h0, h1] = dpf::make_dpf(std::uint8_t{0x2a},
dpf::idpf_at<4, 8>(std::uint8_t{5}, std::uint8_t{9}));
dpf::out<I> reads slot I and takes the prefix from the key.
dpf::out<I, W> checks that the prefix is W.
Go deeper: [incremental.hpp](@ref dpf/incremental.hpp), [placement.hpp](@ref dpf/placement.hpp), [F_IDPF](@ref incremental.hpp).
How you evaluate
| Call | What it does |
|---|---|
eval_point |
One input |
eval_interval |
Inclusive range [from, to] |
eval_full |
Whole domain |
eval_sequence |
Sorted list of points |
eval_inner_product |
Dot with weights during the walk |
eval_until / idpf_eval_ctx |
Compact prefix shares up to a public bit depth |
| Memoizers | Keep tree nodes between calls |
| Output buffers | Hold the written shares |
auto [k0, k1] = dpf::make_dpf(std::uint8_t{42}, std::uint64_t{7});
std::vector<std::uint64_t> w(11, 1);
auto s0 = dpf::eval_inner_product(dpf::paired, k0, std::uint8_t{40},
std::uint8_t{50}, w);
auto s1 = dpf::eval_inner_product(dpf::paired, k1, std::uint8_t{40},
std::uint8_t{50}, w);
// reconstruct(s0, s1) == 7 * w[2]
Let n be the input bit length and λ the seed width (128 bits for
the default AES PRG). A key is Θ(n λ) bits plus its payloads.
That is the Boyle–Gilboa–Ishai CCS 2016 point key (full version
[ePrint 2018/707](@ref bib_fss2018)): one correction word per level. For a small output group their Remark 3.4 stops
ν = log2(λ / log2|G|) levels early. This generator does that:
depth is n minus the log of how many outputs pack in one leaf, and
those low bits select the lane. eval_point is Θ(n) expands. An inclusive interval of L inputs is
Θ(n + L) expands and L output slots. A sorted list of m points is
at most O(n m) expands and m slots. A full-domain eval is Θ(2^n).
An inner product does that same walk and keeps only the accumulator.
Memoizer and buffer sizes are on the [eval manual](@ref evaluation).
Go deeper: [Evaluating DPFs](@ref evaluation),
[eval_inner_product.hpp](@ref dpf/eval_inner_product.hpp),
[eval_until.hpp](@ref dpf/eval_until.hpp),
examples under examples/evaluation/.
idpf_eval_ctx plus eval_until ([ePrint 2021/017](@ref bib_poplar) EvaluateUntil) emit
compact prefix shares up to a public bit depth without a full-domain
walk. idpf_agg_max / idpf_agg_kth ([ePrint 2024/1190](@ref bib_idpfagg)) drive that
API for order statistics — see [I-DPF max and k-th](@ref app_idpf_agg).
Iterables
After a multi-point eval, you often want to walk only the hot leaves,
or zip two parties' buffers.
eval_interval and eval_full return a subinterval_iterable.
eval_sequence returns a subsequence_iterable.
indices_set_in walks the set bits of a bit-output iterable.
advice_bits_of yields the low bit of each element.
batch_of steps several bit arrays together.
tuple_as_zip walks iterables in lockstep.
rotated_by rotates a container.
Go deeper: [Iterables](@ref iterables).
Comparisons and ranges
\htmlonly
A distributed comparison function (DCF) returns a payload when a predicate
holds on the secret point. The four predicates are dpf::lt, dpf::leq,
dpf::gt, and dpf::geq. Each takes the true payload and an optional false
payload (zero by default). lt_at<N> and the same _at<N> forms for
leq, gt, and geq plant the channel on a prefix of length N.
Evaluate with dpf::cmp. Shares are additive.
auto [k0, k1] = dpf::make_dpf(std::uint8_t{40}, dpf::gt(std::uint64_t{1}));
// hot when the query is greater than 40
auto y0 = dpf::eval_point(dpf::cmp, k0, std::uint8_t{50});
auto y1 = dpf::eval_point(dpf::cmp, k1, std::uint8_t{50});
auto opened = dpf::reconstruct(y0, y1); // 1
A wildcard comparison payload is filled later with assign_cmp. Eval
before that throws.
auto [w0, w1] = dpf::make_dpf(std::uint8_t{40},
dpf::lt(dpf::wildcard_value<std::uint64_t>{}));
dpf::assign_cmp(w0, w1, std::uint64_t{7}, std::uint64_t{0});
dpf::idcf(dpf::gt(beta)) (any of the four predicates) stores a correction
at every depth. dpf::cmp is the full point; dpf::cmp_prefix<L> is the
first L bits. dpf::eq(if_true, if_false) is equality, with eq_at<N>
on a prefix. dpf::block_width<B>(dpf::lt(beta)) keeps ring words only at
checkpoints B levels apart.
auto [i0, i1] = dpf::make_dpf(std::uint8_t{40},
dpf::ic(10, 20, std::uint64_t{1}));
// hot when (x - 40) mod 256 is between 10 and 20
auto in0 = dpf::eval_point(dpf::ic, i0, std::uint8_t{55});
A comparison key keeps the n-level seed spine and one payload word
per level (Θ(n λ + n w) bits for a w-bit payload). That is the DCF
of Boyle, Chandran, Gilboa, Gupta, Ishai, Kumar, and Rathee, EUROCRYPT
2021 ([ePrint 2020/1392](@ref bib_dcf)). block_width<B> stores a payload word every
B levels, Θ(n/B) words, and the spine is unchanged. Against that
EUROCRYPT 2021 comparison, which publishes a value word on every level,
block_width<B> is ahead on payload size: about B times fewer value
words, with the same seed spine. Point evaluation expands the siblings
between checkpoints to recover the same comparison. Point eval is one path,
Θ(n) expands, plus an O(n) sum of those words. ic is one such key,
the public-interval gate in their Figure 3, evaluated at two public
shifts, still Θ(n).
Path paints put a unit on sibling subtrees and scale it by
if_true - if_false. The canned ones are lcp, common_prefix,
prefix_mask, diverge_one_hot, break_bit, and prefix_with_length.
path_paint(fn, if_true, if_false) supplies the unit. Each has an _at<N>
form.
auto [p0, p1] = dpf::make_dpf(std::uint8_t{40},
dpf::common_prefix(std::uint64_t{1}));
Go deeper: [dcf.hpp](@ref dpf/dcf.hpp), [blocked_dcf.hpp](@ref dpf/blocked_dcf.hpp), [interval.hpp](@ref dpf/interval.hpp), ideal figures [F_DCF](@ref dcf.hpp), [F_BDCF](@ref blocked_dcf.hpp), [F_IC](@ref interval.hpp).
Verifiable and extractable keys
\htmlonly
Pass dpf::verifiable{} or dpf::extractable{} as an extra make_dpf
argument. verifiable follows de Castro and Polychroniadou, EUROCRYPT
2022 ([ePrint 2021/580](@ref bib_vdpf)): one extra correction seed per level (their hash
outputs 4λ bits), a 2λ-bit proof token, and the proof fold is part
of the same Θ(n) walk. The stored seed is Θ(n λ) more bits.
extractable adds one fp61 sketch token to that walk.
Each party folds a short proof token on a verifiable key.
Equal tokens mean the walk used honest correction seeds.
extractable is a weight-1 sketch over fp61. A second hot point fails
the check. dpf::updatable{} keeps a beaver leaf so a later assign can
rewrite the payload.
auto [k0, k1] = dpf::make_dpf(std::uint8_t{42}, std::uint64_t{7},
dpf::verifiable{});
auto [e0, e1] = dpf::make_dpf(std::uint8_t{42}, std::uint64_t{7},
dpf::extractable{});
Go deeper: [verifiable.hpp](@ref dpf/verifiable.hpp), [F_VDPF](@ref verifiable.hpp), [F_Sketch](@ref verifiable.hpp).
Many points at once
\htmlonly
make_multipoint(alphas, betas) packs many points into cuckoo buckets,
following de Castro and Polychroniadou, EUROCRYPT 2022, §4 (ePrint
2021/580): κ = 3 hashes, one point key per bucket.
Pass dpf::verifiable{} before the optional multipoint_params for a
batched proof: one token. There is one point key per bucket, and the
bucket count is linear in the number of points m, so the keys are
Θ(m n λ) bits. Eval probes three buckets: Θ(n) expands.
std::vector<std::uint8_t> alphas{1, 2, 3};
std::vector<std::uint64_t> betas{4, 5, 6};
auto [k0, k1] = dpf::make_multipoint(alphas, betas);
Go deeper: [multipoint.hpp](@ref dpf/multipoint.hpp), [F_MPDPF](@ref multipoint.hpp).
A vector with one programmable coordinate
\htmlonly
dpf::ppvc commits to a vector in (Z/2^s Z)^n before the hidden
coordinate is chosen. The commitment binds both roots of s aligned
1-bit DPF pairs. Opening one side of each pair writes that coordinate,
or the sum of the vector, and a shift moves it onto a public index.
using scheme = dpf::ppvc<std::uint8_t, 8>;
const auto pp = scheme::setup();
const auto [com, st] = scheme::commit(pp);
const auto op = scheme::open(st, 0, 0x5a, std::uint8_t{40});
dpf::k_ppvc<K, ...> is K of those commitments. The full account is
[Point-programmable vector commitments](@ref ppvc_manual).
Tree shapes: classic and Half-Tree
\htmlonly
The default interior PRG walks a Boyle–Gilboa–Ishai tree (CCS 2016,
full version [ePrint 2018/707](@ref bib_fss2018)).
Select prg::aes128_ccr as the interior PRG to use Half-Tree expands
(H(s) and H(s) XOR s), following Guo, Yang, Wang, Zhang, Xie, Zhang,
and Liu, [ePrint 2022/1431](@ref bib_halftree). Keys stay compatible with the same eval API.
The number of levels is still n, and a key is still Θ(n λ) bits.
Their dealer scheme keeps that length and the n-hash point evaluation,
and states about 2n+2 random-permutation calls to generate a key versus
about 4n, and 1.5N calls for a full-domain evaluation versus 2N.
Go deeper: [tree_traits.hpp](@ref dpf/tree_traits.hpp), [prg_aes_ccr.hpp](@ref dpf/prg_aes_ccr.hpp).
Two-party keygen without a dealer: Doerner–Shelat
\htmlonly
Two parties hold XOR (or additive) shares of alpha.
A third party deals pads and learns nothing.
The result matches what an honest make_dpf would emit.
geneval_* does keygen and eval in one pass on a public query trie.
You get shares of the answer without a reusable key.
const std::uint8_t alpha = 42;
const std::uint8_t x0 = 0x13;
const std::uint8_t x1 = static_cast<std::uint8_t>(alpha ^ x0);
const std::uint64_t beta = 7;
auto [k0, k1] = dpf::make_dpf_doerner_shelat(x0, x1, beta);
// index is x0 + x1; payload shares y0 + y1 reconstruct to beta
const std::uint64_t y0 = 3;
const std::uint64_t y1 = beta - y0;
auto [a0, a1] = dpf::make_dpf_doerner_shelat(
dpf::arith_input, x0, x1, beta);
auto [b0, b1] = dpf::make_dpf_doerner_shelat(
dpf::arith_output, x0, x1, y0, y1);
geneval_point, geneval_interval,
geneval_full, and geneval_sequence do that keygen and the eval in one
pass. They take the two shares, the public query, a dpf::ds_randomness
tape (root sampler and pad stream), and the payload.
The convenience make_dpf_doerner_shelat samples its pad tape locally
and returns both keys with no messages. The opening follows Jack Doerner
and abhi shelat, CCS 2017 ([ePrint 2017/827](@ref bib_ds)). A networked opening does one
round per level, n rounds, because the next seeds depend on that
level's correction word. Each round sends a constant number of λ-bit
blinds and returns one λ-bit correction word plus advice and AND bits.
Xiaojie Guo, Kang Yang, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, and Zheli Liu ([ePrint 2022/1431](@ref bib_halftree), §5.2) generate a DPF in the COT/OLE hybrid
in n+3 rounds with no beaver-pad dealer; this opening uses that dealer
tape. geneval_* is the same per-level opening on the public query trie.
It does not return their reusable key, and with a local tape it sends
nothing.
Preprocessing is one correction-word pad and two AND pads per level,
Θ(n λ) bits. geneval_* itself sends nothing: each live level samples
those pads from the ds_randomness tape and folds the frontier into one
correction word. Local expand time is O(n F) PRG expands, where F is
the number of distinct query leaves on the trie (the call rejects more
than 2^20). That is Θ(n) for one point and follows the trie for an
interval, a listed sequence, or a full domain. No reusable key is stored. arith_input first runs an n-step
ripple carry: n bit-multiplication triples and n bit openings, then
the same tree rounds. arith_output splits the payload and does not add
a round of its own beyond that split.
Two-party socket walk without p2 (IKNP)
\htmlonly
When there is no pad dealer, p0 and p1 sample the same Doerner–Shelat
pad correlations with semi-honest OT extension after Yuval Ishai, Joe
Kilian, Kobbi Nissim, and Erez Petrank, CRYPTO 2003 (dpf::iknp::sample),
seeded by the Chou–Orlandi base OT of Tung Chou and Claudio Orlandi,
LATINCRYPT 2015 ([ePrint 2015/267](@ref bib_chou)) on P-256, and install them into a local
inbox. The tree walk is the same as dist_with_* in party/dist_ds.hpp.
Entry points:
dist_with_point_key_iknp— point / half-tree / wildcard / additive inputdist_with_extractable_point_key_iknpdist_with_cmp_key_iknp— comparison (reveal or oblivious)dist_with_ic_key_iknp— interval containment
A wildcard leaf is the two-party payload bind: keygen does not learn β, and
assign writes it afterwards on the p0–p1 link. Fig-10 updatable rewrites
are a (2,3) operation and stay on dist_dpf3.
Ideal (semi-honest). Each party inputs its share of the point (XOR or
additive) and the payload; each outputs its DPF key. With
RevealPoint/Reveal, the reconstructed point (or comparison/interval
prefix) may be opened because the caller asked. Without reveal, α, the
peer seed, the peer payload share, and pad bits that would open the path
stay hidden. Correction-word gamma pads are XOR shares of
(bit1·rand0)⊕(bit0·rand1) so neither party learns the peer pad bit
(learning that bit plus the opened blind would open the peer path bit).
Costs (asymptotic, then one measured case). Let n be the input bit
length and λ = 128 the seed width. Write T for the XOR-pad tape
length that iknp_deal::add_* demands: for a reveal point key,
T = Θ(n) (ncw = n correction-word pads and nblock = 2n + n_leaf
bit×block pads). An oblivious (non-reveal) walk also buys
n · hash_level_and_count() bit×block pads, and
hash_level_and_count() = 8×16×10×32 = 40960 follows the Boyar–Peralta
32-AND AES S-box ([ePrint 2011/332](@ref bib_boyar)) inside party/oblivious_hash.hpp.
| Path | Rounds | Communication | Local work |
|---|---|---|---|
Dealer make_dpf |
0 | 0 | Θ(n) AES PRG expands |
DS + p2 dealer (dist_with_*) |
n online (one CW open per level) |
Dealer tape Θ(n λ) bits offline; peer opens Θ(n λ) bits |
Θ(n) expands |
| Half-Tree §5.2 ([ePrint 2022/1431](@ref bib_halftree)) | n+3 in the COT/OLE hybrid |
Hybrid COT/OLE (paper §5.2; not this library's opening) | CCR expands |
IKNP + DS (dist_with_*_iknp) |
Constant-round base OT + extension, then the same n DS opens |
Base: two Chou–Orlandi sessions of κ = 128 OTs (33-byte P-256 points). Extension (two directions): each sends κ ⌈T/8⌉ bytes of U plus T · λ/8 bytes of OT correction, then ncw · λ/8 bytes of gamma; B2A pads add one more extension of length nb2a. Peer DS messages match the dealer walk (no p2 frames). |
Θ(κ) P-256 scalar muls for base OT; Θ(κ T / w) AES column expands for the extension (w is the chunk width); then Θ(n) tree expands |
Compared to the p2 dealer path, IKNP removes the third party and replaces
the offline Θ(n λ)-bit pad send with OT whose dominant term is
Θ(κ T) bits for a reveal walk (T = Θ(n)). It does not beat
Half-Tree §5.2's n+3 round count: this library still opens one level
per round after the pads exist. It also does not claim a wall-clock
speedup over dealer keygen; dealer make_dpf stays local and free of
public-key work.
Measurement (party_bench --case iknp_geneval_point --repeat 1 --warmup 0, uint8 domain so n = 8, reveal point, localhost sockets,
one run): wall ≈ 1.08 s; p0 sent 9805 B / received 16499 B; p1 sent
11245 B / received 15059 B; harness rounds = 47 (IKNP frames plus the
n DS opens and the flow's eval openings); prg_evals = 2431 each.
The same harness on iknp_wildcard_leaf (non-reveal wildcard, so the
Boyar–Peralta oblivious hash tape is live) moved tens of megabytes and
took ≈ 1.8 s on one run — that is the n · 40960 pad blow-up, not a
claim about payload assign alone.
(2,3) Shamir DPF (party/dist_dpf3.hpp) still needs a third key holder;
there is no pure 2-party dpf3 entry point.
Go deeper: [doerner_shelat.hpp](@ref dpf/doerner_shelat.hpp),
[geneval.hpp](@ref dpf/geneval.hpp),
[F_DS](@ref doerner_shelat.hpp), [F_GenEval](@ref geneval.hpp),
party mesh [trio.hpp](@ref dpf/net/trio.hpp).
[iknp.hpp](@ref dpf/iknp.hpp), party/iknp_deal.hpp.
[Bibliography](@ref bibliography).
Multiplication and circuits: Beaver
\htmlonly
ABY2.0-style sessions open masked wires once, following Patra, Schneider, Suresh, and Yalame, USENIX Security 2021 (full version [ePrint 2020/1225](@ref bib_aby2)). A fresh triple follows Donald Beaver, [CRYPTO 1991](@ref bib_beaver), which reconstructs both masked factors. Polynomials, dots, scales, and bit-muxes share blinds. Optional MAC tags give Shark/SPDZ-style checks.
One call that samples a list of formulae opens the new wires in one round. Communication is one masked value per newly opened wire, of that wire's width, plus a tag share of the same width when MACs are on. Preprocessing is one blind per wire and one product share per monomial. A later round reuses blinds it already holds and samples only the new monomials. The dealer keeps each full blind; the parties receive the additive splits.
A word that has already left the key can be added and projected in one shot ([a small word](@ref arith_garble_word)). A public table on a short masked index is [FLUTE](@ref flute_lut). A secret point in a public table stays a DPF. The session above is still the interactive product.
Go deeper: [beaver.hpp](@ref dpf/beaver.hpp),
[F_Beaver](@ref beaver.hpp), [F_BeaverAuth](@ref beaver.hpp),
[constrained_cmp.hpp](@ref dpf/constrained_cmp.hpp) for F_CCMP.
A column of shares
The secret position in this library is a key. One cell of a shared array is a unit DPF, a public rotate, and a dot product ([Duoram](@ref app_duoram)).
A hidden shuffle is what you do when you already hold every row and you are
about to open the column. Three passes, from the pairwise seeds k01,
k12, and k20, leave one party out of each permutation. The opened order
is not the stored order, and no single party can recompute it.
shuffle_hidden_pass is one party's step. shuffle_party is the other
helper: one permutation from k01, which every holder of that seed can
recompute.
The shuffle does not look up a cell, and it does not sort. Those stay a DPF and a DCF.
Go deeper: [An array of shares](@ref share_shuffle), [shuffle.hpp](@ref dpf/shuffle.hpp).
When the leaf is a circuit
\htmlonly
A point leaf is subtractive, so the split is b2y and the return is y2b.
A comparison leaf is additive, so the split is a2y. An fss_share opens
like a point leaf. Parties 0 and 1 garbling a replicated leaf use rss2y;
party 2 does not send. The bits are least-significant first. Both shares
are arguments to the conversion. The masked x - r that A2B opens is uniform.
The netlist is XOR, AND, XNOR, and NOT. Party 0 garbles with half-gates
([ePrint 2014/756](@ref bib_halfgates)): 32 bytes per AND, one message, XOR
shares out. The block this is for is yao::aes_mmo, the same zero-key
Matyas–Meyer–Oseas block prg::aes128::eval uses on a tree expand, 5120
ANDs. AES-128 under a shared key is the other packaged netlist, 6400 ANDs.
The Doerner–Shelat oblivious hash still evaluates that S-box as GMW layers
in [the dealer-free section](@ref tour_ds). aes_mmo is one of those blocks
in constant rounds, for a leaf or a seed you already hold as bits.
A comparison, an interval, a public-offset polynomial, and a product of
two leaves do not come here. Those are a key, Grotto, or one Beaver open.
cost_pass does not grow a Yao strategy for them.
A secret if/else or a menu of blocks on those bits is stacked garbling ([a secret branch](@ref yao_stack)). The transmitted rows follow the heavier block. The leaf is still split in and shared back out. A comparison stays on the key.
Go deeper: [A boolean function of a leaf](@ref yao_leaf), [yao.hpp](@ref dpf/yao.hpp), [yao_share.hpp](@ref dpf/yao_share.hpp), [F_Yao](@ref yao.hpp), [F_YaoShare](@ref yao_share.hpp).
Three evaluators
\htmlonly
(2,3) point keys follow Zyskind, Yanai, and Pentland, [ePrint 2024/1658](@ref bib_dpf3),
Figure 3: each evaluator key is a pair of (2,2)-VDPF+ keys.
Each key is a Shamir share in fp61.
Any two parties open. Keys can be verifiable, extractable, or updatable.
Dealer make_dpf3 is local. Each key is two spines, Θ(n λ) bits.
Their evaluation section records about 2× the key size of one two-party
DPF, which is this pair of spines.
Eval is two point walks, Θ(n). Opening the field shares is O(1)
fp61 arithmetic. An updatable payload rewrite is O(λ), independent
of n. The dual-spine Doerner–Shelat form costs two copies of the
two-party opening in [that section](@ref tour_ds).
auto [k1, k2, k3] = dpf::make_dpf3(std::uint8_t{42}, dpf::fp61{7});
auto y1 = dpf::eval_point(k1, std::uint8_t{42});
auto y2 = dpf::eval_point(k2, std::uint8_t{42});
auto y3 = dpf::eval_point(k3, std::uint8_t{42});
auto opened = dpf::reconstruct(
dpf::as_share(k1, y1), dpf::as_share(k2, y2), dpf::as_share(k3, y3));
Dual-spine Doerner–Shelat builds the same three keys from XOR shares of
alpha. Comparison, interval, blocked, and multipoint forms are
make_dpf3_cmp, make_dpf3_ic, make_dpf3_cmp_blocked, and
make_multipoint3. remake_dpf3 replaces an updatable payload.
const std::uint8_t alpha = 42;
const std::uint8_t x0 = 0x13;
const std::uint8_t x1 = static_cast<std::uint8_t>(alpha ^ x0);
auto [s1, s2, s3] = dpf::make_dpf3_doerner_shelat(x0, x1, dpf::fp61{7});
auto opened_ds = dpf::reconstruct(
dpf::as_share(s1, dpf::eval_point(s1, alpha)),
dpf::as_share(s2, dpf::eval_point(s2, alpha)),
dpf::as_share(s3, dpf::eval_point(s3, alpha)));
Go deeper: [dpf3.hpp](@ref dpf/dpf3.hpp),
[dpf3_ds.hpp](@ref dpf/dpf3_ds.hpp),
[dpf3_cmp.hpp](@ref dpf/dpf3_cmp.hpp),
[dpf3_multipoint.hpp](@ref dpf/dpf3_multipoint.hpp),
examples eval_dpf3_*.cpp.
make_it_dpf3 is a different three-server object ([ePrint 2023/028](@ref bib_itdpf)):
additive truth-table shares on {0..255}, not Shamir spines. The sum of
three eval_it_dpf3 values is the point function. See
[Information-theoretic 3-server DPF](@ref it_dpf3) and
[Three-server PIR](@ref app_pir3).
Grotto: math after a public offset
\htmlonly
Open eta = x - r. Then cheap public corrections give rich functions of x
without another tree walk.
| Tool | Idea |
|---|---|
| Offset Horner / poly | Powers of the center, then a binomial shift |
| Binomial jet | Shares of \binom{x}{k}; free public dots |
| Ring switch | Exact move into Z/M, fields, or P-256 scalars |
nmod |
Truncated Barrett reduction by a public modulus |
| Representation shift | Advance a linear recurrence by public \kappa |
| Twisted jets | c^m \lambda^c, including dyadic 1/2 |
| Carry | Truncate, arithmetic shift, extend on shared limbs |
| Prefix parity | XOR or signed prefix sums along a key |
| LUT union | Several piecewise tables on one comparison and one prefix walk |
| LUTs | Constant, easy, dyadic, range, window, principal, Haar and bior(5,3) |
| Closed form / exact steps | Compositions and digit or bit counts |
fixed_mul |
Fixed-point product into a chosen width |
#include "grotto.hpp"
const std::uint8_t center = 12;
const std::uint8_t r = 200;
auto jet_keys = grotto::make_offset_jet_keys<std::uint8_t>(center, 3);
// after eta opens: offset_jet_shares, then offset_jet_dot
auto ring = grotto::make_ring_switch_keys<grotto::zn64<1009>>(r);
auto horner = grotto::make_offset_horner_keys<std::uint8_t, 2>(center);
auto poly = grotto::make_offset_poly_keys(center, 4);
using q16 = grotto::fixedpoint<16, std::int32_t>;
auto prod = grotto::fixed_mul<16, 16>(q16{1.5}, q16{2});
For degree d and K knots, offset Horner, poly, jet, and twist each
store one comparison (d ≤ 3 for Horner, d ≤ 16 otherwise). The
payload is a dpf::vec of the powers, so the λ-bit seed spine is
stored once and the value-correction words grow with the vector. Key
size is Θ(n λ) for the spine plus Θ(d n) bits of value words.
Storrier, Vadapalli, Lyons, and Henry ([ePrint 2023/108](@ref bib_grotto)) evaluate a
public piecewise polynomial from one point key by prefix parity; offset
Horner is this secret-center comparison, not that spline. After η is
public, each party runs one sequence-shaped walk on those knots, the
same order as eval_sequence, then O(d^2) local arithmetic. A ring switch
is one lt key and one point eval, Θ(n). nmod and fixed_mul are
local fixed-width arithmetic (fixed_mul uses at most 8 limbs). Carry
keys are one comparison per live recipe flag, on the limb width, plus
one Beaver bit-opening when the recipe multiplies share MSBs. Prefix
parity on m endpoints is one resumed path walk, O(m n) expands in
the worst case; that walk follows [ePrint 2023/108](@ref bib_grotto).
Several piecewise LUTs share one such comparison:
[make_lut_union_plan](@ref grotto/lut_union.hpp) unions their breakpoints,
and [schedule_lut_union](@ref grotto/lut_union.hpp) is one fss_cmp of
n rounds. The prefix walk over the union is local.
The degree-0 exact
LUTs follow Appendix D of the same paper. Haar and bior(5,3) tables
compress a uniform grid and evaluate in \f$\Theta(1)\f$ arithmetic
([ePrint 2025/013](@ref bib_wave)). Other LUT calls are a knot
search plus a constant-size Horner; exact steps loop over the word.
Detail is on the Grotto pages.
Go deeper: [jet_and_ring](@ref jet_and_ring), [repr_and_twist](@ref repr_and_twist), [grotto.hpp](@ref grotto.hpp), ideal figures on the offset headers under [Ideal functionalities](@ref ideal_functionalities).
JSON and async I/O
Serialize keys with the JSON helpers.
Ship keys over ASIO peers with dpf::asio::make_dpf.
Go deeper: [json.hpp](@ref dpf/json.hpp), [asio.hpp](@ref dpf/asio.hpp).
Running protocols
The overview of links, composition, leaf MPC, and measurement is [Network, parties, and MPC](@ref network_and_mpc).
The party/ programs run a three-role mesh (p0, p1, dealer p2).
Flows cover Beaver, geneval, DCF, DPF3, Grotto, and adversarial checks.
Use --list and --tag to filter.
Composed protocols record strands on a dpf::protocol::composer
([compose.hpp](@ref dpf/compose.hpp)). Values are tagged with a share
domain (fss, a, b, rss, y). An FSS leaf consumed by an ABY2.0
product gets a local b2a (or fss2a) inserted by as, and the leaf stays
on the beaver barrier's critical path so Duoram / SUBLEQ scale cannot float
before the walk. Like blinds and expansions are interned across sub-strands,
and independent opens share one RoundSink round. Party-count changes use an
explicit reshare (rss_from_y for y→rss). Composer-owned Beaver sessions use
beavers::schedule_objective::rounds so sign×polynomial stays one online
round; dealer benches that want Appendix-E peels keep the default prep
objective. Express/Sabre-style audits use fss_point_fused /
level_walk_fused so the sketch rides in the last CW flush.
BGI early-stop is fss_point_early_stop; Poplar checkpoints are
level_walk_prefixes; DCF block_width sizes are level_walk_sized.
Doerner–Shelat is level_walk_ds / level_walk_ds_sized (OH AND-layers
match ds_oh_exchanges_per_level); adaptive idpf_agg is staged
step_adaptive_prefix → drive tail (from_exchange_wave) →
retain_adaptive_prefix; keyword PIR buckets are multipoint_fan;
multi-lane ABY is aby_lane; prepaid SUBLEQ expands are defer_expand.
Party drivers use util::drive_composed / util::drive_composed_trio on
composer::default_plan() with u64_beaver_host or
u64_auth_beaver_host. A client/server query is client_servers
(one upload, one answer). Many instances with uneven stalls are
dpf::app::run_fleet: a worker parks instead of spinning and runs
whichever side can still submit. Cross-party reshare is reshare_with_mask;
pads are dealer_deliver; extra payloads share a round via
exchange_fuse; occupied cuckoo buckets are schedule_cuckoo_probes.
The full API and what stays outside compose are
[Protocol composition](@ref protocol_compose).
Go deeper: [trio.hpp](@ref dpf/net/trio.hpp),
[compose.hpp](@ref dpf/compose.hpp),
party/registry.hpp (in-tree).
Suggested reading order
- [First program](@ref basics), then this tour if you want the map in prose.
- [Capabilities](@ref capabilities) for key features; [Network, parties, and MPC](@ref network_and_mpc) for the runtime; [Logging, statistics, and experiments](@ref experiment_costs) for the run log and CSV costs.
- [Domains](@ref input_types) and [Payloads](@ref output_types).
- [Evaluation](@ref evaluation) and the [code examples](@ref listings).
- [Application sketches](@ref applications).
\htmlonly