Search papers, labs, and topics across Lattice.
This paper introduces a novel information-theoretic error-detecting private information retrieval (itED-PIR) scheme built upon prime-power-order information-theoretic Distributed Point Functions (itDPFs) over rings. By moving from finite fields to prime-power rings, the proposed scheme overcomes limitations of existing APIR schemes, enabling more efficient DPF utilization and significantly reducing key sizes. The single-itDPF-key design further halves query-side communication overhead, making the scheme more practical for large-scale deployments while maintaining privacy and verifiability.
Ring-based DPFs slash key sizes and communication overhead in error-detecting private information retrieval, finally making itED-PIR practical for high-security, large-scale deployments.
Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR), using Distributed Point Functions (DPFs) for subpolynomial complexity and privacy. However, its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings, while its dual-DPF-key design introduces unnecessary communication overhead, limiting its practicality for large-scale deployments. This paper proposes a novel ring-based information-theoretic ED-PIR (itED-PIR) scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs (itDPFs). Built over a prime-power ring, the proposed scheme breaks APIR's field-induced constraint to enable more efficient DPF utilization, significantly reducing key size growth and rendering the scheme feasible for high-security scenarios. Additionally, a single-itDPF-key design halves query-side communication overhead by eliminating APIR's redundant dual-key setup, without compromising privacy or verifiability. Beyond immediate efficiency gains, this work establishes a lightweight, flexible framework for constructing DPF-based malicious-resilient private information retrieval, opening new avenues for privacy-preserving data retrieval in distributed storage systems and post-quantum privacy protocols.
