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>
89 lines
4.4 KiB
Markdown
89 lines
4.4 KiB
Markdown
A *point function* is a huge list of zeros with one non-zero entry.
|
||
The index of that entry is secret. The value there is secret too.
|
||
|
||
A *(2,2) distributed point function* splits that list between two parties.
|
||
Each party gets a short key.
|
||
Either key alone looks random.
|
||
When both parties evaluate at the same public input and combine their shares,
|
||
they recover the true value of the point function there.
|
||
|
||
## Point functions {#point_functions}
|
||
|
||
Write `f_{α,β}` for the function that returns `β` at `α` and `0` elsewhere.
|
||
`make_dpf(α, β)` returns keys `(k0, k1)` such that:
|
||
|
||
- `Eval(k0, x)` and `Eval(k1, x)` are shares of `f_{α,β}(x)`
|
||
- `|k_i|` is about `O(λ · log |domain|)` for security parameter `λ`
|
||
|
||
Leaf payloads use subtractive shares. Comparison payloads use additive shares.
|
||
Open with `dpf::reconstruct`.
|
||
|
||
## What you pass to `make_dpf` {#make_dpf_args}
|
||
|
||
`make_dpf(x, y, ys...)` takes the secret index and one or more payloads.
|
||
`dpf::at<N>(y)` plants `y` on the public prefix of length `N`.
|
||
`dpf::idpf_at<N...>(ys...)` plants one payload per listed prefix.
|
||
`dpf::idpf(y0, y1, ...)` is the consecutive prefixes 1, 2, ….
|
||
Read a slot with `dpf::eval_point(dpf::out<I>, key, x)`, or
|
||
`dpf::out<I, W>` when `W` is that slot's prefix.
|
||
|
||
\code{cpp}
|
||
auto [k0, k1] = dpf::make_dpf(
|
||
std::uint8_t{0x2a},
|
||
dpf::at<4>(std::uint8_t{5}),
|
||
std::uint8_t{9});
|
||
auto hi = *dpf::eval_point(dpf::out<0, 4>, k0, std::uint8_t{0x2a});
|
||
\endcode
|
||
|
||
A comparison payload is `dpf::lt`, `dpf::leq`, `dpf::gt`, or `dpf::geq`.
|
||
The same four names with `_at<N>` sit on a prefix. Evaluate that channel
|
||
with `dpf::cmp`. See [Comparisons and ranges](@ref tour_dcf).
|
||
|
||
Let `n` be the input bit length and `λ` the seed width. The key from
|
||
`make_dpf` is `Θ(n λ)` bits plus the payloads, and `eval_point` expands
|
||
`n` levels. That is the Boyle–Gilboa–Ishai CCS 2016 point key (full
|
||
version [ePrint 2018/707](@ref bib_fss2018)): one correction word per level, not their
|
||
[EUROCRYPT 2015](@ref bib_fss2015) key of `4n(λ+1)` bits. For a small output group `G`, Remark 3.4 of that full version stops
|
||
`ν = log2(λ / log2|G|)` levels early and shortens the key by `ν(λ+2)`
|
||
bits. This generator does that: the tree depth is `n` minus the log of
|
||
how many copies of `G` fit in one leaf, and those low bits select the lane.
|
||
Boyle, Gilboa, Ishai, and Kolobov ([ePrint 2023/028](@ref bib_itdpf)) give a statistically
|
||
private 3-server DPF and a perfectly private 4-server DPF;
|
||
`dpf::make_it_dpf3` is the additive three-server interface on a
|
||
`uint8_t` domain. `make_dpf` is a 2-party PRG key. Interval, sequence,
|
||
and full-domain costs are on [Evaluating DPFs](@ref evaluation).
|
||
|
||
Width literals (`100_u12`, `7_x12`, `1.5_fixed16`, `1_bit`, `2_twobit`,
|
||
`10_nyble`, `_bitstring`) are documented with the types that use them:
|
||
[Input types](@ref input_types), [Output types](@ref output_types).
|
||
|
||
**Defined in**\n
|
||
@ref dpf/dpf_key.hpp, @ref dpf/placement.hpp, @ref dpf/eval_target.hpp
|
||
|
||
## DPF Trees {#dpf_trees}
|
||
|
||
\htmlonly
|
||
<div class="eli5"><b>ELI5.</b> A key stores a root seed and one correction word per level. Expanding the seed walks the tree. On the secret path the correction forces the leaf to the programmed value; off that path the two parties' corrections cancel, so the opened value is zero.</div>
|
||
\endhtmlonly
|
||
|
||
Keys store a seed and a list of *correction words*.
|
||
Evaluation walks a binary tree from the root toward `x`.
|
||
At each level a correction word mixes the two children so only the secret
|
||
path keeps differing seeds. Off-path nodes match and cancel when the parties
|
||
combine.
|
||
|
||
Classic keys use a Boyle–Gilboa–Ishai expand (CCS 2016, full version
|
||
[ePrint 2018/707](@ref bib_fss2018)).
|
||
Half-Tree keys (CCR interior PRG) follow Guo, Yang, Wang, Zhang, Xie,
|
||
Zhang, and Liu, [ePrint 2022/1431](@ref bib_halftree): mid-level children are `H(s)` and
|
||
`H(s) XOR s`. Their dealer point key keeps the CCS 2016 length and the
|
||
`n`-hash point evaluation; they state about `2n+2` random-permutation
|
||
calls to generate a key versus about `4n`, and `1.5N` calls for a
|
||
full-domain evaluation versus `2N`. See [tree_traits.hpp](@ref dpf/tree_traits.hpp).
|
||
|
||
For a slow, friendly walk through every feature, start at the
|
||
[guided tour](@ref guided_tour).
|
||
|
||
\htmlonly
|
||
<div class="tldr"><b>TL;DR.</b> A (2,2) DPF gives each party a short key for one secret point. make_dpf builds it. Point leaves open by subtraction and comparisons by addition. The key is a seed plus one correction word per level.</div>
|
||
\endhtmlonly
|