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

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

Yufan Yao, Jianhua Wang, Ke Wang, Linzhi Shen, Haoyang Yu, Huiyan Chen

Published Jul 17, 2023• 1 citation
Publisher

Abstract

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

DOI
10.21203/rs.3.rs-3153867/v1

Related papers

Trapdoor Delegation and HIBE from Middle-Product LWE in Standard Model

Huy Quoc Le, Dung Hoang Duong, Willy Susilo +1 more

© 2020, Springer Nature Switzerland AG. At CRYPTO 2017, Roşca, Sakzad, Stehlé and Steinfeld introduced the Middle–Product LWE (MPLWE) assumption which is as secure as Polynomial-LWE for a large class of polynomials, making the corresponding cryptographic schemes more flexible in choosing the underlying polynomial ring in design while still keeping the equivalent efficiency. Recently at TCC 2019, Lombardi, Vaikuntanathan and Vuong introduced a variant of MPLWE assumption and constructed the first IBE scheme based on MPLWE. Their core technique is to construct lattice trapdoors compatible with MPLWE in the same paradigm of Gentry, Peikert and Vaikuntanathan at STOC 2008. However, their method cannot directly offer a Hierarchical IBE construction. In this paper, we make a step further by proposing a novel trapdoor delegation mechanism for an extended family of polynomials from which we construct, for the first time, a Hierachical IBE scheme from MPLWE. Our Hierarchy IBE scheme is provably secure in the standard model.

•Jan 1, 2020•8 citations

Full secure identity-based encryption scheme with short public key size over lattices in the standard model

Fenghe Wang, Zhenhua Liu, Chunxiao Wang

An efficient identity-based encryption (IBE) scheme over lattice is proposed in this paper. Under the hardness of the learning with errors (LWE) problem, the proposed scheme is semantic secure against adaptive chosen identity and chosen plaintext attack in the standard model. To improve the efficiency of the lattice-based IBE scheme, unlike the identity string is encoded into a matrix by a group of public matrices in several known constructions, the identity string of l bits is encoded into a vector with the help of l+1 vectors in this paper. With the help of this idea, we achieve the private key extraction of IBE scheme at the same lattice. Then, the public key of the proposed scheme only consists of one n×m matrix and l+1 vectors, compared with that the public keys of the known lattice-based IBE schemes all consist as a group of n×m matrices. Hence, the public key size of this scheme is shorter than that of the known constructions.

International Journal of Computer Mathematics•Mar 16, 2015•20 citations

An ideal lattice based IBE scheme in the standard model

Xiaoyuan Yang, Liqiang Wu, Minqing Zhang +2 more

Under the standard model, an IND-sID-CPA secure IBE (Identity Based Encryption) scheme is proposed, which is based on an improved trapdoor generation function over ring and decisional R-LWE (ring-learning with errors) assumption, thus the hardness of recovering system master key can be reduced to solve the Ideal-SIS (small integer solution) problem, and the attack to the ciphertext is equivalent to solving the SVP (the shortest vector problem) in the worst case on ideal lattice to within a fixed poly( n ) factor. Moreover, the proposed scheme has advantages of high encryption and decryption speed and low encryption blowup factor compared with all known IBE scheme from the standard lattice under the standard model.

Wuhan University Journal of Natural Sciences•Sep 3, 2011•2 citations

Identity-Based Online/Offline Encryption Scheme from LWE

Binger Zuo, Jiguo Li, Yichen Zhang +1 more

With quantum computers, the quantum resistance of cryptographic systems has gradually attracted attention. To overcome the shortcoming of existing identity-based encryption (IBE) schemes in resisting quantum attacks, we introduce an IBE scheme based on learning with errors (LWE). In addition, devices with limited computing power are becoming increasingly common in practice, making it increasingly important to improve the efficiency of online computation of encryption algorithms. The classic solution is to directly improve the efficiency of the Gaussian sampling algorithm, thereby increasing the overall efficiency of the scheme. However, our scheme combines the efficient Gaussian sampling algorithm, G-trapdoor, with online/offline method to further improve the online encryption efficiency of the encryption algorithm. Our scheme completes partial computation before knowing the message and receiver’s identity, and once the message and receiver’s identity are obtained, the online part encryption can be efficiently completed. We construct an identity-based online/offline encryption (IBOOE) scheme from LWE with G-trapdoor, improve the efficiency of online encryption while achieving quantum resistant security. We prove the scheme’s security under the standard model for chosen-plaintext attack (CPA). By comparing with relevant schemes in terms of experiments and analysis, our scheme has improved efficiency by 65% to 80% compared to the classical LWE IBE scheme (increasing with LWE security parameters), and by 60% to 70% compared to the recent IBE scheme from LWE. This greatly improves the efficiency of online computing for low-power encryption devices while ensuring security.

Information•Sep 4, 2024•2 citations

Identity-Based Proxy Re-Encryption Based on LWE with Short Parameters

Keyuan Zhang, Yuan Liu, Licheng Wang +1 more

Proxy re-encryption (PRE) can guarantee the security of data sharing in the cloud making it important in ciphertext sharing in the cloud computing environment. Plenty of the current PRE algorithms based on the learning with errors (LWE) problem are constructed under the random oracle model or have problems such as long public parameter size, large ciphertext expansion rate, etc. We propose an identity-based PRE (IB-PRE) scheme using the LWE problem with short public parameters which can solve the mentioned challenges. Our scheme uses the blocking operation to decrease the public parameter size and a more useful trapdoor generation algorithm to reduce the trapdoor size. These two technologies improve the computational efficiency of the public key. We think that when we divide the identity id into 16 blocks, without much increase in computational overhead, the public key size can be reduced by 88.34%, and the scheme’s security level can remain unchanged. Our scheme achieves adaptive IND-ID-CPA security. It is unidirectional, collusion-resistant, and constructed under the standard model.

International Conference on Mobile Internet, Cloud Computing and Information Security (MICCIS)•Apr 1, 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
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
© 2020, Springer Nature Switzerland AG. At CRYPTO 2017, Roşca, Sakzad, Stehlé and Steinfeld introduced the Middle–Product LWE (MPLWE) assumption which is as secure as Polynomial-LWE for a large class of polynomials, making the corresponding cryptographic schemes more flexible in choosing the underlying polynomial ring in design while still keeping the equivalent efficiency. Recently at TCC 2019, Lombardi, Vaikuntanathan and Vuong introduced a variant of MPLWE assumption and constructed the first IBE scheme based on MPLWE. Their core technique is to construct lattice trapdoors compatible with MPLWE in the same paradigm of Gentry, Peikert and Vaikuntanathan at STOC 2008. However, their method cannot directly offer a Hierarchical IBE construction. In this paper, we make a step further by proposing a novel trapdoor delegation mechanism for an extended family of polynomials from which we construct, for the first time, a Hierachical IBE scheme from MPLWE. Our Hierarchy IBE scheme is provably secure in the standard model.
An efficient identity-based encryption (IBE) scheme over lattice is proposed in this paper. Under the hardness of the learning with errors (LWE) problem, the proposed scheme is semantic secure against adaptive chosen identity and chosen plaintext attack in the standard model. To improve the efficiency of the lattice-based IBE scheme, unlike the identity string is encoded into a matrix by a group of public matrices in several known constructions, the identity string of l bits is encoded into a vector with the help of l+1 vectors in this paper. With the help of this idea, we achieve the private key extraction of IBE scheme at the same lattice. Then, the public key of the proposed scheme only consists of one n×m matrix and l+1 vectors, compared with that the public keys of the known lattice-based IBE schemes all consist as a group of n×m matrices. Hence, the public key size of this scheme is shorter than that of the known constructions.
Under the standard model, an IND-sID-CPA secure IBE (Identity Based Encryption) scheme is proposed, which is based on an improved trapdoor generation function over ring and decisional R-LWE (ring-learning with errors) assumption, thus the hardness of recovering system master key can be reduced to solve the Ideal-SIS (small integer solution) problem, and the attack to the ciphertext is equivalent to solving the SVP (the shortest vector problem) in the worst case on ideal lattice to within a fixed poly( n ) factor. Moreover, the proposed scheme has advantages of high encryption and decryption speed and low encryption blowup factor compared with all known IBE scheme from the standard lattice under the standard model.
With quantum computers, the quantum resistance of cryptographic systems has gradually attracted attention. To overcome the shortcoming of existing identity-based encryption (IBE) schemes in resisting quantum attacks, we introduce an IBE scheme based on learning with errors (LWE). In addition, devices with limited computing power are becoming increasingly common in practice, making it increasingly important to improve the efficiency of online computation of encryption algorithms. The classic solution is to directly improve the efficiency of the Gaussian sampling algorithm, thereby increasing the overall efficiency of the scheme. However, our scheme combines the efficient Gaussian sampling algorithm, G-trapdoor, with online/offline method to further improve the online encryption efficiency of the encryption algorithm. Our scheme completes partial computation before knowing the message and receiver’s identity, and once the message and receiver’s identity are obtained, the online part encryption can be efficiently completed. We construct an identity-based online/offline encryption (IBOOE) scheme from LWE with G-trapdoor, improve the efficiency of online encryption while achieving quantum resistant security. We prove the scheme’s security under the standard model for chosen-plaintext attack (CPA). By comparing with relevant schemes in terms of experiments and analysis, our scheme has improved efficiency by 65% to 80% compared to the classical LWE IBE scheme (increasing with LWE security parameters), and by 60% to 70% compared to the recent IBE scheme from LWE. This greatly improves the efficiency of online computing for low-power encryption devices while ensuring security.
Proxy re-encryption (PRE) can guarantee the security of data sharing in the cloud making it important in ciphertext sharing in the cloud computing environment. Plenty of the current PRE algorithms based on the learning with errors (LWE) problem are constructed under the random oracle model or have problems such as long public parameter size, large ciphertext expansion rate, etc. We propose an identity-based PRE (IB-PRE) scheme using the LWE problem with short public parameters which can solve the mentioned challenges. Our scheme uses the blocking operation to decrease the public parameter size and a more useful trapdoor generation algorithm to reduce the trapdoor size. These two technologies improve the computational efficiency of the public key. We think that when we divide the identity id into 16 blocks, without much increase in computational overhead, the public key size can be reduced by 88.34%, and the scheme’s security level can remain unchanged. Our scheme achieves adaptive IND-ID-CPA security. It is unidirectional, collusion-resistant, and constructed under the standard model.
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.