Information-Theoretic Distributed Point Functions with Shorter Keys
For researchers in cryptography and distributed computing, this work improves the efficiency of ITDPFs, which are fundamental primitives for applications like private information retrieval and secure computation.
This paper constructs a perfectly secure 1-private information-theoretic distributed point function (ITDPF) with output group Z_p for any prime p, achieving asymptotically shorter secret keys compared to existing schemes.
A t-private n-server Information-Theoretic Distributed Point Function ((t,n)-ITDPF) allows one to convert any point function f_{alpha,beta}(x): [N] -> G into n shares (secret keys), such that each server can compute an additive share of f_{alpha,beta}(x) with a key while any <= t servers learn absolutely no information about the function. This paper constructs a novel share conversion based on the private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025) and proposes a perfectly secure 1-private ITDPF with output group G = Z_p, where p can be any prime. Compared with the existing perfectly secure ITDPFs for the same output group, the proposed ITDPF is more efficient with asymptotically shorter secret keys.