Abstract As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the learning with errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, ring-learning with errors (RLWE) and polynomial learning with errors (PLWE), gain efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the “smearing” condition, a condition for attacks on PLWE and RLWE introduced in Elias et al. We expand upon some questions about smearing posed by Elias et al. and show how smearing is related to the coupon collector’s problem. Furthermore, we develop an algorithm for computing probabilities related to smearing. Finally, we present a smearing-based algorithm for solving the PLWE problem.
Abstract As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the learning with errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, ring-learning with errors (RLWE) and polynomial learning with errors (PLWE), gain efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the “smearing” condition, a condition for attacks on PLWE and RLWE introduced in Elias et al. We expand upon some questions about smearing posed by Elias et al. and show how smearing is related to the coupon collector’s problem. Furthermore, we develop an algorithm for computing probabilities related to smearing. Finally, we present a smearing-based algorithm for solving the PLWE problem.
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.
The “learning with errors ” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE. 1
Ring Learning With Errors (Ring-LWE) is one of the basic schemes used to develop cryptographic algorithms that are resistant to quantum attacks, offering better computational efficiency compared to standard Learning With Errors (LWE). Ring-LWE uses the algebraic characteristics of polynomial rings to create a robust and fast encryption system. This study implements and evaluates the Ring-LWE algorithm in the context of public key exchange and encryption. Simulations are performed with various security parameters, including modulus size and error rate, to test the resistance to brute force attacks and lattice-based attacks. The experimental results show that the Ring-LWE algorithm can achieve a balance between security and computational efficiency, with shorter processing time than conventional LWE while maintaining a high level of security even in the face of quantum computers. From this study, it can be concluded that Ring-LWE is an excellent choice for application in post-quantum security systems, especially in encrypted communication and digital authentication applications. The next step can be directed at optimizing resource utilization and testing against various types of attacks.
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.
This note describes a key exchange method based on the ring-LWE (RLWE)
assumption. It builds upon several results, including Regev's
landmark quantum reduction from certain worst case lattice problems
(approx. GapSVP and SIVP) to random instances of the search variant of
a particular learning problem (LWE). It also builds on the follow on
work of Lyubashevsky, Peikert and Regev on the average case hardness
of the RLWE search variant for polynomially bounded numbers of RLWE
samples, along with novel applications of automorphism groups in
number fields for a RLWE search to decision reduction (thereby
demonstrating pseudorandomness of RLWE in these number fields).
Subsequently, these results were adopted for the construction of
Diffie-Hellman like key exchange methods by Peikert, and then by
Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who
proposed efficient variants of such protocols. Subsequent work by
Peikert proposed another efficient variant, phrased as a key
encapsulation method, incorporating a low bandwidth reconciliation
technique allowing two parties to exactly agree on a uniformly
distributed secret value from noisy RLWE instances. This was followed
by a concrete instantiation with parameter sets by Bos, Costello,
Naehrig, Stebila, followed by another instantiation by Alkim, Ducas,
Poppelmann and Schwabe with the same ring polynomial but a smaller
modulus and a different reconciliation method. Unlike most other
public key cryptography based key exchange methods, it is believed
that RLWE based key exchange would remain secure in the event that an
adversary is able to build a quantum computer. This document is a
product of the Crypto Forum Research Group (CFRG).
The swift advancement of quantum computing devices holds the potential to create robust machines that can tackle an extensive array of issues beyond the scope of conventional computers. Consequently, quantum computing machines create new risks at a velocity and scale never seen before, especially with regard to encryption. Lattice-based cryptography is regarded as post-quantum cryptography’s future and a competitor to a quantum computer attack. Thus, there are several advantages to lattice-based cryptographic protocols, including security, effectiveness, reduced energy usage and speed. In this work, we study the learning with errors (LWE) problem and the cryptosystems that are based on the LWE problem and, in addition, we present a new efficient variant of LWE cryptographic scheme.