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

Concurrency and Computation Practice and Experience

Pre‐image sample algorithm with irregular Gaussian distribution and construction of identity‐based signature

Jianhua Yan, Licheng Wang, Jing Li, Muzi Li, Yixan Yang, Wenbin Yao

Published Aug 27, 2016• 3 citations
Publisher

Abstract

Summary Lattice has become an attractive cryptographic tool due to its potential resistance to quantum attacks, worst‐case hardness, simple computation kind, and flexibility. The pre‐image sample algorithm is the most fundamental algorithm in lattice‐based cryptography for its comprehensive applications in various primitives. Currently, due to Micciancio and Peikert (MP) sample algorithm is the most efficient pre‐image sample algorithm. However, this algorithm also needs massive computations. On the one hand, it expenses the cube of the lattice dimension multiplications over reals to set matrices as Gaussian parameters. On the other hand, it needs complex discrete convolution computations. First, this paper proposes an efficient pre‐image sample algorithm with outputs obeying irregular Gaussian distribution. Two measures are adopted to prevent the leakage of the geometrical property of trapdoor caused by irregular Gaussian outputs. A variant of MP trapdoor is proposed, and a new trapdoor is randomly assembled from a big enough space in each sample. Although still using a matrix as the Guassian parameter, in the proposed algorithm, the computational cost to set Gaussian parameters is zero. Meanwhile, the computational overhead for every sample is far less than that of MP sample algorithm. Second, to demonstrate the security and efficiency of the proposed sample algorithm, a hierarchical identity‐based signature scheme is put forward. This scheme is proved existentially unforgeable against selective identity adaptively chosen‐message attacks. Furthermore, the theoretical analysis shows that the proposed identity‐based signature is more efficient than the existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.

DOI
10.1002/cpe.3925

Related papers

Efficient and strongly unforgeable identity‐based signature scheme from lattices in the standard model

Zhenhua Liu, Yupu Hu, Xiangsong Zhang +1 more

ABSTRACT An identity‐based signature scheme from lattices is constructed. The scheme is obtained from a modification of Agrawal, Boneh, and Boyen's lattice identity‐based encryption scheme. In this construction, we use two distinct trapdoors for finding short bases. One trapdoor enables the real implementation to generate short bases for all lattices. The other trapdoor enables the simulator to generate short bases for all lattices. Furthermore, the generating short bases are used to sample short vectors as signatures. Our scheme is computationally efficient. The scheme's strong unforgeability is proven in the standard model and rests on the hardness of the small integer solution problem. Finally, we extend the basic construction to obtain a hierarchical identity‐based signature scheme. Copyright © 2012 John Wiley & Sons, Ltd.

Security and Communication Networks•Mar 7, 2012•29 citations

Novel efficient identity-based signature on lattices

Jiangshan Chen, Yupu Hu, Liang Hong-mei +1 more

With the rapid development of electronic information technology, digital signature has become an indispensable part of our lives. Traditional public key certificate cryptosystems cannot overcome the limitations of certificate management. Identity-based cryptosystems can avoid the certificate management issues. The development of quantum computers has brought serious challenges to traditional cryptography. Post-quantum cryptography research is imperative. At present, almost all post-quantum identity-based signature (IBS) schemes are constructed using Gaussian sampling or trapdoor technologies. However, these two technologies have a great impact on computational efficiency. To overcome this problem, we construct an IBS scheme on lattices by employing Lyubashevsky’s signature scheme. Based on the shortest vector problem on lattices, our scheme does not use Gaussian sampling or trapdoor technologies. In the random oracle model, it is proved that our scheme is strongly unforgeable against adaptive chosen messages and identity attacks. The security level of our scheme is strongly unforgeable, which is a higher level than the existential unforgeability of other schemes. Compared with other efficient schemes, our scheme has advantages in computation complexity and security.

Frontiers of Information Technology & Electronic Engineering•Jul 2, 2020•7 citations

Identity‐based signcryption from lattices

Jianhua Yan, Licheng Wang, Mianxiong Dong +2 more

Abstract Signcryption as a cryptographic primitive can carry out signature and encryption simultaneously at a remarkably reduced cost. Identity‐based cryptography is more convenient than public key infrastructure‐based cryptography in certificate management. As a result, identity‐based signcryption has been studied extensively, and many efficient and provably secure constructions have been proposed. However, most of these schemes are based on intractability assumptions from number theory, and these assumptions have been threatened by the booming quantum computation. Therefore, a recent trend in cryptography is to construct cryptosystems that are based on lattice‐based intractability assumptions because of their plausible features of quantum attack resistance. In this paper, several identity‐based signcryption schemes from lattice hardness assumptions are proposed. In the standard model, these schemes are indistinguishable againstinneradaptively chosen ciphertext attacks (IND‐CCA2) and strongly unforgeable againstinnerchosen message attacks. In our construction, it does not matter whether the original encryption scheme used to construct signcryption is deterministic or probabilistic; the resulted signcryption schemes can reach IND‐CCA2 security. To achieve this, we carefully combine three techniques—the identity‐based encryption from lattice due to Agrawal–Boneh–Boyen (EUROCRYPT 2010), the framework of lattice‐based short signature due to Boyen (Public Key Cryptography 2010), and the Canetti–Halevi–Katz (abbr. CHK) technique, with necessary and tailored optimization—for transforming an (ℓ+ 1)‐level indistinguishable under chosen plaintext attack secure hierarchical identity‐based encryption (HIBE) into anℓlevel IND‐CCA2 secure HIBE scheme. In addition, our security proof also contains a more efficient simulation tool that might have separate interest in cryptographic applications. Copyright © 2015 John Wiley & Sons, Ltd.

Security and Communication Networks•Jul 23, 2015•9 citations

Trapdoors for hard lattices and new cryptographic constructions

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•2,498 citations

A Lattice-based Signcryption Scheme Without Trapdoors

LU Xiu-hua, Wen Qiao-yan, Licheng Wang +1 more

The existing lattice-based signcryption schemes are based on trapdoor generation algorithm and preimage sample algorithm. However, both algorithms are complex, require a lot of time to run, and affect the efficiency of latticed-based signcryption schemes deeply. To solve this problem, the first lattice-based signcryption scheme without trapdoor generation algorithm and preimage sample algorithm is proposed, with the help of the technique of lattice signatures without trapdoors and the associated signature compression technique, as well as the encryption method based on the learning with errors assumption. The scheme achieves indistinguishability against adaptive chosen ciphertext attacks under the learning with errors assumption. It also achieves existential unforgeability against adaptive chosen message attacks under the small integer solution assumption. The proposed scheme is not only quantum resistant, but also efficient.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY•Sep 19, 2016•7 citations

An Efficient Identity-based Signcryption from Lattice

Xiufeng Zhao, Xiang Wang

Signcryption is a cryptographic primitive that can provide valid solution for authentication and confidentiality.In this paper, an efficient identity-based signcryption scheme from lattice was proposed.Our scheme based on Macciancio and Piekert's trapdoor generation method and delegate algorithm for lattice.Our main idea is that establish the identity-based system master key via trapdoor generation method for lattice, and extract user's key by trapdoor delegate algorithm.With the aid of random oracle, we prove that the proposed scheme has CCA security under the learning with errors (LWE) assumption and unforgeability against adaptive chosen messages attacks under the small integer solution (SIS) assumption.Comparison with signature-then-encryption approach shows that our scheme is efficient.

International Journal of Security and Its Applications•Mar 31, 2014•3 citations
Summary Lattice has become an attractive cryptographic tool due to its potential resistance to quantum attacks, worst‐case hardness, simple computation kind, and flexibility. The pre‐image sample algorithm is the most fundamental algorithm in lattice‐based cryptography for its comprehensive applications in various primitives. Currently, due to Micciancio and Peikert (MP) sample algorithm is the most efficient pre‐image sample algorithm. However, this algorithm also needs massive computations. On the one hand, it expenses the cube of the lattice dimension multiplications over reals to set matrices as Gaussian parameters. On the other hand, it needs complex discrete convolution computations. First, this paper proposes an efficient pre‐image sample algorithm with outputs obeying irregular Gaussian distribution. Two measures are adopted to prevent the leakage of the geometrical property of trapdoor caused by irregular Gaussian outputs. A variant of MP trapdoor is proposed, and a new trapdoor is randomly assembled from a big enough space in each sample. Although still using a matrix as the Guassian parameter, in the proposed algorithm, the computational cost to set Gaussian parameters is zero. Meanwhile, the computational overhead for every sample is far less than that of MP sample algorithm. Second, to demonstrate the security and efficiency of the proposed sample algorithm, a hierarchical identity‐based signature scheme is put forward. This scheme is proved existentially unforgeable against selective identity adaptively chosen‐message attacks. Furthermore, the theoretical analysis shows that the proposed identity‐based signature is more efficient than the existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.
ABSTRACT An identity‐based signature scheme from lattices is constructed. The scheme is obtained from a modification of Agrawal, Boneh, and Boyen's lattice identity‐based encryption scheme. In this construction, we use two distinct trapdoors for finding short bases. One trapdoor enables the real implementation to generate short bases for all lattices. The other trapdoor enables the simulator to generate short bases for all lattices. Furthermore, the generating short bases are used to sample short vectors as signatures. Our scheme is computationally efficient. The scheme's strong unforgeability is proven in the standard model and rests on the hardness of the small integer solution problem. Finally, we extend the basic construction to obtain a hierarchical identity‐based signature scheme. Copyright © 2012 John Wiley & Sons, Ltd.
With the rapid development of electronic information technology, digital signature has become an indispensable part of our lives. Traditional public key certificate cryptosystems cannot overcome the limitations of certificate management. Identity-based cryptosystems can avoid the certificate management issues. The development of quantum computers has brought serious challenges to traditional cryptography. Post-quantum cryptography research is imperative. At present, almost all post-quantum identity-based signature (IBS) schemes are constructed using Gaussian sampling or trapdoor technologies. However, these two technologies have a great impact on computational efficiency. To overcome this problem, we construct an IBS scheme on lattices by employing Lyubashevsky’s signature scheme. Based on the shortest vector problem on lattices, our scheme does not use Gaussian sampling or trapdoor technologies. In the random oracle model, it is proved that our scheme is strongly unforgeable against adaptive chosen messages and identity attacks. The security level of our scheme is strongly unforgeable, which is a higher level than the existential unforgeability of other schemes. Compared with other efficient schemes, our scheme has advantages in computation complexity and security.
Abstract Signcryption as a cryptographic primitive can carry out signature and encryption simultaneously at a remarkably reduced cost. Identity‐based cryptography is more convenient than public key infrastructure‐based cryptography in certificate management. As a result, identity‐based signcryption has been studied extensively, and many efficient and provably secure constructions have been proposed. However, most of these schemes are based on intractability assumptions from number theory, and these assumptions have been threatened by the booming quantum computation. Therefore, a recent trend in cryptography is to construct cryptosystems that are based on lattice‐based intractability assumptions because of their plausible features of quantum attack resistance. In this paper, several identity‐based signcryption schemes from lattice hardness assumptions are proposed. In the standard model, these schemes are indistinguishable againstinneradaptively chosen ciphertext attacks (IND‐CCA2) and strongly unforgeable againstinnerchosen message attacks. In our construction, it does not matter whether the original encryption scheme used to construct signcryption is deterministic or probabilistic; the resulted signcryption schemes can reach IND‐CCA2 security. To achieve this, we carefully combine three techniques—the identity‐based encryption from lattice due to Agrawal–Boneh–Boyen (EUROCRYPT 2010), the framework of lattice‐based short signature due to Boyen (Public Key Cryptography 2010), and the Canetti–Halevi–Katz (abbr. CHK) technique, with necessary and tailored optimization—for transforming an (ℓ+ 1)‐level indistinguishable under chosen plaintext attack secure hierarchical identity‐based encryption (HIBE) into anℓlevel IND‐CCA2 secure HIBE scheme. In addition, our security proof also contains a more efficient simulation tool that might have separate interest in cryptographic applications. Copyright © 2015 John Wiley & Sons, Ltd.
We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
The existing lattice-based signcryption schemes are based on trapdoor generation algorithm and preimage sample algorithm. However, both algorithms are complex, require a lot of time to run, and affect the efficiency of latticed-based signcryption schemes deeply. To solve this problem, the first lattice-based signcryption scheme without trapdoor generation algorithm and preimage sample algorithm is proposed, with the help of the technique of lattice signatures without trapdoors and the associated signature compression technique, as well as the encryption method based on the learning with errors assumption. The scheme achieves indistinguishability against adaptive chosen ciphertext attacks under the learning with errors assumption. It also achieves existential unforgeability against adaptive chosen message attacks under the small integer solution assumption. The proposed scheme is not only quantum resistant, but also efficient.
Signcryption is a cryptographic primitive that can provide valid solution for authentication and confidentiality.In this paper, an efficient identity-based signcryption scheme from lattice was proposed.Our scheme based on Macciancio and Piekert's trapdoor generation method and delegate algorithm for lattice.Our main idea is that establish the identity-based system master key via trapdoor generation method for lattice, and extract user's key by trapdoor delegate algorithm.With the aid of random oracle, we prove that the proposed scheme has CCA security under the learning with errors (LWE) assumption and unforgeability against adaptive chosen messages attacks under the small integer solution (SIS) assumption.Comparison with signature-then-encryption approach shows that our scheme is efficient.