Patent ID: 7386122

Claim:
A computer implemented process comprising: obtaining a set of one or more private values Q 1 , Q 2 , . . . , Q m and respective public values G 1 , G 2 , . . . , G m , each pair of values Q i , G i verifying either the equation G i ·Q i v ≡1 mod n or the equation G i ≡Q i v mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p 1 , . . . , p f , at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2 k , and wherein k is a security parameter having an integer value greater than 1, and wherein each public value G i for i=1, . . . , m is such that G i ≡g i 2 mod n, wherein g i for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p i , . . . p f , and g i is a non-quadratic residue of the ring of integers modulo n; receiving a commitment R from a demonstrator, the commitment R having a value computed such that: R=r v mod n, wherein r is an integer randomly chosen by the demonstrator; choosing m challenges d 1 , d 2 , . . . , d m randomly; sending the challenges d 1 , d 2 , . . . , d m to the demonstrator; receiving a response D from the demonstrator, the response D having a value computed such that: D=r●Q 1 d 1 ●Q 2 d 2 ● . . . ●Q m d m mod n; and determining that the demonstrator is authentic if the response D has a value such that: D v ●G 1 ε 1 d 1 ●G 2 ε 2 d 2 ● . . . ●G m ε m d m mod n is equal to the commitment R, wherein, for i=1, . . . , m, ε i =+1 in the case G i ●Q i v =1 mod n and ε i =−1 in the case G i =Q i v mod n.