Identification and/or signature process

• US 5,987,138 A
• Filed: 04/07/1997
• Issued: 11/16/1999
• Est. Priority Date: 04/09/1996
• Status: Expired due to Fees

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Gilbert, Henri, Cherbonnier, Frederic
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): JACK, TODD M
• Application Number:
  US08/834,923
• Time in Patent Office: 953 Days
• Field of Search: 380/23, 380/30
• US Class Current: 380/30
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

According to the invention, the secret key of the claimant is constituted by k numbers s₁, s₂, . . . , s_k with a low public exponent. The verifier draws k numbers a₁, a₂, . . . , a_k in which the number of non-zero a_i is below a given number p. The claimant or signatory calculates an answer involving an exponential product of form s_i^a.sbsp.1 with i between 1 and k. The verifier calculates another exponential product of form v_i^a.sbsp.1, where the v_i are numbers corresponding to the public key of the claimant or signatory. The verifier then verifies that the result obtained is correct. The choice of the public exponent and the limitation on p make it possible to reduce the number of secrets for equal security and an approximately equal number of multiplications.

Claims

1. A computer implemented method by which a claimant is identified by a verifier with a desired security level, comprising:

selecting a number n, k numbers s₁, s₂, . . . s_k less than n, and an exponent e, wherein n is a product of two prime numbers, k is an integer, and e≦

3;

generating a secret key comprising said k numbers, s₁, s₂, . . . s_k, said secret key being known only to the claimant;

calculating k numbers v₁, v₂, . . . v_k, wherein v_i =s_i^-e mod n, and i is an integer index from 1 to k included;

generating a public key comprising said number n, said numbers v₁, v₂, . . . v_k, and said exponent e, said public key being accessible by the verifier;

drawing by the claimant a number r, wherein 0≦

r≦

n-1;

calculating by a processor in the claimant a control number x, wherein x=r^e mod n;

transmitting said control number x from the claimant to the verifier;

choosing an integer p based on the desired security level, wherein 1<

p<

k;

drawing p integers between 1 and k included;

drawing p numbers a_p '"'"'s such that 1≦

a_p ≦

e-1;

setting a_i =0 for i≠

p and for 1≦

i≦

k;

transmitting a question from said verifier to said claimant, said question comprising said a₁, a₂, . . . , a_k ;

calculating by said processor in the claimant an answer y, wherein ##EQU18## transmitting said answer from the claimant to the verifier;

calculating by a processor in the verifier a verifying expression given by;

##EQU19## verifying the claimant identity by the verifier, wherein the claimant identity is verified if said verifying expression equals the control number x.

3. A method as in claim 1 or 2, wherein all steps are repeated sequentially a number t times.

4. A method as in claim 1 or 2, wherein:

calculating the control number x is performed t times thereby calculating t control numbers in parallel;

transmitting the control number is performed t times in parallel;

transmitting the question is performed t times in parallel;

calculating the answer is performed t times in parallel;

transmitting the answer is performed t times in parallel;

calculating the verifying expressions is performed t times in parallel; and

verifying the claimant identity is performed by the verifier based on the t verifying expressions.

5. A method as in claim 1 or 2, wherein choosing p is performed so that p≈

k/2.

6. A method as in claim 1 or 2, wherein choosing p is performed so that p is within 8.57% of k/2.

7. A method as in claim 1, wherein the product ##EQU22## is calculated by performing the following:

a) setting S=P=1 and d=e-1;

b) calculating S=S·

Π

s_i^a i with 1≦

i≦

k and a_i =d;

c) calculating P=P·

S;

d) reducing d by one unit; and

e) repeating steps b), c) and d) for d>

0.

8. A method as in claim 1, wherein the product ##EQU23## is calculated by performing the following:

a) setting S=P=1 and d=e-1;

b) calculating S=S·

Π

v_i^a i with 1≦

i≦

k and a_i =d;

c) calculating P=P·

S;

d) reducing d by one unit; and

e) repeating steps b), c) and d) for d>

0.

15. A method as in claim 8, wherein the product ##EQU27## is calculated by performing the following:

a) setting S=P=1 and d=e-1;

b) calculating S=S·

Π

v_i^a i with 1≦

i≦

k and a_i =d;

c) calculating P=P·

S;

d) reducing d by one unit; and

e) repeating steps b), c) and d) for d>

0.

2. A computer implemented method by which a claimant is identified by a verifier with a desired security level, comprising:

selecting a number n, k numbers s₁, s₂, . . . s_k less than n, and an exponent e, wherein n is a product of two prime numbers, k is an integer, and e ≦

3;

generating a secret key comprising said k numbers, s₁, s₂, . . . s_k, said secret key being known only to the claimant;

calculating k numbers v₁, v₂, . . . v_k, wherein v_i =s_i^-e mod n, and i is an integer index from 1 to k included;

generating a public key comprising said number n, said numbers v₁, v₂, . . . v_k, and said exponent e, said public key being accessible by the verifier;

drawing by the claimant a number r, wherein 0≦

r≦

n-1;

calculating by a processor in the claimant a control number h, wherein h=H(x) and x=r^e mod n, H being a one-way function;

transmitting said control number h from the claimant to the verifier;

choosing an integer p based on the desired security level, wherein 1<

p<

k;

drawing p integers between 1 and k included;

drawing p numbers a_p '"'"'s such that 1≦

a_p ≦

e-1;

setting a_i =0 for i≠

p and for 1≦

i≦

k;

transmitting a question from said verifier to said claimant, said question comprising said a₁, a₂, . . . , a_k;

calculating by said processor in the claimant an answer y, wherein ##EQU20## transmitting said answer from the claimant to the verifier;

calculating by a processor in the verifier a verifying expression given by;

##EQU21## verifying the claimant identity by the verifier, wherein the claimant identity is verified if said verifying expression equals the control number h.

9. A computer implemented method to create a signature for a message m sent by a claimant and received by a verifier who verifies the signature, comprising:

selecting a number n, k numbers s₁, s₂, . . . s_k less than n, and an exponent e, wherein n is a product of two prime numbers, k is an integer, and e≦

3;

generating a secret key comprising said k numbers s₁, s₂, . . . s_k, said secret key being known only to the claimant;

calculating k numbers v₁, v₂, . . . v_k, wherein v_i =s_i^-e mod n, and i is an integer index from 1 to k included;

generating a public key comprising said number n, said numbers v₁, v₂, . . . v_k, and said exponent e, said public key being accessible by the verifier;

drawing by the claimant a number r, wherein 0<

r<

n-1;

calculating by a processor in the claimant a control number x=r^e mod n;

choosing an integer p based on the desired security level, wherein 1<

p<

k;

drawing p integers between 1 and k included;

drawing p numbers a_p '"'"'s such that 1≦

a_p ≦

e-1 and (a₁, a₂, . . . , a_i, a_k)=H(m,x), H being a one-way function;

setting a_i =0 for i≠

p and for 1≦

i≦

k;

calculating y by said processor in the claimant, wherein ##EQU24## transmitting said y and said a_k '"'"'s from the claimant to the verifier, said y and said a_k '"'"'s forming said signature;

calculating by a processor in the verifier a verifying expression given by;

##EQU25## verifying the claimant signature by the verifier, wherein the claimant signature is verified if the verifying expression equals (a₁, a₂, . . . a_k).

10. A method as in claim 9, wherein all steps are repeated sequentially a number t times.

11. A method as in claim 9, wherein:

calculating the control number x is performed t times thereby calculating t control expressions in parallel;

transmitting the control number is performed t times in parallel;

transmitting the question is performed t times in parallel;

calculating the answer is performed t times in parallel;

transmitting the answer is performed t times in parallel;

calculating the verifying expressions is performed t times in parallel; and

verifying the claimant signature is performed by the verifier based on the t verifying expressions.

12. A method as in claim 9, wherein choosing p is performed so that p≈

k/2.

13. A method as in claim 9, wherein choosing p is performed so that p is within 8.57% of k/2.

14. A method as in claim 9, wherein the product ##EQU26## is calculated by performing the following:

a) setting S=P=1 and d=e-1;

b) calculating S=S·

Π

s_i^a i with 1≦

i≦

k and a_i =d;

c) calculating P=P·

S;

d) reducing d by one unit; and

e) repeating steps b), c) and d) for d>

0.