[Resource Topic] 2023/625: Efficient Information-Theoretic Distributed Point Function with General Output Groups

Welcome to the resource topic for 2023/625

Efficient Information-Theoretic Distributed Point Function with General Output Groups

Authors: Junru Li, Pengzhen Ke, Liang Feng Zhang


An n-server information-theoretic \textit{Distributed Point Function} (DPF) allows a client to secret-share a point function f_{\alpha,\beta}(x) with domain [N] and output group \mathbb{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_{\alpha,\beta}(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 share conversions from Efremenko’s PIR and Dvir-Gopi PIR, we obtain both an 8-server DPF with key size O(2^{10\sqrt{\log N\log\log N}}+\log p) and output group \mathbb{Z}_p and a 4-server DPF with key size O(\tau \cdot 2^{6\sqrt{\log N\log\log N}}) and output group \mathbb{Z}_{2^\tau}. 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 PIR, how to reduce the number of servers by resorting to statistical security or using nice integers, and how to obtain DPFs with t-security. We show the applications of the new DPFs by constructing new efficient PIR protocols with result verification.

ePrint: https://eprint.iacr.org/2023/625

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .