Paper 2023/028

Information-Theoretic 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) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority. We present the first statistically private 3-server DPF for domain size $N$ with subpolynomial key size $N^{o(1)}$. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ITC 2022
Information-theoretic cryptographyhomomorphic secret sharingprivate information retrieval
Contact author(s)
elette boyle @ idc ac il
gilboan @ bgu ac il
yuvali @ cs technion ac il
tkolobov @ cs technion ac il
2023-01-09: approved
2023-01-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Niv Gilboa and Yuval Ishai and Victor I. Kolobov},
      title = {Information-Theoretic Distributed Point Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/028},
      year = {2023},
      doi = {10.4230/LIPIcs.ITC.2022.17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.