Study Of Digital Signature Algorithm Based On Lattice Theory

Traditional signatures can no longer meet the development of the digital age,and digital signatures have become an important way to ensure the authenticity,integrity,and non-repudiation of data.Since its inception,digital signatures have developed rapidly,but the development of quantum computers has brought threats to traditional digital signature schemes,leading people to search for post-quantum signature schemes.Lattice cryptography is considered the most promising post-quantum cryptography and can achieve provable security under worst-case assumptions;it is widely used in various cryptographic schemes.In recent decades,lattice signatures have developed rapidly,and lattice-based single-signature schemes have gradually matured.The development of network information has made application scenarios more complex,and users are more concerned about network privacy data.Digital signatures with special functions have emerged to meet more scene requirements.Common types of digital signatures with special functions include attribute signatures,blind signatures,group signatures,ring signatures,proxy signatures,and aggregate signatures.They satisfy more scene requirements and have more research value.This thesis mainly studies the lattice theory digital signature algorithm and innovatively proposes several lattice signature schemes with special functions,including multi-signature,identity-based ring signature,efficient blind signature scheme,and dynamic group signature.The specific achievements are as follows:(1)This thesis proposes two multi-signature schemes,namely the ordered multi-signature and the broadcast multi-signature,to address the problem of high verification cost when all users have signed the information.The multi-signature algorithms do not require verification of each individual signature,but only the final output signature needs to be verified.If the final output signature is verified,it can be said that all members of the group have valid signatures on the information.The proposed multi-signature scheme is designed based on the Short Integer Solution(SIS)on lattice,and for the ordered signature scheme,the previous member signs the information using the SIS one-way function and sends it to the next user,and so on,until the final member outputs the final signature.For the broadcast multi-signature scheme,each member of the group signs the information using the SIS one-way function,and the signatures are sent to a trusted third party for verification.Only when all signatures pass the verification,the third party organizes them into a final signature and sends it to the verifier for verification.To ensure the security of the entire algorithm and prevent side-channel attacks,binomial distribution sampling is used.In order to improve the probability of successful signature output,the bimodal rejection sampling theorem is adopted.This scheme has the characteristics of simple design,high adaptability,and provable security.(2)This thesis proposes an efficient identity-based ring signature scheme to address the problem of difficult key management in the presence of massive keys.In this scheme,the user’s ID is used as the public key,and the member’s private key is generated through an efficient trapdoor derivation algorithm based on lattices,which solves the problem of key management.In order to achieve anonymity in signature,the ISIS zero-knowledge proof and private key padding method are used to construct the signature,and the verifier can verify the correctness of the signature using the ring public key.Through security proof,it can be shown that this ring signature scheme has anonymity under full key exposure and unforgeability under internal corruption.(3)This thesis proposes a blind signature scheme with short public key length to address the issue of long public key and signature length in existing blind signature algorithms.The proposed blind signature scheme has a public key length of only2 klogq,based on the ISIS key generation algorithm.The owner of the information randomly selects an appropriate blinding factor to blind the information and sends the blinded information to the signer.The signer uses the bimodal rejection sampling theorem on lattices to sign the information and sends it back to the owner,who can then unblind the signature to obtain the signer’s signature on the information.Through analysis,it can be shown that this signature scheme satisfies blindness and unforgeability.Finally,an application of blind signature is introduced,namely a privacy-preserving set intersection scheme based on lattice blind signature,which has certain advantages in terms of computational cost.(4)This thesis proposes a lattice-based group signature scheme to address the issue of efficient addition and removal of members as well as revocation of invalid signatures in group signature schemes.In this scheme,the group administrator generates the signature private key and revocation tokens for group users,which are unforgeable by other users.The validity of the signature and revocation tokens is ensured through zero-knowledge proofs.The revocation list(RL)is used to check whether a signing user has been revoked,enabling local revocation functionality.For the addition and removal of users,the administrator can simply make an announcement after authentication,without the need to update user keys,to achieve dynamic functionality.This scheme has anonymity and unforgeability and can easily implement dynamic addition and removal of members.