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
Note: Corrections were made to Lemma 1, Theorem 4, Theorem 6, Lemma 3, and Lemma 6.
Metadata
- Available format(s)
-
PDF
- 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} }