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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ITC 2022
DOI
10.4230/LIPIcs.ITC.2022.17
Keywords
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
History
2023-01-09: approved
2023-01-09: received
See all versions
Short URL
https://ia.cr/2023/028
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/028,
      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{https://eprint.iacr.org/2023/028}},
      url = {https://eprint.iacr.org/2023/028}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.