libdpf/doc/pages/multipoint.md

# Multipoint keys {#multipoint_keys}

\htmlonly
<div class="eli5"><b>ELI5.</b> Cuckoo hashing puts each secret point in one of a few buckets, with three hash functions and one point key per bucket. A query probes its three candidate buckets. Key size is linear in the number of points. The S&amp;P 2025 PCG packing, which would derive those buckets from one seed, is not implemented.</div>
\endhtmlonly

`make_multipoint(alphas, betas)` packs many secret points into cuckoo
buckets (de Castro–Polychroniadou, EUROCRYPT 2022, §4 / [ePrint 2021/580](@ref bib_vdpf)):
`κ = 3` hashes, one point key per bucket. The bucket count is linear in
the number of points `m`, so the keys are `Θ(m n λ)` bits. Eval probes
three buckets.

Pass `dpf::verifiable{}` for one batched proof token over the whole set.
Three-evaluator packing is `make_multipoint3`.

```cpp
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),
[dpf3_multipoint.hpp](@ref dpf/dpf3_multipoint.hpp),
[F_MPDPF](@ref multipoint.hpp).