Digital signature and authentication method and apparatus

• US 20020136401A1
• Filed: 03/20/2001
• Published: 09/26/2002
• Est. Priority Date: 07/25/2000
• Status: Abandoned Application

• Current Assignee: NTRU Cryptosystems Incorporated (Security Innovation Incorporated)
• Original Assignee: NTRU Cryptosystems Incorporated (Security Innovation Incorporated)
• Inventors: Pipher, Jill, Hoffstein, Jeffrey, Silverman, Joseph H.
• Application Number:
  US09/812,917
• Publication Number:
  US 20020136401A1
• Time in Patent Office: Days
• US Class Current: 380/30
• 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

Methods, systems and computer readable media for signing and verifying a digital message m are described. First, ideals p and q of a ring R are selected. Elements f and g of the ring R are generated, followed by generating an element F, which is an inverse of f, in the ring R. A public key h is produced, where h is equal to a product that can be calculated using g and F. Then, a private key that includes f is produced. A digital signature s is signed to the message m using the private key. The digital signature is verified by confirming one or more specified conditions using the message m and the public key h. A second user also can authenticate the identity of a first user. A challenge communication that includes selection of a challenge m in the ring R is generated by the second user. A response communication that includes computation of a response s in the ring R, where s is a function of m and f, is generated by the first user. A verification that includes confirming one or more specified conditions using the response s, the challenge m and the public key h is performed by the second user. Also described are methods, systems and computer readable media for authenticating the identity of a first user by a second user using similar technology.

Claims

1. A method for signing and verifying a digital message m, comprising the steps of:

selecting ideals p and q of a ring R;

generating elements f and g of the ring R;

generating an element F, which is an inverse of f, in the ring R;

producing a public key h, where h is equal to a product that can be calculated using g and F;

producing a private key that includes f;

producing a digital signature s by digitally “

signing”

the message m using the private key; and

verifying the digital signature by confirming one or more specified conditions using the message m and the public key h.

2. The method as defined by claim 1, wherein the digital signature s can be formed using the product of f and w modulo q, wherein w can be formed using the element m.

3. The method of claim 1, wherein a specified condition for verification of the digital signature s is that a quantity derived from s modulo p satisfies a specified relation with a quantity derived from m modulo p.

4. The method of claim 1, wherein a specified condition for verification of the digital signature s is that an element t of the ring R, which is formed from the product of the digital signature s and the public key h modulo q, satisfies a specified condition.

5. The method of claim 4, wherein a specified condition on the element t is that a quantity derived from t modulo p satisfies a specified relation with a quantity derived from m modulo p.

6. A method for signing and verifying a digital message m, comprising the steps of:

selecting integers p and q;

generating polynomials f and g;

determining the inverse F, where

F * f=1 (mod q);

producing a public key h, where

h=F * g (mod q);

producing a private key that includes f;

producing a digital signature s by digitally signing the message m using the private key; and

verifying the digital signature by confirming one or more specified conditions using the message m, the public key h, the digital signature s, and the integers p and q.

7. The method defined by claim 6, wherein the said polynomials f and g are produced as

8. The method defined by claim 6, further comprising:

producing a polynomial was

w=m+w₁+pw₂

where w₁ and w₂ are polynomials; and

producing the signature s as

s=f * w(mod q).

9. The method defined by claim 7, further comprising:

producing the polynomial e_f* m (mod p); and

comparing the polynomials s (mod p) and e_f* m (mod p) to determine whether they satisfy one or more specified conditions.

10. The method defined by claim 7, further comprising:

producing the polynomial e_f* m (mod p); and

comparing the polynomials s (mod p) and e_f* m (mod p) to determine whether they have at least D_s,min, coefficients and no more than D_s,max coefficients that differ;

where D_s,min and D_s,max are integer values.

11. The method defined by claim 6, further comprising:

producing the polynomial t as

t=s * h modulo q; and

determining whether t satisfies one or more specified conditions.

12. The method defined by claim 11, further comprising:

producing the polynomial e_g* m (mod p);

wherein the comparing step determines whether the polynomials t (mod p) and e_g* m (mod p) satisfy one or more specified conditions.

13. The method defined by claim 11, further comprising:

producing the polynomial e_g* m (mod p);

wherein the comparing step determines whether the polynomials t (mod p) and e_g* m (mod p) have at least D_t,min coefficients and no more than D_t,max coefficients that differ;

where D_t,min and D_t,max are integer values.

14. The method as defined in claim 6, the method further comprising:

producing the digital signature by a first user at one location,

transmitting the digital signature to another location, and

verifying the digital signature by a second user at said another location.

15. The method as defined in claim 6, further comprising:

selecting a monic polynomial M(X); and

when multiplying polynomials, first performing ordinary multiplication of polynomials and then dividing the result by M(X) and retaining only the remainder.

16. The method as defined in claim 6, further comprising:

selecting a non-zero integer N; and

when multiplying polynomials, reducing exponents modulo N.

17. The method defined in claim 6, further comprising restraining said polynomials f, g, and m to have bounded coefficients.

18. The method defined in claim 8, further comprising restraining said polynomials f, g, m, w₁ and w₂ to have bounded coefficients.

20. The method as defined by claim 19, further comprising;

generating element w of the ring R using the element m;

wherein the response s comprises the product of f and w modulo q.

21. The method of claim 19, further comprising comparing a first quantity derived from s modulo p with a second quantity derived from m modulo p to determine whether specified condition is satisfied.

22. The method of claim 19,

producing a polynomial t as

t=h * s;

and

determining whether a quantity derived from t modulo p satisfies a specified relation with a quantity derived from m modulo p.

24. The method defined by claim 23, wherein the said polynomials f and g are produced as

25. The method defined by claim 23, further comprising:

producing a polynomial was

w=m+w₁+pw₂

where w₁ and w₂ are polynomials; and

producing the response s as

s=f * w(mod q).

26. The method defined by claim 23, further comprising:

producing the polynomial e_f* m (mod p); and

comparing the polynomials s (mod p) and e_f* m (mod p) to determine whether they satisfy one or more specified conditions.

27. The method defined by claim 23, further comprising:

producing the polynomial e_f* m (mod p); and

comparing the polynomials s (mod p) and e_f* m (mod p) to determine whether they have at least D_s,min, coefficients and no more than D_s,max coefficients that differ;

where D_s,min and D_s,max are integer values.

28. The method defined by claim 23, further comprising:

producing the polynomial t as

t=s * h modulo q; and

determining whether t satisfies one or more specified conditions.

29. The method defined by claim 28, further comprising:

preparing the polynomial e_g* m (mod p);

wherein the comparing step determines whether the polynomials t (mod p) and e_g*m (mod p) satisfy one or more specified conditions.

30. The method defined by claim 28, further comprising:

preparing the polynomial e_g* m (mod p);

wherein the comparing step determines whether the polynomials t (mod p) and e_g* m (mod p) have at least D_t,min coefficients and no more than D_t,max coefficients that differ;

where D_t,min and D_t,max are integer values.

31. The method as defined in claim 23, the method further comprising:

producing the response by a first user at one location,

transmitting the response to another location, and

verifying the response by a second user at said another location.

32. The method as defined in claim 23, further comprising:

selecting a monic polynomial M(X); and

when multiplying polynomials, first performing ordinary multiplication of polynomials and then dividing the result by M(X) and retaining only the remainder.

33. The method as defined in claim 23, further comprising:

selecting a non-zero integer N; and

when multiplying polynomials, reducing exponents modulo N.

34. The method defined in claim 23, further comprising restraining said polynomials f, g, and m to have bounded coefficients.

35. The method defined in claim 25, further comprising restraining said polynomials f, g, m, w₁ and w₂ to have bounded coefficients.

19. A method for authenticating the identity of a first user by a second user, the method including 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, the method comprising the steps of:

selecting ideals p and q of a ring R;

generating elements f and g of the ring R;

generating an element F, which is an inverse of f, in the ring R

producing a public key h, where h is a product that can be produced using g and F;

producing a private key including f and F;

generating a challenge communication by the second user that includes selection of a challenge m in the ring R;

generating a response communication by the first user that includes computation of a response s in the ring R, where s is a function of m and f; and

performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m and the public key h.

23. A method for authenticating the identity of a first user by a second user, the method including 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, the method comprising the steps of:

selecting integers p and q;

generating polynomials f and g;

determining the inverse F, where

F * f=I (mod q);

producing a public key h, where

h=F * (mod q);

producing a private key that includes f,

generating a challenge communication by the second user that includes selection of a challenge m;

generating a response communication by the first user that includes computation of a response s, wherein s is produced using m and f; and

performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m, the public key h, and the integers p and q.

36. A system for signing and verifying a digital message m, the system comprising:

means for selecting ideals p and q of a ring R;

means for generating elements f and g of the ring R;

means for generating an element F, which is an inverse of f, in the ring R;

means for producing a public key h, where h is equal to a product that can be calculated using g and F;

means for producing a private key that includes f;

means for producing a digital signature s by digitally “

signing”

the message m using the private key; and

means for verifying the digital signature by confirming one or more specified conditions using the message m and the public key h.

37. A system for signing and verifying a digital message m, the system comprising:

means for selecting integers p and q;

means for generating polynomials f and g;

means for determining the inverse F, where

F * f=I (mod q);

means for producing a public key h, where

h=F * g (mod q);

means for producing a private key that includes f,

means for producing a digital signature s by digitally signing the message m using the private key; and

means for verifying the digital signature by confirming one or more specified conditions using the message m, the public key h, the digital signature s, and the integers p and q.

38. A system for authenticating the identity of a first user by a second user, including 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, the system comprising:

means for selecting ideals p and q of a ring R;

means for generating elements f and g of the ring R;

means for generating an element F, which is an inverse of f, in the ring R

means for producing a public key h, where h is a product that can be produced using g and F;

means for producing a private key including f and F;

means for generating a challenge communication by the second user that includes selection of a challenge m in the ring R;

means for generating a response communication by the first user that includes computation of a response s in the ring R, where s is a function of m and f; and

means for performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m and the public key h.

39. A system for authenticating the identity of a first user by a second user, including 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, the system comprising:

means for selecting integers p and q;

means for generating polynomials f and g;

means for determining the inverse F, where

F * f=1 (mod q);

means for producing a public key h, where

h=F * g (mod q);

means for producing a private key that includes f;

means for generating a challenge communication by the second user that includes selection of a challenge m;

means for generating a response communication by the first user that includes computation of a response s, wherein s is produced using m and f; and

means for performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m, the public key h, and the integers p and q.

40. , A computer readable medium containing instructions for performing a method for signing and verifying a digital message m, the method comprising the steps of:

selecting ideals p and q of a ring R;

generating elements f and g of the ring R;

generating an element F, which is an inverse of f, in the ring R;

producing a public key h, where h is equal to a product that can be calculated using g and F;

producing a private key that includes f;

producing a digital signature s by digitally “

signing”

the message m using the private key; and

verifying the digital signature by confirming one or more specified conditions using the message m and the public key h.

41. A computer readable medium containing instructions for performing a method for signing and verifying a digital message m, comprising the steps of:

selecting integers p and q;

generating polynomials f and g;

determining the inverse F, where

F * f=I (mod q);

producing a public key h, where

h=F * g (mod q);

producing a private key that includes f;

producing a digital signature s by digitally signing the message m using the private key; and

verifying the digital signature by confirming one or more specified conditions using the message m, the public key h, the digital signature s, and the integers p and q.

42. A computer readable medium containing instructions for performing a method for authenticating the identity of a first user by a second user, the method including 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, the method comprising the steps of:

selecting ideals p and q of a ring R;

generating elements f and g of the ring R;

generating an element F, which is an inverse of f, in the ring R

producing a public key h, where h is a product that can be produced using g and F;

producing a private key including f and F;

generating a challenge communication by the second user that includes selection of a challenge m in the ring R;

generating a response communication by the first user that includes computation of a response s in the ring R, where s is a function of m and f; and

performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m and the public key h.

43. A computer readable medium containing instructions for performing a method for authenticating the identity of a first user by a second user, the method including 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, the method comprising the steps of:

selecting integers p and q;

generating polynomials f and g;

determining the inverse F, where

F * f=1 (mod q);

producing a public key h, where

h=F * g(mod q);

producing a private key that includes f;

generating a challenge communication by the second user that includes selection of a challenge m;

generating a response communication by the first user that includes computation of a response s, wherein s is produced using m and f; and

performing a verification by the second user that includes confirming one or more specified conditions using the response s, the challenge m, the public key h, and the integers p and q.