Patent Document ID: 7653817
Application ID: 11955047
Patent Flag: 1

Claim One:
1. A method performed by one or more computer processors executing program code stored in memory, of generating and verifying a ring signature Sig of a digital message M communicated between a signer and a verifier, wherein the signer is one of a plurality of t members of a set, wherein each of the members of the set is associated with an identity from the identity set {ID 1 ,. .. , ID t }, wherein the signer is associated with the identity ID s , and wherein 1≦s≦t, the method comprising: generating a first cyclic group G 1 of elements and a second cyclic group G 2 of elements; selecting a bilinear, non-degenerate pairing e capable of generating an element of the second cyclic group G 2 from two elements of the first cyclic group G 1 ; selecting a first generator P of the first cyclic group G 1 and a second generator P′ of the first cyclic group G 1 ; selecting a first secret number s; selecting a second secret number s′; selecting a function H capable of generating an element of the first cyclic group G 1 from a first string of binary digits; generating a public point Q i for each of the t members of the set using the function H and the identity ID i associated with the set member; generating a private point sP′+s′Q s for the signer; generating a message function value P M for the message M using a predetermined function; generating the ring signature Sig using at least the signer's private point sP′+s′Q 1 , the public point Q i of each of the t members of the set, and the message function value P M ; and verifying that the ring signature Sig was generated by a member of the set using at least the public point Q i of each of the t members of the set.