Pseudorandom Functions with Weak Programming Privacy and Applications to Private Information Retrieval

Ashrujit Ghoshal, Mingxun Zhou, Elaine Shi, Bo Peng

TL;DR

This paper introduces a new, weaker type of "programmable" pseudorandom function (PPPRF) that can be constructed using only basic one-way functions (OWFs), a weaker assumption than previously required. This new PPPRF is then used to build more efficient Private Information Retrieval (PIR) schemes, achieving better bandwidth and space tradeoffs, particularly in the single-server setting.

What Problem Does This Paper Address?

The paper tackles the challenge of building efficient cryptographic primitives for privacy-preserving data access. Specifically, it focuses on two related areas:

  1. Privately Programmable Pseudorandom Functions (PPPRFs): These are functions that can be "programmed" to output a specific value at a chosen input, while keeping the programming point secret. Existing constructions of PPPRFs with this "programming privacy" relied on strong cryptographic assumptions like Learning with Errors (LWE) or indistinguishability obfuscation, and were often complex. The authors sought to construct PPPRFs with weaker security guarantees (specifically, $1/\textsf{poly}$ security) using only one-way functions (OWFs), which are a more fundamental cryptographic building block.
  2. Private Information Retrieval (PIR): PIR allows a client to retrieve data from a server (or multiple servers) without revealing which specific data item they are requesting. Traditional PIR schemes are inefficient. Preprocessing PIR schemes improve efficiency by allowing clients and/or servers to perform some work upfront. However, achieving efficient preprocessing PIR with minimal assumptions has been a significant challenge. Previous work showed that PPPRFs could be used to build efficient PIR, but since PPPRFs themselves required strong assumptions, this limited the applicability of those PIR schemes. The authors aimed to leverage their new OWF-based PPPRF to improve existing PIR constructions.

Methods

The paper introduces several key technical contributions:

  • Relaxed PPPRF Construction: The core technical innovation is a new construction for a "relaxed" PPPRF. This PPPRF has two main relaxations compared to standard PPPRFs:
  • Small-Domain: It's designed for input domains that are polynomial in size.
  • $1/\textsf{poly}$ Security: It has a small, polynomial probability of failure in its security guarantees. This relaxed PPPRF is built from OWFs and utilizes a "forest-based" approach, combining multiple "PPPRF trees" to achieve the desired properties. The construction involves novel techniques for handling "functional programming privacy," a stronger notion than standard programming privacy, which is crucial for their PIR applications.

  • Efficient Preprocessing PIR Schemes: Using their new relaxed PPPRF, the authors construct improved preprocessing PIR schemes for both 1-server and 2-server settings.

  • 2-Server PIR: They achieve a 2-server PIR with polylogarithmic bandwidth, improving upon prior OWF-based constructions that had higher bandwidth costs.
  • 1-Server PIR: They achieve a 1-server PIR with polylogarithmic online bandwidth and $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ offline bandwidth. This is significant because it matches the lower bounds for offline bandwidth under certain assumptions, and improves the online bandwidth.
  • Combining Client and Server Preprocessing: Notably, their work is the first to demonstrate non-trivial ways to combine client-side and server-side preprocessing techniques for PIR, leading to improved results.
  • Security Amplification: The paper also discusses how to amplify the security of their constructed PIR schemes to achieve negligible failure probability against any polynomial-time adversary, using techniques like Locally Decodable Codes (LDCs).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • OWFs are Sufficient for PPPRFs (with relaxations): The most significant insight is demonstrating that strong cryptographic primitives like LWE or iO are not strictly necessary for constructing PPPRFs. By relaxing the security definition and domain size, basic OWFs suffice, opening up new possibilities for building privacy-preserving protocols from minimal assumptions.
  • Bridging the Gap in PIR Efficiency: The paper directly addresses the efficiency bottleneck in PIR. By constructing a more efficient PPPRF from OWFs, they can then build more practical PIR schemes, especially in the single-server case where they achieve optimal bandwidth tradeoffs.
  • The Power of "Weak" Primitives: This work highlights that even "weak" versions of cryptographic primitives (like $1/\textsf{poly}$-secure PPPRFs) can be powerful enough to construct important cryptographic applications (like efficient PIR). This suggests a broader principle of exploring relaxations to achieve efficiency and minimal assumptions.
  • Synergy of Client and Server Preprocessing: The paper shows that combining client-side and server-side preprocessing, which were previously treated as separate techniques, can lead to novel and improved PIR schemes. This suggests a new direction for research in combining different preprocessing paradigms.

Key Results

  • Relaxed PPPRF from OWFs: Construction of a PPPRF with $1/\textsf{poly}$ security and polynomial domain size, relying only on OWFs.
  • 2-Server Preprocessing PIR: Achieved polylogarithmic bandwidth, $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ client/server space, and $N^{1+\epsilon}$ server space, from OWFs.
  • 1-Server Preprocessing PIR: Achieved polylogarithmic online bandwidth and $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ offline bandwidth, with $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ client space and $N^{1+\epsilon}$ server space, from OWFs. This result, combined with prior lower bounds, establishes a tight understanding of bandwidth/client space tradeoffs for 1-server PIR from Minicrypt assumptions.
  • First to Combine Client/Server Preprocessing for PIR: Demonstrated non-trivial ways to combine these two preprocessing paradigms for improved PIR results.

Limitations and Future Work

  • Relaxed Security: The constructed PPPRF and resulting PIR schemes have $1/\textsf{poly}$ security, meaning there's a small chance of failure. While this is often acceptable in practice, achieving full security from OWFs remains an open question.
  • Polynomial Domain Size: The PPPRF construction is for polynomially sized input domains. Extending this to arbitrary domain sizes while maintaining OWF-based construction would be a significant advancement.
  • Efficiency Improvements: While the paper achieves significant efficiency gains, further improvements in the polynomial factors (e.g., the $\epsilon$ in $N^{1+\epsilon}$) or the poly-logarithmic overhead are always desirable.
  • Broader Applications of Relaxed PPPRFs: The paper focuses on PIR. Exploring other applications where these new, OWF-based relaxed PPPRFs could be beneficial is a natural direction for future work.

Summary updated

Abstract

Although privately programmable pseudorandom functions (PPPRFs) are known to have numerous applications, so far, the only known constructions rely on Learning with Error (LWE) or indistinguishability obfuscation. We show how to construct a relaxed PPPRF with only one-way functions (OWF). The resulting PPPRF satisfies $1/\textsf{poly}$ security and works for polynomially sized input domains. Using the resulting PPPRF, we can get new results for preprocessing Private Information Retrieval (PIR) that improve the state of the art. Specifically, we show that relying only on OWF, we can get a 2-server preprocessing PIR with polylogarithmic bandwidth while consuming $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ client space and $N^{1+\epsilon}$ server space for an arbitrarily small constant $\epsilon \in (0, 1)$. In the 1-server setting, we get a preprocessing PIR from OWF that achieves polylogarithmic online bandwidth and $\widetilde{O}_\lambda(N^{\frac12 + \epsilon})$ offline bandwidth, while preserving the same client and server space as before. Our result, in combination with the lower bound of Ishai, Shi, and Wichs (CRYPTO'24), establishes a tight understanding of the bandwidth and client space tradeoff for 1-server preprocessing PIR from Minicrypt assumptions. Interestingly, we are also the first to show non-trivial ways to combine client-side and server-side preprocessing to get improved results for PIR.
BibTeX
@article{ghoshal2025pseudorandom,
  author = {Ashrujit Ghoshal and Mingxun Zhou and Elaine Shi and Bo Peng},
  title = {{Pseudorandom Functions with Weak Programming Privacy and Applications to Private Information Retrieval}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
  url = {https://openreview.net/forum?id=SKvYCEHvha},
}
Figure