Paper 2022/1060

Programmable Distributed Point Functions

Elette Boyle, Interdisciplinary Center Herzliya, NTT Research
Niv Gilboa, Ben-Gurion University of the Negev
Yuval Ishai, Technion – Israel Institute of Technology
Victor I. Kolobov, Technion – Israel Institute of Technology

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
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
2023-05-17: revised
2022-08-15: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.