Ring-based signature scheme

• US 20040151309A1
• Filed: 03/22/2004
• Published: 08/05/2004
• Est. Priority Date: 05/03/2002
• Status: Abandoned Application

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Yin, Yiqun, Gentry, Craig B
• Application Number:
  US10/476,632
• Publication Number:
  US 20040151309A1
• 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/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A method and system for generating and verifying a digital signature of a message is provided. The digital signature includes digital signature polynomials. Two relatively prime ideals p and q of a ring R are selected. A private key and the second ideal q are used to generate a public key. One or more message polynomials are generated based on the message to be signed. The digital signature polynomials are generated using at least one of the message polynomials, at least one of the private key polynomials, and at least one of the ideals p and q, wherein the digital signature polynomials in unreduced form are not multiples of the private key polynomials in the ring R. The signature is then verified by confirming that a deviation between at least one of the message polynomials and at least one of the digital signature polynomials is less than a predetermined deviation threshold.

Claims

1. A method of generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

selecting relatively prime ideals p and q of a ring R;

selecting a private key including one or more private key polynomials of the ring R;

generating a public key using the private key and the second ideal q;

generating one or more message polynomials based on the message;

generating the digital signature polynomials using at least the following elements;

(a) at least one of the message polynomials;

(b) at least one of the private key polynomials; and

(c) at least one of the ideals p and q;

wherein the digital signature polynomials in unreduced form are not multiples of the private key polynomials in the ring R; and

verifying the digital signature at least by confirming that a deviation between at least one of the message polynomials and at least one of the digital signature polynomials is less than a predetermined deviation threshold.

2. A method of generating and verifying a digital signature of a message as in claim 1, wherein the ring R=[X]/(X^N−

1), where N is an integer greater than 1.

3. A method of generating and verifying a digital signature of a message as in claim 2, wherein the predetermined deviation threshold is less than or equal to N/5.

4. A method of generating and verifying a digital signature of a message as in claim 1, wherein the predetermined deviation threshold is equal to zero.

5. A method of generating and verifying a digital signature of a message as in claim 1, wherein the message polynomials are generated by performing one or more hash functions on the message.

6. A method of generating and verifying a digital signature of a message as in claim 1, wherein:

the generation of the digital signature polynomials further comprises using;

(d) one or more random private polynomials.

7. A method of generating and verifying a digital signature of a message as in claim 1, further comprising:

selecting a one-time private key; and

wherein the generation of the digital signature polynomials further includes using;

(d) the one-time private key.

8. A method of generating and verifying a digital signature of a message as in claim 1, wherein the verification further comprises:

confirming that the digital signature polynomials and the public key satisfy a predetermined relationship.

9. A method of generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

selecting relatively prime ideals p and q of a ring R;

selecting a private key including one or more private key polynomials of the ring R;

generating a public key using the private key and the second ideal q;

generating one or more message polynomials based on the message;

generating the digital signature polynomials using at least the following elements;

(a) at least one of the message polynomials;

(b) at least one of the private key polynomials; and

(c) at least one of the ideals p and q; and

verifying the digital signature at least by confirming that a norm associated with at least one of the digital signature polynomials is less than a predetermined norm threshold.

10. A method of generating and verifying a digital signature of a message as in claim 9, wherein the ring R=[X]/(X^N−

1), where N is an integer greater than 1.

11. A method of generating and verifying a digital signature of a message as in claim 10, wherein the norm associated with at least one of the digital signature polynomial is the norm of the at least one digital signature polynomial.

12. A method of generating and verifying a digital signature of a message as in claim 10, further comprising:

computing a differential polynomial by subtracting one of the message polynomials from one of the digital signature polynomials; and

wherein the norm associated with the at least one digital signature polynomial is the norm of the differential polynomial.

13. A method of generating and verifying a digital signature of a message as in claim 10, wherein:

the norm is a Euclidean norm; and

the predetermined norm threshold is on the order of N.

14. A method of generating and verifying a digital signature of a message as in claim 9, wherein the message polynomials are generated by performing one or more hash functions on the message.

15. A method of generating and verifying a digital signature of a message as in claim 9, wherein:

the generation of the digital signature polynomials further includes using;

(d) one or more random private polynomials.

16. A method of generating and verifying a digital signature of a message as in claim 9, further comprising:

selecting a one-time private key; and

wherein the generation of the digital signature polynomials further includes using;

(d) the one-time private key.

17. A method of generating and verifying a digital signature of a message as in claim 9, wherein the verification further comprises:

confirming that the digital signature polynomials and the public key satisfy a predetermined relationship.

18. A method of generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

selecting ideals p and q of a ring R;

selecting a private key including one or more private key polynomials of the ring R;

generating a public key using the private key and the second ideal q;

generating one or more message polynomials based on the message;

selecting auxiliary multiple-use private information;

generating the digital signature polynomials using at least the following elements;

(a) at least one of the message polynomials;

(b) at least one of the private key polynomials;

(c) at least one of the ideals p and q; and

(d) the auxiliary multiple-use private information; and

verifying the digital signature at least by confirming that the digital signature polynomials and the public key satisfy a predetermined relationship.

19. A method of generating and verifying a digital signature of a message as in claim 18, wherein the ring R=[X](X^N−

1), where N is an integer greater than 1.

20. A method of generating and verifying a digital signature of a message as in claim 18, wherein:

the auxiliary multiple-use private information includes one or more auxiliary private key polynomials of the ring R.

21. A method of generating and verifying a digital signature of a message as in claim 20, wherein the generation of the digital signature polynomials further comprises:

adjusting one or more of the digital signature polynomials using the auxiliary private key polynomials, such that a second-order averaging attack on the digital signature polynomials converges to a value dependent on the auxiliary private key polynomials.

22. A method of generating and verifying a digital signature of a message as in claim 18, wherein the verification of the digital signature polynomials further comprises:

confirming that a deviation between at least one of the message polynomials and at least one of the digital signature polynomials is less than a predetermined deviation threshold.

23. A method of generating and verifying a digital signature of a message as in claim 18, wherein the verification of the digital signature polynomials further comprises:

confirming that a norm of at least one of the digital signature polynomials is less than a predetermined norm threshold.

24. A method of generating and verifying a digital signature of a message as in claim 18, wherein the message polynomials are generated by performing one or more hash functions on the message.

25. A method of generating and verifying a digital signature of a message as in claim 18, wherein:

the generation of the digital signature polynomials further comprises using;

(e) one or more random private polynomials.

26. A method of generating and verifying a digital signature of a message as in claim 18, further comprising:

selecting a one-time private key; and

wherein the generation of the digital signature polynomials further comprises using;

(e) the one-time private key.

27. A method of generating and verifying a digital signature of a message, wherein the digital signature includes two digital signature polynomials u and v, comprising:

selecting relatively prime ideals p and q of a ring R=[X]/(X^N−

1), where Nis an integer greater than 1;

selecting a private key including two private key polynomials, f and g of the ring R;

computing a public key h=*g(mod q);

generating one or more message polynomials m using the message;

selecting a first intermediate private polynomial s and a second intermediate private polynomial t such that s*h=t and such that s and t are substantially congruent modulo p;

selecting a third intermediate private polynomial a so as to minimize the number of deviations between one of the message polynomials m and a quantity t+a*g(mod q);

computing the first digital signature polynomial u=s+a*f(mod q);

computing the second digital signature polynomial v=t+a*g(modq); and

verifying the digital signature at least by confirming that a first deviation between one or more of the message polynomials m and the first digital signature polynomial u is less than a predetermined deviation threshold, and that a second deviation between one or more of the message polynomials m and the second digital signature polynomial v is less than the predetermined deviation threshold.

28. A method of generating and verifying a digital signature of a message as in claim 27, wherein:

the private key polynomials f and g each are congruent modulo p to a polynomial k of the ring R; and

each of the private key polynomials f and g has a Euclidean norm on the order of {square root}{square root over (N)}.

29. A method of generating and verifying a digital signature of a message as in claim 27, further comprising:

selecting a random polynomial r of the ring R; and

wherein

the selection of a first intermediate private polynomial s includes computing s=pr*(1−

h)<sup>−

1</sup>(mod q);

the selection of a second intermediate private polynomial t includes computing t=s*h(mod q); and

the selection of a third intermediate private polynomial a includes computing a=f_p<sup>−

1</sup>*(m−

s)(mod p).

30. A method of generating and verifying a digital signature of a message as in claim 29, wherein the random polynomial r has a Euclidean norm on the order of N or less.

31. A method of generating and verifying a digital signature of a message as in claim 29, wherein the predetermined deviation threshold is less than or equal to N/8.

32. A method of generating and verifying a digital signature of a message as in claim 27, wherein the verification of the digital signature further comprises:

confirming that u*h=v(mod q).

33. A method of generating and verifying a digital signature of a message as in claim 27, wherein the message polynomials m are generated using one or more secure hash functions H(m).

34. A method of generating and verifying a digital signature of a message as in claim 27, wherein the random polynomial r is selected such that r(1)=0.

35. A method of generating and verifying a digital signature of a message, wherein the digital signature includes two digital signature polynomials u and v, comprising the steps of:

selecting relatively prime ideals p and q of a ring R=[X](X^N−

1), where N is an integer greater than 1;

selecting a private key including two private key polynomials, f and g of the ring R;

computing a public key h=f_q<sup>−

1</sup>*g(mod q);

generating one or more message polynomials m using the message;

selecting a random polynomial r;

computing a first intermediate polynomial t=r*h(mod q);

selecting a second intermediate polynomial a such that a has a Euclidean norm on the order of {square root}{square root over (N)} and so as to minimize the number of deviations between a message polynomial m and a quantity t+a*g(mod q);

computing the first digital signature polynomial u=r+a*f(mod q);

computing the second digital signature polynomial v=t+a*g(mod q); and

verifying the digital signature at least by confirming that a Euclidean norm of the first digital signature polynomial u is on the order of N, and that a deviation between the message m and the second digital signature polynomial v is less than or equal to a predetermined deviation threshold.

36. A method of generating and verifying a digital signature of a message as in claim 35, wherein each of the private key polynomials f and g has a Euclidean norm on the order of {square root}{square root over (N)}.

37. A method of generating and verifying a digital signature of a message as in claim 35, wherein the random polynomial r has a Euclidean norm on the order of N or less.

38. A method of generating and verifying a digital signature of a message as in claim 35, wherein the selection of a second intermediate polynomial a includes computing a=g_p⁻

1*(m−

t)(mod p).

39. A method of generating and verifying a digital signature of a message as in claim 38, wherein the predetermined deviation threshold is less than or equal to N/12.

40. A method of generating and verifying a digital signature of a message as in claim 35, wherein the verification of the digital signature further includes confirming that u*h=v(mod q).

41. A method of generating and verifying a digital signature of a message as in claim 35, wherein the message polynomials m are generated using one or more secure hash functions H(m).

42. A method of generating and verifying a digital signature of a message, wherein the digital signature includes four digital signature polynomials u₁, v₁, u₂, and v₂, comprising the steps of:

selecting relatively prime ideals p and q of a ring R=[X](X^N−

1), where N is an integer greater than 1;

computing a public key h=f_q<sup>−

1</sup>*g(mod q);

selecting a one-time private key including a one-time private key polynomial e of the ring R;

generating a pair of one-time public key polynomials h₁ and h₂, wherein h₁=f<sup>−

1</sup>*e(mod q) and h₂=g<sup>−

1</sup>*e(mod q);

selecting a first random polynomial r₁;

computing a first intermediate polynomial t₁=r₁*h₁ (mod q);

selecting a second intermediate polynomial a₁ such that the Euclidean norm of a₁ is on the order of {square root}{square root over (N)} and so as to minimize the number of deviations between one of the message polynomials m and the quantify t₁+a₁*e(mod q);

computing the first digital signature polynomial u₁=r₁+a₁*f(mod q);

computing the second digital signature polynomial v₁=t₁+a₁*e(mod q);

selecting a second random polynomial r₂;

computing a third intermediate polynomial t₂=r₂*h₂(mod q);

selecting a second intermediate polynomial a₁ such that the Euclidean norm of a₂ is on the order of {square root}{square root over (N)} and so as to minimize the number of deviations between one of the message polynomials m and the quantify t₂+a₂*e(mod q);

computing the third digital signature polynomial u₂=r₂+a₂*g(mod q);

computing the fourth digital signature polynomial v₂=t₂+a₂*e(mod q); and

verifying the digital signature at least by confirming that a Euclidean norm of each of the first and third digital signature polynomials u₁ and u₂ is on the order of N, and that a deviation between the message m and each of the second and fourth digital signature polynomials v₁ and v₂ is less than or equal to a predetermined deviation threshold.

43. A method of generating and verifying a digital signature of a message as in claim 42, wherein each of the private key polynomials f and g has a Euclidean norm on the order of {square root}{square root over (N)}.

44. A method of generating and verifying a digital signature of a message as in claim 42, wherein the random polynomials r₁ and r₂ each have a Euclidean norm on the order of N or less.

45. A method of generating and verifying a digital signature of a message as in claim 42, wherein:

the selection of a second intermediate polynomial a₁ includes computing a₁=e_p<sup>−

1</sup>*(m−

t₁)(mod p); and

the selection of a fourth intermediate polynomial a₂ includes computing a₂=e_p<sup>−

1</sup>*(m−

t₂)(mod p).

46. A method of generating and verifying a digital signature of a message as in claim 45, wherein the predetermined deviation threshold is less than or equal to N/12.

47. A method of generating and verifying a digital signature of a message as in claim 42, wherein the selection of a one-time private key including a one-time private key polynomial e further includes selecting a first coefficient e₀ of e to be on the order of q/2p.

48. A method of generating and verifying a digital signature of a message as in claim 47, wherein the predetermined deviation threshold is less than or equal to N/100.

49. A method of generating and verifying a digital signature of a message as in claim 47, wherein the predetermined deviation threshold is equal to zero.

50. A method of generating and verifying a digital signature of a message as in claim 42, wherein selection of the first random polynomial r₁ and the second random polynomial r₁ further includes using one or more auxiliary multi-use private polynomials to compute r₁ and r₂.

51. A method of generating and verifying a digital signature of a message as in claim 50, wherein:

selection of a first random polynomial r₁ further includes computing r₁=a₁′

*f′

, where a₁′

is a first random short polynomial and f is a first auxiliary multi-use private polynomial; and

selection of a second random polynomial r₂ further includes computing r₂=a₂′

*g′

, where a₂′

is a second random short polynomial and g′

is a second auxiliary multi-use polynomial.

52. A method of generating and verifying a digital signature of a message as in claim 50, wherein:

selection of a first random polynomial r₁ further includes computing r₁=a₁′

*f′

+a₁″

*f″

, where a₁′ and

a₁″

are first and second random short polynomials and f′ and

f″

are first and second auxiliary multi-use private polynomial; and

selection of a second random polynomial r₂ further includes computing r₂=a₂′

*g′

+a₂″

*g″

, where a₂′ and

a₂″

are third and fourth random short polynomials and g′ and

g″

are third and fourth auxiliary multi-use private polynomials.

53. A method of generating and verifying a digital signature of a message as in claim 42, wherein verifying the digital signature further includes confirming that

54. A method of generating and verifying a digital signature of a message as in claim 42, wherein the message polynomials m are generated using one or more secure hash functions H(m).

55. An apparatus for generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

a memory for storing ideals p and q of the ring R and a private key including one or more private key polynomials of the ring R; and

a processor operable to generate one or more message polynomials based on the message, to generate the digital signature polynomials using at least one of the message polynomials, at least one of the private key polynomials, and at least one of the ideals p and q such that the digital signature polynomials in unreduced form are not multiples of the private key polynomials in the ring R, and to verify the digital signature at least by confirming that a deviation between at least one of the message polynomials and at least one of the digital signature polynomials is less than a predetermined deviation threshold.

56. An apparatus for generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

a memory for storing ideals p and q of the ring R and a private key including one or more private key polynomials of the ring R; and

a processor operable to generate one or more message polynomials based on the message, to generate the digital signature polynomials using at least one of the message polynomials, at least one of the private key polynomials, and at least one of the ideals p and q, and to verify the digital signature at least by confirming that a norm of at least one of the digital signature polynomials is less than a predetermined norm threshold.

57. An apparatus for generating and verifying a digital signature of a message, wherein the digital signature includes one or more digital signature polynomials, comprising:

a memory for storing ideals p and q of the ring R, a private key including one or more private key polynomials of the ring R, and auxiliary multiple-use private information that is unrelated to the private key; and