Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

A Nonstandard Variant of Learning with Rounding with Polynomial Modulus and Unbounded Samples

Hart William Montgomery

Published Jan 1, 2018• 5 citations
Publisher
DOI
10.1007/978-3-319-79063-3_15

Related papers

On the Hardness of Learning with Rounding over Small Modulus

Andrej Bogdanov, Siyao Guo, Daniel Masny +2 more

Lecture notes in computer science•Dec 18, 2015•114 citations

Learning with Rounding, Revisited - New Reduction, Properties and Applications.

Joël Alwen, Stephan Krenn, Krzysztof Pietrzak +1 more

Abstract. The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen [BPR12] at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem of [BPR12] and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a “lossy mode ” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient minentropy, and very simple new constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. [GKPV10] from ICS ’10, which implicitly showed the existence of a “lossy mode ” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.

International Cryptology Conference•Jan 1, 2013•59 citations

Direct Reduction for Learning with Rounding and its Applications

Leyou Zhang, Zhuang Shan, Qing Wu +1 more

•Jan 1, 2024•0 citations

Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices

Chen Qian

Can deterministic information loss yield post-quantum pseudorandomness with $TC^0$ evaluation? We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. The proof uses source-independent affine transport: public affine maps sampled independently of the hidden errors transport the Gaussian error law close to uniform on the rounding map's zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $TC^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also prove hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.

arXiv:2611.05136•Nov 3, 2026•0 citations

Designs for practical SHE schemes based on Ring-LWR

Madalina Bolboceanu, Anamaria Costache, Erin Hales +3 more

The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key.

IACR Communications in Cryptology•Apr 8, 2025•3 citations

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

quant-pharXiv:2609.01448•Sep 2, 2026•3 citations
Abstract. The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen [BPR12] at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem of [BPR12] and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a “lossy mode ” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient minentropy, and very simple new constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. [GKPV10] from ICS ’10, which implicitly showed the existence of a “lossy mode ” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.
Information Loss Is All You Need: TC0TC^0TC0 Pseudorandomness from Worst-Case Lattices
Can deterministic information loss yield post-quantum pseudorandomness with TC0TC^0TC0 evaluation? We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor O~(q)\widetilde{O}(q)O(q), where qqq is the modulus. The proof uses source-independent affine transport: public affine maps sampled independently of the hidden errors transport the Gaussian error law close to uniform on the rounding map's zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in TC0TC^0TC0, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also prove hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.
The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[log⁡log⁡]\mathsf{QNC}^0[\log\log]QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0\mathsf{QAC}^0QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.