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

International Cryptology Conference

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

Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, Daniel Wichs

Published Jan 1, 2013• 59 citations
OpenAlex

Abstract

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.

Related papers

Revisiting LWR: A Novel Reduction Through Quantum Approximations

Zhuang Shan, Leyou Zhang, Qiqi Lai

Pseudorandom functions (PRFs) are a very important tool in cryptography, and the learning with rounding (LWR) problem is one of the main issues in their construction. LWR problem, is to find from ⌊ A s ⌋ p , where and is the rounding function. The LWR problem is considered a variant of the learning with error (LWE) problem, that is, to find s from b = A s + e , where , and LWE has been reduced to GapSVP and SIVP. The hardness of the lattice problems is the security foundation of the issued schemes. The best‐known reduction for LWR was completed using information‐theoretic entropy arguments, and the reduction requires q ≥ 2 n m p . It does not directly reduce to the closest vector problem (CVP) problem, but rather to the LWE problem. However, the reduction in the aforementioned work significantly reduces the difficulty of LWR. To more accurately characterize the hardness of LWR, this paper uses statistical approximation and a Quantum Fourier Transform to reduce LWR to the CVP, thereby ensuring the hardness of LWR. Furthermore, unlike the previous conclusions, our reduction involves minimal loss and has broad security conditions, requiring only that , where q and p are prime numbers and 0 < α < 1.

IET Information Security•Jan 1, 2025•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

Analysis of Ring-LWE and LWR Cryptographic Schemes: Foundations, Implementation, and Performance

Sandip Kanoo

Lattice-based cryptography has emerged as a leading framework for securing communication in the post-quantum era, supported by strong worst-case hardness guarantees.This study focuses on two central constructions, Ring Learning with Errors (Ring-LWE) and Learning with Rounding (LWR), and examines their mathematical foundations, implementation behavior, and performance characteristics.While Ring-LWE benefits from well-established and conservative security reductions, along with broad applicability across cryptographic primitives, its reliance on discrete Gaussian sampling introduces computational overhead and potential side-channel vulnerabilities.In contrast, LWR replaces stochastic noise with deterministic rounding, thereby simplifying implementation and improving efficiency, particularly on resource-constrained platforms, albeit under comparatively newer and less conservative hardness assumptions.Both schemes are implemented and benchmarked across multiple parameter sets, enabling a systematic comparison of key generation, encryption, and decryption costs.The experimental results highlight the complementary strengths of these approaches and suggest that hybrid constructions may effectively combine the strong theoretical guarantees of Ring-LWE with the practical efficiency of LWR.

International Journal of Applied Science and Engineering•Dec 25, 2025•0 citations

Using Learning with Rounding to Instantiate Post-Quantum Cryptographic Algorithms

Andrea Basso, Joppe W. Bos, Jan-Pieter D’Anvers +9 more

The Learning with Rounding (LWR) problem, introduced as a deterministic variant of Learning with Errors (LWE), has become a promising foundation for post-quantum cryptography. This Systematization of Knowledge (SoK) article presents a comprehensive survey of the theoretical foundations, algorithmic developments, and practical implementations of LWR-based cryptographic schemes. We introduce LWR within the broader landscape of lattice-based cryptography and post-quantum security, highlighting its advantages such as reduced randomness, improved efficiency, and enhanced side-channel resistance. We explore the evolution of security reductions from LWR to LWE, including recent advances that support practical parameter regimes and address challenges in both bounded and unbounded sample settings. This article systematically reviews existing LWR-based schemes — including Saber, Lizard, Florete, Espada, Sable, and SMAUG — analyzing their design choices, parameter sets, and performance tradeoffs. Furthermore, we examine the impact of LWR on side-channel resistance, failure probabilities, and masking efficiency, demonstrating its suitability for secure and efficient implementations. By consolidating the research spanning theory and practice, this SoK aims at guiding future cryptographic design and standardization efforts leveraging LWR.

ACM Transactions on Embedded Computing Systems•Apr 8, 2026•2 citations

Hardness of decision (R)LWE for any modulus.

Adeline Roux-Langlois, Damien Stehlé

Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.

•Jan 1, 2012•12 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
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.
Pseudorandom functions (PRFs) are a very important tool in cryptography, and the learning with rounding (LWR) problem is one of the main issues in their construction. LWR problem, is to find from ⌊ A s ⌋ p , where and is the rounding function. The LWR problem is considered a variant of the learning with error (LWE) problem, that is, to find s from b = A s + e , where , and LWE has been reduced to GapSVP and SIVP. The hardness of the lattice problems is the security foundation of the issued schemes. The best‐known reduction for LWR was completed using information‐theoretic entropy arguments, and the reduction requires q ≥ 2 n m p . It does not directly reduce to the closest vector problem (CVP) problem, but rather to the LWE problem. However, the reduction in the aforementioned work significantly reduces the difficulty of LWR. To more accurately characterize the hardness of LWR, this paper uses statistical approximation and a Quantum Fourier Transform to reduce LWR to the CVP, thereby ensuring the hardness of LWR. Furthermore, unlike the previous conclusions, our reduction involves minimal loss and has broad security conditions, requiring only that , where q and p are prime numbers and 0 < α < 1.
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.
Lattice-based cryptography has emerged as a leading framework for securing communication in the post-quantum era, supported by strong worst-case hardness guarantees.This study focuses on two central constructions, Ring Learning with Errors (Ring-LWE) and Learning with Rounding (LWR), and examines their mathematical foundations, implementation behavior, and performance characteristics.While Ring-LWE benefits from well-established and conservative security reductions, along with broad applicability across cryptographic primitives, its reliance on discrete Gaussian sampling introduces computational overhead and potential side-channel vulnerabilities.In contrast, LWR replaces stochastic noise with deterministic rounding, thereby simplifying implementation and improving efficiency, particularly on resource-constrained platforms, albeit under comparatively newer and less conservative hardness assumptions.Both schemes are implemented and benchmarked across multiple parameter sets, enabling a systematic comparison of key generation, encryption, and decryption costs.The experimental results highlight the complementary strengths of these approaches and suggest that hybrid constructions may effectively combine the strong theoretical guarantees of Ring-LWE with the practical efficiency of LWR.
The Learning with Rounding (LWR) problem, introduced as a deterministic variant of Learning with Errors (LWE), has become a promising foundation for post-quantum cryptography. This Systematization of Knowledge (SoK) article presents a comprehensive survey of the theoretical foundations, algorithmic developments, and practical implementations of LWR-based cryptographic schemes. We introduce LWR within the broader landscape of lattice-based cryptography and post-quantum security, highlighting its advantages such as reduced randomness, improved efficiency, and enhanced side-channel resistance. We explore the evolution of security reductions from LWR to LWE, including recent advances that support practical parameter regimes and address challenges in both bounded and unbounded sample settings. This article systematically reviews existing LWR-based schemes — including Saber, Lizard, Florete, Espada, Sable, and SMAUG — analyzing their design choices, parameter sets, and performance tradeoffs. Furthermore, we examine the impact of LWR on side-channel resistance, failure probabilities, and masking efficiency, demonstrating its suitability for secure and efficient implementations. By consolidating the research spanning theory and practice, this SoK aims at guiding future cryptographic design and standardization efforts leveraging LWR.
Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.
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.