Secure user identification based on ring homomorphisms

• US 6,959,085 B1
• Filed: 05/03/2000
• Issued: 10/25/2005
• Est. Priority Date: 05/03/1999
• Status: Expired due to Fees

• Current Assignee: Onboard Security Inc. (Qualcomm, Inc.)
• Original Assignee: NTRU Cryptosystems Incorporated (Security Innovation Incorporated)
• Inventors: Lieman, Daniel, Silverman, Joseph H., Hoffstein, Jeffrey
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): ZIA, SYED
• Application Number:
  US09/564,112
• Time in Patent Office: 2,001 Days
• Field of Search: 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, includes the steps: selection by the first user of a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ: R→B, and publication by the first user of the public key; generation of the challenge communication by the second user that includes selection of a challenge c in the ring R; generation of the response communication by the first user that includes computation of a response comprising h in the ring R, where h is a function of c and f; and performing of a verification by the second user that includes determination of φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h), φ(c) and φ(f).

Claims

1. A method of communicating information between users of a communication system, the method comprising the steps of:

transmitting from a first user to a second user a result ø

(g) of evaluating an element g in a ring R by a ring homomorphism ø

;

R→

B, wherein the element g satisfies a first set of predetermined conditions;

generating an element h in the ring R as a function of an element c in the ring R satisfying a second set of predetermined conditions, a private key element f of the first user in the ring R, wherein the element f satisfies a third set of predetermined conditions; and

transmitting the element h from the first user to the second user, such that the second user can authenticate the communication from the first user by verifying that the element h satisfies a fourth set of predetermined conditions and by comparing the result ø

(h) of evaluating the element h by the ring homomorphism o to a function of ø

(g), ø

(c), and a public key ø

(f) of the first user.

2. The method of claim 1 wherein the element c is generated by the second user as a challenge to the first user in response to receipt of the result ø

(g).

3. The method of claim 2 wherein the second user authenticates the identity of the first user based on the result of the step of comparing ø

(h) to a function of ø

(g), ø

(c) and ø

(f).

4. The method of claim 1 wherein the element c is generated by the first user applying a hash function to the result ø

(g) and a message m, and the method further includes the step of transmitting the message m from the first user to the second user.

5. The method of claim 4 wherein the second user authenticates a digital signature of the first user based on the result of the step of applying a hash function to the result ø

(g) and the message m to generate an element c, and the method further includes the step of comparing ø

(h) to a function of ø

(g), ø

(c) and ø

(f).

6. The method of claim 1 wherein the ring R is a ring of functions.

7. The method of claim 6 wherein the homomorphism ø

is the evaluation homomorphism at a set of values a₁,a₂ . . . a_s.

8. The method of claim 1 wherein the element h generated as a function of the element c, a private key f, and the first element g, is generated as the value of a polynomial P(f,c,g), wherein P(X,Y,Z) is a polynomial with coefficients in R.

9. The method of claim 8 wherein the second user authenticates the communication from the first user by comparing the result ø

(h) of evaluating the element h by the ring homomorphism ø

to the result of evaluating ø

(P)(ø

(f)ø

,ø

(c),ø

(g)), wherein ø

(P) is the polynomial obtained by evaluating the coefficients of the polynomial P by the ring homomorphism ø

.

10. The method of claim 8 wherein the polynomial P(X,Y,Z) is the polynomial ZX+Z²Y.

11. The method of claim 8 wherein f is a nc-tuple, c is an nc-tuple, and g is an ng-tuple and P is a polynomial in n_f+n_c+n_g variables.

12. The method of claim 11 wherein n_c is equal to n_fn_g and the polynomial P is equal to the summation of X_iY_ijZ_j as i ranges from 1 to n_f and j ranges from 1 to n_g.

13. The method of claim 1 wherein the ring R is the ring Fq[X]/(X^N−

1) of polynomials over the field F_q of q elements modulo the ideal generated by the polynomial X^N−

1 and wherein N is a divisor of q−

1.

14. The method of claim 13 wherein the first set of predetermined conditions on the element g are that the coefficients of g are small compared to q.

15. The method of claim 13 wherein the second set of predetermined conditions on the element c are that the coefficients of c are small compared to q.

16. The method of claim 13 wherein the third set of predetermined conditions on the element f are that the coefficients of f are small compared to q.

17. The method of claim 13 wherein the fourth set of predetermined conditions on the element h are that the coefficients of h are small compared to q.

18. A method of communicating information between users of a communication system, the method comprising the steps of:

generating an element h in a ring R as a function of an element g in the ring R satisfying a first set of predetermined conditions, an element c in the ring R satisfying a second set of predetermined conditions, and a private key element f of a first user in the ring R satisfying a third set of predetermined conditions;

transmitting the element h from the first user to a second user, such that the second user can authenticate the communication from the first user by verifying that the element h satisfies a fourth set of predetermined conditions and by using a ring homomorphism ø

;

R+B and verifying that the quantity ø

(h), the quantity ø

(c), and a public key ø

(f) of the first user satisfy a fifth set of predetermined conditions.

19. The method of claim 18 wherein h is also a function of an element g, in the ring R, and wherein the element +(g₁) is transmitted from the first user to the second user and wherein the second user also uses ø

(g₁) to authenticate the communication.

20. The method of claim 18 wherein the element c is generated by the second user as a challenge to the first user.

21. The method of claim 20 wherein the second user authenticates the identity of the first user based on the result of the step of verifying that the element h satisfies the fourth set of predetermined conditions and that the quantities ø

(h), ø

(c), and ø

(f) satisfy the fifth set of predetermined conditions.

22. The method of claim 18 wherein the element c is generated by the first user applying a hash function to the message m, and the method further includes the step of transmitting the message m from the first user to the second user.

23. The method of claim 22 wherein the second user authenticates a digital signature of the first user based on the result of the step of applying a hash function to the message m to generate an element c, and the method further includes the step verifying that the element h satisfies the fourth set of predetermined conditions and that the quantities ø

(h), ø

(c), and ø

(f) satisfy the fifth set of predetermined conditions.

24. The method of claim 18 wherein the ring R is a ring of functions.

25. The method of claim 24 wherein the homomorphism ø

is the evaluation homomorphism at a set of values a₁, a₂ . . . , a_s.

26. The method of claim 18 wherein the element h generated as a function of the element c, a private key f, and the first element g, is generated as the value of a polynomial P(f,c,g), wherein P(X,Y,Z) is a polynomial with coefficients in R.

27. The method of claim 26 wherein the fifth set of predetermined conditions by which the second user authenticates the communication from the first user are that the equation ø

(P)(ø

(f),ø

(c),Z)=0 has a solution Z in the ring R, wherein ø

(P) is the polynomial obtained by evaluating the coefficients of the polynomial P by the ring homomorphism ø

.

28. The method of claim 26 wherein the polynomial P(X,Y,Z) is the polynomial ZX+Z²Y.

29. The method of claim 26 wherein f is a n_f-tuple, c is an n_c-tuple, and g is an n_g-tuple and P is a polynomial in n_f+n_c+n_g variables.

30. The method of claim 29 wherein the polynomial P is equal to XZ₂+Y₁Z₁Z₂+Y₂Z₂².

31. The method of claim 30 wherein the fifth set of predetermined conditions is that (φ

(φ

+φ

(C₁)φ

(g₁))²+4(c₂)φ

(h) is the square of an element of the ring B.

32. The method of claim 28 wherein the fifth set of predetermined conditions by which the second user authenticates the communication from the first user are that the quantity ø

(f)²+4ø

(c)ø

(h) is the square of an element of the ring B.

33. The method of claim 18 wherein the ring R is the ring Fq[X]/(X^N−

1) of polynomials over the field F_q of q elements modulo the ideal generated by the polynomial X^N−

1 and wherein N is a divisor of q−

1.

34. The method of claim 33 wherein the first set of predetermined conditions on the element g are that the coefficients of g are small compared to q.

35. The method of claim 33 wherein the second set of predetermined conditions on the element c are that the coefficients of c are small compared to q.

36. The method of claim 33 wherein the third set of predetermined conditions on the element f are that the coefficients of f are small compared to q.

37. The method of claim 33 wherein the fourth set of predetermined conditions on the element h are that the coefficients of h are small compared to q.

38. A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, comprising the steps of:

selection by the first user of a private key f in a ring R and a public key that includes φ

(f) in a ring B that is mapped from f using the ring homomorphism φ

;

R→

B, and publication by the first user of the public key;

generation of the challenge communication by the second user that includes selection of a challenge c in the ring R;

generation of the response communication by the first user that includes computation of a response comprising h in the ring R, where h is a function of c and f, and

performing of a verification by the second user that includes determination of φ

(c) from c, φ

(h) from h, and an evaluation that depends on φ

(h), φ

(c) and φ

(f).

39. The method as defined by claim 38, wherein said generation of the response communication by the first user includes selection by the first user of an element g in the ring R, and wherein h is also a function of g.

40. The method as defined by claim 39, wherein φ

(g) is also communicated to the second user, and wherein said performing of a verification includes an evaluation that also depends on φ

(g).

41. The method as defined by claim 39, wherein said authentication includes an initial commitment communication from said first user to said second user, and wherein said commitment communication includes φ

(g).

42. The method as defined by claim 39, wherein said first user further selects an element g, in the ring R and determines φ

(g₁) therefrom, and further comprising communicating φ

(g₁) to the second user.

43. The method as defined by claim 42, wherein said authentication includes an initial commitment communication from said first user to said second user, and wherein said commitment communication includes φ

(g₁).

44. The method as defined by claim 39, wherein f, c, and g are elements in respective subsets of the ring R.

45. The method as defined by claim 42, wherein f, c, g, and g, are elements in respective subsets of the ring R.

46. The method as defined by claim 39, wherein f, c, g, and h are polynomials, and wherein φ

(f), φ

(c), φ

(g) and φ

(h) each represent one or more values of the respective polynomials from which they are mapped.

47. The method as defined by claim 43, wherein f, c, g, g, and h are polynomials, and wherein φ

(f), φ

(c), φ

(g), φ

(g₁) and φ

(h) each represent one or more values of the respective polynomials from which they are mapped.

48. The method as defined by claim 39, wherein said step of generation of the response includes computation of h in the form h=(f+cg)g.

49. The method as defined by claim 39, wherein at least one of the elements f, c, and g is an n-tuple with n greater than 1, and φ

evaluated at an n-tuple of elements (r₁, r₂ . . . r_n) of R is equal to the n-tuple of respective values (φ

(r₁), φ

(r₂) . . . φ

(r_n)) of φ

.

50. The method as defined by claim 40, wherein at least one of the elements f, c, and g is an n-tuple with n greater than 1, and φ

evaluated at an n-tuple of elements (r₁, r₂, . . . r_n) of R is equal to the n-tuple of respective values (φ

(r₁), φ

(r₂) . . . φ

(r_n)) of φ

.

51. The method as defined by claim 41, wherein at least one of the elements f, c, and g is an n-tuple with n greater than 1, and φ

evaluated at an n-tuple of elements (r₁, r₂ . . . r_n) of R is equal to the n-tuple of respective values (φ

(r₁), φ

(r₂) . . . (r_n)) of φ

.

52. The method as defined by claim 42, wherein at least one of the elements f, c, and g is an n-tuple with n greater than 1, and φ

evaluated at an n-tuple of elements (r₁, r₂ . . . r_n) of R is equal to the n-tuple of respective values (φ

(r₁), φ

(r₂) . . . (r_n)) of φ

.

53. The method as defined by claim 43, wherein at least one of the elements f, c, and g is an n-tuple with n greater than 1, and φ

evaluated at an n-tuple of elements (r₁, r₂ . . . r_n) of R is equal to the n-tuple of respective values (φ

(r₁), φ

(r₂) . . . (r_n)) of φ

.

54. The method as defined by claim 52, wherein element c includes the pair c₁, c₂ and elements g₁, g₂, correspond respectively to the pair g₁, g₂, and wherein h is of the form

h=(f+c₁g₁+c₂g₂)g₂.

55. The method as defined by claim 53, wherein element c includes the pair c₁, c₂ and elements g₁, g correspond respectively to the pair g₁, g₁, and wherein h is of the form

h=(f+c₁g₁+c₂g₂)g₂.

56. The method as defined by claim 50, wherein element f includes the pair f₁, f₂, element g includes the pair g₁, g₂, and element c includes the 4-tuple C₁₁, c₁₂, c₁₂, c₂₁, C₂₂, and wherein h is of the form

h=f₁g₁c₁₁+f₁g₁c₁₂+f₂g₁c₂₁+f₂g₂c₂₂.

57. The method as defined by claim 51, wherein element f includes the pair f₁, f₂, element g includes the pair g₁, g₂, and element c includes the 4-tuple c₁₁, c₁₂, C₁₂, c₂₁, c₂₂, and wherein h is of the form

h=f₁g₁c₁₁+f₁g₁c₁₂+f₂g₁c₂₁+f₂g₂c₂₂.

58. The method as defined by claim 42, wherein said verification includes a determination of whether certain values of functions of φ

(f), φ

(c), φ

(g₁), φ

(h) are squares modulo q, where q is a certain integer modulus used in key creation by the first user.

59. The method as defined by claim 43, wherein said verification includes a determination of whether certain values of functions of φ

(f), φ

(c), φ

(g₁), φ

(h) are squares modulo q, where q is a certain integer modulus used in key creation by the first user.

60. The method as defined by claim 53, wherein said verification includes a determination of whether certain values of functions of φ

(f)φ

, φ

(c), φ

(g₁), φ

(h) are squares modulo q, where q is a certain integer modulus used in key creation by the first user.

61. The method as defined by claim 55, wherein said verification includes a determination of whether certain values of functions of φ

(f), φ

(c), φ

(g₁), φ

(h) are squares modulo q, where q is a certain integer modulus used in key creation by the first user.

67. The method as defined by claim 54, wherein f, c, g₁, and h are polynomials, and wherein φ

(f), φ

(c), φ

(g₁) and φ

(h) each represent one or more values of the respective polynomials from which they are mapped.

70. The method as defined by claim 67, wherein at least one of the elements f, c, and g₁ is an n-tuple with n greater than 1.

71. The method as defined by claim 70, wherein element c includes the pair c₁, c₂ and element g₁ is part of the pair g₁, g₂, and wherein h is of the form

h=(f+c₁g₁+c₂g₂)g₂.

73. The method as defined by claim 58, wherein said verification includes a determination of whether certain values of functions of φ

(f), φ

(c), φ

(g₁), φ

(h) are squares modulo q, where q is a certain integer modulus used in key creation by the first user.

62. An authentication method that includes authenticating, by a second user, of a signed digital message of a first user communicated from said first user to said second user, comprising the steps of:

selecting by the first user, of a private key f in a ring R and a public key that includes φ

(f) in a ring B that is mapped from f using the ring homomorphism φ

;

R→

B, and publication by the first user of the public key;

selecting, by the first user, of an element g₁ in the ring R, determining φ

(g₁), and applying a hash function to at least a message m to produce an element c;

generating, by the first user, an element h which is a function of c and f;

communicating, from the first user to the second user, the message m and a digital signature comprising φ

(g₁) and h;

determining, by the second user, of the element c, by applying a hash function to at least the message m, and determining, by the second user of φ

(c) from c and φ

(h) from h; and

authenticating, by the second user, of the digital signature, said authenticating including an evaluation that depends on φ

(h), φ

(f) and φ

(c).

63. The method as defined by claim 62, wherein said steps, by the first user and the second user, of applying a hash function to at least the message m, comprise applying a hash function to the message m.

64. The method as defined by claim 62, wherein said steps, by the first user and the second user, of applying a hash function to at least the message m, comprise applying a hash function to a combination of the message m and φ

(g₁).

65. The method as defined by claim 62, wherein f, c, and g, are elements in respective subsets of the ring R.

66. The method as defined by claim 62, wherein f, c, g₁, and h are polynomials, and wherein φ

(f), φ

(c), φ

(g₁) and φ

(h) each represent one or more values of the respective polynomials from which they are mapped.

68. The method as defined by claim 62, wherein h is of the form h=(f+cg₁)g₁.

69. The method as defined by claim 66, wherein at least one of the elements f, c, and g₁ is an n-tuple with n greater than 1.

72. The method as defined by claim 69, wherein element f includes the pair f₁, f₂, element g, is part of the pair g₁, g₂, and element c includes the 4-tuple c₁₁, c₁₂, C₁₂, c₂₁, c₂₂, and wherein h is of the form

h=f₁g₁c₁₁+f₁g₁c₁₂+f₂g₁c₂₁+f₂g₂c₂₂.

74. A method for use by a first user to prove its identity to a second user who sends a challenge to the first user and wishes to authenticate the identity of the first user, comprising the steps of:

selecting a private key f in a ring R and a public key that includes φ

(f) in a ring B that is mapped from f using the ring homomorphism φ

;

R→

B, and publication by the first user of the public key;

receiving the challenge communication from the second user that includes selection of a challenge element c in the ring R; and

generation of the response communication that includes computation of a response comprising h in the ring R, where h is a function of c and f;

whereby the second user can perform a verification that includes determination of φ

(c) from c, φ

(h) from h, and an evaluation that depends on φ

(h), φ

(c) and φ

(f).

75. A method for producing and sending a signed digital message comprising the steps of:

selecting a private key f in a ring R and a public key that includes φ

(f) in a ring B that is mapped from f using the ring homomorphism φ

;

R→

B, and publication by the first user of the public key;

selecting an element g₁ in the ring R, determining φ

(g₁), and applying a hash function to at least a message m to produce an element c;

generating an element h which is a function of c and f; and

communicating the message m and a digital signature comprising φ

(g₁) and h.