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

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

Huy Quoc Le, Dung Hoang Duong, Willy Susilo, Josef Pieprzyk

Published Jan 1, 2020• 9 citations
OpenAlex

Abstract

© 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.

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

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

Weixian Lai, Hao Lei, Lichun Li +1 more

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.

•Jul 1, 2026•0 citations

Advanced cryptography from lattice isomorphism—new constructions of IBE and FHE

Zhengnan Lai

We show how to translate some of the more advanced techniques used in LWE-based cryptography to the setting of lattice-isomorphism-based cryptography, which was recently introduced by Ducas and van Woerden [Eurocrypt, 2022]. In particular, we show constructions of two powerful cryptographic primitives, identity-based encryption (IBE) and fully homomorphic encryption (FHE). We then prove their security under the assumption that a suitable version of the Lattice Isomorphism Problem is hard.Our constructions use quite general and modular techniques, and we expect them to have other applications. Specifically, we show that the now-ubiquitous techniques introduced by Gentry, Peikert, and Vaikuntanathan [STOC, 2008] to build IBE and Gentry, Sahai, and Waters [Crypto, 2013] to build FHE can be made to work in our setting using any sufficiently “nice” lattice.

•Aug 26, 2026•0 citations

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

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

arXiv:2007.06881•Lecture notes in computer science•Jan 1, 2020•0 citations

Tighter Security Proof for IBE from MP-LWE Assumption in the Random Oracle Model

Yanyan Liu, Yu Li, Yiru Sun +3 more

In this paper, We present a significantly tighter security proof for the identity-based encryption scheme constructed from the middle-product learning with errors (MP-LWE) assumption in the random oracle model (ROM) for the first time. The IBE scheme from MP-LWE was originally proposed by Lombardi et al. in TCC 2019, utilizing the proof strategy of Gentry et al. in STOC 2008. This strategy resulted in the reduction loss that depends on the total number of random oracle queries. In order to reudce the reduction loss, we use the proof strategy by Katsumata et al. in JoC 2021, thereby making the reduction loss independent of the total number of random oracle queries. As part of our approach, we developed novel conclusions and algorithm on MP-LWE that are likely to be of independent interest.

International Conference on Computer Information Science and Application Technology (CISAT)•Jul 1, 2026•0 citations

How to Delegate a Lattice Basis.

David M. Cash, Dennis Hofheinz, Eike Kiltz

We present a technique, which we call basis delegation, that allows one to use a short basis of a given lattice to derive a new short basis of a related lattice in a secure way. And since short bases for lattices essentially function like cryptographic trapdoors, basis delegation turns out to be a very powerful primitive. As the main application of our technique, we show how to construct hierarchical identity-based encryption (HIBE) that is secure, without random oracles, under the assumption that certain standard lattice problems are hard in the worst case. This construction and its variants constitute the first HIBE schemes from lattices, as well as the first lattice-based constructions of stateless signatures and identity-based encryption without random oracles. 1

•Jan 1, 2009•54 citations
© 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.
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
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.
We show how to translate some of the more advanced techniques used in LWE-based cryptography to the setting of lattice-isomorphism-based cryptography, which was recently introduced by Ducas and van Woerden [Eurocrypt, 2022]. In particular, we show constructions of two powerful cryptographic primitives, identity-based encryption (IBE) and fully homomorphic encryption (FHE). We then prove their security under the assumption that a suitable version of the Lattice Isomorphism Problem is hard.Our constructions use quite general and modular techniques, and we expect them to have other applications. Specifically, we show that the now-ubiquitous techniques introduced by Gentry, Peikert, and Vaikuntanathan [STOC, 2008] to build IBE and Gentry, Sahai, and Waters [Crypto, 2013] to build FHE can be made to work in our setting using any sufficiently “nice” lattice.
In this paper, We present a significantly tighter security proof for the identity-based encryption scheme constructed from the middle-product learning with errors (MP-LWE) assumption in the random oracle model (ROM) for the first time. The IBE scheme from MP-LWE was originally proposed by Lombardi et al. in TCC 2019, utilizing the proof strategy of Gentry et al. in STOC 2008. This strategy resulted in the reduction loss that depends on the total number of random oracle queries. In order to reudce the reduction loss, we use the proof strategy by Katsumata et al. in JoC 2021, thereby making the reduction loss independent of the total number of random oracle queries. As part of our approach, we developed novel conclusions and algorithm on MP-LWE that are likely to be of independent interest.
We present a technique, which we call basis delegation, that allows one to use a short basis of a given lattice to derive a new short basis of a related lattice in a secure way. And since short bases for lattices essentially function like cryptographic trapdoors, basis delegation turns out to be a very powerful primitive. As the main application of our technique, we show how to construct hierarchical identity-based encryption (HIBE) that is secure, without random oracles, under the assumption that certain standard lattice problems are hard in the worst case. This construction and its variants constitute the first HIBE schemes from lattices, as well as the first lattice-based constructions of stateless signatures and identity-based encryption without random oracles. 1