Cryptographic communication process

• US 5,790,675 A
• Filed: 07/24/1996
• Issued: 08/04/1998
• Est. Priority Date: 07/27/1995
• Status: Expired due to Term

• Current Assignee: CP8 Technologies (Thales SA)
• Original Assignee: CP8 TRANSAC
• Inventors: Patarin, Jacques
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/685,856
• Time in Patent Office: 741 Days
• Field of Search: 380/30, 380/28, 380/23, 380/25, 380/46, 380/49
• 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

A novel asymmetrical cryptographic schema which can be used for enciphering, signature and authentication. The schema is based on low degree public polynomial equations with value in a finite ring K.

The mechanism is not necessarily bijective. The secret key makes it possible to hide polynomial equations with value in extensions of the ring K. The solving of these equations makes it possible, if one has the secret key, to execute operations which are not executable with the public key alone.

Claims

1. A cryptographic communication process which transforms a value (X) represented by (n) elements of a finite ring (K) into an image value (Y) represented by (n'"'"') elements of the ring (K), characterized in that:

a) each element (n'"'"') of the image value (Y) is in the form of a public polynomial equation having a low degree (D) greater than or equal to 2 composed of the elements (n) of the value (X);

b) obtaining the image value (Y) from the value (X) by means of a transformation comprising the following steps, at least some of which require the knowledge of a cryptographic secret;

b1) applying to the value (X) a first secret polynomial transformation (s) having a degree 1 composed of the (n) elements of the value (X) in order to obtain a first image (I1) with (n) elements;

which (n) elements of the first image (I1) represent a variable or a small number (k) of variables (x, x'"'"', x", . . . , x^k) belonging to an extension (L_W) with the degree W of the ring (K) with W*k=n,

b2) transforming the first image (I1) to a second image by applying to the first image (I1) a transformation defined as follows;

space="preserve" listing-type="equation">f;

L.sub.W.sup.k →

L.sub.W.sup.k

(x, x'"'"', x", . . . , x^k)├

→

(y, y'"'"', y", . . . , y^k) noting that (y, y'"'"', y", . . . , y^k) is the image of (x, x'"'"', x", . . . , x^k) from the transformation f, knowing that f verifies the following two properties;

b2.1) in a base (B) of the extension (L_W) of the ring, each component of the image (y, y'"'"', y", . . . , y^k) is expressed in the form of a polynomial composed of the components of (x, x'"'"', x", . . . , x^k) in this base, which polynomial has a total degree less than or equal to said degree (D) of the public polynomial equation;

b2.2) expressed in the extension (L_W) of the ring, the transformation (f) is such that antecedents of (f) are calculated when they exist, except for certain entries, the number or which is negligible relative to the total number of entries;

b3) applying to the second image (I2) a second secret polynomial transformation (t) having a degree of 1, composed of the elements of the second image (I2) in order to obtain a third image (I3) having a determined number of elements; and

b4) selecting (n'"'"') elements from the elements in the third image (I3) to form said image value (Y).

2. The process according to claim 1, in which said low degree (D) of the public polynomial equation is equal to 2.

3. The process according to claim 1, in which the number k of variables is equal to 1.

4. The process according to claim 3, in which said low degree (D) of the public polynomial equation is equal to 2, (K) is a finite field, and said transformation (F) has the following form:

space="preserve" listing-type="equation">f;

L.sub.W - - - - - - - →

L.sub.W

space="preserve" listing-type="equation">x├

┤

Σ

.sub.i,j β

.sub.i,j *x.sup.Q+P +Σ

.sub.i α

.sub.i *x.sup.S +μ

.sub.0

in which q is the cardinal of the field (K);

Q=q.sup.θ

i,j, P=q.sup.φ

i,j, and S=q.sup.ξ

i, β

_i,j, α

_i and μ

₀ are elements of L_W, and θ

ⁱ,j, φ

ⁱ,j and ξ

ⁱ are integers, and in which the degree in x of the polynomial f is less than or equal to 1,000.

5. The process according to claim 1, such that there are no polynomial equations with a low total degree composed of the components of (x, x'"'"', x", . . . , x^k) and (y, y'"'"', y", . . . , y^k) other than linear combinations of the products of the public equations in small polynomials.

6. The process according to claim 1, such that there are no polynomial equations with the form:

Σ

γ

_ij x_i y_j +Σ

α

_i x_i Σ

β

_j y_j +δ

₀ =0, with at least one of the coefficients γ

_ij, α

_i, β

_j or δ

₀ being non null, which are always verified if the coefficients y_j are the components of the enciphered message, and the coefficients x_i are the components of the unenciphered message.

7. The process according to claim 1, in which the ring (K) is a finite field and the extension (L_W) of the ring is an extension with a degree of W of the ring (K), which means that (L_W) is isomorphic with K X!/g(X), in which g is an irreducible polynomial with a degree of W on K.

8. A process for the asymmetric authentication, by a first person called the verifier, of another person called the prover, characterized in that:

sending the prover a first value (Y) from the verifier;

returning to the verifier from the prover a second value (X) obtained by applying to the first value (Y) a transformation which corresponds to the inverse transformation of that which was the subject of claim 1;

applying to the second value (X) from the verifier the transformation from claim 1 and verifying by the verifier that the result conforms to a predetermined relation linked to the first value (Y).

12. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 1, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

13. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 2, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

14. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 3, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

15. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 4, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

16. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 5, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

17. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 6, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

18. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 7, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

19. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 8, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.

9. A cryptographic communication process which transforms a value (X) represented by (n) elements of a finite ring (K) into an image value (Y) represented by (n'"'"') elements of the ring (K), characterized in that:

a) each element (n'"'"') of the image value (Y) is in the form of a public polynomial equation having a low degree (D) greater than or equal to 2 composed of the elements (n) of the value (X);

b) obtaining the image value (Y) from the value (X) by means of a transformation comprising the following steps, some of which require the knowledge of a cryptographic secret;

b1) applying to the value (X) a first secret polynomial transformation (s) having a degree 1 composed of the (n) elements of the value (X) in order to obtain a first image (I1) with (n) elements;

b2) forming one or more branches, each of which branches is composed of elements of the first image (I1) and,

•

applying to at least one branch (e) the (n_e) elements of the branch representing a variable or a small number (k) of variables (x, x'"'"', x", . . . , x^k) belonging to an extension (L_W) with a degree W of the ring (K) with W*k=n_e, and a transformation defined as follows;

space="preserve" listing-type="equation">f.sub.e ;

L.sub.W.sup.k →

L.sub.W.sup.k

space="preserve" listing-type="equation">(x, x'"'"', x", . . . , x.sup.k)├

→

(y, y'"'"', y", . . . , y.sup.k)

noting that (y, y'"'"', y", . . . , y^k) is the image of (x, x'"'"', x", . . . , x^k) from the transformation f_e, with f_e verifying the following two properties;

b2.1) in a base (B) of the extension (L_W) of the ring, each component of the image (y, y'"'"', y", . . . , y^k) is expressed in the form of a polynomial composed of the components of (x, x'"'"', x", . . . , x^k) in this base, which polynomial has a total degree less than or equal to said degree (D) of the public polynomial equation;

b2.2) expressed in the extension (L_W) of the ring, the transformation (f_e) is such that the antecedents of (f_e) when they exist may be calculated, except for certain entries, the number of which is negligible relative to the total number of entries

•

and applying to the other potential branches polynomial transformations with a degree less than or equal to said degree (D) composed of the components with value in the ring (K);

b3) which branch thus transformed, or the plurality of branches thus transformed, then concatenated, constitutes a second image (I2);

b4) applying to the second image (I2) a second secret polynomial transformation (t), having a degree 1 composed of the elements of the second image (I2) in order to obtain a third image (I3) having a determined number of elements; and

b5) selecting (n'"'"') elements from among the elements in the third image (I3) to form said image value (Y).

10. The process according to claim 9, in which a polynomial with a degree less than or equal to (D) is added at the output of the branch thus transformed or other branches, which polynomial depends only on the variables of the branches situated immediately ahead of this branch.

11. The process according to claim 9, in which the first image (I1) has several branches, one of which branches manipulates values of at least 32 bits.

20. A process for the asymmetric signature of a message (X) and for the verification of this signature, characterized in that the signature is obtained by applying to the message, or to a public transformation of the message, a transformation which corresponds to the inverse transformation of that which is the subject of the process in claim 9, and in that the verification consists of checking that a result (Y) is obtained which conforms to predetermined relations linked to the message to be signed.