This paper proposes the first lattice-based sequential aggregate signature （SAS） scheme with lazy verification that is provably secure in the random oracle model. As opposed to large integer factoring and discrete l...This paper proposes the first lattice-based sequential aggregate signature （SAS） scheme with lazy verification that is provably secure in the random oracle model. As opposed to large integer factoring and discrete logarithm based systems, the security of the construction relies on worst-case lattice problem, namely, under the small integer solution （SIS） assumption. Generally speaking, SAS schemes enable any group of signers ordered in a chain to sequentially combine their signatures such that the size of the aggregate signature is much smaller than the total size of all individual signatures. Unlike prior such proposals, the new scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature, and the signer can add its own signature to an unverified aggregate and forward it along immediately, postponing verification until load permits or the necessary public keys are obtained. Indeed, the new scheme does not even require a signer to know the public keys of other signers.展开更多
This paper proposes the first code-based quantum immune sequential aggregate signature(SAS)scheme and proves the security of the proposed scheme in the random oracle model.Aggregate signature(AS)schemes and sequential...This paper proposes the first code-based quantum immune sequential aggregate signature(SAS)scheme and proves the security of the proposed scheme in the random oracle model.Aggregate signature(AS)schemes and sequential aggregate signature schemes allow a group of potential signers to sign different messages respectively,and all the signatures of those users on those messages can be aggregated into a single signature such that the size of the aggregate signature is much smaller than the total size of all individual signatures.Because of the aggregation of many signatures into a single short signature,AS and SAS schemes can reduce bandwidth and save storage;moreover,when a SAS is verified,not only the valid but also the order in which each signer signed can be verified.AS and SAS schemes can be applied to traffic control,banking transaction and military applications.Most of the existing AS and SAS schemes are based either on pairing or Rivest-Shamir-Adleman(RSA),and hence,can be broken by Shor’s quantum algorithm for Integer Factoring Problem(IFP)and Discrete Logarithm Problem(DLP).There are no quantum algorithms to solve syndrome decoding problems.Hence,code-based cryptography is seen as one of the promising candidates for post-quantum cryptography.This paper shows how to construct quantum immune sequential aggregate signatures based on coding theory.Specifically,we construct our scheme with the first code based signature scheme proposed by Courtois,Finiasz and Sendrier(CFS).Compared to the CFS signature scheme without aggregation,the proposed sequential aggregate signature scheme can save about 90%storage when the number of signers is asymptotically large.展开更多
基金supported by the National Natural Science Foundations of China (61173151, 61472309)
文摘This paper proposes the first lattice-based sequential aggregate signature （SAS） scheme with lazy verification that is provably secure in the random oracle model. As opposed to large integer factoring and discrete logarithm based systems, the security of the construction relies on worst-case lattice problem, namely, under the small integer solution （SIS） assumption. Generally speaking, SAS schemes enable any group of signers ordered in a chain to sequentially combine their signatures such that the size of the aggregate signature is much smaller than the total size of all individual signatures. Unlike prior such proposals, the new scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature, and the signer can add its own signature to an unverified aggregate and forward it along immediately, postponing verification until load permits or the necessary public keys are obtained. Indeed, the new scheme does not even require a signer to know the public keys of other signers.
基金This work was supported in part by the National Natural Science Foundation of China under Grant 62072240by the Natural Science Foundation of Jiangsu Province under Grant BK20210330by the National Key Research and Development Program of China under Grant 2020YFB1804604.
文摘This paper proposes the first code-based quantum immune sequential aggregate signature(SAS)scheme and proves the security of the proposed scheme in the random oracle model.Aggregate signature(AS)schemes and sequential aggregate signature schemes allow a group of potential signers to sign different messages respectively,and all the signatures of those users on those messages can be aggregated into a single signature such that the size of the aggregate signature is much smaller than the total size of all individual signatures.Because of the aggregation of many signatures into a single short signature,AS and SAS schemes can reduce bandwidth and save storage;moreover,when a SAS is verified,not only the valid but also the order in which each signer signed can be verified.AS and SAS schemes can be applied to traffic control,banking transaction and military applications.Most of the existing AS and SAS schemes are based either on pairing or Rivest-Shamir-Adleman(RSA),and hence,can be broken by Shor’s quantum algorithm for Integer Factoring Problem(IFP)and Discrete Logarithm Problem(DLP).There are no quantum algorithms to solve syndrome decoding problems.Hence,code-based cryptography is seen as one of the promising candidates for post-quantum cryptography.This paper shows how to construct quantum immune sequential aggregate signatures based on coding theory.Specifically,we construct our scheme with the first code based signature scheme proposed by Courtois,Finiasz and Sendrier(CFS).Compared to the CFS signature scheme without aggregation,the proposed sequential aggregate signature scheme can save about 90%storage when the number of signers is asymptotically large.
