PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Youlong Ding, Aayush Jain, Ilan Komargodski

arXiv:2608.25213v1cs.CC

TL;DR

Low-depth PRF constructions have been limited by the sequential depth of generic transformations and by assumptions stronger or more structured than desired. The paper introduces a tapering GGM-style transformation and depth-efficient WPRFs, yielding NC1 PRFs from LWE, standard LPN, and CDH. The results include polynomial-ratio LWE, standard LPN, and CDH-based constructions.

  • Problem

    Generic GGM-style transformations are sequential, while few NC1 PRFs were known from standard or well-studied assumptions.

  • Method

    The paper combines a tapering GGM-style weak-to-strong transformation with new and existing low-depth WPRF constructions.

  • Results

    The paper obtains NC1 PRFs from LWE with polynomial modulus-to-noise ratio, standard LPN, and CDH.

  • Takeaways & Limitations

    WPRFs in NC1 can be generically upgraded to PRFs in NC1, enabling new NC1 constructions under several classical assumptions.

  • Takeaways & Limitations

    The security proof requires a left-monotonicity condition for extending non-adaptive security to adaptive adversaries, and naive hybrids would require quasi-polynomial security.

Abstract

from arXiv · show

We present a new generic transformation from weak PRFs computable in depth $d(n) = Ω(\log n)$ to strong PRFs computable in depth $O(d(n))$. This construction refines the classical tree-based paradigm of GGM by {tapering} the internal state so the per-level depth decreases geometrically. We complement the above with new depth-efficient weak PRF constructions based on various standard assumptions. As a corollary, we obtain new $\mathsf{NC}^1$-computable PRFs from various classical assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2)from the standard \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS '97, J. ACM '04].

1 Introduction

The paper develops a depth-preserving generic transformation from weak PRFs to strong PRFs and instantiates it to obtain NC1 PRFs from several standard assumptions. These results improve prior constructions based on stronger or more structured assumptions.

  • Generic transformation: The transformation upgrades WPRFs of depth d(λ) = Ω(log λ) to strong PRFs of depth O(d(λ)), preserving NC1 computability.It is a black-box adaptation of GGM-style bootstrapping.
  • LWE: The construction yields new NC1 PRFs from standard LWE with polynomial modulus-to-noise ratio α = n^ε for any ε > 0.Prior NC1 constructions used Ring-LWE with a super-polynomial ratio.
  • LPN: The paper obtains the first NC1 PRFs from standard LPN with arbitrary inverse polynomial noise probability.This uses a recent NC1 WPRF construction from standard LPN.
  • CDH: The framework produces the first NC1 PRFs from CDH, improving on prior work based on DDH or generalized Diffie–Hellman assumptions.The instantiation uses a synthesizer constructed from CDH.
  • Existing candidates: Existing logarithmic-depth WPRF candidates can be upgraded to logarithmic-depth PRFs under the same underlying assumptions.The transformation also applies to synthesizers, which are weaker than WPRFs.

2 Overview of Techniques

The paper fine-tunes GGM by tapering internal state sizes, yielding a depth-preserving weak-to-strong PRF transformation, and combines it with low-depth constructions from standard assumptions.

  • Depth-preserving transformation: The transformation upgrades weak PRFs of depth d(λ) = Ω(log λ) to strong PRFs of depth O(d(λ)).It is a black-box adaptation of GGM and related bootstrapping techniques.
  • Depth-preserving transformation: The construction avoids the sequential depth of vanilla GGM, whose baseline exceeds NC1 even when the WPRF depth is Θ(log λ).Vanilla GGM additionally incurs Θ(log λ) depth for selecting relevant chunks at each level.
  • Depth-preserving transformation: Tapering shrinks the WPRF key and state sizes geometrically across GGM levels, reducing the per-level evaluation depth.The state length decreases from λ(i) to λ(i+1) at each step.
  • Security proof: Security is established by hashing queries so that sufficiently long prefixes are distinct, then using key-uniform WPRFs to propagate pseudorandomness to final outputs.Pairwise-independent hashing makes prefixes distinct with probability 1 − O(q^2/λ^i*), while unbiased transformations preserve uniformity.
  • Instantiation framework: The approach applies more generally to synthesizers because the WPRF input pool is included in the key and hidden from the adversary.Standard domain-extension and non-adaptive-to-adaptive transformations preserve depth.
  • Instantiation framework: For LWE, the paper combines chaining with a sublog-depth rounded-Gaussian sampler to obtain WPRFs in NC1 under polynomial noise-to-modulus ratios.The sampler uses Box–Muller to approximate a continuous Gaussian, then rounds modulo q.

3 Preliminaries

The preliminaries define the circuit model, pseudorandomness notions, statistical terminology, and closure operations used throughout the paper.

  • Circuit model: Function families are evaluated by non-uniform bounded-fan-in Boolean circuits with AND, OR, and NOT gates.A family has size s and depth d when every keyed function has a circuit within those bounds.
  • Security notions: The notation defines indistinguishability by query, time, and advantage bounds, with q = 0 for experiments that provide samples without oracle access.The triangle inequality adds distinguishing advantages across hybrid steps.
  • Security notions: Strong pseudorandomness gives an adversary adaptive oracle access, whereas weak pseudorandomness gives only random input-output samples.The strong experiment compares a keyed function with a random function; the weak experiment compares sampled pairs with independent uniform outputs.
  • Hashing: n-wise independent hashing means that outputs on up to n distinct inputs are independent and uniform, making collisions unlikely under 2-wise independence.The collision bound follows from pairwise independence and a union bound over input pairs.
  • Closure properties: XOR sums preserve pseudorandomness when one independent summand is pseudorandom, while products concatenate outputs with a linear security loss.Output restriction preserves pseudorandomness, and range extension increases output length through products.
  • Auxiliary definitions: Negligible functions eventually fall below every inverse polynomial, and almost-randomness implies strong pseudorandomness.The latter implication holds against any adversary making at most q queries.

4 Tapering-GGM: A Generic Construction

The construction tapers a GGM-style tree by geometrically shrinking internal states, preserving depth while using key-uniformity to complete the security argument.

  • Construction: The tapering tree shrinks the state length at every level, causing subsequent WPRF calls to have decreasing depth.The construction uses geometrically decreasing state lengths and multiple independent trees whose outputs are XORed.
  • Security: Key-uniform WPRFs make each fixed-input output uniform under a uniformly sampled key, providing information-theoretic uniformity after query shattering.Key-uniformity is defined as 1-wise independence for every fixed input.
  • Key-uniformization: A depth-d WPRF can be key-uniformized with only one additional circuit-depth layer.The construction adds a random one-time pad while preserving weak pseudorandomness and 1-wise independence.
  • Parameters: The main theorem sets m = λ, Δ = λ, ℓ = log log log λ, and λ(i) = λ2^-i+1 for the tapered construction.These parameters govern the number of trees, layers, and state lengths used in the security analysis.
  • Security: The security proof first replaces the top levels with random functions to shatter queries, then relies on key-uniformity below the shattering layer.Independent XOR copies reduce the bad-event probability to negligible 2^-m.
  • Depth: For d(λ) = Ω(log λ) with d(λ)/log λ non-decreasing, the resulting PRF has depth O(d(λ)); in particular, NC1 WPRFs yield NC1 PRFs.The depth analysis isolates the sequential tapering path and evaluates the final XOR in parallel.

5 NC1 PRFs from LWE

The LWE instantiation constructs an NC1 weak PRF using a shallow rounded-Gaussian sampler and a chaining construction, then obtains NC1 PRFs through the generic transformation.

  • Construction: The construction combines a deterministic low-depth rounded-Gaussian sampler with a Kim-style chaining construction to obtain an LWE-based WPRF.The sampler is designed to be accurate for the LWE reduction while remaining shallow enough for the final WPRF.
  • Gaussian sampling: The finite-precision Box–Muller pipeline approximates ln, cos, and √· before scaling and rounding the resulting Gaussian.Newton iteration computes the square root, while polynomial approximations handle logarithm and cosine.
  • Sampler: For log q = O(κ), the rounded-Gaussian sampler has Boolean-circuit depth O(poly(log κ)).The sampler manipulates fixed-point values and chooses truncation errors exponentially small in κ.
  • WPRF construction: The chaining construction shrinks its vector length by a factor of κ at every layer until one modulus-q value remains.Each layer computes masked LWE inner products and deterministically samples fresh errors from high-order bits of the previous layer.
  • Depth: The resulting family has evaluation depth O(log n + τ · (poly(log κ) + log log q)) = O(log λ).This establishes logarithmic-depth evaluation for the LWE-based WPRF.
  • Consequences: Polynomial-modulus LWE yields NC1 WPRFs and, via the generic transformation, NC1 PRFs under the stated inverse-polynomial noise-ratio assumption.The paper also derives an NC1 PRF consequence from GapSVP under the corresponding polynomial approximation-ratio condition.

6 NC1 PRFs from LPN

The LPN instantiation combines an NC1 weak PRF from standard LPN with the paper’s depth-preserving weak-to-strong transformation to obtain NC1 PRFs.

  • Construction: The section combines the Ding–Jain–Komargodski NC1 WPRF construction from standard LPN with the generic weak-to-strong transformation.The transformation preserves the relevant circuit-depth class.
  • Assumption: The LPN assumption compares noisy linear samples with uniformly random samples over the binary field.Noise is drawn from a Bernoulli distribution with parameter μ.
  • Weak PRFs: If μ(n) = n^-ε for some ε ≥ 0, then standard LPN implies the existence of WPRFs in NC1.The cited theorem applies for arbitrary inverse-polynomial noise probability of this form.
  • Strong PRFs: Under the same inverse-polynomial-noise condition, the paper obtains PRFs in NC1 from standard LPN.The proof applies the depth-preserving transformation to the NC1 WPRFs supplied by the LPN theorem.

7 NC1 PRFs from CDH

The construction obtains NC1 PRFs from CDH by recognizing that its generic transformation only needs hidden-input pseudorandomness, captured by synthesizers. Since CDH yields NC1 synthesizers, the transformation gives NC1 PRFs.

  • Hidden-input security: The generic transformation uses a primitive weaker than a WPRF because its random input pool is sampled in the PRF key and never revealed.The proof uses the underlying family only on outputs evaluated at hidden random inputs.
  • Synthesizers: Synthesizers formalize pseudorandomness when adversaries receive outputs on shared hidden random inputs across many independently sampled keys.They are defined analogously to WPRFs, but replace ordinary weak pseudorandomness with hidden-input pseudorandomness.
  • Synthesizers: Every WPRF is a synthesizer, but the converse need not hold because hiding inputs can preserve pseudorandomness when standard WPRF security fails.A one-time-pad transformation can also make a synthesizer key-uniform.
  • Generic transformation: For any d(λ) = Ω(log λ), synthesizers computable in depth d(λ) yield PRFs computable in depth O(d(λ)).In particular, NC1 synthesizers yield NC1 PRFs.
  • CDH instantiation: NC1 synthesizers from the Computational Diffie–Hellman assumption therefore imply PRFs in NC1 under CDH.The paper instantiates the transformation with the classical Naor–Reingold synthesizer construction.

A.1 Proof of Lemma 6

The proof shows that XOR-combining n independent almost-random function components preserves almost-randomness while multiplying the error parameter by n.

  • Lemma statement: If F is (q, ϵ)-almost-random, then F^⊕n is (q, ϵn)-almost-random.The statement applies for every n ∈ N.
  • Construction: The combined family samples n independent random and auxiliary components and XORs their corresponding function outputs.Independence lets the construction represent the combined family as F_{r1,aux1} ⊕ ··· ⊕ F_{rn,auxn}.
  • Bad-set analysis: The combined bad set consists of inputs and auxiliary tuples for which every component lies in the original bad set.Left-monotonicity transfers from the original bad set to the combined one.
  • Uniformity argument: For any auxiliary tuple outside the combined bad set, at least one component is almost uniform on the queried inputs.XOR with the remaining independent components then produces a uniform output distribution.

A.2 Proof of Corollary 2

The proof establishes the generic corollary by contradiction using tapering sets: a sufficiently persistent WPRF distinguisher would contradict the assumed security framework.

  • Corollary setup: The corollary’s construction produces a PRF from a key-uniform WPRF.The proof invokes the corresponding corollary for the transformed family.
  • Conclusion: The contradiction shows that the underlying family is not a secure WPRF, completing the proof that the constructed family is a PRF.The argument combines the generic theorem with the derived security contradiction.
  • Contradiction setup: The reduction applies on an infinite broken subset B_R selected beyond a threshold where its security bound can work.The threshold is chosen so that i^{log log log i/2} exceeds i^{c_1}.
  • Tapering sets: For each i, the tapering set is T_i = {i2^{-j+1} : j ∈ [2c_1]}.These sets encode the parameter scales used in the contradiction argument.
  • Tapering sets: Each tapering set T_i intersects only finitely many other tapering sets.If j is sufficiently large relative to i, every element of T_j exceeds the largest element of T_i.
  • Contradiction: A distinguisher on every relevant tapering scale yields an infinite intersection pattern, contradicting the finite-intersection property of the tapering sets.The proof separates the cases B′ = ∅ and B′ ≠ ∅ before deriving contradiction.

A.3 Proof of Theorem 4

Theorem 4 proves that the LWE-based construction is a weak PRF by replacing its iterated randomness one round at a time and reducing distinguishability to LWE.

  • Theorem statement: Under (m, t, ϵ)-LWE, Construction 3 yields a (m, t − poly(λ), ϵ′)-WPRF.The theorem specifies the resulting adversary-size loss and advantage parameter ϵ′.
  • Conclusion: Combining the initial and adjacent hybrid lemmas proves the theorem, and therefore LWE implies that G is a secure WPRF.The construction’s intermediate values and bounded errors support the hybrid simulation.
  • Hybrid argument: The modified evaluation samples y^(i*) uniformly, while the remaining rounds follow the original construction.This creates adjacent hybrids differing at one round.
  • Hybrid argument: The proof uses hybrids H0 and H1,i* that progressively replace the construction’s round outputs with independently sampled uniform values.H0 is the real WPRF experiment, while H1,i* uses the modified function at round i*.
  • Initial transition: Lemma 22 establishes the initial hybrid transition through a coupling distribution between the real and modified evaluations.The coupling samples common inputs and a common key before producing both evaluations.
  • Adjacent transitions: Each adjacent transition is reduced to distinguishing LWE samples from uniform, with an additional statistical error bounded by m · κ^τ · 2^{-Ω(κ)}.The reduction increases circuit size by m · poly(λ).
Loading 2608.25213v1…