Improved Algorithms for Isomorphisms of Polynomials

– Extended Version –

Jacques Patarin, Louis Goubin Bull Smart Cards and Terminals 68 route de Versailles - BP 45 78431 Louveciennes Cedex - France e-mail : {J.Patarin,L.Goubin}@frlv.bull.fr

Nicolas Courtois Systèmes Information Signal (SIS) Université de Toulon et du Var - BP 132 83957 La Garde Cedex - France e-mail : courtois@univ-tln.fr

Abstract

This paper is about the design of improved algorithms to solve Isomorphisms of Polynomials (IP) problems. These problems were first explicitly related to the problem of finding the secret key of some asymmetric cryptographic algorithms (such as Matsumoto and Imai’s C^{∗} scheme of [13], or some variations of Patarin’s HFE scheme of [15]). Moreover, in [15], it was shown that IP can be used in order to design an asymmetric authentication or signature scheme in a straightforward way. We also introduce the more general Morphisms of Polynomials problem (MP). As we see in this paper, these problems IP and MP have deep links with famous problems such as the Isomorphism of Graphs problem or the problem of fast multiplication of n × n matrices.

The complexities of our algorithms for IP are still not polynomial, but they are much more efficient than the previously known algorithms. For example, for the IP problem of finding the two secret matrices of a Matsumoto-Imai C^{∗} scheme over K = F_{q}, the complexity of our algorithms is O(q^{n/2}) instead of O(q^{(n^{2})}) for previous algorithms. (In [14], the C^{∗} scheme was broken, but the secret key was not found). Moreover, we have algorithms to achieve a complexity O(q^{\frac{3}{2} n}) on any system of n quadratic equations with n variables over K = F_{q} (not only equations from C^{∗}). We also show that the problem of deciding whether a polynomial isomorphism exists between two sets of equations is \underline{not} NP-complete (assuming the classical hypothesis about Arthur-Merlin games), but solving IP is at least as difficult as the Graph Isomorphism problem (GI) (and perhaps much more difficult), so that IP ! is unl ikely to be solvable in polynomial time. Moreover, the more general Morphisms of Polynomials problem (MP) is NP-hard. Finally, we suggest some variations of the IP problem that may be particularly convenient for cryptographic use.

Key Words: Morphisms of Polynomials, Isomorphisms of Polynomials, Graph Isomorphisms, Zero-Knowledge Authentications, Asymmetric Signatures.

Note: This paper is the extended version of the paper with the same title published at Eurocrypt’98.

1 Introduction

This paper presents new algorithms for the Isomorphism of Polynomials (IP) problem. IP was explicitly described in [15], where it was shown that if some efficient algorithm exists for IP, then the secret key of some asymmetric cryptosystems (such as the C^{∗} scheme of [13] or some variations of the HFE scheme of [15]) would be found. (The cryptanalysis of C^{∗} given in [14] breaks the scheme without finding the secret key). No polynomial algorithm is known for IP. On the other side, in [15], it was also shown that if no efficient algorithm exists for IP, then this IP problem can be used to design some zero-knowledge authentication schemes. These schemes can also be transformed in order to have an asymmetric signature scheme.

This paper is divided into two parts. In part I, we present different variations of IP and we study a closely related problem, called MP for ”Morphisms of Polynomials”. We then show that these problems are closely related to other and more famous problems such as the Graph Isomorphism problem, and Fast Matrix Multiplication. In part II, we present our improved algorithms for IP. These algorithms are not polynomial (so the schemes based on IP are not broken), but they are much more efficient that the previously known schemes.

Part I: Presentation and general properties of the IP and MP problems

2 The IP and MP problems

IP was presented in [15]. Let us recall what this problem is, in the particular case of quadratic forms (the problem can be generalized without difficulties to cubic forms, as well as forms of higher degree). Let u and n be two integers. Let F_{q} be a finite field. Let (A) be a public set of u quadratic equations with n variables a_{1}, ..., a_{n} over the field F_{q}. We can write these equations as follows:

b_{k} = ∑_{i} ∑_{j} γ_{ijk}a_{i}a_{j} + ∑_{i} μ_{ik}a_{i} + δ_{k}  (1 ≤ k ≤ u).  (A)

Now let s be a bijective and affine transformation of the variables a_{i}, 1 ≤ i ≤ n, and let t be a bijective and affine transformation of the variables b_{k}, 1 ≤ k ≤ u. We denote s(a_{1}, ..., a_{n}) = (x_{1}, ..., x_{n}) and t(b_{1}, ..., b_{n}) = (y_{1}, ..., y_{n}). ¿From (A) we obtain another set (B) of k equations that give the y_{k} values from the x_{i} values:

y_{k} = ∑_{i} ∑_{j} γ′_{ijk}x_{i}x_{j} + ∑_{i} μ′_{ik}x_{i} + δ′_{k}  (1 ≤ k ≤ u).  (B)

We say that (s, t) is an isomorphism from (A) to (B), and we say that (A) and (B) are isomorphic. The IP problem is the following: if (A) and (B) are two public sets of u quadratic equations, and if (A) and (B) are isomorphic, find an isomorphism (s, t) from (A) to (B). When s and t are not necessary bijective, we call the corresponding problem the ”Morphism of Polynomials” problem (MP).

3 Examples

We now present three ”toy examples” in order to become more familiar with the IP and MP problems.

Example of IP with two secrets

Let K = F_{2} be the field in which all the variables x_{0}, ..., x_{4}, y_{0}, ..., y_{4}, a_{0}, ..., a_{4}, b_{0}, ..., b_{4} lie. Let:

(A) \{ \begin{matrix}b_{1} = a_{1} + a_{1}a_{5} + a_{2}a_{3} + a_{2}a_{4} + a_{3}a_{4} \\ b_{2} = a_{3} + a_{4} + a_{5} + a_{1}a_{2} + a_{1}a_{4} + a_{4}a_{5} \\ b_{3} = a_{5} + a_{1}a_{2} + a_{1}a_{3} + a_{1}a_{5} + a_{2}a_{3} + a_{3}a_{5} + a_{4}a_{5} \\ b_{4} = a_{2} + a_{3} + a_{4} + a_{5} + a_{1}a_{5} + a_{3}a_{4} + a_{3}a_{5} \\ b_{5} = a_{4} + a_{1}a_{3} + a_{1}a_{5} + a_{2}a_{3} + a_{2}a_{4} + a_{2}a_{5} + a_{3}a_{4} + a_{3}a_{5} + a_{4}a_{5} \end{matrix}

and let:

(B) \{ \begin{matrix}y_{1} = x_{1} + x_{3} + x_{4} + x_{5} + x_{1}x_{2} + x_{1}x_{3} + x_{1}x_{5} + x_{2}x_{4} + x_{3}x_{5} + x_{4}x_{5} \\ y_{2} = x_{1}x_{4} + x_{1}x_{5} + x_{2}x_{3} + x_{2}x_{4} + x_{1}x_{5} + x_{4}x_{5} \\ y_{3} = x_{1} + x_{3} + x_{4} + x_{1}x_{2} + x_{1}x_{5} + x_{2}x_{3} + x_{3}x_{4} \\ y_{4} = x_{3} + x_{4} + x_{1}x_{2} + x_{1}x_{5} + x_{3}x_{4} + x_{3}x_{5} + x_{4}x_{5} \\ y_{5} = x_{2} + x_{4} + x_{5} + x_{1}x_{3} + x_{1}x_{4} + x_{2}x_{3} + x_{2}x_{4} + x_{2}x_{5} \end{matrix}

The problem is to find two bijective and linear transformations s and t such that (x_{1}, ..., x_{5}) = s(a_{1}, ..., a_{5}), (y_{1}, ..., y_{5}) = t(b_{1}, ..., b_{5}) and such that (A) becomes (B) with these transformations. (This is sometimes called an ”IP problem with two secrets” since here there are \underline{two} secret affine transformations to find: s and t).

[figure: 1; 2; 3; 4; 1; 2; 3; 4]

Figure 1: Graph (I) Graph (II)

Note 1: This ”toy example” comes from the ”toy example” given in [13] for C^{∗}, when the 8 variables are separated in 3 + 5 variables, as explained in [14]. The equation (A) come from the equation b = a^{3} in F_{2^{5}}.

Note 2: It is possible to show that, when s is found, then t is easy to find. However, an exhaustive search on s would require 2^{n^{2}} = 2^{25} computations in this toy example. Our aim is to improve this complexity.

Example of IP with one secret

Let us consider the problem of finding an isomorphism between graphs (I) and (II) of figure 1. Let K be the finite field F_{2}. Let (A) and (B) be the two following sets of equations:

(A) \{ \begin{matrix}y_{1} = a_{1}a_{3} + a_{1}a_{4} + a_{2}a_{3} + a_{2}a_{4} + a_{3}a_{4} \\ y_{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2} \end{matrix} and (B) \{ \begin{matrix}y_{1} = x_{1}x_{2} + x_{1}x_{3} + x_{2}x_{3} + x_{2}x_{4} + x_{3}x_{4} \\ y_{2} = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} \end{matrix}

The problem is to find a bijective and linear transformation s such that (x_{1}, ..., x_{4}) = s(a_{1}, ..., a_{4}), and such that – with this change of variables – the system (A) becomes the system (B) (i.e. such that y_{1} becomes as written in (B), and y_{2} also becomes as written in (B)). If we are able to find all the solutions of this IP problem (this is sometimes called an ”IP problem with one secret” since here there is \underline{one} affine transformation s to find), then some of these solutions will be Graph Isomorphisms from Graph (I) to Graph (II). This comes from the fact that – in (A) – y_{1} was written such that the monomial a_{i}a_{j} is in y_{1} if and only if the point i is linked with the point j in graph (I). Similarly – in (B) – y_{1} was written such that the monomial x_{i}x_{j} is in y_{1} if and only if the point i is linked with the point j in graph (II). Moreover, y_{2} was chosen to be a symmetrical polynomial of the variables, so that any graph isomorphism between graph (I) and graph (II) will be a solution to this particular IP problem with one secret. In section 4, we will generalize this construction to study more precisely the links between Graph Isomorphism and IP with one secret.

Example of MP The variables belong to a ring or to a field K. Let (A) and (B) be the two following sets of equations:

(A) \{ \begin{matrix}b_{1} = a_{1}a′_{1} \\ b_{2} = a_{2}a′_{2} \\ b_{3} = a_{3}a′_{3} \\ b_{4} = a_{4}a′_{4} \\ b_{5} = a_{5}a′_{5} \\ b_{6} = a_{6}a′_{6} \\ b_{7} = a_{7}a′_{7} \end{matrix} and (B) \{ \begin{matrix}y_{1} = x_{1}x′_{1} + x_{3}x′_{2} \\ y_{2} = x_{2}x′_{1} + x_{4}x′_{2} \\ y_{3} = x_{1}x′_{3} + x_{3}x′_{4} \\ y_{4} = x_{2}x′_{3} + x_{4}x′_{4} \end{matrix}

The problem is to find two (non bijective) linear transformations s and t such that (a_{1}, ..., a_{7}, a′_{1}, ..., a′_{7}) = s(x_{1}, ..., x_{4}, x′_{1}, ..., x′_{4}), (y_{1}, ..., y_{4}) = t(b_{1}, ..., b_{7}), s of rank 8, t of rank 4, and such that when (A) is satisfied and when these two transformations s and t are done, then (B) is satisfied. We can notice that the system (B) is the system of equations of a product of two 2 × 2 matrices:

( \begin{matrix}y_{1} & y_{3} \\ y_{2} & y_{4} \end{matrix} ) = ( \begin{matrix}x_{1} & x_{3} \\ x_{2} & x_{4} \end{matrix} ) · ( \begin{matrix}x′_{1} & x′_{3} \\ x′_{2} & x′_{4} \end{matrix} )

In the system (A), we have exactly seven multiplications, so that solving the MP problem is solving the problem: ”How to multiply 2 × 2 matrices with 7 (instead of 8) multiplications”. (The number of additions, subtractions and multiplications with constants of K can be high, but the number of multiplications of terms of the matrices is at most 7). V. Strassen found in 1969 how to multiply 2 × 2 matrices with 7 multiplications (cf [17]). His solution is the following:

\{ \begin{matrix}a_{1} = x_{3} − x_{4} \\ a_{2} = x_{1} + x_{4} \\ a_{3} = x_{1} − x_{2} \\ a_{4} = x_{1} + x_{3} \\ a_{5} = x_{1} \\ a_{6} = x_{4} \\ a_{7} = x_{2} + x_{4} \end{matrix}  \{ \begin{matrix}a′_{1} = x′_{2} + x′_{4} \\ a′_{2} = x′_{1} + x′_{4} \\ a′_{3} = x′_{1} + x′_{3} \\ a′_{4} = x′_{4} \\ a′_{5} = x′_{3} − x′_{4} \\ a′_{6} = x′_{2} − x′_{1} \\ a′_{7} = x′_{1} \end{matrix}  and \{ \begin{matrix}y_{1} = b_{1} + b_{2} − b_{4} + b_{6} \\ y_{2} = b_{4} + b_{5} \\ y_{3} = b_{6} + b_{7} \\ y_{4} = b_{2} − b_{3} + b_{5} − b_{7} \end{matrix}

4 IP with one secret is at least as difficult as Graph Isomorphism

First links between the two problems

We first generalize the construction of section 3 about IP with one secret. Let (I) and (II) be two n-vertices graphs, and let (A) and (B) the following systems:

(A) \{ \begin{matrix}y_{1} = ∑_{i,j} γ_{ij}x_{i}x_{j} \\ y_{2} = ∑_{i=1}^{n} x_{i}^{2} \end{matrix} and (B) \{ \begin{matrix}y_{1} = ∑_{i,j} μ_{ij}a_{i}a_{j} \\ y_{2} = ∑_{i=1}^{n} a_{i}^{2}, \end{matrix}

where all the γ_{ij} and μ_{ij} coefficients lie in {0, 1} and satisfy:

γ_{ij} = 1 ⇔ The i and j vertices of graph (I) are linked together
μ_{ij} = 1 ⇔ The i and j vertices of graph (II) are linked together.

It is easy to see that each graph isomorphism between (I) and (II) corresponds to a morphism of polynomials between (A) and (B). This morphism of polynomials is a very special one, since it can be defined by a_{i} = x_{φ(i)}, where φ is some permutation of {1, ..., n}. Reciprocally, can any isomorphism of polynomials between (A) and (B) be characterized by a_{i} = x_{φ(i)} for some permutation φ of {1, ..., n} ? Of course not, and explicit examples can be built to be convinced. Nevertheless, we can consider the following argument: there exist q^{n(n+1)} possible affine transformations between the x_{i} and the a_{i}, among which q^{n}(q^{n} − 1)(q^{n} − q)(q^{n} − q^{2})...(q^{n} − q^{n−1}) are bijective. The probability that such a transformation leaves y_{1} invariant is a priori ≤ _{\frac{1}{q^{\frac{n(n+1)}{2} +1}}} (because there are

\frac{n(n+1)}{2} monomials x_{i}x_{j} (i ≤ j), and a constant term). The same property is a priori true for y_{2}. Moreover, since

q^{n}(q^{n} − 1)(q^{n} − q)(q^{n} − q^{2})...(q^{n} − q^{n−1}) < (q^{\frac{n(n+1)}{2} +1})^{2},

we can think that – ”most of the time” – there are very few solutions for the IP problem between (A) and (B) that do not correspond to a solution of Graph Isomorphism. Of course, it is a rough evaluation. Nevertheless, it suggests that if a method is found to solve the IP problem with one secret, then we should be able to use this method to also solve the Graph Isomorphism problem. We now study how to obtain a real proof of this property.

Possible improvements

Notice that several practical solutions can be thought of to better eliminate the ”unwanted” solutions of the IP problem between (A) and (B) (i.e. those which do not correspond to a graph isomorphism). For instance, we can add the equation y_{3} = x_{1} +x_{2} +...+x_{n} to (A), and similarly y_{3} = a_{1} +a_{2} +...+a_{n} to (B). More generally, any symmetrical polynomial can be added, for example y_{4} = x_{1}^{3} + x_{2}^{3} + ... + x_{n}^{3} to (A) and y_{4} = a_{1}^{3} + a_{2}^{3} + ... + a_{n}^{3} to (B). (In that case, we must suppose that we can solve IP not only for quadratic systems, but also for systems of higher degree). Another ad hoc solution consists in adding the equation y_{3} = x_{1}^{2} to (A) and y_{3} = a_{k}^{2} to (B), where k is randomly chosen between 1 and n. This way, we can expect – for some of these k values – to eliminate the ”unwanted” solutions, while keeping at least one solution of the Graph Isomorphism problem (but this is not a proof).

A better idea, in order to obtain real proofs, is to introduce two new variables, say X and X′, and to consider the two following systems:

(A) \{ \begin{matrix}y_{1} = ∑_{i,j} γ_{ij}x_{i}x_{j} \\ y_{2} = (X − x_{1})(X − x_{2})...(X − x_{n}) \end{matrix} and (B) \{ \begin{matrix}y_{1} = ∑_{i,j} μ_{ij}a_{i}a_{j} \\ y_{2} = (X′ − a_{1})(X′ − a_{2})...(X′ − a_{n}) \end{matrix} ,

where the γ_{ij} and μ_{ij} values are defined as before. Now, since K[X, X′, a_{1}, ..., a_{n}, x_{1}, ..., x_{n}] is a factorial ring, any solution of the IP problem between (A) and (B) is indeed a solution of the Graph Isomorphism problem (note that the two equations in (A) and (B) can also be combined in one equation like this: y_{1} = (X − x_{1})...(X − x_{n})(X − ∑_{i,j} γ_{ij}x_{i}x_{j})). However, there is still a problem with this construction: the equations y_{2} are of degree n, and if an equation of degree n, with n + 1 variables, is given as a sum of monomials (expanded form), it has a non polynomial (in n) number of terms. We now present the real proof of the link between IP and GI, where this problem is solved, and moreover, we consider again IP on quadratic forms only.

The real proof

We first prove a general property about permutations:

Theorem 4.1 Any permutation σ of {1, ..., n} can be written in a unique way as follows:

σ = τ_{i_{n},n} ∘ τ_{i_{n−1},n−1} ∘ ... ∘ τ_{i_{1},1},

where i_{k} ∈ {1, ..., k} for all k, 1 ≤ k ≤ n, and where τ_{i,j} is the permutation that exchanges i and j (by convention, τ_{i,i} =Id).

Proof: We proceed by induction on n. It is easy to check the result for n = 1 and n = 2. Let us suppose that the result is true for a given integer n, and let us consider a permutation σ of {1, ..., n + 1}. Let i_{n+1} = σ(n + 1), and let σ′ = τ_{i_{n+1},n+1} ∘ σ. The fact that σ′(n + 1) = n + 1 shows that σ′ induces a permutation of {1, ..., n} (that we also denote by σ′). ¿From the induction hypothesis, there exist indices i_{1}, ..., i_{n} satisfying i_{k} ∈ {1, ..., k} for all k, 1 ≤ k ≤ n, and such that:

σ′ = τ_{i_{n},n} ∘ ... ∘ τ_{i_{1},1}.

As a result, we have:

σ = τ_{i_{n+1},n+1} ∘ ... ∘ τ_{i_{1},1},

with i_{k} ∈ {1, ..., k} for all k, 1 ≤ k ≤ n + 1. We have thus proved the existence of the above decomposition of σ. The unicity is a consequence of the following combinatoric argument. Let us denote by S_{n} the set of all permutations of {1, ..., n} and by T the set of all permutations that can be written as τ_{i_{n},n} ∘ ... ∘ τ_{i_{1},1}. There are at most n possibilities for i_{n}, n−1 possibilities for i_{n−1}, ..., and 1 possibility for i_{1}. Therefore, T contains ≤ n! elements. Moreover, we have just proven that the function

F : \{ \begin{matrix}T → S_{n} \\ (τ_{i_{n},n}, ..., τ_{i_{1},1}) ↦ τ_{i_{n},n} ∘ ... ∘ τ_{i_{1},1} \end{matrix}

is surjective. Since |T | ≤ |S_{n}|, we can conclude that F is bijective. The unicity is thus proven.

We now see how to use this theorem to ”translate” the fact that the transformation s involved in the NP-problem corresponding to a Graph Isomorphism instance is characterized by a_{i} = x_{φ(i)} for some permutation φ ∈ S_{n}. According to theorem 4.1, such a permutation can be written as the product of (at most) n permutations τ_{i,j}. To simplify, let us first give a ”translation” of the fact that an affine transformation s : x ↦ a is characterized either by s =Id, or by a_{i} = x_{φ(i)} (for all i), with φ = τ_{ij} for two given indices i and j. It is equivalent to saying that s is an isomorphism of polynomials between the two following systems:

(A) \{ \begin{matrix}y_{0} = (X − x_{i})(X − x_{j}) \\ y_{k} = x_{k} (1 ≤ k ≤ n, k ≠ i, j) \\ y_{n+1} = X \end{matrix} and (B) \{ \begin{matrix}y_{0} = (A − a_{i})(A − a_{j}) \\ y_{k} = a_{k} (1 ≤ k ≤ n, k ≠ i, j) \\ y_{n+1} = A \end{matrix}

By using this argument several times, we obtain the following ”translation” of a Graph Isomorphism problem into an IP problem: s corresponds to an isomorphism of the graphs (i.e. in particular is of the form a_{i} = x_{φ(i)} for some φ ∈ S_{n}) iff it is an isomorphism of polynomials between the two following systems:

(A) \{ \begin{matrix}y_{0} = ∑_{i,j} γ_{ij}x_{i}x_{j} \\ ∀i, j, 1 ≤ i < j ≤ n, (i, j) ≠ (n − 1, n), \{ \begin{matrix}y_{(2n−1)ν_{ij}+1} = (X − x_{i}^{(ν_{ij})})(X − x_{j}^{(ν_{ij})}) \\ y_{(2n−1)ν_{ij}+k+1} = x_{k}^{(ν_{ij})} (1 ≤ k < i) \\ y_{(2n−1)ν_{ij}+k} = x_{k}^{(ν_{ij})} (i < k < j) \\ y_{(2n−1)ν_{ij}+k−1} = x_{k}^{(ν_{ij})} (j < k ≤ n) \\ y_{(2n−1)ν_{ij}+(n−1)+k} = x_{k}^{(ν_{ij+1})} (1 ≤ k ≤ n) \end{matrix} \\ \{ & \begin{matrix}y_{(2n−1)(n−2)(n+1)/2+1} = (X − x_{i}^{((n−2)(n+1)/2)})(X − x_{j}^{((n−2)(n+1)/2)}) \\ y_{(2n−1)(n−2)(n+1)/2+k+1} = x_{k}^{((n−2)(n+1)/2)} (1 ≤ k < i) \\ y_{(2n−1)(n−2)(n+1)/2+k} = x_{k}^{((n−2)(n+1)/2)} (i < k < j) \\ y_{(2n−1)(n−2)(n+1)/2+k−1} = x_{k}^{((n−2)(n+1)/2)} (j < k ≤ n) \end{matrix} \\ y_{(2n−1)(n−2)(n+1)/2+n} = X \end{matrix}

and

(B) \{ \begin{matrix}y_{0} = ∑_{i,j} μ_{ij}x_{i}x_{j} \\ ∀i, j, 1 ≤ i < j ≤ n, (i, j) ≠ (n − 1, n), \{ \begin{matrix}y_{(2n−1)ν_{ij}+1} = (A − a_{i}^{(ν_{ij}+1)})(A − a_{j}^{(ν_{ij}+1)}) \\ y_{(2n−1)ν_{ij}+k+1} = a_{k}^{(ν_{ij}+1)} (1 ≤ k < i) \\ y_{(2n−1)ν_{ij}+k} = a_{k}^{(ν_{ij}+1)} (i < k < j) \\ y_{(2n−1)ν_{ij}+k−1} = a_{k}^{(ν_{ij}+1)} (j < k ≤ n) \\ y_{(2n−1)ν_{ij}+(n−1)+k} = a_{k}^{(ν_{ij+1})} (1 ≤ k ≤ n) \end{matrix} \\ \{ & \begin{matrix}y_{(2n−1)(n−2)(n+1)/2+1} = (A − a_{i})(A − a_{j}) \\ y_{(2n−1)(n−2)(n+1)/2+k+1} = a_{k} (1 ≤ k < i) \\ y_{(2n−1)(n−2)(n+1)/2+k} = a_{k} (i < k < j) \\ y_{(2n−1)(n−2)(n+1)/2+k−1} = a_{k} (j < k ≤ n) \end{matrix} \\ y_{(2n−1)(n−2)(n+1)/2+n} = A \end{matrix}

where ν_{ij} = i − 1 + \frac{(j−1)(j−2)}{2} and X, A, as well as the x_{k}^{(ν)} and a_{k}^{(ν)}, are intermediate variables. Each of these two systems contains \frac{2n^{3}−3n^{2}−n+4}{2} equations over \frac{(n+1)(n^{2}−2n+2)}{2} variables.

Conclusion: By solving IP with one secret on a set of O(n^{3}) quadratic equations we can solve any Graph Isomorphism problem with n vertices. Therefore, IP is at least as hard as GI.

Remark:

1. In the particular case where (A) and (B) contain only one quadratic equation with n variables, there exist a polynomial algorithm to find the isomorphism (see [15]).

2. We do not pretend that this construction gives a new and more efficient way to solve the Graph Isomorphism problem. In fact, although no polynomial algorithm is known for the Graph Isomorphism problem, in practice very efficient algorithms are known: for example it is feasible to find an isomorphism for graphs even for ”hard” instances of 1000 vertices graphs in less than 10 minutes on a personal computer (see [6] p. 22). So the main interest of this construction is to show that the IP problem with one secret is probably not solvable with a probabilistic algorithm of polynomial complexity. (Because GI was carefully studied and many people think that GI is not solvable in polynomial complexity).

5 MP is NP-hard

In this section, we prove that the Morphism of Polynomials (MP) problem, defined in section 2, is NP-hard for any finite field, and for the rational numbers. The proof uses some properties of three-dimensional tensors. Let us first recall some basic definitions:

Definitions:

1. A three-dimensional tensor is a three-dimensional array T = (t_{ijk}) of numbers.

2. It has rank 1 iff it can be written as the outer product of three vectors (i.e. iff there exist three vectors x, y and z such that m_{ijk} = x_{i}y_{j}z_{k} for all indices i, j, k).

3. The rank of a general tensor T is the minimal number of rank 1 tensors T_{ν} such that T = ∑_{ν} T_{ν}.

The following result about the complexity of finding the rank of a three-dimensional tensor was proved by Johan Håstad in [11]:

Theorem 5.1 (Håstad) Tensor rank is NP-complete for any finite field and NP-hard for the rational numbers.

Let us now see how this fundamental property can be applied to our MP problem. Let us suppose we have an algorithm Φ that solves the MP-problem in polynomial time (in particular, this algorithm can be used to know whether there exist a solution or not for some given instance of the MP-problem). Let T = (t_{ijk}) be a m×n×ℓ (three-dimensional) tensor. It is well known (see for instance [18]) that the rank of T is exactly equal to the minimal number of multiplications needed to compute the following corresponding set of bilinear forms by a bilinear non-commutative algorithm:

(B) { y_{1} = ∑_{i=1}^{m} ∑_{j=1}^{n} t_{ij1}x_{i}x′_{j} ; ⋮ ; y_{ℓ} = ∑_{i=1}^{m} ∑_{j=1}^{n} t_{ijℓ}x_{i}x′_{j}.

Let r (= rank(T)) be this minimal value. By definition, r can be thought as the smallest integer u such that two linear transformations s : (x_{1}, ..., x_{m}, x′_{1}, ..., x′_{n}) ↦ (a_{1}, ..., a_{u}, a′_{1}, ..., a′_{u}) and t : (b_{1}, ..., b_{u}) ↦ (y_{1}, ..., y_{ℓ}) exist, that transform

(A) { b_{1} = a_{1} · a′_{1} ; ⋮ ; b_{u} = a_{u} · a′_{u}.

into (B). This is a particular instance of the MP problem. For u = mn, finding a solution (s, t) is quite easy. Namely, we can define s and t by the following formulas:

∀i, 1 ≤ i ≤ m, ∀j, 1 ≤ j ≤ n, \{ \begin{matrix}a_{(i−1)n+j} = x_{i} \\ a′_{(i−1)n+j} = x′_{j}. \end{matrix}

∀k, 1 ≤ k ≤ ℓ, y_{k} = ∑_{i=1}^{m} ∑_{j=1}^{n} t_{ijk}b_{(i−1)n+j}.

Note: Moreover, any symmetry of a given three-dimensional tensor leaves its rank unchanged, so that we have in fact:

r ≤ min(mn, nk, km),

which is the analogue of the classical inequality rank(M) ≤ min(m, n) for a (two-dimensional) m × n matrix M. The Φ algorithm can now be used to build a polynomial algorithm that computes the exact value of r:

1. Let u = mn.

2. With the help of Φ, try to find two linear transformations s : (x_{1}, ..., x_{m}, x′_{1}, ..., x′_{n}) ↦ (a_{1}, ..., a_{u}, a′_{1}, ..., a′_{u}) and t : (b_{1}, ..., b_{u}) ↦ (y_{1}, ..., y_{ℓ}) that transform

(A) { b_{1} = a_{1} · a′_{1} ; ⋮ ; b_{u} = a_{u} · a′_{u}.

into (B).

3. If Φ gives a solution, then replace u by u − 1 and go back to step 2, else output ”r = u + 1”.

It is easy to see that this algorithm outputs the correct value of r after at most mn calls to the (polynomial) Φ algorithm, so that we have built an algorithm that computes the rank of a threedimensional tensor in polynomial time. According to the result of Johan Håstad mentioned above, we can thus conclude that the MP-problem is NP-hard for any finite field, and for the rational numbers.

Remarks:

1. More precisely, we have just proven that the ”Deciding MP” problem (i.e. the problem of finding whether there exist a morphism between to given sets of multivariate polynomial equations) is NP-complete. As we will see in section 6, this property becomes false if we replace ”MP” by ”IP”.

2. MP is clearly a very important problem in mathematics: an efficient algorithm would give the computation of the minimum number of standard multiplications to compute the product of two 3 × 3, 4 × 4 or k × k matrices, for small k, and – from this – improved algorithms for Gaussian reductions and related problems may be found. (The best known asymptotic algorithms are at the present in O(n^{c}), where c ≃ 2.3755, see [4]. It is also interesting to see what kind of brute-force computations have been done so far to solve such problems, see [10].)

3. The fact that MP is NP-hard, and moreover the fact that MP is a very important problem that seems to be very difficult even with very small parameters, are strong motivations to design cryptographic algorithms based on this problem. From [2] and [7], it is known that any problem of NP can be used to design an asymmetric authentication scheme (with the help of ”good” hash functions). (The proof is extendable to design asymmetric signature schemes. again with the help of ”good” hash functions). Since MP is in NP, we can apply these general results. However, these very general constructions are not very practical, and it may be more difficult to design efficient schemes from MP than from IP.

6 Deciding IP is not NP-complete

We call ”Deciding IP” the problem of finding whether there exist an isomorphism between two sets of multivariate polynomials equations. In this section, we prove that the Deciding IP problem is not NP-complete, under the classical hypothesis that the so-called ”polynomial-time hierarchy” does not collapse. The proof is based on the following general results (see [9] and [3] for proofs):

Theorem 6.1 (Goldwasser, Sipser) If a problem has a constant-round interactive proof, then it also has a constant-round Arthur-Merlin protocol.

Theorem 6.2 (Boppana, Håstad, Zachos) If the complement of a problem Π has an Arthur-Merlin protocol with a constant number of rounds, and if Π is NP-complete, then the polynomial-time hierarchy collapses.

Note: Arthur-Merlin protocols have been studied by Babai and Moran in [1], but we do not need to go into further details for our proof.

What remains to do is building a constant-round interactive proof for the ”Non Isomorphism of Polynomials” (Non-IP) problem. For that purpose, we use techniques discovered by Goldwasser, Micali and Rackoff ([8]) for the analogous ”Quadratic Non-Residuosity” problem, and also used by Goldreich, Micali and Wigderson ([7]) for ”Graph Non-Isomorphism”, and by Petrank and Roth ([16]) for ”Code Non-Equivalence”. As usual, we suppose that two sets (U_{0}) and (U_{1}) of polynomial equations are public, and an infinitelypowerful prover (called Merlin) wants to convince a polynomial-time verifier (called Arthur) that (U_{0}) and (U_{1}) are not isomorphic. They can proceed as follows:

First round: Arthur takes K numbers α_{1}, ..., α_{K} randomly chosen in {0, 1}. For each k, 1 ≤ k ≤ K, Arthur builds a set (V_{k}) which is isomorphic to (U_{α_{k}}), by choosing two random s_{k} and t_{k} bijective affine permutations and computing (V_{k}) = t_{k} ∘ (U_{α_{k}}) ∘ s_{k}. He sends (V_{1}), ..., (V_{K}) to Merlin.

Second round: For each k, 1 ≤ k ≤ K, Merlin tries to guess α_{k}, i.e. he tries to find whether (V_{k}) is isomorphic to (U_{0}) or (U_{1}). He sends his guesses (β_{1}, ..., β_{K}) to Arthur.

Final verification: Arthur accepts the proof iff β_{k} = α_{k} for all k, 1 ≤ k ≤ K.

It is easy to see that:

1. If (U_{0}) and (U_{1}) are non isomorphic, Merlin never fails in convincing Arthur.

2. If (U_{0}) and (U_{1}) are isomorphic, the probability that Arthur is convinced that (U_{0}) and (U_{1}) are non-isomorphic is at most 2^{−K}.

Part II: New algorithms for IP

We use the same notations as in section 2 (for u, n, q, (A) and (B)). In sections 7 and 8, we will design some improved algorithms for the IP problem on two sets of u quadratic equations with n variables. Then, in section 10, we will concentrate on the special case u = n.

7 A first algorithm for IP

Let α_{1}, …, α_{u} be u values randomly chosen in K = F_{q}. There is a probability 1/q^{u} that ∑_{i=1}^{u} α_{i}b_{i} =

y_{1} ∘ s (∗). Moreover when (∗) occurs it is very easy to find an affine bijection S transforming a into x such that (∗) does occur (when (∗) is written in a and x instead of b and y). The reason for this is that there is a ”canonical” representation of each equation of degree two over a finite field (cf. [12], chapter 6 for example), and from the canonical representations of ∑_{i=1}^{u} α_{i}b_{i} and y_{1},

when these equations are written in a and x, it will be easy to find such a bijection S. What is the probability that this S is indeed the right s ? If u ≠ 1, in the matrix of the secret affine function s we have n(n + 1) coefficients and (∗) gives only 1 + n(n + 1)/2 quadratic equations on these coefficients if K = F_{2} and n(n + 1)/2 + n + 1 is K ≠ F_{2}. So

the probability that we will recover the right s this way is expected to be approximately 1/q^{u−1}.q^{\frac{n^{2}+n}{2}}

if K = F_{2} and approximately 1/q^{u−1} ·q^{\frac{n^{2}−n}{2}} if K ≠ F_{2}. Then, when s is found it is then easy to recover t by gaussian reductions on the coefficients of t.

The complexity of this algorithm to recover the secrets is expected to be O(q^{\frac{n^{2}+n+2u}{2}} ) if K = F_{2} and

O(q^{\frac{n^{2}−n+2u}{2}} ) if K ≠ F_{2} (because we try again another S until we find a valid solution). This is better

than the complexity O(q^{n^{2}+n}) of exhaustive search on s.

Note 1. If u = 1 then the first part of the algorithm will easily find an s solution (not necessary the right s) so u must be ≠ 1.

Note 2. It is logical to try to improve this algorithm, for example by using two equations ∑_{i=1}^{u} α_{i}b_{i} =

y_{1} ∘ s and ∑_{i=1}^{u} α′_{i}b_{i} = y_{2} ∘ s. However, it is not clear how to combine these equations in order to improve

the algorithm. More precisely, when u ≥ 2, we do not know any polynomial algorithm for the IP problem. Even for u = 2, finding such an algorithm appears to be as difficult as finding a probabilistic polynomial algorithm for the Graph Isomorphism problem, as we saw in section 4.

8 A second algorithm for IP (found by H. Gilbert and F. Cherbonnier)

As before, let A be the quadratic transformation that gives b from a, and B be the quadratic transformation that gives y from x:

b = A(a) ; y = B(x).

Let s and t be the two secret affine transformations such that a = s(x) and y = t(b). Therefore:

b = t^{−1} ∘ B(x) = A ∘ s(x).

The idea is to use the fact that the components of A∘s are always linear combinations of the components of B. Moreover, this is of course also true if we consider A ∘ s only on a small number of variables.

Example Let (A) and (B) be the following two sets of equations:

(A) : \{ \begin{matrix}b_{1} = a_{1} + a_{1}a_{5} + a_{2}a_{3} + a_{2}a_{4} + a_{3}a_{4} \\ b_{2} = a_{3} + a_{4} + a_{5} + a_{1}a_{2} + a_{1}a_{4} + a_{4}a_{5} \\ b_{3} = a_{5} + a_{1}a_{2} + a_{1}a_{3} + a_{1}a_{5} + a_{2}a_{3} + a_{3}a_{5} + a_{4}a_{5} \\ b_{4} = a_{2} + a_{3} + a_{4} + a_{5} + a_{1}a_{5} + a_{3}a_{4} + a_{3}a_{5} \\ b_{5} = a_{4} + a_{1}a_{3} + a_{1}a_{5} + a_{2}a_{3} + a_{2}a_{4} + a_{2}a_{5} + a_{3}a_{4} + a_{3}a_{5} + a_{4}a_{5} \end{matrix}

((A) comes from b = a^{3}).

(B) : \{ \begin{matrix}y_{1} = x_{1} + x_{3} + x_{4} + x_{5} + x_{1}x_{2} + x_{1}x_{3} + x_{1}x_{5} + x_{2}x_{4} + x_{3}x_{5} + x_{4}x_{5} \\ y_{2} = x_{1}x_{4} + x_{1}x_{5} + x_{2}x_{3} + x_{2}x_{4} + x_{2}x_{5} + x_{4}x_{5} \\ y_{3} = x_{1} + x_{3} + x_{4} + x_{1}x_{2} + x_{1}x_{5} + x_{2}x_{3} + x_{3}x_{4} \\ y_{4} = x_{3} + x_{4} + x_{1}x_{2} + x_{1}x_{5} + x_{3}x_{4} + x_{3}x_{5} + x_{4}x_{5} \\ y_{5} = x_{2} + x_{4} + x_{5} + x_{1}x_{3} + x_{1}x_{4} + x_{2}x_{3} + x_{2}x_{4} + x_{2}x_{5} \end{matrix}

The problem is to find two linear transformations s and t such that a = s(x) and y = t(b).

Remark This example comes from a transformation made in [14] of the ”toy example” given in [13].

We will choose x_{4} = 0 and x_{5} = 0 (so that we obtain a vector space of dimension 6 > 5 generated by the monomials x_{1}, x_{2}, x_{3}, x_{1}x_{2}, x_{1}x_{3}, x_{2}x_{3}). (B) becomes:

(B) : \{ \begin{matrix}y_{1} = x_{1} + x_{3} + x_{1}x_{2} + x_{1}x_{3} \\ y_{2} = x_{2}x_{3} \\ y_{3} = x_{1} + x_{3} + x_{1}x_{2} + x_{2}x_{3} \\ y_{4} = x_{3} + x_{1}x_{2} \\ y_{5} = x_{2} + x_{1}x_{3} + x_{2}x_{3} \end{matrix}

So the vector space generated by the equations of (B) is the vector space generated by the 5 vectors {x_{1}, x_{2}, x_{1}x_{3}, x_{2}x_{3}, x_{3} + x_{1}x_{2}}. Let s be:

(s) : \{ \begin{matrix}a_{1} = α_{1}x_{1} + α_{2}x_{2} + α_{3}x_{3} (+α_{4}x_{4} + α_{5}x_{5}) \\ a_{2} = β_{1}x_{1} + β_{2}x_{2} + β_{3}x_{3} (+β_{4}x_{4} + β_{5}x_{5}) \\ a_{3} = γ_{1}x_{1} + γ_{2}x_{2} + γ_{3}x_{3} (+γ_{4}x_{4} + γ_{5}x_{5}) \\ a_{4} = δ_{1}x_{1} + δ_{2}x_{2} + δ_{3}x_{3} (+δ_{4}x_{4} + δ_{5}x_{5}) \\ a_{5} = ε_{1}x_{1} + ε_{2}x_{2} + ε_{3}x_{3} (+ε_{4}x_{4} + ε_{5}x_{5}) \end{matrix}

We then perform an exhaustive search on the α_{i}, β_{i}, γ_{i}, δ_{i}, ε_{i} (1 ≤ i ≤ 3) values, i.e. there are 2^{15} possibilities for these values.

Example of value: We try

\{ \begin{matrix}a_{1} = x_{1} (+α_{4}x_{4} + α_{5}x_{5}) \\ a_{2} = x_{2} (+β_{4}x_{4} + β_{5}x_{5}) \\ a_{3} = x_{3} (+γ_{4}x_{4} + γ_{5}x_{5}) \\ a_{4} = 0 (+δ_{4}x_{4} + δ_{5}x_{5}) \\ a_{5} = x_{1} + x_{2} (+ε_{4}x_{4} + ε_{5}x_{5}) \end{matrix}

Then:

b_{1} = x_{1}x_{2} + x_{2}x_{3}.

However, this b_{1} is not in the vector space generated by {x_{1}, x_{2}, x_{1}x_{3}, x_{2}x_{3}, x_{3} + x_{1}x_{2}}. As a result, this choice for the values α_{i}, β_{i}, γ_{i}, δ_{i}, ε_{i} (1 ≤ i ≤ 3) can be eliminated.

Complexity: For about one try among 32, the five values b_{i} (1 ≤ i ≤ 5) will be in the vector space generated by \{x_{1}, x_{2}, x_{1}x_{3}, x_{2}x_{3}, x_{3} + x_{1}x_{2}\} (because each value b_{i} has a probability about \frac{1}{2} to be in this vector space). Then for these cases, we will consider x_{4} ≠ 0 and we will try all the values for α_{4}, β_{4}, γ_{4}, δ_{4}, ε_{4}. This way, we may thus hope to find the good s (and t) after about 2^{15} tried values.

General complexity of the algorithm In general, (A) and (B) are two sets of the following type:

(A) : { b_{1} = P_{1}(a_{1}, ..., a_{n}) ; ⋮ ; b_{u} = P_{u}(a_{1}, ..., a_{n}) and (B) : { y_{1} = P′_{1}(x_{1}, ..., x_{n}) ; ⋮ ; y_{u} = P′_{u}(x_{1}, ..., x_{n})

We will choose all the values x_{i} = 0, i > λ, where λ is such that:

λ + \frac{λ(λ − 1)}{2} > u (i.e. λ ≃ \sqrt{2u})

Therefore, the vector space generated by x_{1}^{2}, x_{2}^{2}, ..., x_{λ}^{2}, x_{1}x_{2}, ..., x_{i}x_{j} (1 ≤ i < j ≤ λ), ..., x_{λ−1}x_{λ} will have a dimension > u. We will then perform an exhaustive search on the part of s that gives a_{1}, ..., a_{n} from x_{1}, ..., x_{λ}, i.e. on λn values. The complexity of this part 1 is thus expected to be about q^{nλ} = q^{n\sqrt{2}\sqrt{u}}. Then for about one try among (q^{\frac{λ^{2}+λ}{2} −u})^{u}, the u values b_{i} (1 ≤ i ≤ u) will be in the right vector space. Then for these cases we will continue by introducing the value x_{λ+1}. This introduces q^{n} new possibilities, so that the typical value λ for the complexity of this part 2 of the algorithm is such that \frac{λ^{2}+λ}{2} − u ≥ \frac{n}{u} (i.e. λ ≃ \sqrt{2}\sqrt{\frac{n}{u} + u}).

Conclusion: The complexity of this algorithm is thus expected to be at most q^{nλ} = q^{n\sqrt{2}\sqrt{\frac{n}{u} +u}}.

Remarks

• When u = n, this is q^{O(n^{\frac{3}{2}} )}, which is better than the bound q^{O(n^{2})} of the previous algorithms.

• When u = 2, this is also q^{O(n^{\frac{3}{2}} )}.

9 Some easy cases of IP with one secret

As seen in section 4, IP with one secret is at least as difficult as Graph Isomorphism. However, some instances of IP with one secret are easy to solve, as we will see now. Let us consider for example the case of IP on two quadratic equations over a field of characteristic p ≠ 2. We can write these equations as:

\{ \begin{matrix}q_{1} = ^{t}aA_{1}a \\ q_{2} = ^{t}aA_{2}a \end{matrix} and \{ \begin{matrix}q_{1} = ^{t}xB_{1}x \\ q_{2} = ^{t}xB_{2}x \end{matrix}

These two systems of two equations are public. The secret invertible matrix is S such that x = Sa. The problem is to find S. Let us assume that A_{1} or A_{2} is invertible (say A_{1} for example). Since

\{ \begin{matrix}A_{1} = ^{t}SB_{1}S \\ A_{2} = ^{t}SB_{2}S \end{matrix}

we have (since A_{1} is invertible):

B_{2}S = B_{1}SA_{1}^{−1}A_{2}. (∗)

This equation (∗) is of \underline{degree one} in the values of the secret matrix S ! So, from (∗) we will obtain some informations on the matrix S. However, it is not clear how to obtain similar informations on S when A_{1} and A_{2} are not invertible (the case p = 2 may also create some technical difficulties, but it may be also feasible to find S when p = 2 and A_{1} or A_{2} is invertible).

Toy example 1: Let K = F_{3} and let the public equations be:

\{ \begin{matrix}q_{1} = 2a_{1}^{2} + a_{1}a_{2} + 2a_{1}a_{3} + a_{2}^{2} + 2a_{2}a_{3} \\ q_{2} = a_{1}^{2} + a_{1}a_{3} + a_{2}^{2} + 2a_{3}^{2} \end{matrix} and \{ \begin{matrix}q_{1} = 2x_{1}^{2} + x_{1}x_{2} + 2x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} \\ q_{2} = 2x_{1}^{2} + x_{1}x_{2} + x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} + 2x_{3}^{2}. \end{matrix}

So A_{1} = ( \begin{matrix}2 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ), A_{2} = ( \begin{matrix}1 & 0 & 2 \\ 0 & 1 & 0 \\ 2 & 0 & 2 \end{matrix} ), B_{1} = ( \begin{matrix}2 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ) and B_{2} = ( \begin{matrix}2 & 2 & 2 \\ 2 & 1 & 1 \\ 2 & 1 & 2 \end{matrix} ).

Here A_{1} and A_{2} are invertible.

Let S = ( \begin{matrix}α_{1} & β_{1} & γ_{1} \\ α_{2} & β_{2} & γ_{2} \\ α_{3} & β_{3} & γ_{3} \end{matrix} ).

By writing that B_{2}S = B_{1}SA_{1}^{−1}A_{2}, we find (after some Gaussian reductions):

\begin{matrix}α_{1} = 0, & α_{2} = ?, & α_{3} = 2α_{2}, \\ β_{1} = 2α_{2}, & β_{2} = 2α_{2}, & β_{3} = 0, \\ γ_{1} = 0, & γ_{2} = ?, & γ_{3} = α_{2}. \end{matrix}

So after a few tries on α_{2} and γ_{2}, a solution can easily be found for S:

S = ( \begin{matrix}0 & 1 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 2 \end{matrix} ) .

Toy example 2: Let K = F_{3} and let the public equations be:

\{ \begin{matrix}q_{1} = 2a_{1}^{2} + a_{1}a_{2} + 2a_{1}a_{3} + a_{2}^{2} + 2a_{2}a_{3} \\ q_{2} = 2a_{1}^{2} + a_{1}a_{3} + a_{2}^{2} + 2a_{3}^{2} \end{matrix} and \{ \begin{matrix}q_{1} = 2x_{1}^{2} + x_{1}x_{2} + 2x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} \\ q_{2} = 2x_{1}x_{2} + x_{1}x_{3} + 2x_{2}^{2} + 2x_{2}x_{3} + 2x_{3}^{2}. \end{matrix}

So A_{1} = ( \begin{matrix}2 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ), A_{2} = ( \begin{matrix}2 & 0 & 2 \\ 0 & 1 & 0 \\ 2 & 0 & 2 \end{matrix} ), B_{1} = ( \begin{matrix}2 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ) and B_{2} = ( \begin{matrix}0 & 1 & 2 \\ 1 & 2 & 1 \\ 2 & 1 & 2 \end{matrix} ).

Here A_{1} is invertible, and A_{2} is not invertible.

Let S = ( \begin{matrix}α_{1} & β_{1} & γ_{1} \\ α_{2} & β_{2} & γ_{2} \\ α_{3} & β_{3} & γ_{3} \end{matrix} ).

By writing that B_{2}S = B_{1}SA_{1}^{−1}A_{2}, we find (after some Gaussian reductions):

\begin{matrix}α_{1} = ?, & α_{2} = ?, & α_{3} = ?, \\ β_{1} = α_{1} + α_{2} + 2α_{3}, & β_{2} = α_{1} + α_{3} & β_{3} = α_{1} + 2α_{2} + 2α_{3}, \\ γ_{1} = α_{1}, & γ_{2} = 2α_{2} + 2α_{3}, & γ_{3} = α_{2}. \end{matrix}

So after a few tries on α_{1}, α_{2}, α_{3}, a solution can easily be found for S:

S = ( \begin{matrix}0 & 1 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 2 \end{matrix} ) .

10 Algorithms for IP with two secrets in O(q^{O(n)})

Further investigation of the IP problem requires to divide it into smaller subproblems. Thus, we separate the one and two secret cases, and more precisely we limit ourselves to the central case u = n. We call this case central because the case u = 1 is easily solved as most cases u > (n+1)(n+2)/2. As a matter of fact it becomes easy as soon as some (n + 1)(n + 2)/2 equations are independent (as a formal sum of x_{i}x_{j} coefficients), so that the u quadratic equations form a generating set. The probability of being so rapidly tends to 1 as u grows. In that case any invertible s allow to find at least one t by Gaussian reduction and every two generating sets of equations are isomorphic. We also found interesting to separate the affine part of applications s and t, as the linear case seems a bit easier. However, since it is always possible to find the constant terms by exhaustive search in O(q^{n}), any algorithm for the IP problem with linear s and t with complexity O(q^{αn}) can obviously be transformed into a general algorithm for affine s and t with complexity O(q^{(α+1)n}).

So from now on and throughout the present section we exclusively consider the IP problem with two secret linear s and t transformations. As a consequence of separation between affine and linear parts, we should suppose that A(0) = 0 and B(0) = 0. Otherwise we would have a completely artificial weakness, as we know that t(A(0)) = B(0) and it gives an a priori knowledge on t.

The present section is divided into three parts (in these three parts, s and t are assumed to be linear). First, we will see a simple algorithm solving most cases of the IP in n^{O(1)}O(q^{n}) and using n^{O(1)}O(q^{n}) memory. Then we will explain a very different approach which uses only polynomial memory and runs in between n^{O(1)}O(q^{n}) and n^{O(1)}O(q^{2n}) for all IP cases. Finally we will try to combine the ideas of these two attacks in a very powerful, ‘birthday paradox’-based attack which to the best of our knowledge runs for every IP in n^{O(1)}O(q^{n/2}) with n^{O(1)}O(q^{n/2}) memory. Only the last attack uses the fact that equations given in IP are quadratic forms. The first two can operate on any function of indifferent degree.

10.1 A simple attack in n^{O(1)}O(q^{n}) based on inversion

This attack operates in n^{O(1)}O(q^{n}) and uses n^{O(1)}O(q^{n}) of memory space used essentially to form a complete table of A and B functions. Let A be a randomly chosen quadratic equations set. We studied a probability p_{i} of a random value b of the A form to have i possible corresponding entries a. We made a lot of computer simulations and we have found that the probability distribution of p_{i} for a randomly chosen set of quadratic equations is the same as for any randomly chosen function, which can be easily shown to be p_{i} = \frac{1}{ei!}. It allows to divide entries into classes, following their image’s inversion degree. The elements of each class can be summed up and the corresponding values for A and B must correspond through the linear transformation s. They do not necessarily sum up to 0, since as p_{i} → 0 we have very small classes and for a random A they should not sum to 0.

It is easy to show that if n ≤ q we would get more than n equations and we could recover s by Gaussian reduction. With less than n equations we iterate the process as follows:

If we have found one equation s(x^{(0)}) = a^{(0)} we can increase the number of classes in our partition of initial values space. We use the fact that if s(x) = a, we also have s(x + x^{(0)}) = a + a^{(0)}. Therefore we classify a not only by the inversion degree of its image A(a) as before, but we will also consider the class of a + a^{(0)}. The number of classes will systematically increase.

This attack will work for any sensible non-bijective (> 2 classes) quadratic equations set. Yet we cannot solve a toy example given at the beginning of the article, since it is bijective. In order to solve these cases we hit upon another approach.

10.2 The ”to and fro” attack

We will describe the attack on the toy example from the chapter 2, showing directly how it works. Let q = 2 and n = 5. We consider

A : \{ \begin{matrix}b_{0} = a_{0} + a_{0}a_{4} + a_{1}a_{2} + a_{1}a_{3} + a_{2}a_{3} \\ b_{1} = a_{2} + a_{3} + a_{4} + a_{0}a_{1} + a_{0}a_{3} + a_{3}a_{4} \\ b_{2} = a_{4} + a_{0}a_{1} + a_{0}a_{2} + a_{0}a_{4} + a_{1}a_{2} + a_{2}a_{4} + a_{3}a_{4} \\ b_{3} = a_{1} + a_{2} + a_{3} + a_{4} + a_{0}a_{4} + a_{2}a_{3} + a_{2}a_{4} \\ b_{4} = a_{3} + a_{0}a_{2} + a_{0}a_{4} + a_{1}a_{2} + a_{1}a_{3} + a_{1}a_{4} + a_{2}a_{3} + a_{2}a_{4} + a_{3}a_{4} \end{matrix}

and

B : \{ \begin{matrix}y_{0} = x_{0} + x_{2} + x_{3} + x_{4} + x_{0}x_{1} + x_{0}x_{2} + x_{0}x_{4} + x_{1}x_{3} + x_{2}x_{4} + x_{3}x_{4} \\ y_{1} = x_{0}x_{3} + x_{0}x_{4} + x_{1}x_{2} + x_{1}x_{3} + x_{1}x_{4} + x_{3}x_{4} \\ y_{2} = x_{0} + x_{2} + x_{3} + x_{0}x_{1} + x_{0}x_{4} + x_{1}x_{2} + x_{2}x_{3} \\ y_{3} = x_{2} + x_{3} + x_{0}x_{1} + x_{0}x_{4} + x_{2}x_{3} + x_{2}x_{4} + x_{3}x_{4} \\ y_{4} = x_{1} + x_{3} + x_{4} + x_{0}x_{2} + x_{0}x_{3} + x_{1}x_{2} + x_{1}x_{3} + x_{1}x_{4} \end{matrix}

as functions F_{2^{5}} → F_{2^{5}}. We have made a table of functions A and B, where for simplification purposes we denote F_{2^{5}} elements

by integers, so that to x = (x_{4}, x_{3}, x_{2}, x_{1}, x_{0}) corresponds x = ∑_{i=0}^{n} x_{i}2^{i}. Therefore if we read in the

table that A(5) = 31 it means that if a = (a_{4}, a_{3}, a_{2}, a_{1}, a_{0}) = (0, 0, 1, 0, 1) then x = s(a) equals to (1, 1, 1, 1, 1).

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2 8 29 30 31
A 0 1 8 15 10 31 23 4 26 25 3 6 9 30 5 20 14 18 22 12 24 16 21 27 2 28 11 19 13 7 17 29
B 0 5 16 24 13 25 11 18 29 10 30 4 28 26 9 2 17 27 19 20 21 14 1 23 7 31 22 3 15 6 8 12

In the real application we will not construct any table, and we will proceed with exhaustive search at every time we need to compute A^{−1} or B^{−1} which happens O(n) times in this attack.

The main idea is to say that if we have k equations on s:

{ s(x^{(1)}) = a^{(1)} ; ⋮ ; s(x^{(k)}) = a^{(k)}

that are linearly independent, we have q^{k} − 1 dependent equations

{ s(∑ ∼ x^{(i)}) = ∑ ∼ a^{(i)} ; ⋮

– where ∼ denotes some coefficients. But since A is generally non-linear we can get from that as much as (or almost) q^{k} − 1 independent equations ‘on the other side’:

{ A (s(∑ ∼ x^{(i)})) = A (∑ ∼ a^{(i)}) ; ⋮

Then we apply t (formally), which changes nothing as to linear independence of these equations:

{ t (A(s(∑ ∼ x^{(i)}))) = t (A(∑ ∼ a^{(i)})) ; ⋮

And finally, since B = t ∘ A ∘ s we have about q^{k} − 1 implicit equations on t:

{ B(∑ ∼ x^{(i)}) = t (A(∑ ∼ a^{(i)})) ; ⋮

We can do that the other direction, start from equations on t and get s in a very similar way, but it is less convenient since we need to compute A^{−1} or B^{−1} and sum up all possible solutions. In our example it was easy, since it is bijective.

The whole method is called ”to and fro” as it proceeds toing and froing from one side to another and ends when we get n independent equations on s and another n on t.

If q ≠ 2 we have q^{k} − 1 >> k and the attack complexity is about n^{O(1)}O(q^{n}) and n^{O(1)}O(q^{2n}) at most to find initial 1 or 2 equations. If q = 2 it is n^{O(1)}O(q^{2n}) in most cases (no exceptions are known) since we can start with 2 equations.

Let us see how it works on our example: We start with the two following equations:

\{ \begin{matrix}s(1) = 1 \\ s(2) = 7 \end{matrix}

Our equation set A comes from b = a^{3} in the F_{2^{n}}, n = 5 field, and it has n · 2^{n} automorphisms of the form:

\{ \begin{matrix}s : x ↦ αx^{1+2^{β}} \\ t : x ↦ α^{−1−2^{θ}}x^{2^{−β}} \end{matrix} with α ≠ 0, β ∈ \{0, 1, …, n − 1\}.

Therefore there are at least n2^{n} solutions s and t (in fact we have found there are no more). Thus the probability of our 2 equations being right is \frac{n2^{n}}{2^{2n}} = \frac{n}{2^{n}} and the whole attack complexity is only n^{O(1)}O(q^{n}). Moreover, for n = 5 one gets \frac{n}{2^{n}} ∼ 0.15 and we admit to have been lucky choosing two starting equations right. Then we get 3 dependent equations:

\{ \begin{matrix}s(1) = 1 \\ s(2) = 7 \\ s(3) = 6 \end{matrix}

as – in F_{32} – 1 + 2 = 3 and 1 + 7 = 6.

Then we use the table to ‘transfer’ equations on the other side:

\{ \begin{matrix}t(1) = 5 \\ t(4) = 16 \\ t(23) = 24 \end{matrix}

For example with s(2) = 7, we get A(7) = 4 and B(2) = 16 and all that implies that t(4) = 16.

Now we combine them again to get 2^{3} − 1 = 7 dependent equations:

\{ \begin{matrix}t(1) = 5 \\ t(4) = 16 \\ t(5) = 21 \\ t(18) = 13 \\ t(19) = 8 \\ t(22) = 29 \\ t(23) = 24 \end{matrix}

And using A^{−1} and B^{−1} we get 7 equations on s:

\{ \begin{matrix}s(1) = 1 \\ s(2) = 7 \\ s(3) = 6 \\ s(4) = 17 \\ s(8) = 18 \\ s(20) = 14 \\ s(30) = 27 \end{matrix}

6 from those 7 equation are actually independent, and yet it is enough to recover s by Gaussian reduction. Similarly we get t and verify the correctness of our solution.

(a_{0}, a_{1}, a_{2}, a_{3}, a_{4}) = [ \begin{matrix}1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{matrix} ] (x_{0}, x_{1}, x_{2}, x_{3}, x_{4})

(y_{0}, y_{1}, y_{2}, y_{3}, y_{4}) = [ \begin{matrix}1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{matrix} ] (b_{0}, b_{1}, b_{2}, b_{3}, b_{4})

If we look closely at the ”to and fro” attack we can see that it can be transformed into an ‘birthday paradox’ or ‘meet in the middle’ attack with all the related speed-memory tradeoffs. This is possible because in our attack we can operate as follows:

1. First, we start with given 2 or 1 values on entries of A we write on the one side, and the corresponding entries for B we write on the other side.

2. Then on each side we compute new values as before by successive linear transformations, applying A or A^{−1} and B or B^{−1}, again linear transformations etc. Thus we obtain new values which still match the respective values on the other side. We call this phenomenon ”boosting” as the initial information is amplified.

3. At the end we look for a linear s that maps these two (ordered) sets.

Now in order to transform the attack into the ‘birthday paradox’-based attack, we need only to modify part 3. Let us assume we have n + ε related entries a^{(i)} for A and on the other side n + ε related entries x^{(i)} for B. We do not need to compute s to know they are really related by s. There is a different way: we find separately how the n + ε related entries a^{(i)} are linearly dependent between themselves and we do the same for the n + ε entries x^{(i)} of B. Two sets which are related by s must have the same linear dependencies. Now we can easily detect a collision in two huge lists of sets looking for the same dependencies.

The probability of error can be made as small as we want since n+ε have at least ε linear dependencies, and the probability of them being all true for a linearly non-related set of data grows very small with ε: 1/q^{εn}.

Our next attack explores this ‘birthday’ approach with several improvements, as we want to insure the possibility of starting all cases of ”to and fro” with one equation and we do not want to do any exhaustive search for inversion of A or B.

10.3 Combined power attack.

In order to further improve our attacks we found out that it would be nice to have a function which we call ”boosting function” with the following properties: on an entry x we compute in polynomial time x′ = F (x) such that F is preserved by the isomorphism of polynomials:

If s(x) = a, F_{B}(x) = x′ and F_{A}(a) = a′, then s(x′) = a′.

However:

Theorem 10.1 There is no non-trivial boosting function which works for all the quadratic equations sets.

Proof: The ”to and fro” attacks will almost always, apart from improbable cases, allow to recover in a unique, deterministic way, the entire s and t starting from 2 equations on s. Yet, a non-trivial boosting function would allow, with some non-zero probability, to do the same starting with only one equation. Now, in the very precise equations set derived from b = a^{3} it is not possible. From the structure of b = a^{3} automorphisms shown in the last chapter we can easily see that there are at least n possible solutions s and t satisfying any given equation on s.

The situation is not that bad though, since in most q ≠ 2 cases the very simple function:

F (z) = B(rz), with r ∈ F_{p}

can give few equations on t with one equation on s.

Therefore we must look for less powerful functions and in some way relax its axioms. We have found few ways of doing so:

1. We may consider more general functions, dealing with different sets of information on entries and results of a function.

2. Moreover we may use different boosting functions depending on the particularities A.

3. We ask the condition of x′ = F (x) being preserved by the isomorphism to be true only with a certain noticeable probability.

4. We can have a function F probabilistic.

5. It is enough to suppose that x′ = F (x) is preserved no more by all, but by at least by one possible isomorphism that satisfies the initial data.

The last two additions are important, since they are those which do demolish our proof of non-existence of boosting function. We call a boosting function or ”weak boosting function” a function which satisfies 1.-5., and the previous definition is referred to as a ”strong boosting function”. In the following attack description we used 3 different boosting functions F, G and H to cover different cases of quadratic forms set A. All these function are based on the same principle of ‘differential solving’ described as follows:

Since we have quadratic equations in A, it is possible to perform a ‘differential solving’ of these equations, i.e. given a pair c and d one can find two entries a and a′ such that a−a′ = c and A(a)−A(a′) = d. Here is how we can proceed: we write the polar version of the A form set:

Q(a, c) = A(a + c) − A(a) − A(c)

which is bilinear in the x_{i} and the y_{i}. Then the equation we need to solve:

A(a + c) − A(a) = d

is the same as

Q(a, c) = A(c) + d

which – once c and d are fixed – contains only linear equations on the a_{i}, and allows us to compute by Gaussian reduction all its solutions.

The differential solving, as described above, leads to the following boosting function:

F unction(z) = ∑_{x such that B(x+z)=B(x)} x.

It works fine for p ≠ 2, but it fails for p = 2. The problem is that if a is a solution, a + c is a solution as well, and we cannot either easily tell them apart, either sum them up, since a + (a + c) gives a, which is not a new data. We will take one of these values, at random, in every pair (x, x + z). The sum will be known with possible (+z), and exactly with probability 1/2 which is not bad. We put:

F_{B}(z) = ∑_{x such that B(x+z)=B(x) one only ∈{x,x+z}} x.

The function is defined the same way for A:

F_{A}(c) = ∑_{a such that A(a+c)=A(a) one only ∈{a,a+c}} a.

It is clear that the boosting function F works only for non-bijective forms. For bijective forms we use another boosting function based on the same principle:

G_{B}(z) = ∑_{x such that B(x+z)=B(x)+B(z) one only ∈{x,x+z}} x.

Finally, because of the theorem we showed, neither of F and G can work in the particular case of C^{∗} cryptosystem quadratic forms. We use then:

H_{B}(z) = ∑_{x such that B(x+z)=B(x)+α_{B} one only ∈{x,x+z}} x.

with α_{B} chosen at random, but as a function of B, so it is always the same for the same B. We do the same for A. The H works because it restricts the number of solutions s we are going to find to those for which t(α_{A}) = α_{B} and there are still enough of them. In [5] we describe another boosting function K which could be useful in case the present should fail on some particular quadratic form set. We now describe the whole attack:

The combined power attack This attack is designed to solve all the IP cases, u = n and with linear s and t transformations, with the complexity n^{O(1)}q^{n/2} and using n^{O(1)}q^{n/2} of space. We do not know any particular function which would resist it.

1. Initialisation.

We pick at random (log n)^{O(1)}q^{n/2} entries z^{(i)} and (log n)^{O(1)}q^{n/2} entries c^{(i)} (the same can be used). Thus by the well known ‘birthday principle’ there are at least (log n)^{O(1)} collisions such that s(z^{(i)}) = c^{(j)}.

2. Starting (1 value ↦ log log n + O(1) values): We put z^{(i,0)} = z^{(i)} et c^{(i,0)} = c^{(i)}. Then we apply log log n + O(1) times an appropriate boosting function:

z^{(i,j+1)} = F_{B}(z^{(i,j)})

and

c^{(i,j+1)} = F_{A}(c^{(i,j)})

(eventually replace F by G or H.)

On this stage, if any of the F_{B}(z^{(i,j)}) or F_{A}(c^{(i,j)}) is zero, we throw away the initial value z^{(i)} or c^{(i)}. Thus we keep 1 out of about O(1)^{log log n+O(1)} = (log n)^{O(1)} initial entries which is still enough.

If p = 2 our boosting functions values are randomly chosen from 2 possibilities and there are few possible lists (z^{(i,j)}, j = 1..). Still, the number of possible lists is small: 2^{log log n+O(1)} = O(log n).

Having thrown away some values, we have still about O(log n) collisions s(z^{(i)}) = c^{(j)}. And even if p = 2, we can expect about O(1) to have made the same choices in probabilistic functions F, G, H. Finally, there are at least O(1) pairs (z^{(i)}, c^{(j)}) such that

∀k = 1..(log log n + O(1)), S(z^{(i,k)}) = c^{(j,k)}

3. Pre-Expansion (log log n + O(1) input values ↦ log n + O(1) output values): We apply simply B to all possible linear combinations of the z^{(i)}and we get about q^{log log n+O(1)} > log n + O(1) new values we note t^{(i,j)}, j = 1..(log n + O(1)).

We can suppose that at least log n + O(1) are independent, and we take care to have them always written in the same fixed order.

We do the same for A and we get the d^{(i,j)} list.

4. Expansion (log n + O(1) output values ↦ n + O(1) input values): For every candidate i we apply again the ‘differential solving’ principle for B. The input difference will always be the same z^{(i,0)}. For the output differences we will take all the possible linear combinations of the t^{(i,j)}, j = 1..(log n + O(1)).

Thus we get about q^{log n+O(1)} > n + O(1) values defined as follows:

∑_{the x such that B(x+z)−B(x)=∑_{j}∼t^{(i,j)} one only ∈{x,x+z}} x.

with ∼ being some coefficients ∈ F_{q}.

¿From these values we keep n + ε, ε ∈ O(1) which again need to be taken always in the same ordering. We call them z^{(i,j)}, j = 1..(n + ε).

We do the same for A and it gives c^{(i,j)}, j = 1..(n + ε).

5. Label distribution.

For each list z^{(i,j)}, j = 1..(n + ε) we are going to detect by Gaussian reduction all the possible linear dependencies. In order to easily manage the set of dependencies we will proceed in a way to get only independent linear equations, as follows: for j = 1, 2, … we seek all the linear dependencies between z^{(i,j)} and those of the z^{(i,k)}, k < j which are non-zero and have not been found linearly dependent before.

This list of linear dependencies, having between 2 and n + ε members is a label, a signature we give to the list z^{(i,j)}, j = 1.., and actually to the sole value z^{(i,0)}.

As we explained before (5.2), if two lists, one for A and another for B, are related by the linear application s, they will have the same label. If they are not, the error probability is as small as 1/q^{εn}. Furthermore ε = 2 is enough.

6. Collision detection. If p ≠ 2 we simply look for two same labels.

If p = 2, two lists z^{(i,k)}, k = 1.. and c^{(j,k)}, k = 1.. can be still presumed to correspond through s for some i, j to be found, but imperfectly known: with possible +z^{(i,0)} for the first list and +c^{(i,0)} for the second.

The probability of a n + ε + 1 elements list to have the same label as if some randomly chosen elements would have been added the same value z^{(i,0)} is quite big: about \frac{1}{2^{ε}} as we expect to have ε linear relations in a list and it is 1/2 for one relation. Therefore we expect that with the probability about \frac{1}{2^{2ε}} we can detect if two z^{(i,0)} and c^{(j,0)} are related by s. Again ε = 2 is enough and we have \frac{1}{2^{2ε}} = \frac{1}{16}. It means that for p = 2 one in 16 s functions we find in the present attack is correct.

Finally, in all cases we simply search for i and j such that z^{(i,k)}, k = 0..(n + ε) and c^{(j,k)}, k = 0..(n + ε) have the same label.

7. Computing of s. We can then compute s by Gaussian reduction on > n equations on s: s(z^{(i,k)}) = c^{(j,k)}, k = 0..(n + ε).

8. Ending step.

¿From s we easily get t and we verify the solution. Eventually, if p = 2, we need to try about 16 collisions.

We do not know any example of quadratic equations for which all the three variations of the attack would fail altogether. We did not program the whole attack so far, but we did testing on particular points that seemed to be uncertain.

11 Suggestions of IP variations

IP with one secret

As we have seen above, some improved algorithms exist for IP with two secrets. Therefore, when IP is used for authentication or signature as explained in [15], it might be suggested to use IP with one secret instead of IP with two secrets in order to have a more efficient scheme. It may look surprising that IP with one secret might be a more difficult problem (with practical values of the parameters) than IP with two secrets. However, this is not so surprising: in IP with two secrets, we have about 2n^{2} unknown coefficients of K (the secret values of the s and t matrices) and about \frac{n^{3}}{2} quadratic equations on these unknown values (when we formally identify the two sets of equations (A) and (B)), i.e. much more equations than unknowns. However, in IP with one secret, the parameters can be chosen in order that the number of equations (given by a formal identification) will be about approximately equal to the number of unknown! s. Thi s occurs for instance when (A) and (B) are two sets of two quadratic equations. (However, in section 9, we have seen that some instances of this problem are easy to solve.) As a result, despite the fact that there is only one affine change of variables, such a problem might be more difficult than the IP with two secrets. (IP with one secret on a single cubic equation might also be of interest.)

Subgroups of GL_{n}(K)

Another possible idea would be to choose the secret transformations s and t of IP with two secrets in a subgroup G of GL_{n}(K). (GL_{n}(K) is the set of all linear bijective transformations from K^{n} to K^{n}). This way, n may be chosen rather large (in order to make the problem difficult) and the length of the asymmetric signature (when the problem is used as explained in [15] for asymmetric signatures) might still be of reasonable size. For instance, G might be the orthogonal group of some quadratic form q (i.e. the set of all g ∈ GL_{n}(K) such that ∀x ∈ K^{n}, q(g(x)) = q(x)), or G might be the group of all matrices of the form ( \begin{matrix}A & −B \\ B & A \end{matrix} ), where A and B are two \frac{n}{2} × \frac{n}{2} matrices. It is not clear whether choosing s

and t in such a subgroup G makes it easier to solve the IP problem or not.

Remark: A similar idea is used in the DSS or in Schnorr’s algorithm, where – in order to have shorter length for the signatures – a subgroup is chosen for the exponents used in these schemes. However, here, the schemes are very different.

12 Conclusion

In this paper, we have shown that the MP and IP problems are not only related to the problem of finding the secret key of esoteric cryptographic algorithms, but also to very general problems such as Graph Isomorphism and Fast Matrix Multiplication. From their definitions, MP and IP look very similar but, as we have seen in this paper, Deciding MP is NP-complete whereas Deciding IP is not NP-complete (assuming the usual hypothesis about Arthur-Merlin games). If O(n^{2}) is the length of the secrets to be found, then our new algorithms for IP (”with two secrets”) have a complexity in O(q^{n}) or O(q^{n/2}) when s and t are linear (so at most O(q^{\frac{3}{2} n}) when s and t are affine). This is not polynomial, but this is clearly much better than the complexity O(q^{(n^{2})}) of the previous algorithms. For example, for the toy example given in [13], we have found the secret key with only about 7 computations (!), instead of 2^{25} for previously known algorithms (or 2^{50} for exhaustive search on the two secret matrices s and t). This means that the schemes based on IP problems with two secrets (such as some the schemes described in [15]) should have larger values of the parameters than expected for security. However, there are a lot of possible variations for IP and the choice of the variations and the choice of the parameters can still be done in order to ! have both efficient asymmetric schemes and no practical attacks.

Acknowledgements: We thank Henri Gilbert and Frédéric Cherbonnier for giving their algorithm of section 8. We also want to thank Jean-Pierre Seifert for pointing out references [11] and [16] to us, and Don Coppersmith for pointing out a possible link between morphisms of polynomials and fast matrix multiplication.

References

[1] László Babai, Shlomo Moran, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, JCSS, vol. 36, 1988, pp. 254-276.

[2] Manuel Blum, How to prove a theorem so no one else can claim it, Proceeedings of the International Congress of Mathematics, Berkeley CA, 1986, pp. 1444-1451.

[3] Ravi B. Boppana, Johan Håstad, Stathis Zachos, Does co-NP have short interactive proofs, Information Proc. Letters, vol. 25, 1987, pp. 127-132.

[4] Don Coppersmith, Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Computation (1990), 9, pp. 251-280.

[5] Nicolas Courtois, Les cryptosystèmes asymétriques à représentation obscure, Rapport de DEA, Paris 6 University, July 1997.

[6] Scott Fortin, The Graph Isomorphism Problem, Technical Report 93-20, University of Alberta, Edmonton, Alberta, Canada, July 1996. This paper is available at ftp://ftp.cs.ualberta.ca/pub/TechReports/1996/TR96-20/TR96-20.ps.gz

[7] Oded Goldreich, Silvio Micali, Avi Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Journal of the ACM, v. 38, n. 1, Jul. 1991, pp. 691-729.

[8] Shafi Goldwasser, Silvio Micali, Charles Rackoff, The knowledge complexity of interactive proofs, SIAM J. Comput., vol. 18, 1989, pp. 186-208.

[9] Shafi Goldwasser, Michael Sipser, Private coins vs. public coins in interactive proof systems, Advances in Computing Research, S. Micali (Ed.), vol. 5, 1989, pp. 73-90.

[10] John Gustafson, Srinivas Aluru, Massively Parallel Searching for Better Algorithms or, How to Do a Cross Product with Five Multiplications, Ames Laboratory, Department of Energy, ISU, Ames, Iowa. This paper is available at http://www.scl.ameslab.gov/Publications/FiveMultiplications/Five.html

[11] Johan Håstad, Tensor Rank is NP-Complete, Journal of Algorithms, vol. 11, pp. 644-654, 1990.

[12] Rudolf Lidl, Harald Niederreiter, ”Finite Fields”, Encyclopedia of Mathematics and its applications, Volume 20, Cambridge University Press.

[13] Tsutomu Matsumoto, Hideki Imai, Public quadratic polynomial-Tuples for efficient Signature-Verification and Message-Encryption, EUROCRYPT’88, Springer-Verlag, pp. 419-453.

[14] Jacques Patarin, Cryptanalysis of the Matsumoto and Imai public Key Scheme of Eurocrypt’88, CRYPTO’95, Springer-Verlag, pp. 248-261.

[15] Jacques Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of asymmetric Algorithms, EUROCRYPT’96, Springer-Verlag, pp. 33-48.

[16] Erev Petrank, Ron M. Roth, Is Code Equivalence Easy to Decide ?, IEEE Transactions on Information Theory, 1997.

[17] Volker Strassen, Gaussian elimination is not optimal, Numerische Mathematik 13, 1969, pp. 354-356.

[18] Volker Strassen, The asymptotic spectrum of tensors, J. Reine Angew. Math., vol. 384, pp. 102-152, 1988.