Patent ID: 7725724

Claim:
A digital signature method to be performed by a computer based on braid group conjugacy problem, parameters involved in this method comprising a signatory (S), a signature verifying party (V), a message (M) needing signature, a braid group B n (l) divided into a left subgroup LB m (l) and a right subgroup RB n−1−m (l), an integer n for a number of generators in the braid group B n (l), an integer m for a number of generators in a left subgroup LB m (l), an integer l for an upper bound of a length of a braid, a one way hash function h from bit sequence {0, 1}* to braid groups B n (l); said signature method comprising the following steps of: Step 1. the signatory (S) selecting a braid x generated from the left subgroup LB m (l), a second braid x′ generated from the braid group B n (l), and a third braid a generated from the braid group B n (l), by the computer, wherein the computer is adapted to making them meet x′=a′xa, and considering braid pair (x′,x) as a public key of signatory (S), a as a private key of signatory (S); Step 2. signatory (S) using hash function h for message (M) needing signature, by the computer, wherein the computer is adapted to get y=h(M) from the braid group B n (l); Step 3. generating a braid b from the right subgroup RB n−1−m (l) at random, by the computer, wherein the computer is adapted to signing the message (M) with the private key a and a generated random braid b to obtain Sign(M)=a −1 byb −1 a; and Step 4. the signatory (S) outputting, by the computer, message (M) and a signature of message (M) Sign(M).