HFE and MinRank Public Key Cryptography

Slide 1

HFE and MinRank.

(in public key cryptography)

Support, biblio etc: http://www.minrank.org http://hfe.minrank.org

by Nicolas T. Courtois

Bull CP8 R&D, France courtois@minrank.org

Slide 2

Road Map

1. Alternatives for RSA.

2. OWF with Multivariate Quadratic equations (MQ)

3. Trapdoors - Hidden Field Equations (HFE)

4. 80-bit trapdoor HFE Challenge 1:

⋄ HFE ⇝ MinRank ⇝ MQ ⇝ Solve [Shamir-Kipnis 99], 2^{152} ⋄ HFE ⇝ MinRank ⇝ Solve [Shamir-Kipnis-Courtois 99], 2^{97} ⋄ HFE ⇝ Solve [Courtois 1999], 2^{62}

5. Short signatures (≤ 80 bits !)

6. Zero-knowledge identification with MinRank Slide 3

Alternatives for RSA

The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization (...) is to consider several modular equations in several variables (...)

HFE is believed to be one of the strongest schemes of this type. (...)

Adi Shamir

Two way of generalizing RSA ?

EC Perform the same operations on more complex groups: Elliptic curves [Koblitz, Miller, Crypto’85]

HFE Use more complex polynomials: HFE. [Patarin, Eurocrypt’96]

Slide 4

Security foundations

RSA - based on an algebraical problem: factoring (no exact proof), the RSA problem.

EC - generalize the problems DL and RSA in a group that looks ‘very complex’: black box group. Security based on obscurity of representation of a group and extended expertise.

HFE Two layers of security:

(a) Algebraical problems: MinRank, MQ, IP, HFE.

(b) May combine several layers of ‘obscurity’, operations that destroy the algebraical structure: HFEv-.

Slide 5

Practical security AD 2000

RSA 512 bits - broken [08.1999], 8 000 mips-years.

EC 97 bits - broken [09.1999], about 15 000 mips-years.

HFE (a) The HFE problem 80 bits (s.c. HFE Challenge 1) - Best known attack is in 2^{62} [Courtois 1999].

(b) Modified versions of HFE 80 bits, like HFE–, HFEv, HFEv- etc. No method is known to ditinguish a trapdoor HFE function from random quadratic function. Only attacks very close to the exhaustive search.

Slide 6

Multivariate Quadratic one-way functions

The MQ problem over a ring K: Find (one) solution to a system of m quadratic equations with n variables in K.

f : \{ \begin{matrix}b_{k} = ∑_{i=0}^{n} ∑_{j=i}^{n} λ_{ijk} a_{i}a_{j} \\ with k = 1..m, a_{0} = 1 \end{matrix}

Case n = m = 1.

[figure: K = ZZ_{N}]is hard, factoring N [Rabin].

[figure: K = GF (q)]solved, also for any fixed degree [Berlekamp 1967].

Slide 7

MQ is NP-complete for any field K

[Garey,Johnson], [Patarin, Goubin]. Proof for K = GF (2): We encode 3-SAT ⇝ cubic equations:

{ 0 = x ∨ y ∨ z ; 1 = ¬t ; ⋮  { 0 = xyz + xy + yz + xz + x + y + z ; 1 = 1 + t ; ⋮

Trasform cubic ⇝ quadratic. We put: ⋄ new variables y_{ij} = x_{i}x_{j} ⋄ new trivial equations 0 = y_{ij} − x_{i}x_{j}.

Slide 8

Solving MQ

Case m > \frac{n^{2}}{2} : MQ is solved by linearization (folklore): • New variables y_{ij} = x_{i}x_{j}.

• At least m linear equations with m variables.

Case m = ε\frac{n^{2}}{2} : MQ is expected to be polynomial in n^{O(1/\sqrt{ε})}. This fact has been first claimed by Shamir and Kipnis at Crypto’99. The paper by Courtois, Patarin, Shamir and Klimov ( Eurocrypt 2000) consolidated this claim. XL algorithm.

Case m ≈ n: MQ might be subexponential (no proof).

Slide 9

Conclusions on MQ from Eurocrypt 2000

The best known algorithms for solving n multivariate equations with n variables over a very small finite field are better than the exhaustive search only for about n > 100.

Trapdoors in MQ

General principles od design: ⋄ A hidden function - invertible due to some algebraic properties. ⋄ A basic (algebraic) version of a trapdoor - conceals algebraic structure with invertible affine variable changes (e.g. basic HFE). ⋄ An extended (combinatorial) version of a trapdoor - destroys the algebraic structrue by non-invertible operations (e.g. HFEv-).

Slide 10

K - finite field K = GF (q), q prime or q = p^{α} ∃ a (unique) finite field GF (q^{n}) = K[X]/P (X) with P being a degree n irreducible polynomial over K. GF (q^{n}) ≡ K^{n}, vector space, dimension n over K: x ∈ GF (q^{n}) is encoded as (x_{1}, …, x_{n}), n-tuple of coeffs of a polynomial from K[X] modulo P.

Multivariate and univariate representations.

Every function f : K^{n} → K^{n} can be written as: ⋄ a univariate polynomial. ⋄ n multivariate polynomials with n variables over K.

HFE and MinRank Public Key Cryptography

Slide 11

Multivariate and univariate degree.

If b = f(a) = a^{q^{s}} then all the b_{i} = f_{i}(a_{1}, …, a_{n}) are K-linear. If f(a) = ∑ a^{q^{s}+q^{t}} then all the f_{i} are quadratic.

Example over GF (2).

b = f(a) = a + a^{3} + a^{5} = (a_{2}X^{2} + a_{1}X + a_{0}) + (a_{2}X^{2} + a_{1}X + a_{0})^{3} + (a_{2}X^{2} + a_{1}X + a_{0})^{5} mod X^{3} + X^{2} + 1 = (a_{2}+a_{2}a_{1}+a_{2}a_{0}+a_{1})X^{2}+(a_{2}a_{1}+a_{1}a_{0}+a_{2})X+(a_{0}+a_{2}+a_{1}a_{0}+a_{2}a_{0})

\{ \begin{matrix}b_{2} & = & a_{2} + a_{2}a_{1} + a_{2}a_{0} + a_{1} \\ b_{1} & = & a_{2}a_{1} + a_{1}a_{0} + a_{2} \\ b_{0} & = & a_{0} + a_{2} + a_{1}a_{0} + a_{2}a_{0} \end{matrix}

Slide 12

Hidden Field Equation (HFE).

f(a) = ∑_{q^{s}+q^{t}≤d} γ_{st} a^{q^{s}+q^{t}}

• Re-write as n multivariate quadratic equations: f : { b_{i} = f_{i}(a_{1}, …, a_{n}) }_{i=1..n}

• Hide the univariate representation of f:

Apply two affine invertible variable changes S and T. g = T ∘ f ∘ S

g : x ↦^{S} a ↦^{f} b ↦^{T} y

Slide 13

Using HFE

[figure: public key:] n quadratic polynomials g : { y_{i} = g_{i}(x_{1}, …, x_{n}) }_{i=1..n} [figure: private key:] Knowledge of T, S and f. Since f is bounded degree and univariate, we can invert it: Several methods for factoring univariate polynomials over a finite field are known since [Berlekamp 1967]. Quite slow, example n=128, d=25, 0.17s on PIII-500.

Computing g^{−1} using the private information

x ⟵^{S^{−1}} a ⟵^{f^{−1}} b ⟵^{T^{−1}} y

Slide 14

The HFE problem

A restriction of MQ to the trapdoor function g defined above. [figure: Given]the multivariate representation of g and an y. [figure: Find]a solution x such that g(x)=y. The problem is not to recover a representation of K^{n} in which g becomes a univariate function of bounded degree, but to take advantage of it’s existence to invert function.

HFE problem ≠ HFE cyptosystem

[figure: basic HFE]- algebraical, ∃ algebraical attacks using the existence of the trapdoor. [figure: HFE-, HFEv, ..]versions - combinatorial problems, no attacks on trapdoor.

Nicolas T. Courtois 7

Slide 15

How to recover S and T.

If f were known, ∃ algo in q^{n/2}, the IP problem [Courtois, Eurocrypt’98].

Remark [Shamir]: f is ‘known in 99%’ because d << q^{n} − 1

The weakness of HFE identified [Shamir-Kipnis, Crypto’99].

The homogenous quadratic parts of g (and f) can be written in the univariate representation and represented by a using a symmetric matrix G (resp. F):

g(x) = ∑_{i=0}^{n−1} ∑_{j=i}^{n−1} G_{ij} x^{q^{i}+q^{j}}

rank(G)= supposedly n, and rank(F)=r avec r = log d.

Slide 16

T^{−1} ∘ g =^{?} f ∘ S

Lemma 1 [Shamir-Kipnis]: The matrix representation of f ∘ S is of the form G′ = W GW^{t}. Same rank r. Lemma 2 [Shamir-Kipnis]: T^{−1} ∘ g = ∑_{k=0}^{n−1} t_{k}G^{∗k} with G^{∗k} being the public matrix representations of g^{q^{k}}.

The attack focuses on finding a transformation T such that the matrix representation of T^{−1} ∘ g is of small rank. Find such t_{k} ∈ K^{n} that

Rank(∑_{k=0}^{n−1} t_{k}G^{∗k}) = r

Thus recovering the secret key of HFE is reduced to MinRank.

Slide 17

The problem MinRank

MinRank(n, n, m, r, K)

Given: m matrices n × n over a ring K: M_{1}, … M_{m}.

Find a linear combination α of M_{i} of rank ≤ r.

Rank(∑_{i} α_{i}M_{i}) ≤ r.

Fact: MinRank is NP-complete [Shallit, Frandsen, Buss 1996].

A very hard problem, contains lattice reduction, syndrome decoding, rank-distance decoding problems etc.. MinRank can encode any set of multivariate equations.

Slide 18

Attacks, cont’d

Two ways to solve this MinRank: express it as

• [Shamir-Kipnis] MQ with n(n − r) quadratic equations with

r(n − r) variables over K^{n}, solve by relinearization/XL. 2^{152}

Exhaustive search = 2^{80}

• [Courtois] [also cf. Coppersmith, Stern, Vaudenay] All the sub-matrices (r + 1)x(r + 1) are singular. Linearization.

2^{97}

Slide 19

Do we need to recover the secret key ?

Some cryptanalyses of multivariate schemes:

1. For some the secret key is computed:

• D^{∗} [Courtois 97].

• ‘Balanced Oil and Vinegar’ [Kipnis, Shamir Crypto’98]

• HFE [Kipnis, Shamir Crypto’99].

2. But in many cases the attack does not compute the secret key:

• 2 Shamir schemes. [Coppersmith, Stern, Vaudenay]

• Matsumoto and Imai C^{∗} and [C] schemes [Patarin]

• D^{∗}, L. Dragon, S-boxes, C^{∗−} [Patarin, Goubin, Courtois]

• Equation attacks on HFE [Courtois]

Slide 20 What characterizes functions g that can(not) be inverted ?

⋄ Symmetric cryptography - there should not be a simple way to relate x and g(x) with some equations [Shannon 1948], idea of impredictibility, pseudorandomness.

⋄ Asymmetric cryptography - usually explicit equations g(x). The pseudorandmness paradigm can hardly be applied.

Every deterministic attack can be seen as a series of transformations that start with some complex and implicit equations (x_{i}). It gives at the end some equations that are explicit and simple, e.g. x_{i} = 0 ou 1.

Definition [very informal]: [figure: One-way function]All ‘basic’ combinations of given equations do not give equations that are explicit or ‘simpler’.

Nicolas T. Courtois 10

Slide 21 We denote by G_{j} the expressions in the x_{i} of public equations of g s.t. the equations to solve are G_{j} = 0.

We can generate other (multivariate) equations (true for x) by low degree combination of the G_{j} and the x_{i}.

We require that such ‘trivial’ combinations of public equations remain ‘trivial’

Definition [informal]: A [figure: trivial equation]is small degree combination of the G_{j} and the x_{i}, with terms containing at least one G_{j} and such that it’s complexity (e.g. multivariate degree) does not collapse.

[figure: Soundess] : One such equation, substituted with the values of G_{j} = 0 gives a new low degree equation in the x_{i}.

Slide 22

Implicit equations attacks [Patarin, Courtois].

Several attacks that use several types of equations. Common properties:

⋄ We can only predict the results in very simple cases.

⋄ Experimental equations can be found with no apparent thoretical background.

⋄ The equations are detected only beyond some threshold (e.g. 840 Mo).

HFE Challenge 1

We found equations of type 1 + x + y + x^{2}y + xy^{2} + x^{3}y + x^{2}y^{2}.

An optimised attack runs in 2^{62}, 390 Gb disk space [Courtois 99].

Slide 23

Asymptotic security of HFE

\begin{matrix}Improved Shamir-Kipnis attack \\ Direct attacks by Courtois \end{matrix} \} same cxty
W F = n^{3 log d}

Polynomial if d fixed. Subexponential, because d = n^{O(1)}, therefore

W F = n^{O(log n)}
W F = e^{O(log^{2} n)}

Slide 24

State of Art

⋄ The asymptotic complexity of breaking the algebraical HFE (HFE problem) is currently e^{log^{2}n}. ⋄ In practice basic HFE with n ≥ 127, d > 96 is still secure. ⋄ Modified, combinatorial versions of HFE have no weaknesses known, e.g. HFE^{−} [Asiacrypt’98], vHFE: [Eurocrypt’99]. ⋄ Combinatorial versions of HFE can be hundreds of times faster than RSA, be implemented on smart cards, or give very short signatures for memory cards.

Slide 25

Digital signatures.

f - a trapdoor function, n bits. Usual method: [figure: σ = f^{−1}( H(m) )] H - cryptographic hash. Existential Forgery: Birthday paradox attack:

1. Generate 2^{n/2} verions of the message to be signed m_{1}, …, m_{2^{n/2}}, adding spaces, commas, addenda etc..

2. Generate a list of 2^{n/2} values f(σ_{j}), for random σ_{j}.

3. Sort the two lists, we expect to find (i, j) such that: f(σ_{j}) = H(m_{i})

Slide 26 Thus breaking signatures of 80 bits requires is done in about 2^{40}.

Possible solution [Patarin]

Uses two hash functions H_{1},H_{2}:

[figure: σ = f^{−1} ( H_{1}(m) + f^{−1} [H_{2}(m) + f^{−1}(H_{1}(m))] )]

This method can give secure signatures of e.g. 80 bits. Comparison of typical signatures:

RSA ⇝ 1024 bits
EC ⇝ 220 bits
HFE + above method ⇝ 80 bits  (the shortest known)

Nicolas T. Courtois 13

Slide 27

What signatures are the best ? Bad question

Use several algorithms and issue several certificates. Programs, terminals and devices will have at least one common algorithm for few years. Pro-active scenario: Invalidate some algorithms and introduce new ones. Example, when 768-bit RSA is broken, the 1024-bit RSA expires. Un example of combined certificate: RSA + EC + HFE = 1024 + 256 + 128 bits. RSA is slow and signatures are so long that all the rest is for free !

Slide 28

Zero-knowledge Identification

The breakthrough invention of Zero-knowledge [Goldwasser, Micali, Rackoff 1985]. A Zero-knowledge identification protocol: A protocol between two units the Prover and the Verifier.

• Goal At the end of interaction V says Acceptor Refuse.

• Correctness An honest Prover is always accepted.

• Soundness No one can impersonate the Prover with an overwhelming probability.

• Zero-knowledge An (even malicious) verifier cannot extract from the Prover any information about Prover’s secret knowledge (or ability) that he can’t find out himself.

Slide 29

Known solutions

Several practical Zero-knowledge protocols have been proposed, e.g. Fiat-Shamir, Guillou-Quisquater. Few of them are based on a NP complete problem:

• PKP [Shamir]

• PPP [Pointcheval]

• Schemes related to coding [Harari, Girault, Stern, Chen].

New algorithm - MinRank

Slide 30

Protocol settings

The public key are m non-singular matrices n × n over a finite field GF (q), M_{1}, …, M_{m}. The secret key is α ∈ GF (q)^{n}, such that M = ∑ α_{i} · M_{i} has the rank r < n.

Proposed instances of MinRank.

A small example (best attack in 2^{122}) K = GF (65521), n = 7, m = 7, r = 5. Pick up 10 random matrices 7 × 7, The last matrix is adjusted so that MinRank has a random solution.

Slide 31

The Prover computations

P chooses:

• two random non-singular matrices S and T.

• a random n × n matrix X.

• a random combination β_{1} of M_{i}:

N_{1} = ∑ β_{1i} · M_{i}

P uses the expression of M to get an expression of N_{2} = M + N_{1} as:

N_{2} = ∑ β_{2i} · M_{i}

Principle: (T N_{2}S + X) − (T N_{1}S + X) = T (N_{2} − N_{1})S = T MS.

Slide 32

One round of identification

\overrightarrow{H(X), H(T N_{1}S + X), H(T N_{2}S + X), H(S, T)}

\overleftarrow{q ∈ \{0, 1, 2\}}

If q = 0 the prover reveals:

\overrightarrow{(T N_{1}S + X), (T N_{2}S + X)}

If q = 1, 2 the prover reveals:

\overrightarrow{S, T, β_{q}, X}