Paper 2023/625

Efficient Information-Theoretic Distributed Point Function with General Output Groups

Junru Li, ShanghaiTech University
Pengzhen Ke, ShanghaiTech University
Liang Feng Zhang, ShanghaiTech University
Abstract

An n-server information-theoretic Distributed Point Function (DPF) allows a client to secret-share a point function fα,β(x) with domain [N] and output group G among n servers such that each server learns no information about the function from its share (called a key) but can compute an additive share of fα,β(x) for any x. DPFs with small key sizes and general output groups are preferred. In this paper, we propose a new transformation from share conversions to information-theoretic DPFs. By applying it to the share conversions from Efremenko's PIR and Dvir-Gopi PIR, we obtain both an 8-server DPF with key size and output group and a 4-server DPF with key size and output group . The former allows us to partially answer an open question by Boyle, Gilboa, Ishai, and Kolobov (ITC 2022) and the latter allows us to build the first DPFs that may take any finite Abelian groups as output groups. We also discuss how to further reduce the key sizes by using different PIRs, how to reduce the number of servers by resorting to statistical security or using nice integers, and how to obtain DPFs with -security. We show the applications of the new DPFs by constructing new efficient PIR protocols with result verification.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Designs, Codes, and Cryptography
Keywords
Distributed point functionPrivate information retrieval
Contact author(s)
lijr2 @ shanghaitech edu cn
History
2025-02-15: revised
2023-05-02: received
See all versions
Short URL
https://ia.cr/2023/625
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2023/625,
      author = {Junru Li and Pengzhen Ke and Liang Feng Zhang},
      title = {Efficient Information-Theoretic Distributed Point Function with General Output Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/625},
      year = {2023},
      url = {https://eprint.iacr.org/2023/625}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.