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

Public Key Encryption from MP-LWE for the Middle-Product One

Weixian Lai, Hao Lei, Lichun Li, Wenbin Chen

Published Jul 1, 2026• 0 citations
Publisher

Abstract

Middle-Product Learning with Errors (MP-LWE) is a variant of the LWE problem introduced by Rosca et al., which achieves a trade-off between security and efficiency for lattice-based public-key encryption. In a nutshell, the public-key encryption based on MP-LWE outperform LWE-based schemes in efficiency while mitigating risks inherent in constructions from Polynomial/Ring LWE. A challenging problem is how to construct a PKE scheme whose security is based on some difficult problem that is the same hard as LWE, but it is of higher efficiency than existing LWE-based PKE schemes. In this paper, we solve this problem. First, we show MP-LWE for the middle-product one is of the same hard as LWE. Second, we propose a PKE scheme from MP-LWE for the middle-product one with shorter public key length than PKE scheme based on LWE.

DOI
10.1109/icsip70099.2026.11744276

Related papers

Improved Trapdoors and Public Key Search Encryption Based on Middle-Product LWE

Yufan Yao, Jianhua Wang, Ke Wang +3 more

Abstract Middle-product learning with errors (MP-LWE) was proposed in 2017 by Rosa et al., it is considered to be a method that combines the high efficiency of the R-LWE with the security guarantee of the ordinary LWE. Following the idea of this problem, in the TCC 2019, Alex Lombardi et al. further studied the method of constructing identity-based encryption (IBE) scheme on the premise of the MP-LWE. They introduced several major technologies, these include the introduction of a new leftover hash lemma and the instan-tiation of a brand-new variant of lattice trapdoor corresponding to MP-LWE. The idea of instantiation of trapdoor is very novel, but the equation can not be solved correctly by using the trapdoor. In the current work, we have improved the research results of the Lombardi et al., that is, we re-instantiate the trapdoor matching MP-LWE and use it to construct a new IBE scheme. Further, we also use the classical transformation of Abdalla et al. to transform the constructed IBE scheme into a MP-LWE-based public key search encryption scheme (PEKS). Compared to IBE and PEKS schemes from LWE, our scheme is more effective, and their ciphertexts and keys size are only O˜(n) in size (for identities of size n bits). Compared to IBE and PEKS schemes from ring-LWE, our schemes have similar efficiency

•Jul 17, 2023•1 citation

New variant for Learning with Errors Problem

Xuyang Wang, Aiqun Hu, Hao Fang

The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.

Procedia Computer Science•Jan 1, 2018•3 citations

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, 2016•2 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

Efficient Chosen-Ciphtertext Secure Public Key Encryption Scheme From Lattice Assumption

Fenghe Wang, Chunxiao Wang, Yupu Hu

Abstract: Using the Bonsai trees primitive and Gentry’s CPA-secure (chosen-plaintext attack) public-key encryption (PKE) scheme, we propose an efficient chosen-ciphtertext secure PKE scheme over lattice. If the decision variant of the learning with errors (LWE) problem is hard and the one-time signature used in this scheme is strong unforgeable, the proposed PKE scheme is indistinguishable against the adaptive chosen-ciphtertext attack (IND-CCA2). One of the characters for this scheme is that, before any encryption operation, the encryption algorithm uses a new choice rule to fix the public parameter matrixes used in the encryption operation. With the help of this new choice rule, we can achieve the chosen-ciphtertext security with much shorter the public key size in contrast to the lattice-based encryption scheme proposed in STOC’09 by Peikert. Moreover, as a CCA-secure PKE scheme, the message-tociphtertext expanse factor of this scheme which is controlled efficiently is nearly closed to the message-to-ciphtertext expanse factor of Gentry’s scheme which is CPA secure. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed PKE scheme is secure even in quantum-era.

Applied Mathematics & Information Sciences•Oct 9, 2013•0 citations

STP‐LWE: A Variant of Learning with Error for a Flexible Encryption

Bo Gao, Yanfeng Shi, Chunli Yang +3 more

We construct a flexible lattice based scheme based on semitensor product learning with errors (STP‐LWE), which is a variant of learning with errors problem. We have proved that STP‐LWE is hard when LWE is hard. Our scheme is proved to be secure against indistinguishable chosen message attacks, and it can achieve a balance between the security and efficiency in the hierarchical encryption systems. In addition, our scheme is almost as efficient as the dual encryption in GPV08.

Mathematical Problems in Engineering•Jan 1, 2014•11 citations
Middle-Product Learning with Errors (MP-LWE) is a variant of the LWE problem introduced by Rosca et al., which achieves a trade-off between security and efficiency for lattice-based public-key encryption. In a nutshell, the public-key encryption based on MP-LWE outperform LWE-based schemes in efficiency while mitigating risks inherent in constructions from Polynomial/Ring LWE. A challenging problem is how to construct a PKE scheme whose security is based on some difficult problem that is the same hard as LWE, but it is of higher efficiency than existing LWE-based PKE schemes. In this paper, we solve this problem. First, we show MP-LWE for the middle-product one is of the same hard as LWE. Second, we propose a PKE scheme from MP-LWE for the middle-product one with shorter public key length than PKE scheme based on LWE.
Abstract Middle-product learning with errors (MP-LWE) was proposed in 2017 by Rosa et al., it is considered to be a method that combines the high efficiency of the R-LWE with the security guarantee of the ordinary LWE. Following the idea of this problem, in the TCC 2019, Alex Lombardi et al. further studied the method of constructing identity-based encryption (IBE) scheme on the premise of the MP-LWE. They introduced several major technologies, these include the introduction of a new leftover hash lemma and the instan-tiation of a brand-new variant of lattice trapdoor corresponding to MP-LWE. The idea of instantiation of trapdoor is very novel, but the equation can not be solved correctly by using the trapdoor. In the current work, we have improved the research results of the Lombardi et al., that is, we re-instantiate the trapdoor matching MP-LWE and use it to construct a new IBE scheme. Further, we also use the classical transformation of Abdalla et al. to transform the constructed IBE scheme into a MP-LWE-based public key search encryption scheme (PEKS). Compared to IBE and PEKS schemes from LWE, our scheme is more effective, and their ciphertexts and keys size are only O˜(n) in size (for identities of size n bits). Compared to IBE and PEKS schemes from ring-LWE, our schemes have similar efficiency
The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.
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.
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.
Abstract: Using the Bonsai trees primitive and Gentry’s CPA-secure (chosen-plaintext attack) public-key encryption (PKE) scheme, we propose an efficient chosen-ciphtertext secure PKE scheme over lattice. If the decision variant of the learning with errors (LWE) problem is hard and the one-time signature used in this scheme is strong unforgeable, the proposed PKE scheme is indistinguishable against the adaptive chosen-ciphtertext attack (IND-CCA2). One of the characters for this scheme is that, before any encryption operation, the encryption algorithm uses a new choice rule to fix the public parameter matrixes used in the encryption operation. With the help of this new choice rule, we can achieve the chosen-ciphtertext security with much shorter the public key size in contrast to the lattice-based encryption scheme proposed in STOC’09 by Peikert. Moreover, as a CCA-secure PKE scheme, the message-tociphtertext expanse factor of this scheme which is controlled efficiently is nearly closed to the message-to-ciphtertext expanse factor of Gentry’s scheme which is CPA secure. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed PKE scheme is secure even in quantum-era.