Paper 2025/2294

Fully Distributed Multi-Point Functions for PCGs and Beyond

Abstract

We give fully distributed multi-point function (DMPF) constructions that share a sparse map over a domain of size $N$. Setup takes secret-shared indices; each later expansion takes new payloads for those indices and returns shares of the map. Our main construction, Waterfall Cuckoo, samples public hashes before assigning the inputs to bins. An occupancy scan followed by bounded repair finds the assignment; a hidden permutation conceals it during routing. Sparse DPFs then provide $4N$ or $3N$ leaf work per expansion, replacing the $tN$ work of $t$ independent DPFs. We prove correctness and semi-honest simulation in the ideal-subprotocol model, with an explicit routing-error bound. For the random sparse supports in Ring-LPN PCGs, we also give Reverse Cuckoo, a $2N$-expansion specialization. It programs hashes around a hidden placement and leaks information about the support: in the ideal hash model, outputs are weighted by their number of valid placements. We characterize the idealized leakage, state the additional decisional Ring-LPN assumption, and evaluate leakage-aware decoding attacks. A separate analysis bounds the concrete hash evaluator's batch correctness error below $2^{-40}$ at ring degree $2^{20}$ with the support-rejection filter specified in the analysis. Our measurements use a variant of this specialized Reverse-Cuckoo pipeline without support rejection or AES rekeying, and with different mask, permutation, and evaluator-seed sampling rules. At degree $2^{20}$ it produces 1.81 million Goldilocks-field OLEs per second, with 12.99 MB communicated per expansion. Against the reported FHE baseline at the same field and degree, these figures give $6.57\times$ higher throughput and $13.60\times$ lower expansion communication. Setup costs and comparisons with the sum-of-DPFs baseline are reported separately. Waterfall's costs are modeled; gains for other fields, rings, and PCG constructions remain application-dependent.

Note: Fixes issue with Rev Cuckoo DMPF, introduced refined schemes.