Paper 2023/625

Efficient Information-Theoretic Distributed Point Function with General Output Groups

Abstract

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.