Chen Qian of Shandong University has introduced the Learning with Algebraic Rounding (LAR) assumption, a new approach to achieving post-quantum pseudorandomness through deterministic rounding. The work demonstrates that this method can achieve security with fixed polynomial parameters, removing a key limitation of previous (LWR) techniques that required parameters tailored to a predetermined sample bound.

LAR bases its security on the hardness of established lattice problems, GapSVP and SIVP, at approximation factor O(q), where q is the modulus. This establishes a quantifiable security basis for the new method and offers “the first post-quantum weak pseudorandom function with joint key-and-input evaluation in TC^0.”

Learning with Algebraic Rounding (LAR) Introduction

The core of LAR lies in its algebraic rounding function, denoted $A R_{T}$ , which takes an input vector x from $Z^{d}$ , performs element-wise division and flooring operations modulo q, and outputs a rounded vector in $Z^{d}$ . This process inherently introduces deterministic information loss, but the work demonstrates this loss is sufficient for post-quantum pseudorandomness under specific conditions. Specifically, the rounded output determines a coset in Z^d/L(T), where L(T) represents a lattice, and Smith coordinates encode this coset as a label in $F_{q}$ ^ℓ, a finite field.

This encoding ensures that changes to the input only affect the label through the lattice structure, preserving indistinguishability. The researchers built a classical reduction from Gaussian LWE, and combined it with the quantum worst-case reduction to LWE, to establish this foundation. This means every fiber point has a probability of | $F_{g, 0}$ |^(-1), further solidifying the method’s security profile.

Lattice Hardness Foundations: GapSVP and SIVP

This connection to well-studied cryptographic primitives provides a quantifiable security basis for LAR, moving beyond reliance on ad-hoc assumptions. The reduction linking LAR to these lattice problems proceeds through a chain of transformations, beginning with a quantum reduction from Gaussian Learning with Errors (LWE).

This establishes a connection between worst-case lattice hardness and the security of LAR, meaning that if solving GapSVP or SIVP becomes feasible in quantum time, so too does breaking the decisional version of LAR. The classical portion of the reduction then demonstrates that distinguishing between uniform and random labels in LAR is equivalent to solving a uniform-zero-fiber LWE problem, further solidifying the method’s security foundation.

The researchers demonstrate that a uniform quantum polynomial-time distinguisher for decisional LAR would also yield uniform quantum polynomial-time algorithms for worst-case GapSVPγ and SIVPγ in dimension N. “Consequently, quantum worst-case hardness that excludes such solvers succeeding on infinitely many dimensions implies decisional LAR hardness against uniform QPT distinguishers for every polynomial classical sample count,” the paper states. This means the security holds even when considering an infinite number of security parameters, offering a robust foundation for cryptography. The work’s reliance on GapSVPγ and SIVPγ, where γ represents the approximation gap, highlights the importance of these problems in securing future communication systems.

Deterministic Rounding vs. Learning with Errors (LWE)

This advancement addresses a key challenge in lattice-based cryptography, allowing for fixed polynomial parameters and eliminating the need to predefine the size of the sample used in calculations. The approach hinges on transporting Gaussian errors to a distribution that rounding can absorb exactly, preserving exactly uniform public inputs during the process. This connection is demonstrated through a reduction chain involving GapSVP and SIVP, two established and difficult lattice problems.

“The separation is computational: exhaustive search identifies the secret from O(N) examples at fixed confidence,” the researchers state, highlighting the method’s resistance to brute-force attacks. This research distinguishes itself from earlier work by focusing on exactly uniform inputs and deterministic evaluation with a worst-case lattice foundation. Naor and Reingold previously explored algebraic constructions based on factoring and the decisional Diffie-Hellman assumption, but these were vulnerable to quantum algorithms.

The current work bypasses these limitations, offering a more robust and efficient approach to post-quantum cryptography. The reduction chain begins with a quantum worst-case lattice foundation and concludes with consequences for classical random-example access, further solidifying the security of the LAR assumption.

TC^0 Evaluation and Post-Quantum Pseudorandomness

This contrasts with earlier approaches that necessitated adjustments based on anticipated sample sizes, increasing complexity and potential vulnerabilities. This robustness is achieved under the condition of quantum worst-case lattice hardness, linking the security of LAR to well-studied cryptographic problems. Proposition 10. 2 from the research details that the resulting bounded implementation achieves post-quantum weak pseudorandomness against uniform quantum polynomial-time (QPT) random-example distinguishers, receiving a polynomial number of classical examples.

The evaluation circuit itself relies on a fixed sequence of arithmetic stages: inner products, coordinatewise floors and the quotient sum. The research demonstrates consequences beyond pseudorandomness, extending to the learning of polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners. “The normalized labels also have polynomial-size two-hidden-layer ReLU representations on a uniform finite grid, with rational weights and biases of polynomially bounded magnitude and bit length,” the paper states, highlighting the connection between algebraic rounding and neural network learning.

This connection is significant because it suggests potential applications in areas beyond cryptography, such as machine learning security and robustness. The findings represent a step toward more efficient and secure post-quantum cryptographic systems, relying on deterministic rounding rather than random noise, and offering a quantifiable security basis.

Source-Independent Affine Transport Framework

An affine transport framework allows for a reduction of Gaussian Learning with Errors (LWE) to uniform-zero-fiber LWE, establishing a pathway toward more efficient cryptography. This framework uses public affine maps, sampled independently of hidden errors, to move the Gaussian error law closer to a uniform distribution on the rounding map’s zero-label fiber while maintaining exactly uniform public matrices. A polynomial-time sampler for the same public parameter family is provided for every fixed inverse-polynomial accuracy, streamlining the process.

The algebraic reduction from uniform-zero-fiber LWE to decisional LAR relies on this source-independent affine transport, which sends Gaussian errors close to uniform on the fiber using only public randomness. The linear part of the transformation always remains invertible modulo q, ensuring the public matrix stays exactly uniform and independent of the transported error. The framework requires a positive, source-independent law for the public randomness so that the joint endpoint law, averaged over both the public choices and the source, is close to uniform on $H_{0}$ .

Weak Pseudorandom Functions and Keyed Families

This finding extends beyond traditional cryptographic assumptions and explores the limits of deterministic information loss in achieving post-quantum security. The research specifically addresses whether deterministic information loss alone can yield pseudorandomness evaluated with $T C^{0}$ circuits, a computationally simple class of circuits. Previous methods for constructing weak pseudorandom functions (weak PRFs) often relied on pseudorandom generators or required a polynomial modulus-to-noise ratio, limiting their practicality.

This work presents a direct field-valued construction with fixed polynomial parameters, supporting any polynomial random-example budget. The reduction employed changes the target to quotient-valued block rounding, using a source-independent randomized affine transport and sharing randomness across the sample table.

The team’s reduction differs from prior work by choosing the transport accuracy after the adversary’s sample and advantage bounds, enabling support for every polynomial sample count within a fixed public family. “Weak PRFs with low-complexity evaluation also give hardness of noise-free learning from uniform random examples,” the paper states, highlighting the link between pseudorandomness and the difficulty of learning from limited data.

This connection suggests that an efficient learner capable of predicting labels with a nonnegligible advantage would be able to distinguish pseudorandom labels from independent uniform ones, further solidifying the cryptographic implications of this research. The work builds on the foundation laid by Goldreich, Goldwasser and Micali, whose initial constructions of PRFs relied on pseudorandom generators and one-way functions.

Polynomial-Modulus LWR Hardness Challenges

This advancement circumvents restrictions established by Newton and Richelson regarding polynomial-modulus LWR hardness, demonstrating that such hardness isn’t universally impossible despite those earlier limitations. The work establishes a path toward constructing cryptographic systems with fixed polynomial parameters, simplifying implementation and potentially improving efficiency. The researchers decompose each input into its encoded label and a residual within the zero fiber, using the balanced-fiber property to ensure each point has a probability of $q^{- r}$ under a uniform distribution.

A reduction chain connects these lattice problems to Gaussian LWE, uniform-zero-fiber LWE and finally to decisional LAR, establishing a firm foundation for its security claims. This connection is formalized as GapSVPγ, SIVPγ ≤quantum Gaussian LWE ≤classical uniform-zero-fiber LWE ≤classical dLAR, demonstrating that worst-case lattice hardness directly implies decisional LAR hardness. The classical transformations within this chain are QPT on classical sample tables.

Hardness of Learning ReLU Networks from Uniform Data

Establishing the hardness of learning ReLU networks from uniform data, the work demonstrates that polynomial-size two-hidden-layer networks present a challenge even for quantum learners. This finding extends to improper learners operating in polynomial time, meaning those that may not perfectly classify all examples but still achieve a significant advantage over random guessing. The research establishes a quantifiable security basis for a new method, linking it to established lattice problems and offering a path toward post-quantum cryptographic systems.

The team’s approach builds on the concept of deterministic rounding, replacing the random noise traditionally used in methods like Learning with Errors (LWE). The researchers demonstrate that restricting the secret to nonzero keys yields a field-valued weak pseudorandom function with joint key-and-input $T C^{0}$ evaluation.

This connection to established lattice problems provides a concrete foundation for the method’s security, and the work rules out the possibility of a quantum polynomial-time improper learner successfully distinguishing the labels from random noise. The paper further notes that exhaustive search can identify the secret from O(N) classical examples at fixed confidence, but this requires computationally inefficient methods.

Cryptographic Hardness and Distribution-Free Learning

The hardness of learning intersections of halfspaces now connects to worst-case lattice problems, establishing a link between computational complexity and cryptographic security. This connection bypasses the need for a learner to succeed across every input distribution, focusing instead on a separation that preserves the prescribed input law, a distinction highlighted by Kharitonov’s work on cryptographic hardness under uniform inputs. This approach allows for a more focused assessment of security guarantees, particularly in the context of improper learning where hypotheses may fall outside the target class.

For one fixed family with polynomially bounded modulus and dimensions, its deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. These guarantees extend to uniform quantum polynomial-time learners accessing classical noiseless random examples, with hypotheses evaluated by efficient deterministic classical circuits. The resulting weak pseudorandom function, evaluated with $T C^{0}$ complexity, is grounded in the quantum worst-case hardness of lattice problems.

👉 More information
🗞 Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices
✍️ Chen Qian
🧠 ArXiv: https://arxiv.org/abs/2611.05136

More like this