Research On Post Quantum Ring Signature Scheme

The security of classical public key cryptography mainly depends on the hardness of large integer factorization problem and discrete logarithm problem.However,these two mathematical problems have fast algorithm under quantum computer.Thus,with the rapid development of quantum computer,these classical public key cryptographic schemes have been greatly challenged.The cryptography..community calls cryptographic schemes which can resist quantum computer attacks as post-quantum schemes,and the design of such schemes has become a hot research issue.The powerful ring signature scheme is also highly valued by the cryptography community because of its wide application in the blockchain.Ring signature is a variant of digital signature introduced by Rivest et al.,which can certify that one among a particular set of parties has signed a particular message,without reveal who is the signer.There are many practical variants of ring signature,and the most widely used ones are:linkable ring signature,threshold ring signature,repudiable ring signature,etc.This thesis mainly studies the design of efficient post-quantum secure ring signature and its variants.The main contributions include the following three aspects.Ring Signature and Linkable Ring Signature:This thesis designs an efficient ring signature and linkable ring signature scheme based on the MP-LWE problem,respectively.In terms of efficiency,the signature size of our linkable ring signature is 2-40× shorter than the previous MP-LWEbased scheme.The larger the ring size is,the greater the advantage is.In terms of technology,we first design an identification scheme based on the MP-LWE problem,and then we use the framework proposed by Yuen et al.(Crypto 2021)to transform the identification scheme to the MP-LWE based ring signature scheme.Finally,we show how to achieve linkability from this ring signature by using a collision resistant hash function.This thesis also provides available parameter options for our(linkable)ring signature scheme to achieve 128 bits of security.Threshold Ring Signature:This thesis proposes a compact latticebased threshold ring signature scheme.In terms of efficiency,the signature size our scheme is at least 60 × smaller than the previous scheme.In terms of technology,this thesis combines the ideas of aggregated signature and zeroknowledge proof in threshold ring signature for the first time.The core idea of our scheme is that a group of t signers first generate an aggregated signature by interacting with each other,then they compute a zero-knowledge proof to prove that the aggregated signature is indeed generated by t individuals together.Since there are only one aggregated signature and one proof in our final signature,the resulting signature is very succinct.To achieve this goal,this thesis provide a lattice-based t-out-of-N proof protocol for the first time.This protocol allows the signer to prove to the verifier that the signature is valid without revealing their identity.Our t-out-of-N proof protocol may also be used in other protocols,and thus has its own independent interest.Finally,we also provide a parameter.option for our threshold ring signature scheme to achieve 128 bits of security.Repudiable Ring Signature:This thesis proposes the first formal definition of repudiation-unforgeability and gives the first logarithmic-size repudiable ring signature scheme.The core idea of our scheme is that:we use a somewhere perfectly binding hash function to compress the ring R,and then use the digest of R to calculate signatures.Finally,we also point out an error in their thesis.Park et al.claimed that their scheme satisfies adaptive anonymity against adversarially chosen keys,but we find that their scheme does not satisfy this property.To illustrate this,we construct a special attack against the anonymity of their scheme.