💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

This paper introduces a generic transformation that converts weak PRFs into strong PRFs with minimal depth overhead, enabling the construction of $\mathsf{NC}^1$ -computable PRFs from standard assumptions including LWE, LPN, and CDH, thereby resolving long-standing open problems in low-depth cryptography.

Original authors: Youlong Ding, Aayush Jain, Ilan Komargodski

Published 2026-08-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Youlong Ding, Aayush Jain, Ilan Komargodski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, security often relies on a special kind of mathematical tool called a pseudorandom function. Imagine a machine that takes a secret code and a piece of data, then spits out a string of numbers that looks completely random to anyone watching. If the machine is working correctly, no one can tell the difference between its output and a truly random sequence, even if they have seen the machine work many times before. These tools are the invisible locks and keys that protect everything from online banking to private messages. For decades, researchers have been trying to build these machines so they run as fast as possible, specifically by making them work in very few steps. In the language of computer science, this means building them with a circuit that is very shallow, allowing the calculation to happen almost instantly on modern processors. The faster and simpler these tools are, the more efficiently they can be used in complex systems like secure voting or private data sharing.

For a long time, there was a stubborn gap in our ability to build these fast, shallow machines. We knew how to create them using very strong, complex mathematical assumptions, but those required deep, slow circuits. Conversely, we could build shallow circuits, but only if we relied on weaker, less proven assumptions or very specific, rigid mathematical structures. It was like having a key that opened a door but was too heavy to carry, or a key that was light but only fit a single, strange lock. The goal was to find a way to make a lightweight key that could open any door, using only the most standard, reliable locks available. This challenge has stood for nearly thirty years, limiting how efficiently we could secure the digital world.

A team of researchers has now bridged this gap with a new, general method that transforms a weaker, easier-to-build tool into a strong, secure one without slowing it down. Their work, published in a paper titled "Pseudorandom Functions in NC1 from LWE/LPN/CDH," demonstrates that it is possible to construct these fast, shallow machines using three of the most fundamental and widely trusted assumptions in cryptography. The researchers achieved this by refining an old idea called the GGM construction, which builds a complex function by walking through a tree of smaller calculations. The traditional way of doing this was like walking down a long hallway where every step required the same amount of effort, making the total journey long and slow. The new method changes the shape of the hallway. As the process moves deeper into the tree, the amount of work required at each step shrinks geometrically. The first few steps are heavy, but the subsequent steps become lighter and lighter, so quickly that the total effort remains small. This "tapering" technique allows the researchers to keep the entire process within the bounds of a shallow, fast circuit.

To prove this new method works, the team applied it to three specific mathematical problems that are known to be hard to solve. The first is the Learning With Errors problem, which involves finding a hidden pattern in a noisy set of data. Previous attempts to build fast machines from this problem required a specific, more complex version of the math that used very large numbers. The new work shows that the standard version, with much smaller numbers, is sufficient. The second problem is Learning Parity with Noise, which deals with finding a hidden pattern in a stream of bits that has been flipped randomly. The researchers showed that their method works with the standard version of this problem, removing the need for the specialized, structured versions that were previously required. The third problem is the Computational Diffie-Hellman assumption, a cornerstone of modern internet security used to exchange secret keys. For decades, the only known way to build fast machines from this assumption relied on a stronger, more restrictive version of the problem. The new construction proves that the standard version is enough.

The significance of this work lies in its generality and its reliance on standard assumptions. By showing that a weak, shallow tool can be upgraded to a strong, secure one without adding depth, the researchers have unlocked the ability to build fast, secure functions from the most basic and well-studied mathematical problems. This resolves several long-standing questions in the field and provides a new, flexible blueprint for future cryptographic systems. The researchers did not just suggest that this might be possible; they provided a concrete, step-by-step construction and a rigorous proof that it works. They demonstrated that the depth of the resulting machine is essentially the same as the depth of the starting tool, preserving the speed advantage while gaining the necessary security.

This achievement means that for the first time, we can build these essential security tools using the most common and trusted mathematical foundations, without sacrificing speed. It removes the need for specialized, complex variants of these problems that were previously thought to be necessary for efficiency. The result is a more robust and versatile foundation for the digital security of the future, allowing for faster and more efficient encryption methods that can be deployed across a wide range of technologies. The work stands as a definitive proof that the barrier between weak, fast tools and strong, fast tools has been broken, opening the door to a new era of efficient cryptographic design.

Technical Summary: Pseudorandom Functions in NC1 from LWE/LPN/CDH

1. Problem Statement

The construction of Pseudorandom Functions (PRFs) with low parallel complexity (specifically within the class NC1, computable by polynomial-size, logarithmic-depth circuits) has been a long-standing open problem in cryptography. While PRFs can be generically constructed from Pseudorandom Generators (PRGs) via the Goldreich-Goldwasser-Micali (GGM) transformation, this method is inherently sequential. Even if the underlying PRG is computable in logarithmic depth, the resulting PRF requires depth $\omega(\log n)$ , placing it outside NC1.

Prior to this work, known NC1-computable PRFs were scarce and relied on highly specific algebraic structures or strong assumptions:

Naor-Reingold (1997, 2004): Constructed PRFs in $TC_0 \subseteq NC1$ from Decisional Diffie-Hellman (DDH) and factoring.
Banerjee-Peikert-Rosen (2012): Constructed PRFs in $TC_0$ from Ring-LWE, but required a super-polynomial modulus-to-noise ratio.
Ding-Jain-Komargodski (2025): Constructed PRFs from structured variants of Learning Parity with Noise (LPN), such as SeededLPN or Ring-LPN.

The central challenge is to achieve NC1-computable PRFs from standard assumptions (LWE with polynomial modulus-to-noise ratio, standard LPN, and Computational Diffie-Hellman) without relying on structured variants or super-polynomial parameters.

2. Methodology

The paper introduces a two-pronged approach: a generic depth-preserving transformation from Weak PRFs (WPRFs) to strong PRFs, and new depth-efficient constructions of WPRFs (or synthesizers) from standard assumptions.

2.1 Tapering-GGM: A Generic Transformation

The authors propose a novel adaptation of the GGM tree construction, termed Tapering-GGM, which upgrades a WPRF to a strong PRF while preserving the evaluation circuit depth.

The Tapering Mechanism: In a standard GGM tree, the state size remains constant, and the depth accumulates linearly with the number of tree levels ( $\ell \cdot d_{WPRF}$ ). In Tapering-GGM, the state size shrinks geometrically at each level. If the security parameter at level $i$ is $\lambda^{(i)}$ , the authors define $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Consequently, the depth of the WPRF call at level $i$ , denoted $d(\lambda^{(i)})$ , decreases geometrically.
Depth Analysis: If the base WPRF has depth $d(\lambda) = \Theta(\log \lambda)$ , the total depth of the Tapering-GGM construction becomes:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
This geometric decay ensures the total depth remains $O(d(\lambda))$ , keeping the construction within NC1 if the input WPRF is in NC1.
Security Challenges & Solutions:
- Challenge: As the tree goes deeper, the security parameter $\lambda^{(i)}$ becomes small (sub-polynomial), potentially breaking the computational security of the underlying WPRF.
- Solution 1 (Hashing): The input is first hashed via a pairwise independent hash function. This ensures that with high probability, the adversary's queries are "shattered" (mapped to distinct paths) within the top $O(\log_\Delta q)$ levels, where the security parameter is still polynomial.
- Solution 2 (Key-Uniformity): For levels below the shattering point, the construction relies on information-theoretic security. The authors require the WPRF to be key-uniform (1-wise independent). If the state at the shattering level is pseudorandom, the subsequent composition of key-uniform transformations maps this state to a perfectly uniform output, regardless of the computational hardness of the lower-level WPRFs.

2.2 Depth-Efficient WPRF Constructions

The authors instantiate the Tapering-GGM framework with new WPRF constructions from standard assumptions:

From LWE (Learning With Errors):
- The authors construct the first NC1 WPRF from standard LWE with a polynomial modulus-to-noise ratio ( $\alpha = n^{-\epsilon}$ ).
- Key Technical Tool: A Rounded Gaussian Sampler computable in $O(\text{poly}(\log \log \lambda))$ depth. They approximate the Box-Muller transform using low-depth polynomial approximations for $\ln$ , $\cos$ , and Newton iteration for square roots.
- Construction: They employ a chaining paradigm (inspired by Kim [Kim20]). The construction computes masked LWE inner products layer by layer. The high-order bits of the output of one layer deterministically sample the error distribution for the next layer. The boundedness of the error sampler ensures stability, allowing the security proof to proceed via hybrids.
From LPN (Learning Parity with Noise):
- The authors leverage a recent result by Ding, Jain, and Komargodski [DJK25] which provides WPRFs in NC1 from standard LPN (arbitrary inverse polynomial noise).
- By combining this with Tapering-GGM, they obtain the first NC1 PRFs from standard LPN, removing the need for structured variants (e.g., Ring-LPN) required by prior works.
From CDH (Computational Diffie-Hellman):
- The authors observe that Tapering-GGM actually requires a primitive weaker than a WPRF: a Synthesizer (where the input pool is hidden from the adversary).
- They instantiate the transformation using the Naor-Reingold synthesizer construction [NR95, NR99], which is computable in NC1 under the CDH assumption. This yields the first NC1 PRFs from CDH, improving upon the previous DDH-based constructions.

3. Key Contributions

Generic Depth-Preserving Transformation: A black-box transformation that converts any WPRF (or synthesizer) computable in depth $d(\lambda) = \Omega(\log \lambda)$ into a strong PRF computable in depth $O(d(\lambda))$ . This resolves the generic barrier preventing NC1 PRFs from standard assumptions.
NC1 PRFs from Standard LWE: The first construction of PRFs in NC1 from LWE with a polynomial modulus-to-noise ratio, resolving an open problem explicitly stated in Vaikuntanathan's lecture notes. This relies on the hardness of GapSVP with polynomial approximation factors.
NC1 PRFs from Standard LPN: The first construction of PRFs in NC1 from the standard LPN assumption, eliminating the need for structured variants like Ring-LPN or Sparse LPN.
NC1 PRFs from CDH: The first construction of PRFs in NC1 from the Computational Diffie-Hellman assumption, improving upon the 30-year-old Naor-Reingold result which relied on the stronger Decisional Diffie-Hellman (DDH).
Low-Depth Gaussian Sampler: A novel deterministic circuit for sampling rounded Gaussian errors in $O(\text{poly}(\log \log \lambda))$ depth, which is a critical component for the LWE-based WPRF.

4. Results

The paper establishes the following concrete results:

Theorem: If there exist WPRFs in NC1, then there exist PRFs in NC1.
Corollary (LWE): Assuming the LWE assumption holds for noise-to-modulus ratio $\alpha = n^{-\epsilon}$ , there exist PRFs in NC1.
Corollary (LPN): Assuming the LPN assumption holds for noise probability $\mu = n^{-\epsilon}$ , there exist PRFs in NC1.
Corollary (CDH): Assuming the CDH assumption holds, there exist PRFs in NC1.
Corollary (GapSVP): Assuming GapSVP is hard to approximate within a $\tilde{O}(n^{1+\epsilon})$ factor, there exist PRFs in NC1.

5. Significance

The paper claims to resolve several long-standing open problems in the complexity of cryptographic primitives. By decoupling the depth of PRF evaluation from the sequential nature of the GGM transformation, the authors demonstrate that strong PRFs can be constructed from a wide array of standard assumptions without sacrificing parallel efficiency.

Specifically, the work:

Removes the reliance on Ring-LWE and super-polynomial parameters for NC1 PRFs, moving to standard LWE with polynomial parameters.
Removes the reliance on structured LPN variants, moving to standard LPN.
Weakens the hardness assumption for CDH-based PRFs from DDH to CDH.
Provides a generic framework (Tapering-GGM) that can upgrade any existing log-depth WPRF candidate (e.g., from [ABG+14], [AR16]) into a log-depth PRF, provided the underlying assumption holds.

The authors position this work as a fundamental step in understanding the parallel complexity of cryptography, with implications for secure computation protocols, learning theory (via PRF-versus-learning connections), and meta-complexity.