Secure user identification based on constrained polynomials

• US 6,076,163 A
• Filed: 10/20/1997
• Issued: 06/13/2000
• Est. Priority Date: 10/20/1997
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.), Onboard Security Inc. (Qualcomm, Inc.), NTRU Cryptosystems Incorporated (Security Innovation Incorporated)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Yin, Yiqun Lisa, Robshaw, Matthew John Barton, Lieman, Daniel Bennett, Kaliski, Jr., Burton S., Hoffstein, Jeffrey
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US08/954,712
• Time in Patent Office: 967 Days
• Field of Search: 380/28, 380/21, 380/23, 380/24, 380/30, 380/283, 380/285, 709/228, 713/176, 713/168, 713/170
• US Class Current: 713/168
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

Methods and apparatus for providing secure user identification or digital signatures based on evaluation of constrained polynomials. In an exemplary user identification technique, a prover sends a verifier a commitment signal representative of a first polynomial satisfying a first set of constraints. The verifier sends the prover a challenge signal representative of a second polynomial satisfying a second set of constraints. The prover generates a response signal as a function of (i) information used to generate the commitment signal, (ii) a challenge signal, and (iii) a private key polynomial of the prover, such that the response signal is representative of a third polynomial satisfying a third set of constraints. The verifier receives the response signal from the prover, and authenticates the identity of the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover. In a digital signature technique, the challenge signal may be generated by the prover applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and the prover sends the message to the verifier. The verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover. The constraints on the polynomials are selected such that an attacker will find it very difficult to recover the private key polynomial from the partial information sent between the prover and verifier.

Claims

1. An authentication method, carried out between a prover and a verifier, the method comprising the steps of:

generating a response signal as a function of (i) information used to generate a commitment signal representative of a first polynomial, (ii) a challenge signal representative of a second polynomial, and (iii) a private key of the prover, such that the response signal is representative of a third polynomial having two or more terms and satisfying a set of constraints; and

sending the response signal from the prover to the verifier, such that the verifier can authenticate a communication from the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover.

2. The method of claim 1 wherein the first polynomial satisfies a first set of constraints, the second polynomial satisfies a second set of constraints, and the third polynomial satisfies a third set of constraints.

3. The method of claim 1 wherein the generating step includes computing the third polynomial as the first polynomial times the sum of the private key and the second polynomial.

4. The method of claim 1 further including the step of sending the commitment signal from the prover to the verifier prior to the step of generating the response signal.

5. The method of claim 4 wherein the challenge signal is generated by the verifier and sent as a challenge to the prover in response to receipt of the commitment signal.

6. The method of claim 1 wherein the verifier authenticates the identity of the prover based on the result of evaluating the response signal.

7. The method of claim 1 wherein the challenge signal is a simulated challenge signal generated by the prover applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and the method further includes the step of sending the message from the prover to the verifier.

8. The method of claim 7 wherein the prover sends the simulated challenge signal to the verifier as part of a digital signature on the message.

9. The method of claim 7 wherein the verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover.

10. The method of claim 1 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x);

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier authenticates a communication from the prover by comparing A_h (x) to A_g (x)(A_f (x)+A_c (x)), where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

11. The method of claim 1 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x);

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values ai where A_f (x) is a function of f(x); and

(v) the verifier authenticates a communication from the prover by comparing A_f (S) to A_g (S)*(A_f (S)+A_c (S)), where A_c (S) is obtained by evaluating a polynomial A_h (x) at the values α

_i, A_c (S) is obtained by evaluating a polynomial A_f (x) at the values α

_i, and A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

12. The method of claim 1 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (x) and a message, wherein A_g (x) and the response signal represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier recovers c(x) by applying the hash function to A_g (x) and the message, and authenticates the digital signature by comparing A_g (x) to A_g (x)(A_f (x)+A_c (x)) where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

13. The method of claim 1 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (S) and a message, wherein A_g (S) and the response signal represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier recovers c(x) by applying the hash function to A_g (S) and the message, and authenticates the digital signature by comparing A_h (S) to A_g (S)(A_f (S)+A_c (S)) where A_h (S) is obtained by evaluating A_h (x) at the values α

_i, A_c (S) is obtained by evaluating A_c (x) at the values α

_i, and A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

14. The method of claim 1 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (x) and a message, wherein c(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier uses c(x) and h(x) to compute A_c (x) and A_h (x), respectively, recovers A_g (x) by computing A_h (x)(A_f (x)+A_c (x))^-1, and then authenticates the digital signature by comparing c(x) to the result of applying the hash function to A_g (x) and the message, where A_h (x) and A_c (x) are functions of h(x) and c(x) , respectively.

15. The method of claim 1 wherein:

(i) the first polynomial is g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to a polynomial g'"'"'(x) computed as A_g (x)+m where A_g (x) is a function of g(x) and m is a message, and wherein g'"'"'(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier computes c(x) by applying the hash function to g'"'"'(x), recovers A_g (x) by computing A_h (x)(A_f (x)+A_c (x))^-1, recovers the message m by computing g'"'"'(x)-A_g (x), and then authenticates the digital signature by determining if m has an expected redundancy, where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

16. The method of claim 1 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (S) and a message, wherein c(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f (x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier uses c(x) and h(x) to compute A_c (S) and A_h (S), respectively, recovers A_g (S) by computing A_h (S)(A_f (S)+A_c (S))^-1, and then authenticates the digital signature by comparing c(x) to the result of applying the hash function to A_g (S) and the message, where A_h (S) and A_c (S) are functions of h(x) and c(x), respectively, evaluated at the values α

_i.

17. The method of claim 1 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

ⁱ, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash unction to a polynomial g'"'"'(x) computed as A_g (S)+m where in is a message, and wherein g'"'"'(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i, where A_f (x) is a function of f(x); and

(v) the verifier computes c(x) by applying the hash function to g'"'"'(x), recovers A_g (S) by computing A_h (S)(A_f (S)+A_c (S))^-1, recovers the message m by computing g'"'"'(x)-A_g (S), and then authenticates the digital signature by determining if m has an expected redundancy, where A_h (S) and A_c (S) are functions of h(x) and c(x), respectively, evaluated at the values α

ⁱ.

18. An apparatus for implementing an authentication process between a prover and a verifier, the apparatus comprising:

a memory for storing a private key of the prover; and

a processor coupled to the memory and operative to generate a response signal as a function of (i) information used to generate a commitment signal representative of a first polynomial, (ii) a challenge signal representative of a second polynomial, and (iii) the private key of the prover, such that the response signal is representative of a third polynomial having two or more terms and satisfying a set of constraints, wherein the processor is further operative to send the response signal from the prover to the verifier, such that the verifier can authenticate a communication from the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover.

19. The apparatus of claim 18 wherein the first polynomial satisfies a first set of constraints, the second polynomial satisfies a second set of constraints, and the third polynomial satisfies a third set of constraints.

20. The apparatus of claim 18 wherein the processor is further operative to compute the third polynomial as the first polynomial times the sum of the private key and the second polynomial.

21. The apparatus of claim 18 wherein the processor is further operative to send the commitment signal from the prover to the verifier prior to generating the response signal.

22. The apparatus of claim 21 wherein the challenge signal is generated by the verifier and sent as a challenge to the prover in response to receipt of the commitment signal.

23. The apparatus of claim 18 wherein the verifier authenticates the identity of the prover based on the result of a result of evaluating the response signal.

24. The apparatus of claim 18 wherein the processor is further operative to generate the challenge signal as a simulated challenge signal by applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and to send the message from the prover to the verifier.

25. The apparatus of claim 24 wherein the processor is further operative to send the simulated challenge signal to the verifier as part of a digital signature on the message.

26. The apparatus of claim 24 wherein the verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover.

27. The apparatus of claim 18 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x);

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier authenticates a communication from the prover by comparing A_h (x) to A_g (x)(A_f (x)+A_c (x)), where A_h (x) and A_c (x) are functions of h(x) and c(x) respectively.

28. The apparatus of claim 18 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x);

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier authenticates a communication from the prover by comparing A_h (S) to A_g (S)*(A_f (S)+A_c (S)) , where A_h (S) is obtained by evaluating a polynomial A_h (x) at the values α

_i, A_c (S) is obtained by evaluating a polynomial A_c (x) at the values α

_i, and A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

29. The apparatus of claim 18 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (x) and a message, wherein A_g (x) and the response signal represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x) ; and

(v) the verifier recovers c(x) by applying the hash function to A_g (x) and the message, and authenticates the digital signature by comparing A_h (x) to A_g (x)(A_f (x)+A_c (x)) where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

30. The apparatus of claim 18 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (S) and a message, wherein A_g (S) and the response signal represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier recovers c(x) by applying the hash function to A_g (S) and the message, and authenticates the digital signature by comparing A_h (S) to A_g (S)(A_f (S)+A_c (S)) where A_h (S) is obtained by evaluating A_h (x) at the values α

_i, A_c (S) is obtained by evaluating A_c (x) at the values α

_i, and A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

31. The apparatus of claim 18 wherein:

(i) the first polynomial is a polynomial A_g (x) which is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (x) and a message, wherein c(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier uses c(x) and h(x) to compute A_c (x) and A_h (x), respectively, recovers A_g (x) by computing A_h (x)(A_f (x)+A_c (x))^-1, and then authenticates the digital signature by comparing c(x) to the result of applying the hash function to A_g (x) and the message, where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

32. The apparatus of claim 18 wherein:

(i) the first polynomial is g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to a polynomial g'"'"'(x) computed as A_g (x)+m where A_g (x) is a function of g(x) and m is a message, and wherein g'"'"'(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key is a polynomial A_f (x) which is a function of f(x); and

(v) the verifier computes c(x) by applying the hash function to g'"'"'(x), recovers A_g (x) by computing A_h (x)(A_f (x)+A_c (x))^-1, recovers the message m by computing g'"'"'(x)-A_g (x), and then authenticates the digital signature by determining if m has an expected redundancy, where A_h (x) and A_c (x) are functions of h(x) and c(x), respectively.

33. The apparatus of claim 18 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to A_g (S) and a message, wherein c(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier uses c(x) and h(x) to compute A_c (S) and A_h (S), respectively, recovers A_g (S) by computing A_h (S)(A_f (S)+A_c (S))^-1, and then authenticates the digital signature by comparing c(x) to the result of applying the hash function to A_g (S) and the message, where A_h (S) and A_c (S) are functions of h(x) and c(x), respectively, evaluated at the values α

_i.

34. The apparatus of claim 18 wherein:

(i) the commitment signal corresponds to A_g (S), which is a polynomial A_g (x) evaluated at a set S of values α

_i, where the polynomial A_g (x) is a function of a polynomial g(x), wherein x is an integer value;

(ii) the second polynomial is a polynomial c(x) generated by applying a hash function to a polynomial g'"'"'(x) computed as A_g (S)+m where m is a message, and wherein g'"'"'(x) and the third polynomial represent a digital signature which is sent with the message from the prover to the verifier;

(iii) the third polynomial is a polynomial h(x) computed as g(x)*(f(x)+c(x)), where * denotes reduced polynomial multiplication and f(x) is a polynomial corresponding to the private key;

(iv) the public key corresponds to A_f (S) and is obtained by evaluating a polynomial A_f (x) at the values α

_i where A_f (x) is a function of f(x); and

(v) the verifier computes c(x) by applying the hash function to g'"'"'(x), recovers A_g (S) by computing A_h (S)(A_f (S)+A_c (S))^-1, recovers the message m by computing g'"'"'(x)-A_g (S), and then authenticates the digital signature by determining if m has an expected redundancy, where A_h (S) and A_c (S) are functions of h(x) and c(x), respectively, evaluated at the values α

_i.

35. An authentication method, carried out between a prover and a verifier, the method comprising the steps of:

receiving in the verifier a response signal from the prover generated as a function of (i) information used to generate a commitment signal representative of a first polynomial, (ii) a challenge signal representative of a second polynomial, and (iii) a private key of the prover, such that the response signal is representative of a third polynomial having two or more terms and satisfying a set of constraints; and

authenticating in the verifier a communication from the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover.

36. An apparatus for implementing an authentication process between a prover and a verifier, the apparatus comprising:

a memory associated with the verifier for storing a public key of the prover; and

a processor coupled to the memory and operative to receive a response signal from the prover generated as a function of (i) information used to generate a commitment signal representative of a first polynomial, (ii) a challenge signal representative of a second polynomial, and (iii) a private key of the prover, such that the response signal is representative of a third polynomial having two or more terms and satisfying a set of constraints; and

to authenticate a communication from the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover.