Paper 2022/1060
Programmable Distributed Point Functions
Abstract
A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret unit vector across two or more parties. Despite growing ubiquity within applications and notable research efforts, the best 2-party DPF construction to date remains the tree-based construction from (Boyle et al, CCS'16), with no significantly new approaches since. We present a new framework for 2-party DPF construction, which applies in the setting of feasible (polynomial-size) domains. This captures in particular all DPF applications in which the keys are expanded to the full domain. Our approach is motivated by a strengthened notion we put forth, of programmable DPF (PDPF): in which a short, input-independent "offline" key can be reused for sharing many point functions. * PDPF from OWF: We construct a PDPF for feasible domains from the minimal assumption that one-way functions exist, where the second "online" key size is polylogarithmic in the domain size $N$. Our approach offers multiple new efficiency features and applications: * Privately puncturable PRFs: Our PDPF gives the first OWF-based privately puncturable PRFs (for feasible domains) with sublinear keys. * $O(1)$-round distributed DPF Gen: We obtain a (standard) DPF with polylog-size keys that admits an analog of Doerner-shelat (CCS'17) distributed key generation, requiring only $O(1)$ rounds (versus $\log N$). * PCG with 1 short key: Compressing useful correlations for secure computation, where one key is of minimal size. This provides up to exponential communication savings in some application scenarios.
Note: Corrections were made to Lemma 1, Theorem 4, Theorem 6, Lemma 3, and Lemma 6.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- Distributed Point FunctionPuncturable Pseudorandom Function
- Contact author(s)
-
elette boyle @ idc ac il
gilboan @ bgu ac il
yuvali @ cs technion ac il
tkolobov @ cs technion ac il - History
- 2023-05-17: revised
- 2022-08-15: received
- See all versions
- Short URL
- https://ia.cr/2022/1060
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1060, author = {Elette Boyle and Niv Gilboa and Yuval Ishai and Victor I. Kolobov}, title = {Programmable Distributed Point Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1060}, year = {2022}, url = {https://eprint.iacr.org/2022/1060} }