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

International Journal of Foundations of Computer Science

Novel Identity-Based Hash Proof System with Compact Master Public Key from Lattices in the Standard Model

Qiqi Lai, Bo Yang, Zhe Xia, Yannan Li, Yuan Chen, Zhenlong Li

Published Jun 1, 2019• 1 citation
Publisher

Abstract

As the progress of quantum computers, it is desired to propose many more efficient cryptographic constructions with post-quantum security. In the literatures, almost all cryptographic schemes and protocols can be explained and constructed modularly from certain cryptographic primitives, among which an Identity-Based Hash Proof System (IB-HPS) is one of the most basic and important primitives. Therefore, we can utilize IB-HPSs with post-quantum security to present several types of post-quantum secure schemes and protocols. Up until now, all known IB-HPSs with post-quantum security are instantiated based on latticed-based assumptions. However, all these lattice-based IB-HPSs are either in the random oracle model or not efficient enough in the standard model. Hence, it should be of great significance to construct more efficient IB-HPSs from lattices in the standard model. In this paper, we propose a new smooth IB-HPS with anonymity based on the Learning with Errors (LWE) assumption in the standard model. This new construction is mainly inspired by a classical identity-based encryption scheme based on LWE due to Agreawal et al. in Eurocrypt 2010. And our innovation is to employ the algorithm SampleGaussian introduced by Gentry et al. and the property of random lattice to simulate the identity secret key with respect to the challenge identity. Compared with other existing IB-HPSs in the standard model, our master public key is quite compact. As a result, our construction has much lower overheads on computation and storage.

DOI
10.1142/s0129054119400148

Related papers

Novel Smooth Hash Proof Systems Based on Lattices

Qiqi Lai, Bo Yang, Yong Hong Yu +2 more

As a basic and important primitive, hash proof system can be used to construct many cryptographic schemes and protocols. Therefore, it is significant to instantiate more efficient hash proof systems from various assumptions. Although there are many hash proof systems based on various classical assumptions, only a handful of efficient hash proof systems are known based on post-quantum assumptions. In this paper, we present several new hash proof systems based on the standard learning with errors (LWE) problem, which is at least as hard as standard worst-case lattice problems. Comparing with other existing constructions based on lattices, our main advantages are 2-fold: much simpler and more efficient. And our constructions can be easily extended to be identity-based ones and updatable ones. Throughout the paper, our main idea is to base hash proof systems on a new subset indistinguishability problem related to LWE, and employ the property of smooth parameter of q-ary orthogonal lattices to ensure smoothness.

The Computer Journal•Dec 6, 2017•5 citations

Smooth Hash Proof System Based on the Learning With Errors Problem With Multi-Bit Key Output

Momeng Liu, Yupu Hu, Shanshan Zhang +1 more

Since hash proof system (HPS) can be utilized to build versatilely cryptographic schemes, the study on realizing this cryptographic primitive has been a very active research area. With the increasing concerns on the huge progress in quantum computing, it urges cryptographers to explore the existence of quantum-resistant HPS schemes, such as the one relying on some lattice-based assumptions. However, most lattice-based HPS proposals are relatively inefficient (e.g., simply outputting one-bit key), even though lattice-based schemes can enjoy many advantageous features: worst-case to average-case reduction, resistance so far to quantum algorithms, and good asymptotic efficiency. Therefore, efficient HPS schemes based on lattice problems are deeply in demand. Through a comprehensive analysis, we found that some lattice-based HPS schemes can be rephrased as their corresponding key encapsulation mechanism (KEM) forms, which generally rely on diverse reconciliation mechanisms and directly imply key exchange protocols under lattice-based assumptions. In this paper, inspired by a novel reconciliation mechanism based on the learning with errors (LWE) problem, we first properly adapt this LWE-based reconciliation mechanism for arbitrary modulus. Then using this improved reconciliation mechanism, we propose an efficient LWE-based HPS scheme which can generate multiple encapsulated key bits and perform better in both computation and storage costs than other related results. Moreover, our proposed lattice-based HPS scheme can be also extended to identity-based and updatable settings for demonstrating its diverse applications.

IEEE Access•Jan 1, 2019•0 citations

Leakage-resilient IBE from lattices in the standard model

Xizhao Luo, Peide Qian, Yanqin Zhu

We present an identity-based encryption in the relative-leakage model. In our construction, we firstly make use of a notion of new cryptographic primitive, identity-based hash proof system (IB-HPS), to construct a leakage-resilient IB-HPS from lattices in the standard model, which has the same amount of relative leakage as that in [11]. Then, based on our IB-HPS scheme, we construct directly an efficient leakage-resilient identity-based encryption scheme in the model.

International Conference on Information Science and Engineering•Dec 1, 2010•1 citation

Hash Proof System Based on Lattice

Xia Feng, Bo Yang, Qiong Huang +1 more

We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.

International Journal of Advancements in Computing Technology•May 31, 2012•1 citation

Adaptive-ID Secure Identity-Based Signature Scheme from Lattices in the Standard Model

Zecheng Wang, Xuemin Chen, Pingshui Wang

Identity-based signature (IBS) which is a paradigm built on public key cryptography has played a significant role in light-weight authentication. With the advent of the post quantum era, the lattice has become a main mathematical tool to construct quantum-immune cryptographic schemes. By utilizing an admissible hash function with compatible algorithms and lattice trapdoors as basic building blocks, we propose a new IBS scheme over lattices. The scheme is proved existentially unforgeable against adaptive identity attacks and chosen message attacks in the standard model under inhomogeneous short integer solution assumption via the generalized partitioning proof technique. Moreover, the scheme needs only logarithmic basic matrices as master public key while keeping the same private key size and signature size as those of other standard model lattice-based IBS schemes. This construction is the first adaptive-ID secure standard model IBS scheme over lattice with such space efficiency.

IEEE Access•Jan 1, 2017•6 citations

Full Secure Identity-Based Encryption Scheme over Lattices in the Standard Model

Wang Jizhong, Wang Chunxiao

Using a known lattice-based chosen plain-text secure encryption scheme and the Bonsai trees primitive, a identity-based encryption (IBE) scheme is proposed in this paper. A public matrices chosen rule that has been used in a known efficient lattice-based chosen ciphtertext secure encryption scheme is used in this paper to reduce the public key size and the message-to ciphtertext expanse factor. Under the hardness of the decision variant of the learning with errors (LWE) problem, we prove that the proposed IBE scheme is indistinguishable against the adaptive chosen identities and chosen-plaintext attack in the standard model. Since a new public key chosen rule is used in our design scheme, the public key size of the proposed scheme would be short. Moreover, the message-to-ciphtertext expanse factor of this scheme is also controlled efficiently which is nearly closed to that of Gentry's scheme. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed IBE scheme is secure even in quantum-era.

International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC)•Nov 1, 2015•3 citations
As the progress of quantum computers, it is desired to propose many more efficient cryptographic constructions with post-quantum security. In the literatures, almost all cryptographic schemes and protocols can be explained and constructed modularly from certain cryptographic primitives, among which an Identity-Based Hash Proof System (IB-HPS) is one of the most basic and important primitives. Therefore, we can utilize IB-HPSs with post-quantum security to present several types of post-quantum secure schemes and protocols. Up until now, all known IB-HPSs with post-quantum security are instantiated based on latticed-based assumptions. However, all these lattice-based IB-HPSs are either in the random oracle model or not efficient enough in the standard model. Hence, it should be of great significance to construct more efficient IB-HPSs from lattices in the standard model. In this paper, we propose a new smooth IB-HPS with anonymity based on the Learning with Errors (LWE) assumption in the standard model. This new construction is mainly inspired by a classical identity-based encryption scheme based on LWE due to Agreawal et al. in Eurocrypt 2010. And our innovation is to employ the algorithm SampleGaussian introduced by Gentry et al. and the property of random lattice to simulate the identity secret key with respect to the challenge identity. Compared with other existing IB-HPSs in the standard model, our master public key is quite compact. As a result, our construction has much lower overheads on computation and storage.
As a basic and important primitive, hash proof system can be used to construct many cryptographic schemes and protocols. Therefore, it is significant to instantiate more efficient hash proof systems from various assumptions. Although there are many hash proof systems based on various classical assumptions, only a handful of efficient hash proof systems are known based on post-quantum assumptions. In this paper, we present several new hash proof systems based on the standard learning with errors (LWE) problem, which is at least as hard as standard worst-case lattice problems. Comparing with other existing constructions based on lattices, our main advantages are 2-fold: much simpler and more efficient. And our constructions can be easily extended to be identity-based ones and updatable ones. Throughout the paper, our main idea is to base hash proof systems on a new subset indistinguishability problem related to LWE, and employ the property of smooth parameter of q-ary orthogonal lattices to ensure smoothness.
Since hash proof system (HPS) can be utilized to build versatilely cryptographic schemes, the study on realizing this cryptographic primitive has been a very active research area. With the increasing concerns on the huge progress in quantum computing, it urges cryptographers to explore the existence of quantum-resistant HPS schemes, such as the one relying on some lattice-based assumptions. However, most lattice-based HPS proposals are relatively inefficient (e.g., simply outputting one-bit key), even though lattice-based schemes can enjoy many advantageous features: worst-case to average-case reduction, resistance so far to quantum algorithms, and good asymptotic efficiency. Therefore, efficient HPS schemes based on lattice problems are deeply in demand. Through a comprehensive analysis, we found that some lattice-based HPS schemes can be rephrased as their corresponding key encapsulation mechanism (KEM) forms, which generally rely on diverse reconciliation mechanisms and directly imply key exchange protocols under lattice-based assumptions. In this paper, inspired by a novel reconciliation mechanism based on the learning with errors (LWE) problem, we first properly adapt this LWE-based reconciliation mechanism for arbitrary modulus. Then using this improved reconciliation mechanism, we propose an efficient LWE-based HPS scheme which can generate multiple encapsulated key bits and perform better in both computation and storage costs than other related results. Moreover, our proposed lattice-based HPS scheme can be also extended to identity-based and updatable settings for demonstrating its diverse applications.
We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.
Identity-based signature (IBS) which is a paradigm built on public key cryptography has played a significant role in light-weight authentication. With the advent of the post quantum era, the lattice has become a main mathematical tool to construct quantum-immune cryptographic schemes. By utilizing an admissible hash function with compatible algorithms and lattice trapdoors as basic building blocks, we propose a new IBS scheme over lattices. The scheme is proved existentially unforgeable against adaptive identity attacks and chosen message attacks in the standard model under inhomogeneous short integer solution assumption via the generalized partitioning proof technique. Moreover, the scheme needs only logarithmic basic matrices as master public key while keeping the same private key size and signature size as those of other standard model lattice-based IBS schemes. This construction is the first adaptive-ID secure standard model IBS scheme over lattice with such space efficiency.
Using a known lattice-based chosen plain-text secure encryption scheme and the Bonsai trees primitive, a identity-based encryption (IBE) scheme is proposed in this paper. A public matrices chosen rule that has been used in a known efficient lattice-based chosen ciphtertext secure encryption scheme is used in this paper to reduce the public key size and the message-to ciphtertext expanse factor. Under the hardness of the decision variant of the learning with errors (LWE) problem, we prove that the proposed IBE scheme is indistinguishable against the adaptive chosen identities and chosen-plaintext attack in the standard model. Since a new public key chosen rule is used in our design scheme, the public key size of the proposed scheme would be short. Moreover, the message-to-ciphtertext expanse factor of this scheme is also controlled efficiently which is nearly closed to that of Gentry's scheme. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed IBE scheme is secure even in quantum-era.