Paper 2023/028
Information-Theoretic Distributed Point Functions
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
-
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},
url = {https://eprint.iacr.org/2023/028}
}
