Journal of Information Security

On the LWE Cryptosystem with More General Disturbance

Zhiyong Zheng, Kun Tian

Published Jan 1, 2022• 3 citations

Abstract

The main purpose of this paper is to give an extension on learning with errors problem (LWE) based cryptosystem about the probability of decryption error with more general disturbance. In the first section, we introduce the LWE cryptosystem with its application and some previous research results. Then we give a more precise estimation probability of decryption error based on independent identical Gaussian disturbances and any general independent identical disturbances. This upper bound probability could be closed to 0 if we choose applicable parameters. It means that the probability of decryption error for the cryptosystem could be sufficiently small. So we verify our core result that the LWE-based cryptosystem could have high security.

DOI: 10.4236/jis.2022.133008

Related papers

On the LWE Cryptosystem with More General Disturbance

Zhiyong Zheng, Tian Kun

Abstract The main purpose of this chapter is to give an extension on learning with errors problem (LWE)-based cryptosystem about the probability of decryption error with more general disturbance. In the first section, we introduce the LWE cryptosystem with its application and some previous research results. Then we give a more precise estimation probability of decryption error based on independent identical Gaussian disturbances and any general independent identical disturbances. This upper bound probability could be closed to 0 if we choose applicable parameters. It means that the probability of decryption error for the cryptosystem could be sufficiently small. So we verify our core result that the LWE-based cryptosystem could have high security.

Financial Mathematics and FintechJan 1, 20230 citations

Learning with Errors Public Key Cryptosystem with Its Security

Zhiyong Zheng, Kun Tian, Yi Zhang +1 more

The main purpose of this paper is to introduce the LWE public key cryptosystem with its security. In the first section, we introduce the LWE public key cryptosystem by Regev with its applications and some previous research results. Then we prove the security of LWE public key cryptosystem by Regev in detail. For not only independent identical Gaussian disturbances but also any general independent identical disturbances, we give a more accurate estimation probability of decryption error of general LWE cryptosystem. This guarantees high security and widespread applications of the LWE public key cryptosystem.

Journal of Information SecurityJan 1, 20230 citations

Feasibility Analysis and Optimization of Non-Gaussian Error Distributions in LWE-based Cryptosystems: A Step Distribution Approach

Rongxun Yao

The Learning with Errors (LWE) problem is a fundamental hardness assumption for post-quantum lattice-based cryptography. Standard LWE schemes rely on discrete Gaussian error distributions, which incur high sampling overhead. This paper explores the feasibility of replacing the Gaussian distribution with a novel non-Gaussian alternative—the Step Distribution—within Regev’s classic LWE public-key encryption scheme. The Step Distribution partitions the error range into equal-width steps, with probabilities proportional to Gaussian weights at step midpoints. The distribution is formally defined, its asymptotic convergence to the discrete Gaussian is proved, and conditions under which the decryption error probability becomes negligible are derived. The Step Distribution offers a tunable parameter—the number of steps—that allows a trade-off between security (closeness to the Gaussian) and computational efficiency. This work provides a flexible error distribution for LWE-based cryptosystems, particularly suitable for resource-constrained environments.

Frontiers in Computing and Intelligent SystemsJul 30, 20260 citations

On the Hardness of the Asymmetric Learning With Errors Problem

Jiang Zhang, Shuqin Fan

Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGYFeb 19, 20200 citations

Augmented Learning with Errors: The Untapped Potential of the Error Term.

Rachid El Bansarkhani, Özgür Dagdelen, Johannes A Buchmann

Abstract. The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security. To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem. As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.

Jan 1, 20141 citation

Securely Instantiating Cryptographic Schemes Based on the Learning with Errors Assumption

Florian Göpfert

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

Jan 1, 20162 citations