Signals

Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography

Maria E. Sabani, Ilias Κ. Savvas, Georgia Garani

Published Apr 13, 2024• 27 citations

Abstract

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.

DOI: 10.3390/signals5020012

Related papers

Lattice-Based Cryptography

Seong Oun Hwang, Intae Kim, Wai‐Kong Lee

This chapter introduces post-quantum cryptography. It describes lattice-based cryptographic constructions of post-quantum cryptography. Lattice-based cryptographic constructions are one of candidates of post-quantum cryptography, which are believed to be secure against quantum computers. Learning with errors (LWE) is one of the most promising primitives in many usages due to its lightweight operation and rigorous security reduction against the worst-case of the lattice problems that are considered to be hard to solve even after the advance of quantum computers. After the research about the connection between the LWE problem and some lattice problems, some variants of LWE, of which the secret distributions are modified from the uniform distribution, were proposed. Due to the efficiency and compactness of ring-LWE, many lattice-based cryptosystems are constructed as ring-LWE based, rather than LWE-based. The chapter explains a ring variant of Lizard scheme, called RLizard, IND-CCA secure encryption scheme.

CRC Press eBooksFeb 19, 20210 citations

Integration of post-quantum cryptography in the TLS protocol (LWE Option)

Luís Da Costa

With the possibility of quantum computers making an appearance, possibly capable of breaking several well established and widespread crytposystems (especially those that implement public key cryptography), necessity has arisen to create new cryptographic algorithms which remain safe even against adversaries using quantum computers. Several algorithms based on different mathematical problems have been proposed which are considered to be hard to solve with quantum computers. In recent years, a new lattice-based mathematical problem called Learning With Errors (and its variant Ring - Learning With Errors) was introduced, and several cryptosystems based on this problem were introduced, some of which are becoming practical enough to compete with traditional schemes that have been used for decades. The primary focus in this work is the implementation of two Ring - Learning With Errors based schemes (one key exchange mechanism and one digital signature scheme) on the TLS protocol via the OpenSSL library as a way of checking their overall viability in real-world scenarios, by comparing them to classical schemes implementing the same functionalities.

Jan 1, 20190 citations

On Advances of Lattice-Based Cryptographic Schemes and Their Implementations

Harshana Bandara, Yasitha Herath, Thushara Weerasundara +1 more

Lattice-based cryptography is centered around the hardness of problems on lattices. A lattice is a grid of points that stretches to infinity. With the development of quantum computers, existing cryptographic schemes are at risk because the underlying mathematical problems can, in theory, be easily solved by quantum computers. Since lattice-based mathematical problems are hard to be solved even by quantum computers, lattice-based cryptography is a promising foundation for future cryptographic schemes. In this paper, we focus on lattice-based public-key encryption schemes. This survey presents the current status of the lattice-based public-key encryption schemes and discusses the existing implementations. Our main focus is the learning with errors problem (LWE problem) and its implementations. In this paper, the plain lattice implementations and variants with special algebraic structures such as ring-based variants are discussed. Additionally, we describe a class of lattice-based functions called lattice trapdoors and their applications.

CryptographyNov 9, 202236 citations

LEADING THE WAY IN QUANTUM-RESISTANT CRYPTOGRAPHY FOR EVERYDAY SAFETY

Luka Baklaga

The development of quantum-resistant solutions is imperative as the emergence of quantum computing presents a substantial risk to existing cryptography systems. Lattice-based cryptography, especially schemes based on the Learning with Errors (LWE) problem, is one of the most promising methods. To guarantee long-term security, even LWE-based methods could need to be strengthened further as quantum algorithms advance. By mixing Gaussian and discrete uniform distributions to create a mixed error distribution, this work enhances the classic LWE problem. The experimental findings show that, with a slight rise in computing overhead, the mixed error distribution improves the security of the LWE problem by strengthening its resistance to quantum techniques. By presenting a novel approach for enhancing the resilience of cryptographic methods in the quantum era, this research contributes to the continuing work in post-quantum cryptography. Moreover, it introduces the direction of future model improvements and provides multidisciplinary methods for increasing the complexity of cryptographic algorithms.

Jan 1, 20240 citations

An Enhanced Learning with Error-Based Cryptosystem: A Lightweight Quantum-Secure Cryptography Method

Mostefa Kara, Konstantinos Κarampidis, Giorgos M. Papadourakis +2 more

Quantum-secure cryptography is a dynamic field due to its crucial role in various domains. This field aligns with the ongoing efforts in data security. Post-quantum encryption (PQE) aims to counter the threats posed by future quantum computers, highlighting the need for further improvement. Based on the learning with error (LWE) system, this paper introduces a novel asymmetric encryption technique that encrypts entire messages of n bits rather than just 1 bit. This technique offers several advantages including an additive homomorphic cryptosystem. The robustness of the proposed lightweight public key encryption method, which is based on a new version of LWE, ensures that private keys remain secure and that original data cannot be recovered by an attacker from the ciphertext. By improving encryption and decryption execution time—which achieve speeds of 0.0427 ms and 0.0320 ms, respectively—and decreasing ciphertext size to 708 bits for 128-bit security, the obtained results are very promising.

J — Multidisciplinary Scientific JournalOct 13, 20243 citations

From Factoring to Lattices: Forging Post-Quantum Cryptographic Security

Revista, Zen, MATH, 10

The landscape of modern cryptography is fundamentally challenged by the advent of quantum computing. Current public-key cryptosystems, which form the bedrock of secure digital communication, rely on the computational hardness of problems such as integer factorization (RSA) and the discrete logarithm problem (ECC). However, Shor's algorithm, if implemented on a sufficiently powerful quantum computer, can efficiently break these schemes, rendering them insecure. This paper explores the critical transition from these classical number theory problems to lattice-based cryptography, presenting a comprehensive analysis of the motivations, theoretical underpinnings, and practical implications for forging post-quantum cryptographic security. We delve into the mathematical foundations of lattice problems, such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE), which are believed to resist known quantum algorithms. Through a thorough literature review, we trace the evolution of cryptographic thought, detailing the vulnerabilities of pre-quantum schemes and the emergence of lattice-based constructions as leading candidates for post-quantum standardization. The methodology outlines a comparative theoretical analysis of security, efficiency, and robustness against both classical and quantum attacks. Results demonstrate the compelling advantages of lattice-based schemes in terms of provable security reductions and resistance to quantum threats, albeit with considerations for increased key and ciphertext sizes. The discussion highlights the challenges and opportunities in the deployment and standardization of these new cryptographic primitives, emphasizing their critical role in securing future digital infrastructures. This work concludes that lattice-based cryptography offers a robust and theoretically sound pathway to establishing enduring security in a quantum-threatened world.

Dec 3, 20250 citations