Patent ID: 7080254

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 keys (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 i , . . . , 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 , 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 1 , . . . , p f , and wherein, for at least one integer value l between 1 and m, g l or (−g l ) is a quadratic residue of the body of integers modulo n, and wherein, for at least one integer value s between 1 and m, q s is neither congruent to g s mod n nor congruent to (−g s ) mod n, wherein, for i=1, . . . ,m, q i ≡Q i −v/2 mod n in the case G i ×Q i v =1 mod n and q i =Q i v/2 mod n in the case G i =Q i v mod n; and using at least the private values Q 1 ,Q 2 , . . . ,Q m in an authentication or in a signature method.