Public-key signature methods and systems

• US 7,100,051 B1
• Filed: 04/19/2000
• Issued: 08/29/2006
• Est. Priority Date: 04/29/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.), CP8 Technologies (Thales SA)
• Original Assignee: NDS Limited (Cisco Systems, Inc.), CP8 Technologies (Thales SA)
• Inventors: Kipnis, Aviad, Goubin, Louis, Patarin, Jacques
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): CHEN, SHIN HON
• Application Number:
  US09/552,115
• Time in Patent Office: 2,323 Days
• Field of Search: 713/168, 713/170, 713/18, 713/180, 380/30, 380/28, 380/45
• US Class Current: 713/180
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

The invention provides for a cryptographic method for digital signature.

A set S1 of k polynomial functions P_k(x₁, . . . , x_n+v, y₁, . . . , y_k) are supplied as a public key, where k, v, and n are integers, x₁, . . . , x_n+v are n+v variables of a first type, and y₁, . . . , y_k are k variables of a second type, the set S1 being obtained by applying a secret key operation on a given set S2 of k polynomial functions P′_k(a₁, . . . , a_n+v, y₁, . . . , y_k), a₁, . . . , a_n+v designating n+v variables including a set of n “oil” and v “vinegar” variables.

A message to be signed is provided and submitted to a hash function to produce a series of k values b₁, . . . , b_k. These k values are substituted for the k variables y₁, . . . . , y_k of the set S2 to produce a set S3 of k polynomial functions P″_k(a₁, . . . , a_n+v), and v values a′_n+1, . . . , a′_n+1, are selected for the v “vinegar” variables. A set of equations P″_k(a₁, . . . , a′_n+v)=0 is solved to obtain a solution for a′₁, . . . , a′_n and the secret key operation is applied to transform the solution to the digital signature.

Claims

1. A digital signature cryptographic method, performed by a computing device, the method comprising:

supplying a set S1 of k polynomial functions as a public-key, the set S1 including the functions P₁(x₁, . . . , x_n+v, y₁, . . . , y_k), . . . , P_k(x₁, . . . , x_n+v, y₁, . . . , y_k), where k, v, and n are integers, x₁, . . . , x_n+v are n+v variables of a first type, y₁, . . . , y_k are k variables of a second type, and the set S1 is obtained by applying a secret key operation on a set S2 of k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) where a₁, . . . , a_n+v are n+v variables which include a set of n “

oil”

variables a₁, . . . , a_n, and a set of v “

vinegar”

variables an a_n+1, . . . , a_n+v, the supplying comprising selecting the number v of “

vinegar”

variables to be greater than the number n of “

oil”

variables;

providing a message to be signed;

applying a hash function on the message to produce a series of k values b₁, . . . , b_k;

substituting the series of k values b₁, . . . , b_k for the variables y₁, . . . , y_k of the set S2 respectively to produce a set S3 of k polynomial functions P″

_k(a₁, . . . a_n+v), . . . , P″

_k(a₁, . . . , a_n+v);

selecting v values a′

_n+1, . . . , a_n+v for the v “

vinegar”

variables a_n+1, . . . a_n+v;

solving a set of equations P″

₁(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0, . . . , P″

_k(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0 to obtain a solution for a′

₁, . . . , a′

_n;

applying the secret key operation to transform a′

₁, . . . , a′

_n+v to a digital signature e₁, . . . , e_n+v; and

assigning e₁, . . . , e_n+v as the digital signature of the message.

2. A method according to claim 1 and also comprising verifying the digital signature.

3. A method according to claim 2 and wherein said verifying comprises:

obtaining the signature e₁, . . . , e_n+v, the message, the hash function and the public key;

applying the hash function on the message to produce the series of k values b₁, . . . , b_k; and

verifying that the equations P₁(e₁, . . . , e_n+v, b₁, . . . , b_k)=0, . . . , P_k(e₁, . . . , e_n+v, b₁, . . . , b_k)=0 are satisfied.

4. A method according to claim 1 and wherein the method comprises an HFEV scheme and the set S2 comprises a set f(a) of k polynomial functions of the HFEV scheme.

5. A method according to claim 4 and wherein said set S2 comprises an expression including k functions that are derived from a univariate polynomial.

6. A method according to claim 5 and wherein said univariate polynomial includes a univariate polynomial of degree less than or equal to 100,000.

7. A method according to claim 1 and wherein the method comprises a UOV scheme and the set S2 comprises a set S of k polynomial functions of the UOV scheme.

8. A method according to claim 1 and wherein v is selected such that q^v is greater than 2³², where q is the number of elements of a finite field K over which the sets S1, S2 and S3 are provided.

9. A method according to claim 1 and wherein said supplying comprises obtaining the set S1 from a subset S2′

of k polynomial functions of the set S2, the subset S2′

being characterized in that all coefficients of components involving any of the y₁, . . . , y_k variables in the k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) are zero, and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables.

10. A method according to claim 9 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy one of the following conditions;

(a) for each characteristic p other than 2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, v satisfies the inequality q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰, where K is a finite field over which the sets S1, S2 and S3 are provided,

(b) for p=2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n*(1+sqrt(3)) and less than or equal to n³/6, and

(c) for each p other than 2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n and less than or equal to n⁴.

11. A method according to claim 9 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy the inequalities v<

n² and q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰ for a characteristic p=2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, where K is a finite field over which the sets S1, S2 and S3 are provided and q is the number of elements of K.

12. A method according to claim 1 and wherein said secret key operation comprises a secret affine transformation s on the n+v variables a₁, . . . , a_n+v.

13. A cryptographic method for verifying the digital signature of claim 1, the method comprising:

obtaining the signature e₁, . . . , e_n+v, the message, the hash function and the public key;

applying the hash function on the message to produce the series of k values b₁, . . . , b_k; and

verifying that the equations P₁(e₁, . . . , e_{n+v, b1}, . . . , b_k)=0, . . . , P_k(e₁, . . . , e_n+v, b₁, . . . , b_k)=0 are satisfied.

14. A digital signature produced by the method of claim 1.

15. A method according to claim 1 and wherein said supplying comprises obtaining the set S1 from a subset S2′

of k polynomial functions of the set S2, the subset S2′

being characterized in that all coefficients of components involving orders higher than 1 of any of the n “

oil”

variables a₁, . . . , a_n and coefficients of components involving multiplication of two or more of the n “

oil”

variables a₁, . . . , a_n in the k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) are zero, and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables.

16. A method according to claim 15 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy one of the following conditions;

(a) for each characteristic p other than 2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, v satisfies the inequality q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰, where K is a finite field over which the sets S1, S2 and S3 are provided,

(b) for p=2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n*(1+sqrt(3)) and less than or equal to n³/6, and

(c) for each p other than 2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n and less than or equal to n⁴.

17. A method according to claim 15 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy the inequalities v<

n² and q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰ for a characteristic p=2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, where K is a finite field over which the sets S1, S2 and S3 are provided and q is the number of elements of K.

18. A method according to claim 1 and wherein the computing device comprises at least one of the following:

a computer; and

a smart card.

19. A computer system for generating a signature, comprising:

a signature input receiver operative to receive a set S1 of k polynomial functions as a public-key and a message to be signed, the set S1 including the functions P₁(x₁, . . . , x_n+v, y₁, . . . , y_k), . . . , P_k(x₁, . . . , x_n+v, y₁, . . . , y_k), where k, v, and n are integers, x₁, . . . , x_n+v are n+v variables of a first type, y₁, . . . , y_k are k variables of a second type, and the set S1 is obtained by applying a secret key operation on a set S2 of k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k), where a₁, . . . , a_n+v are n+v variables which include a set of n “

oil”

variables a₁, . . . , a_n, and a set of v “

vinegar”

variables a_n+1, . . . , a_n+v and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables; and

a signature processor operatively associated with the signature input receiver and operative to perform the following operations;

to apply a hash function on the message to produce a series of k values b₁, . . . , b_k,

to substitute the series of k values b₁, . . . , b_k for the variables y₁, . . . , y_k of the set S2 respectively to produce a set S3 of k polynomial functions P″

₁(a₁, . . . , a_n+v), . . . , P″

_k(a₁, . . . , a_n+v),

to select v values a′

_n+1, . . . , a′

_n+v for the v “

vinegar”

variables a_n+1, . . . , a_n+v;

to solve a set of equations P″

₁(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0, . . . , P″

_k(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0 to obtain a solution for a′

1, . . . , a′

_n;

to apply the secret key operation to transform a′

₁, . . . , a′

_n+v into a digital signature e₁, . . . , e_n+v; and

to assign e₁, . . . , e_n+v as the digital signature of the message.

20. Apparatus according to claim 19 and also comprising a signature verifier operatively associated with the signature processor and operative to verify the digital signature.

21. Apparatus according to claim 20 and wherein said signature verifier is operative to verify the digital signature by performing the following operations:

obtaining the signature e₁, . . . , e_n+v, the message, the hash function and the public key;

applying the hash function on the message to produce the series of k values b₁, . . . , b_k; and

verifying that the equations P₁(e₁, . . . , e_n+v, b₁, . . . , b_k)=0, . . . , P_k(e₁, . . . , e_n+v, b₁, . . . , b_k)=0 are satisfied.

22. Apparatus according to claim 19 and wherein the signature processor is operative to perform an HFEV scheme, and the set S2 comprises a set f(a) of k polynomial functions of the HFEV scheme.

23. Apparatus according to claim 22 and wherein said set S2 comprises an expression including k functions that are derived from a univariate polynomial.

24. Apparatus according to claim 23 and wherein said univariate polynomial includes a univariate polynomial of degree less than or equal to 100,000.

25. Apparatus according to claim 19 and wherein the signature processor is operative to perform a UOV scheme, and the set S2 comprises a set S of k polynomial functions of the UOV scheme.

26. Apparatus according to claim 19 and wherein v is selected such that q^v is greater than 2³², where q is the number of elements of a finite field K over which the sets S1, S2 and S3 are provided.

27. Apparatus according to claim 19 and wherein the set S1 is obtained from a subset S2′

of k polynomial functions of the set S2, the subset S2′

being characterized in that all coefficients of components involving any of the y₁, . . . , y_k variables in the k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) are zero, and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables.

28. Apparatus according to claim 27 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy one of the following conditions;

(a) for each characteristic p other than 2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, v satisfies the inequality q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰, where K is a finite field over which the sets S1, S2 and S3 are provided,

(b) for p=2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n*(1+sqrt(3)) and less than or equal to n³/6, and

(c) for each p other than 2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n and less than or equal to n⁴.

29. Apparatus according to claim 27 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy the inequalities v<

n² and q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰ for a characteristic p=2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, where K is a finite field over which the sets S1, S2 and S3 are provided and q is the number of elements of K.

30. Apparatus according to claim 19 and wherein said secret key operation comprises a secret affine transformation s on the n+v variables a₁, . . . , a_n+v.

31. A signature verifier for verifying the digital signature generated by the signature generator of claim 19, the signature verifier comprising a verifier processor operative to perform the following operations:

to obtain the signature e₁, . . . , e_n+v, the message, the hash function and the public key via the signature input receiver;

to apply the hash function on the message to produce the series of k values b₁, . . . , b_k; and

to verify that the equations P₁(e₁, . . . , e_n+v, b₁, . . . , b_k)=0, . . . , P_k(e₁, . . . e_n+v, b₁, . . . , b_k)=0 are satisfied.

32. Apparatus according to claim 19 and wherein the set S1 is obtained from a subset S2′

of k polynomial functions of the set S2, the subset S2′

being characterized in that all coefficients of components involving orders higher than 1 of any of the n “

oil”

variables a₁, . . . , a_n and coefficients of components involving multiplication of two or more of the n “

oil”

variables a₁, . . . , a_n in the k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) are zero, and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables.

33. Apparatus according to claim 32 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy one of the following conditions;

(a) for each characteristic p other than 2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, v satisfies the inequality q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰, where K is a finite field over which the sets S1, S2 and S3 are provided,

(b) for p=2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n*(1+sqrt(3)) and less than or equal to n³/6, and

(c) for each p other than 2 in an “

Oil and Vinegar”

scheme of degree 3, v is greater than n and less than or equal to n⁴.

34. Apparatus according to claim 32 and wherein the set S2 comprises a set S of k polynomial functions of a UOV scheme, and the number v of “

vinegar”

variables is selected to satisfy the inequalities v<

n² and q<sup>(v−

n)−

1</sup>*n⁴>

2⁴⁰ for a characteristic p=2 of a field K in an “

Oil and Vinegar”

scheme of degree 2, where K is a finite field over which the sets S1, S2 and S3 are provided and q is the number of elements of K.

35. Apparatus according to claim 19 and wherein the computer system comprises at least one of the following:

a computer; and

a smart card.

36. A digital signature generated by a computer system the digital signature comprising:

a signature e₁, . . . , e_n+v generated by processing a set S1 of k polynomial functions provided as a public-key and a message to be signed, where the set S1 includes functions P₁(x₁, . . . , x_n+v, y₁, . . . , y_k), . . . , P_k(x₁, . . . , x_n+v, y₁, . . . , y_k), where k, v, and n are integers, x₁, . . . , x_n+v are n+v variables of a first type, y₁, . . . , y_k are k variables of a second type, and the set S1 is obtained by applying a secret key operation on a set S2 of k polynomial functions P′

₁(a₁, . . . , a_n+v, y₁, . . . , y_k), . . . , P′

_k(a₁, . . . , a_n+v, y₁, . . . , y_k) where a₁, . . . , a_n+v are n+v variables which include a set of n “

oil”

variables a₁, . . . , a_n, and a set of v “

vinegar”

variables a_n+1, . . . , a_n+v, and the number v of “

vinegar”

variables is greater than the number n of “

oil”

variables, so that a hash function applied on the message to produce a series of k values b₁, . . . , b_k that are substituted for the variables y₁, . . . , y^k of the set S2 respectively to produce a set S3 of k polynomial functions P″

₁(a₁, . . . , a_n+v), . . . , P″

_k(a₁, . . . , a_n+v) and v values a′

_n+1, . . . , a′

_n+v that are selected for the v “

vinegar”

variables a_n+1, . . . , a_n+v enable to solve a set of equations P″

₁(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0, . . . , P″

_k(a₁, . . . , a_n, a′

_n+1, . . . , a′

_n+v)=0 to obtain a solution for a′

₁, . . . , a′

_n+v, and application of the secret key operation transforms a′

₁, . . . , a′

_n+v into e₁, . . . , e_n+v which is assigned as the digital signature of the message.