Patent ID: 7245718

Claim:
A method for authenticating d i identities using two prime numbers p and q such that q|p−1, each identity includes a private key s i and a public key v i , and a publicly known generator is α such that α q ≡1 (mod p), comprising: providing, a verifier, with an ordered list of the public keys v i ; selecting uniformly at random, by a prover, a non-negative number r less than q; sending a number x=α r (mod p) from the prover to a verifier; selecting uniformly at random, by the verifier, a non-negative number e less than 2 (t+logd) , where log is base 2 , and a number t is a predetermined security parameter; receiving by the prover from the verifier the number e; generating, by the prover, a number y=r+Σ i s i *e i (mod q); sending by the prover to the verifier the number y; determining if an equality x=α y *Π i (v i ) e i (mod p) is true; and accepting the prover as having the d i identities if and only if the equality is true.