An arXiv version 1 preprint dated 25 Aug 2026 puts forward a generic route from weak pseudorandom functions, or WPRFs, to strong pseudorandom functions without asymptotic depth loss. Its main proposition says that a WPRF computable at depth d(lambda) = Omega(log lambda) yields a strong PRF at depth O(d(lambda)); WPRFs in NC1 yield PRFs in NC1. The paper analyzes efficient ensembles of keyed function families.
The target is analyzed in a non-uniform Boolean circuit model with bounded-fan-in AND, OR and NOT gates. The paper asks whether the weak-to-strong upgrade can remain generic while keeping evaluation circuits in the same asymptotic depth scale. Its NC1 claims are statements about that circuit model and depth analysis.
The tapering idea
The construction, called Tapering-GGM, shrinks its internal state geometrically as it moves down a tree. That tapering reduces the depth of later WPRF calls, the mechanism used to preserve the overall asymptotic depth. The security proof uses computational WPRF security above a shattering layer and key-uniformity below it.
Key-uniformization is another moving part. A depth-d WPRF can be converted into a depth-(d + 1) key-uniform WPRF, according to the paper. After the shattering step, m independent XOR copies reduce the bad-event probability to 2^-m. Together, those steps form the construction's shallow-circuit security argument.
A route through LWE
For the LWE route, the paper analyzes a rounded Gaussian sampler. If log q = O(kappa), it gives the sampler Boolean-circuit depth O(poly(log kappa)). Under the separate condition log q = o(kappa), it says the sampler lies within statistical distance 2^-Omega(kappa) of the rounded Gaussian distribution it targets. Those are different conditions for depth and accuracy, an important detail in reading the asymptotic result.
The LWE-based family G_lambda is stated to have depth O(log n + tau * (poly(log kappa) + log log q)) = O(log lambda). Theorem 4 states that, if the LWE assumption holds, G is a secure WPRF. The generic upgrade then gives the paper's NC1 PRF claim when LWE_alpha holds for alpha(n) = 1/n^epsilon for some epsilon >= 0.
LPN, CDH and GapSVP
The same framework is used to state results under other assumptions. For LPN, the paper claims NC1 PRFs when the noise probability is mu(n) = n^-epsilon for some epsilon >= 0, using a cited prior NC1 WPRF construction. For CDH, it claims NC1 PRFs through synthesizers and the generic transformation.
A further claim links the framework to GapSVP. The paper says NC1 PRFs follow if GapSVP is hard to approximate within the factor written as O-tilde(n^(1 + epsilon)) for any epsilon >= 0. This conclusion depends on the stated worst-case-to-average-case reduction, while the LPN and CDH routes depend on the prior constructions they cite.
What the bounds mean
The results should be read as conditional existence claims. They do not establish that LWE, LPN, CDH or the stated GapSVP hardness condition is true; they state what can be built if the assumptions and reductions are valid. The reported bounds are asymptotic, including O(d(lambda)) for the generic upgrade, O(poly(log kappa)) for sampler depth and O(log lambda) for the LWE chain. The paper therefore establishes a route and proof framework, while the concrete circuit cost remains unspecified by these asymptotic statements.
Paper data and sources
Original title: Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$, Generically)
Authors: Youlong Ding, Aayush Jain, Ilan Komargodski
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text