Zero-knowledge proof cryptography methods and devices
OwnerLouis Guillou, Jean-Jacques Quisquaterinventors
Life of this patent
Estimating the term…
Abstract
A cryptography method involving a keyholder having a number m≧1 of private keys Q1, Q2, . . . , Qm and respective public keys G1, G2, . . . , Gm, each pair of keys (Qi, Gi) (where i=1, . . . , m) satisfying either the relationship G1=Qiv mod n or the relationship Gi×Qiv=1 mod n, where n is a public integer equal to the product of f (where f>1) private prime factors p1, . . . , pf, at least two of which are separate, and the exponent v is a public integer equal to a power of 2. Disclosed is what mathematical structure may be imparted to the public keys for it to be impossible to calculate said private keys from said public parameters in a reasonable time unless said prime factors are known. Devices adapted to implement the method are also disclosed.
Claims20
An asymmetrical key cryptography method involving a processor-implemented keyholder having a number m≧1 of private keys Q1, Q2, . . . , Qm and respective public keys G1, G2, . . . , Gm, each pair of keys (Qi, Gi) (where i=1, . . . , m ) satisfying either the relationship Gi=Qiv mod n or the relationship Gi×Qiv=1 mod n, where n is a public integer equal to the product of f(where f>1) private prime factors p1, . . . , pf, at least two of which are separate, and the exponent v is a public integer equal to a power of 2, wherein the method comprises:
- arranging, by a processor, exponent v to have the relationship v=2b+k,
- where k is a strictly positive integer and b=max(b1, . . . , bf), where bj (where j=1, . . . , f) is the highest integer such that (pj−1)/2bj−1 is even;
- and
- arranging, by the processor each public key Gi (where i=1, . . . , m ) to have the form Gi=gi2ai, mod n,
- where the base numbers gi are integers strictly greater than 1 and the numbers ai, are integers such that 1≦ai, ≦b and at least one of them is strictly greater than 1.
Dependencies are inferred from the claim text.