Digital signature method based on braid groups conjugacy and verify method thereof

Abstract

The present invention discloses a digital signature scheme based on braid group conjugacy problem and a verifying method thereof, wherein a signatory S selects three braids xεLB(l), x'εB(l), aεB(l), and considers braid pair (x′,x) as a public key of S, braid a as a private key of S; Signatory S uses hash function h for a message M needing signature to get y=h(M)εB(l); generating a braid bεRB(l) randomly, then signing M with a and b to obtain Sign(M)=abyba; a signature verifying party V obtains the public key of S, calculating the message M by employing hash function h, obtaining the y=h(M); judging whether sign(M) and y, sign(M)x′ and xy are conjugate or not, if yes, sign(M) is a legal signature of message M; the present invention reduces the number of braids involved and the number for conjugacy decision without reducing security, thereby improving the operation efficiency of signature.