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

Journal of Information Security

Learning with Errors Public Key Cryptosystem with Its Security

Zhiyong Zheng, Kun Tian, Yi Zhang, Yunfan Lu

Published Jan 1, 2023• 0 citations
Publisher

Abstract

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.

DOI
10.4236/jis.2023.141003

Related papers

On the LWE Cryptosystem with More General Disturbance

Zhiyong Zheng, Kun Tian

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.

Journal of Information Security•Jan 1, 2022•3 citations

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 Fintech•Jan 1, 2023•0 citations

LWE Public Key Cryptosystem

Zhiyong Zheng, Kun Tian, Fengxia Liu

Abstract In 2005, O.Regev proposed the first LWE public key cryptosystem at Tel Aviv University in Israel based on LWE distribution $$A_{s,\chi }$$ . Because of this paper, Regev won the highest award for theoretical computer science in 2018—the Godel Award. The size of public key is $$\tilde{O}(n^2)$$ bits, and the size of private key s and ciphertext is $$\tilde{O}(n)$$ bits. The plaintext encrypted each time is 1 bit. In fact, the LWE public key cryptosystem is a probabilistic cryptosystem, which depends on a high probability algorithm. Since the security of LWE problem has been clearly proved (see Chap. 3 ), the LWE cryptosystem has received extensive attention as soon as it was proposed, and it becomes the most cutting-edge research topic in the lattice-based cryptosystem study.

Financial Mathematics and Fintech•Dec 10, 2022•2 citations

Cryptography with the Ring-LWE (Learning With Errors) Algorithm

Hesty Sitohang, Roy Untung Pratama Saing, Agnes Selaras Osabela Sarahono +3 more

Ring-LWE (Ring Learning With Errors) is a post-quantum cryptography algorithm based on mathematical problems in number theory and algebra. It is an extension of LWE (Learning With Errors) first introduced by Oded Regev and is used for secure data encryption from quantum computer attacks. The process consists of three main steps: key generation, encryption, and decryption. Key generation uses random polynomials and noise to create public and private keys. While encryption produces ciphertext in the form of polynomial pairs, decryption uses the private key to return the ciphertext to the original message. To conduct the experiment, the modulus value q = 17, the modulus polynomial f(x) = x2 + 1, and the private key and random polynomial have been determined. The results of the experiment show that the message can be accurately decrypted using the private key, thus proving the success of this algorithm in maintaining data security. With its security properties that are resistant to quantum attacks, Ring-LWE is a promising alternative for future cryptography.

Jurnal Teknik Indonesia•May 20, 2024•0 citations

A Latticed-Based Public Key Encryption with KDM Security from R-LWE

Yan Fang Wu, Zheng Huang, Qiao Yan Wen

Since the introduction of the ring learning with errors (R-LWE) by Lyubashevsky, Peikert and Regev, many efficient and secure applications were founded in cryptography. In this paper, we mainly present an efficient public-key encryption scheme based on the R-LWE assumption. It is very simple to describe and analyze. As well as it can achieve security against certain key-dependent message (KDM) attacks. Namely, this efficient encryption scheme can securely encrypt its own secret key. The security of this scheme follows from the already proven hardness of the R-LWE problem since the R-LWE assumption is reducible to worst-case problems on the ideal lattice. Besides, the scheme enjoys a high level efficiency and low cost since the operations of the scheme are very simple and fast. The cost of both the encryption and decryption is only polylog(n) bit per message symbol.

Advanced engineering forum•Sep 1, 2012•0 citations

Public-key cryptosystems from the worst-case shortest vector problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•822 citations
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.
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.
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.
Abstract In 2005, O.Regev proposed the first LWE public key cryptosystem at Tel Aviv University in Israel based on LWE distribution As,χA_{s,\chi }As,χ​ . Because of this paper, Regev won the highest award for theoretical computer science in 2018—the Godel Award. The size of public key is O~(n2)\tilde{O}(n^2)O~(n2) bits, and the size of private key s and ciphertext is O~(n)\tilde{O}(n)O~(n) bits. The plaintext encrypted each time is 1 bit. In fact, the LWE public key cryptosystem is a probabilistic cryptosystem, which depends on a high probability algorithm. Since the security of LWE problem has been clearly proved (see Chap. 3 ), the LWE cryptosystem has received extensive attention as soon as it was proposed, and it becomes the most cutting-edge research topic in the lattice-based cryptosystem study.
Ring-LWE (Ring Learning With Errors) is a post-quantum cryptography algorithm based on mathematical problems in number theory and algebra. It is an extension of LWE (Learning With Errors) first introduced by Oded Regev and is used for secure data encryption from quantum computer attacks. The process consists of three main steps: key generation, encryption, and decryption. Key generation uses random polynomials and noise to create public and private keys. While encryption produces ciphertext in the form of polynomial pairs, decryption uses the private key to return the ciphertext to the original message. To conduct the experiment, the modulus value q = 17, the modulus polynomial f(x) = x2 + 1, and the private key and random polynomial have been determined. The results of the experiment show that the message can be accurately decrypted using the private key, thus proving the success of this algorithm in maintaining data security. With its security properties that are resistant to quantum attacks, Ring-LWE is a promising alternative for future cryptography.
Since the introduction of the ring learning with errors (R-LWE) by Lyubashevsky, Peikert and Regev, many efficient and secure applications were founded in cryptography. In this paper, we mainly present an efficient public-key encryption scheme based on the R-LWE assumption. It is very simple to describe and analyze. As well as it can achieve security against certain key-dependent message (KDM) attacks. Namely, this efficient encryption scheme can securely encrypt its own secret key. The security of this scheme follows from the already proven hardness of the R-LWE problem since the R-LWE assumption is reducible to worst-case problems on the ideal lattice. Besides, the scheme enjoys a high level efficiency and low cost since the operations of the scheme are very simple and fast. The cost of both the encryption and decryption is only polylog(n) bit per message symbol.
We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.