On the Structure of Randomly Permuted Concatenated Code —

Structure d’un Code Concaténé Permuté Aléatoirement

Nicolas Sendrier

Projet CODES, INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 Le Chesnay CEDEX, FRANCE

Abstract

Our purpose here is to show how it is possible to recover the structure of a randomly permuted concatenated code, and how to use this information for decoding. This result prohibits the use of first order concatenated codes in public-key cryptosystems based on error-correcting codes.

Résumé

Nous montrons ici comment il est possible de reconstituer la structure d’un code concaténé permuté aléatoirement et comment utiliser cette information pour le décodage. Ce résultat met en cause l’utilisation des code concaténés du premier ordre dans les systèmes de chiffrement à clé publique basés sur les codes correcteurs d’erreurs.

On the Structure of Randomly Permuted Concatenated Code

Nicolas Sendrier ^{∗}

1 Introduction

In order to build a cryptosystem based on error-correcting codes, we need a family of linear codes with given parameters, that has some “good” cryptographic properties. The family must be large enough to forbid an exhaustive attack, and each code of the family must have a decoding algorithm of low algorithmic complexity to allow an easy decryption. Additionally, the codes should be such that after a random permutation of the coordinates, the algebraic structure of doesn’t show.

In the two known systems, proposed by McEliece [McE78] and Niederreiter [Nie86], the public key is a permuted version of the code, either a permuted generating matrix (McEliece) or a permuted parity check matrix (Niederreiter).

There are two possible attacks of these systems. The first one consists in a try to decode a given encrypted message. We will refer to this as the direct attack, and it basically consist in decoding a random linear code. The second possible attack, the structural attack, consist in a try to recover the structure, or part of the structure, of the original code from the public key.

McEliece proposed in his original paper to use 50-error-correcting binary Goppa codes of length 1024. These codes are resistant to the direct attacks [LB88, vT90, Cha94, CC94], and no structural attack is known.

Sidelnikov and Shestakov gave a successful structural attack of a scheme using Generalized Reed-Solomon codes [SS92].

We investigate here the use of first order concatenated codes. These codes offer the advantage of a lower decoding complexity at the cost of a larger key size. We present a structural attack of a system based on such codes. The attack is practical with code parameters that are resistant to the direct attacks.

∗Projet CODES, INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 Le Chesnay CEDEX, FRANCE

2 McEliece and Niederreiter cryptosystems

We consider a family of C(n, k, ≥ d) linear codes over GF (q) that possess a low complexity d-bounded decoding procedure. Let t = (d − 1)/2, r = n − k. Both Φ_{C} and Ψ_{C} used below are procedures that can be easily derived from the decoding procedure of C.

2.1 Description

McEliece cryptosystem

• Secret key:

– an element C of the family,

– a k × k non-singular matrix S,

– a n × n permutation matrix P.

• Public key: G′ = SGP, where G is a generating matrix of C.

• Encryption: m ⟶ mG′ + e, e a random vector of weight t.

• Decryption: y ⟼ Φ_{C}(yP^{−1})S^{−1}, with Φ_{C}(xG + e) = x whenever the weight of e is t or less.

Niederreiter cryptosystem

• Secret key:

– an element C of the family,

– a r × r non-singular matrix S,

– a n × n permutation matrix P.

• Public key: H′ = SHP, where H is a parity check matrix of C.

• Encryption: m ⟶ H′m^{T}, the message m is of weight t.

• Decryption: y ⟼ Ψ_{C}(S^{−1}y)P, with Ψ_{C}(Hm^{T}) = m whenever the weight of m is t or less.

2.2 Goppa codes

Let n, m and t be positive integers, let L = {α_{1}, …, α_{n}} be an ordered subset of GF (q)^{m} and let g(z) be a monic polynomial in GF (q^{m})[z] of degree t such that g(α_{i}) ≠ 0 for all α_{i} in L.

The Goppa code Γ(L, g) is the set of vectors a = (a_{1}, …, a_{n}) in GF (q)^{n} such that

R_{a}(z) = ∑_{i=1}^{n} \frac{a_{i}}{z − α_{i}} ≡ 0 mod g(z)

The code Γ(L, g) has a minimum distance greater or equal to the designed distance δ = t+1 and a dimension at least equal to n − rm. There exists a δ-bounded (i.e. (δ − 1)/2-error-correcting) decoding procedure of Γ(L, g) with algorithmic complexity O(nδ).

Proposition 1 [MS77, p. 342] If g(z) is square-free, then Γ(L, g) = Γ(L, g^{2}). Thus the minimum distance of Γ(L, g(z)) is at least equal to 2t + 1.

This proposition provides a t-error-correcting algorithm of Γ(L, g) when g(z) has no squared factor.

2.3 Parameters

McEliece uses a family of binary Goppa codes of length n = 1024, with L = GF (1024) and g(z) monic square-free in GF (1024)[z] of degree t = 50. The codes obtained will have a dimension k ≥ 524 and a designed distance δ = 2t + 1 = 101. The actual minimum distance and dimension of these codes may be larger.

The characteristics of the two systems with this family are the following:

McEliece:

• Key size: 67 072 bytes.

• Transmission rate: 0.512.

• Number of codes: ≈ 2^{498}.

Niederreiter:

• Key size: 32 750 bytes.

• Transmission rate: 0.568.

• Number of codes: ≈ 2^{498}.

Remarks on the parameters:

• The substantial difference in the key sizes is due to the fact that Niederreiter system allows a public key in systematic form at no cost for security, as stated below.

Proposition 2 Let H′ be the public-key of a cryptosystem using Niederreiter scheme. Let H̄′ = UH′ be a systematic form the parity check matrix H′. Any attack able to break a scheme using H̄′ is able to break a scheme using H′.

Proof: Let W_{t} denote the set of words of weight t in GF (q)^{n}. We consider the two encryption procedures

\begin{aligned}N & : & W_{t} & ⟶ & GF (q)^{n−k} \\ & & m & ⟼ & H′m^{T} \end{aligned} and \begin{aligned}N̄ & : & W_{t} & ⟶ & GF (q)^{n−k} \\ & & m & ⟼ & H̄′m^{T} \end{aligned}

These two mappings are injective. Let’s assume that we have an oracle Φ able to compute m = Φ(y) = N̄^{−1}(y) for all column vector y in N̄(W_{t}).

Let y be an element of N(W_{t}), we have y = N(m) = H′m^{T} for some m in W_{t}. The column vector Uy = UN(m) = UH′m^{T} = N̄(m) is in N̄(W_{t}), and Φ(Uy) = m. The oracle Φ can be used for breaking N. □

• The transmission rate for McEliece system is equal to k/n, that is the number of information symbols divided by the number of transmitted symbols.

For Niederreiter system the number of possible messages is the number of q-ary words of weight t and length n, and the number of transmitted symbols is n − k. Thus the transmission rate is

\frac{log_{q} (\binom{n}{t}(q − 1)^{t})}{n − k}

• The number of codes is the number of monic square-free polynomials of degree 50 in GF (1024)[z] that are relatively prime to z^{1024} − z.

Proposition 3 [LN83, pp. 92–93] The number of monic irreducible polynomial of degree t over GF (q) is equal to

N_{q}(t) = \frac{1}{t} ∑_{s|t} μ (\frac{t}{s}) q^{s}

where μ is the Moebius function.

The generating serie of the monic square-free polynomial over GF (q^{m}) is given by

∏_{s>0} (1 + z^{s})^{N_{q^{m}}(s)}

(the number of such polynomials of degree t is equal to [z^{t}]S(z), the coefficient of z^{t} in S(z)). And to obtain the number of such polynomials that are relatively prime to z^{q^{m}} − z = ∏_{β∈GF (q^{m})}(z − β) we just have to take out the factors of degree 1. Thus the generating serie is

S(z) = ∏_{s>1} (1 + z^{s})^{N_{q^{m}}(s)}

Of course the formula for S(z) cannot be computed, but we have [z^{t}]S(z) = [z^{t}]S̄(z) with

S̄(z) = ∏_{s=1}^{t} ( ∑_{i=0}^{⌊t/s⌋} \binom{N_{q}(s)}{i}z^{is})

where ⌊·⌋ denotes the integer part, and [z^{t}]S̄(z) can be computed.

The number of monic square-free polynomials of degree 50 in GF (1024)[z] that are relatively prime to z^{1024} − z is 2^{498.56}. Note that this number is very close do 2^{500} the number of monic polynomials of degree 50 in GF (1024)[z].

2.4 Cryptanalysis

The cryptanalysis of the two systems are equivalent [LDW94]. There are mainly two guidelines to cryptanalyze these systems:

1. Decode a random linear code.

2. Recover the original structure of the code from the public key.

The first attack has been investigated at length in the last few years. Its efficiency is usually expressed as the average number of bits operation, called work factor, necessary to decode one instance of the cryptosystem.

In the original paper, McEliece gives a direct attack with a work factor of 2^{81}. A first improvement [LB88] leads to a work factor of 2^{71}, and the best known attacks today [Cha94, CC94] have a work factor of 2^{66}.

The knowledge of the structure of Goppa codes didn’t allow, up to now, an efficient structural attack of Goppa codes. However, some other families are not safe, Sidelnikov and Shestakov [SS92] proved that the structure of a generalized Reed-Solomon code cannot be hidden by a permutation of the support.

3 Using first order concatenated codes in Niederreiter cryptosystem

Here an after we consider here the use a first order concatenated code in Niederreiter cryptosystem.

3.1 First order concatenated codes

3.1.1 Definition

Let’s consider:

• a linear code B(n_{B}, k_{B}, d_{B}) over GF (q), called inner code,

• a linear code E(n_{E}, k_{E}, d_{E}) over GF (q^{k_{B}}), called outer code,

• an isomorphism θ : GF (q^{k_{B}}) → B of vector space over GF (q). We will denote by Θ the mapping:

\begin{aligned}Θ & : & (GF (q^{k_{B}}))^{n_{E}} & ⟶ & B^{n_{E}} \\ & & (a_{1}, …, a_{n_{E}}) & ⟼ & (θ(a_{1}), …, θ(a_{n_{E}})) \end{aligned}

By definition the first order concatenated code of inner code B and outer code E is:

C = B□_{θ}E = Θ(E)

3.1.2 Generating matrix

Let α be a primitive element of GF (q^{k_{B}}), the set (1, α, …, α^{k_{B}−1}) is a basis of GF (q^{k_{B}}) over GF (q), and the k_{B} × n_{B} matrix

G_{θ,α} = ( θ(1) ; θ(α) ; ⋮ ; θ(α^{k_{B}−1}) )  (1)

is a generating matrix of B.

For any β in GF (q^{k_{B}}) we denote by A_{β} the matrix of the GF (q)-vector-space homomorphism of GF (q^{k_{B}}) that maps any element x into βx. The matrix A_{0} is zero, and for any integer i in Z, we have A_{α^{i}} = A_{α}^{i}.

Let G_{E} = (β_{i,j})_{0≤i<k_{E},0≤j<n_{E}} be any generating matrix of E. Then the bloc matrix

(A_{β_{i,j}}G_{θ,α})_{0≤i<k_{E},0≤j<n_{E}}

is a generating matrix of C = B□_{θ}E.

3.1.3 Parameters

In order to use error-correcting codes for public-key cryptosystems, we need a family of linear codes over GF (q) of length n, dimension k, minimum distance d ≥ 2t + 1, and a low complexity decoding algorithm able to correct any t errors in a bloc.

We consider first order concatenated codes constructed from:

• a random binary inner code B(16, 7, 5),

• a generalized Reed-Solomon (GRS) outer code E(128, 44, 85) over GF (2^{7}).

This leads to concatenated codes of parameters

B□E = C(2048, 308, ≥ 425).

For these codes we have an efficient algorithm that can correct up to 212 errors in a bloc. The cost of the decoding is at most one third of the cost of the decoding of a 50-error-correcting binary Goppa code of length 1024.

Niederreiter cryptosystem using the concatenated codes described above have the following parameters:

• Key size: 66 990 bytes.

• Transmission rate: 0.562.

• Number of codes: ≈ 2^{944}.

The number of binary codes of length n and dimension k is equal to [MS77, p. 698]:

\frac{(2^{n} − 1)(2^{n} − 2) … (2^{n} − 2^{k−1})}{(2^{k} − 1)(2^{k} − 2) … (2^{k} − 2^{k−1})}

Among these, we estimate that about 0.33% are of minimum distance greater or equal to 5 – We have generated 5 10^{8} random codes of length 16 and minimum distance 7, among these, 1677051 had minimum distance 5 and 58 had minimum distance 6.

The number of distinct GRS codes of length 128 and given (non trivial) dimension over GF (128) is 127^{127}.

Resistance to known attacks The Lee-Brickell work factor for the correction of 212 errors in a binary code of length 2048 and dimension 308 is 2^{71}, the same as for the Goppa codes of McEliece.

3.2 Some definitions

Definition 1 The support of a word x in GF (q)^{N}, denoted supp(x), is the set of its non zero position. By extension the support of a set is the union of the support of its elements.

Definition 2 Two linear codes C and C′ of length n over GF (q) are equivalent if there exist a permutation matrix P such that for any generating matrix G of C, the matrix G′ = GP is a generating matrix of C′.

Definition 3 Let GF (q^{m}) be an extension of GF (q), the Frobenius field automorphism of GF (q^{m}) relatively to GF (q) is the mapping

\begin{aligned}F_{q} & : & GF (q^{m}) & ⟶ & GF (q^{m}) \\ & & x & ⟼ & x^{q} \end{aligned}

Note that any power of F_{q} is also a field automorphism of GF (q^{m}).

Definition 4 Two linear codes C and C′ of length n over GF (q^{m}) are F_{q}-equivalent if there exist a permutation matrix P and a power F_{q}^{s} of the Frobenius such that for any generating matrix G of C, the matrix G′ = \overline{GP} is a generating matrix of C′, where \overline{GP} is obtained by applying F_{q}^{s} to the coefficients of GP.

4 Structural attack

Let’s consider the first order concatenated code C_{o} = B_{o}(n_{B}, k_{B}, d_{B})□_{θ_{o}}E_{o}(n_{E}, k_{E}, d_{E}) over GF (q). We assume that we know the code C′_{o} obtained from C_{o} by a random permutation of the support, and we wish to recover a concatenated structure of this code, that is a concatenated code C = B□E equivalent to C′_{o}. Note that B and E need not to be equal to the original inner and outer codes.

4.1 B-blocs of a concatenated code

Definition 5 (B-blocs) For all i, 1 ≤ i ≤ n_{E}, let e_{i} be the element of GF (q^{k_{B}}) with a “1” in i-th position and zeros everywhere else. We denote by Vect(e_{i}) the vector-space generated by e_{i}. The i-th B-bloc of the concatenated code B□_{θ}E is defined to be the support of Θ(Vect(e_{i})).

4.1.1 Connected codes

Definition 6 Two words x and y in GF (q)^{n} are said to be connected if

supp(x) ∩ supp(y) ≠ ∅.

Two positions i and j are said to be connected by a subset S if there exist a sequence of words x_{0}, x_{1}, …, x_{l} in S such that

• i ∈ supp(x_{0}) and j ∈ supp(x_{l})

• for all i, 0 ≤ i < l, x_{i} and x_{i+1} are connected.

A subset S of GF (q)^{n} is said to be a connecting set of a set I of positions (in short S connects I), if any two elements of I are connected by S. In particular, we have I ⊂ ∪_{x∈S} supp(x).

4.1.2 Dual of a concatenated code

Proposition 4 [ZL84] If B^{⊥} ≠ {0}, the dual distance of C is at most d_{B}^{⊥}.

Proposition 5 Any word of C^{⊥} of Hamming weight less than min(d_{E}^{⊥}, 2d_{B}^{⊥}) has its support included in a single B-bloc.

If the set E_{B^{⊥}} = {x ∈ B^{⊥}, d_{B}^{⊥} ≤ w_{H}(x) < 2d_{B}^{⊥}} connects supp B^{⊥}, then the set E_{C^{⊥}} = {x ∈ C^{⊥}, d_{B}^{⊥} ≤ w_{H}(x) < 2d_{B}^{⊥}} connects any B-bloc of C, and from Proposition 5 it cannot connect a set containing positions in more than one B-blocs.

procedure get bloc(C)

j ← 0 1: x ← get new small weight codeword(C^{⊥})

for i from 1 to j do

if L_{i} ∩ supp(x) ≠ ∅ then

L_{i} ← L_{i} ∪ supp(x), if |L_{i}| = n_{B} then return(L_{i}) else goto 1

j ← j + 1, L_{j} ← supp(x), goto 1

Table 1: Procedure to compute one B-bloc of C

Thus by computing all the codewords of weight d^{⊥} to 2d^{⊥} − 1 in C^{⊥}, we can recover the B-blocs. In practice, it is not necessary to compute all these word, because there are many small subsets of E_{C^{⊥}} that will connect a given B-bloc. For instance the procedure described in Table 1 can be used.

If d_{B}^{⊥} is small, computing d_{B}^{⊥} is easy, and getting words of weight smaller than 2d_{B}^{⊥} in C^{⊥} can be efficiently done by any of the know algorithms [Leo88, Ste89, Cha94, CC94]. This procedure proved to be efficient for the proposed parameters; we obtained the 128 B-blocs in about one minute with a program in C running on a workstation DEC 3000.

4.2 Permutation between two equivalent codes

The problem we wish to solve now that we have the B-blocs is to have all of them in the same order. In other word, we wish to solve the following problem:

“Given two equivalent codes, how can we obtain the permutation between their supports?”

4.2.1 Signature of a position

Let C and C′ be two equivalent linear codes. Let J and J′ denote respectively the supports of C and C′. We will assume that the automorphism group of C (and thus of C′) is reduced to the identity element. Within this assumption, there is a unique bijection σ : J′ → J that establish the one to one correspondence between the positions of C and C′. Our purpose is to compute σ.

For any subset I of J, we will denote by C(I) the code obtained by deleting in C the positions of I.

Definition 7 The signature of an element i of J, denoted S_{i}, is defined to be the weight distribution of the code C({i}).

We define an equivalence R over the set J:

i R j ⇔ S_{i} = S_{j}

This equivalence induces a partition of J:

J = I_{1} ∪ … ∪ I_{l}

We assume that the equivalence classes of this relation are ordered according to any total ordering of the weight distribution.

If we apply the same process to C′, we will obtain a partition I′_{1} ∪ … ∪ I′_{l} such that for any s, 1 ≤ s ≤ l, I_{s} and I′_{s} have same size and signature. Furthermore we have σ(I′_{s}) = I_{s}. Thus if all the equivalence classes have cardinality 1, we are able to produce σ.

If not, we can repeat the process for all s with the codes C(I_{s}) and C′(I′_{s}) which are equivalent too. By merging all the partitions, we can hope to obtain σ.

For the codes we have considered, this was sufficient, and all the B-blocs can be reordered in about 20 seconds with a program in C running on a workstation DEC 3000.

Remark 1 • This algorithm is susceptible to works only with codes that have an automorphism group reduced to the element identity. It will not work neither if the number of equivalence classes of R is small, say two or three, which happens for codes of small length (less than 10).

• Another drawback of this method is that it requires the computation of weight distributions. This practically limits the dimension (or codimension) of C to 30.

4.3 Finding the outer code

4.3.1 A constructive lemma

Let α be a primitive element of GF (q^{k_{B}}). For any β in GF (q^{k_{B}}) we will denote A_{β} the matrix of the homomorphism x ↦ βx in the basis (1, α, …, α^{k_{B}−1}).

Lemma 1 Let C = B(n_{B}, k_{B}, d_{B})□_{θ}E(n_{E}, k_{E}, d_{E}) be a concatenated code. Let r_{E} = n_{E} − k_{E}. Let’s consider a generating matrix of C

G_{C} = ( \begin{matrix}G_{B} & … & 0 & G_{1,1} & … & G_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & G_{B} & G_{k_{E},1} & … & G_{k_{E},r_{E}} \end{matrix} )

where G_{B} and each non-zero bloc G_{i,j} is a generating matrix of B. For each pair (i, j), we put G_{i,j} = H_{i,j}G_{B}.

1. There exists a non-singular matrix U such that for all pair (i, j), we have

H_{i,j} = UA_{β_{i,j}}U^{−1}, β_{i,j} ∈ GF (q^{k_{B}})

and

G_{E} = ( \begin{matrix}1 & … & 0 & β_{1,1} & … & β_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & 1 & β_{k_{E},k_{E}} & … & β_{k_{E},r_{E}} \end{matrix} )

is a generating matrix of E.

2. For any U′ such that

H_{i_{0},j_{0}} = U′A_{β′_{i_{0},j_{0}}}U^{′−1}

for some pair (i_{0}, j_{0}) and β_{i_{0},j_{0}} is not in a subfield of GF (q^{k_{B}}), we have

(a) β′_{i_{0},j_{0}} = β_{i_{0},j_{0}}^{q^{s}} for some s, 0 < s < k_{B} − 1,

(b) H_{i,j} = U′A_{β′_{i,j}}U^{′−1}, with β′_{i,j} = β_{i,j}^{q^{s}} for all pairs (i, j).

The matrix

G_{E′} = ( \begin{matrix}1 & … & 0 & β′_{1,1} & … & β′_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & 1 & β′_{k_{E},k_{E}} & … & β′_{k_{E},r_{E}} \end{matrix} )

obtained in the second part of the lemma is the generating matrix of a code E′(n_{E}, k_{E}, d_{E}) which is F_{q}-equivalent to E.

The element β′_{i_{0},j_{0}} is an arbitrary root in GF (q^{k_{B}}) of the minimal polynomial p(X) of H_{i_{0},j_{0}}. Thus β′_{i_{0},j_{0}} = β_{i_{0},j_{0}}^{q^{s}} is a conjugate of β_{i_{0},j_{0}}. We then compute a U′ such that H_{i_{0},j_{0}} = U′A_{i_{0},j_{0}}U′ −1 (U′ is not unique), the lemma assures that for all pair (i, j), we have H_{i,j} = U′A_{β′_{i,j}}U^{′−1} and β′_{i,j} = β_{i,j}^{q^{s}}. This enables us to construct G_{E′}.

4.3.2 Construction of the outer code

slightlyAt that point, we assume that all the B-blocs have been recovered, and we order the position by putting one B-bloc after another. This leads after a Gaussian elimination to a generating matrix of the form:

G_{C} = ( \begin{matrix}G_{B} & 0 & … & 0 & G_{1,1} & … & G_{1,r_{E}} \\ 0 & G_{B} & ... & ⋮ & G_{2,1} & … & G_{2,r_{E}} \\ ⋮ & ... & ... & 0 & ⋮ & ... & ⋮ \\ 0 & … & 0 & G_{B} & G_{k_{E},k_{E}} & … & G_{k_{E},r_{E}} \end{matrix} )

where G_{B} and each non zero G_{i,j} is a generating matrix of the same code B equivalent to the original outer code. Note that if the outer code is MDS, then all the G_{i,j} are non zero. We assume here that the k_{E} first B-blocs are such that they allow the bloc diagonal form of G_{C}.

Proposition 6 Each bloc G_{i,j} in G_{C} will be equal to

G_{i,j} = UA_{β_{i,j}}U^{−1}G_{B}

where U is a k_{B} × k_{B} non singular matrix over GF (q) and

G_{E} = ( \begin{matrix}1 & 0 & … & 0 & β_{1,1} & … & β_{1,r_{E}} \\ 0 & 1 & ... & ⋮ & β_{2,1} & … & β_{2,r_{E}} \\ ⋮ & ... & ... & 0 & ⋮ & ... & ⋮ \\ 0 & … & 0 & 1 & β_{k_{E},k_{E}} & … & β_{k_{E},r_{E}} \end{matrix} )

is the generating matrix of a code E(n_{E}, k_{E}, d_{E}) over GF (q^{k_{B}}) F_{q}-equivalent to the original outer code and such that C = B□E.

Proof: The code B is equivalent to the original inner code B_{o}. Let Π_{B} denote the matrix of the permutation between the supports B and B_{o}.

Let Π_{E} denote the permutation between the B-blocs in C and their original position in C_{o}. We denote E′ the outer code obtained by permuting the coordinates of E_{o} according to Π_{E}.

We have C = B□_{θ′}E′, where θ′(α^{i}) = θ_{o}(α^{i})Π_{B}, for all i, 0 ≤ i ≤ k_{B} − 2. By use of lemma 1 we can construct an E(n_{E}, k_{E}, d_{E}) code over GF (q^{k_{B}}) such that C = B□E, and E is F_{q}-equivalent to E′ and thus by transitivity to E_{o}. □

4.4 Decoding the newly constructed code

Decoding the permuted version C′_{o} of C_{o} = B_{o}□E_{o} is thus equivalent to decoding a concatenated code B□E where B is equivalent to B_{o} and E is F_{q}-equivalent to E_{o}.

In any case, this proves that the original problem, can be divided in two problems, one for the inner code and one for the outer. Thus the concatenated structure is not hidden, though the structure of each of the component code is.

Furthermore we considered a random binary inner code a GRS outer code. Thus decoding B instead of B_{o} makes not difference at all. Since E is F_{q}-equivalent to E_{o}, E is also a GRS code, and from [SS92] we know that this is enough to decode E as easily as E_{o}.

References

[CC94] A. Canteaut and H. Chabanne. A further improvement of the work factor in an attempt at breaking McEliece cryptosystem. In P. Charpin, editor, Livre des résumé – EUROCODE 94, pages 163–167, Abbaye de la Bussière sur Ouche, France, October 1994. INRIA.

[Cha94] F. Chabaud. On the security of some cryptosystems based on error-correcting codes. In A. de Santis, editor, pre-proceedings of EUROCRYPT’94, pages 127– 135, May 1994.

[LB88] P.J. Lee and E.F. Brickell. An observation on the security of McEliece’s publickey cryptosystem. In C.G. Günther, editor, Advances in Cryptology – EURO-CRYPT’88, number 330 in LNCS, pages 275–280. Springer-Verlag, 1988.

[LDW94] Y.X. Li, R.H. Deng, and X.M. Wang. On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Transactions on Information Theory, 40(1):271–273, January 1994.

[Leo88] J.S. Leon. A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory, 34(5):1354– 1359, September 1988.

[LN83] R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 1983.

[McE78] R.J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol., Pasadena, CA, pages 114–116, Jan.-Feb. 1978.

[MS77] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.

[Nie86] H. Niederreiter. Knapsack-type crytosystems and algebraic coding theory. Prob. Contr. Inform. Theory, 15(2):157–166, 1986.

[SS92] V.M. Sidelnikov and S.O. Shestakov. On insecurity of cryptosystem based on generalized Reed-Solomon codes. manuscript, 1992.

[Ste89] J. Stern. A method for finding codewords of small weight. In G. Cohen and J. Wolfmann, editors, Coding theory and applications, number 388 in LNCS, pages 106–113. Springer-Verlag, 1989.

[vT90] J. van Tilburg. On the mceliece cryptosystem. In S. Goldwasser, editor, Advances in Cryptology - CRYPTO’88, number 403 in LNCS, pages 119–131. Springer-Verlag, 1990.

[ZL84] V. Zinoviev and S. Litsyn. Shortening of codes. Problemy Peredachi Informatsii, 20(1):3–11, January 1984.

A Proof of Lemma 1

Let α be a primitive element of GF (q^{k_{B}}). For any β in GF (q^{k_{B}}) we will denote A_{β} the matrix of the homomorphism x ↦ βx in the basis (1, α, …, α^{k_{B}−1}).

For any square matrix A, the centralizer of A, denote by Z(A), is the set of the matrices that commutes with A. That is the set of all matrices C such that CA = AC.

Lemma 2 Let β be an element of GF (q^{k_{B}}) which is not in a subfield. Let U and U′ be two k_{B} × k_{B} non-singular matrices. The two following assertions are equivalent

1. UA_{β}U^{−1} = U′A_{β}U^{′−1}

2. for all γ in GF (q^{k_{B}}), UA_{γ}U^{−1} = U′A_{γ}U^{′−1}

Proof: If the second assertion is true, then, in particular, the first one is true.

Reciprocally, since β is not in a subfield of GF (q^{k_{B}}), the set (1, β, …, β^{k_{B}−1}) is a basis of GF (q^{k_{B}}), then any γ in GF (q^{k_{B}}) can be written

γ = ∑_{i=0}^{k_{B}−1} γ_{i}β^{i}, γ_{i} ∈ GF (q)

and we also have

A_{γ} = ∑_{i=0}^{k_{B}−1} γ_{i}A_{β}^{i}, γ_{i} ∈ GF (q)

This proves that Z(A_{β}) ⊂ Z(A_{γ}) for all γ in GF (q^{k_{B}}).

Furthermore we have UA_{γ}U^{−1} = U′A_{γ}U^{′−1} if and only if U^{−1}U′ is in Z(A_{γ}). From the first assertion, we know that U^{−1}U′ ∈ Z(A_{β}), and thus U^{−1}U′ ∈ Z(A_{γ}) for all γ, and the second assertion is true. □

Lemma 1 Let C = B(n_{B}, k_{B}, d_{B})□_{θ}E(n_{E}, k_{E}, d_{E}) be a concatenated code. Let r_{E} = n_{E} − k_{E}. Let’s consider a generating matrix of C

G_{C} = ( \begin{matrix}G_{B} & … & 0 & G_{1,1} & … & G_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & G_{B} & G_{k_{E},1} & … & G_{k_{E},r_{E}} \end{matrix} )

where G_{B} and each non-zero bloc G_{i,j} is a generating matrix of B. For each pair (i, j), we put G_{i,j} = H_{i,j}G_{B}.

H_{i,j} = UA_{β_{i,j}}U^{−1}, β_{i,j} ∈ GF (q^{k_{B}})  (2)

and

G_{E} = ( \begin{matrix}1 & … & 0 & β_{1,1} & … & β_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & 1 & β_{k_{E},k_{E}} & … & β_{k_{E},r_{E}} \end{matrix} )

is a generating matrix of E.

2. For any U′ such that

H_{i_{0},j_{0}} = U′A_{β′_{i_{0},j_{0}}}U^{′−1}

for some pair (i_{0}, j_{0}) and β_{i_{0},j_{0}} is not in a subfield of GF (q^{k_{B}}), we have

(a) β′_{i_{0},j_{0}} = β_{i_{0},j_{0}}^{q^{s}} for some s, 0 < s < k_{B} − 1,

(b) H_{i,j} = U′A_{β′_{i,j}}U^{′−1}, with β′_{i,j} = β_{i,j}^{q^{s}} for all pairs (i, j).

Proof: Let

G_{E} = ( \begin{matrix}1 & … & 0 & β_{1,1} & … & β_{1,r_{E}} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & 1 & β_{k_{E},k_{E}} & … & β_{k_{E},r_{E}} \end{matrix} )

be a generating matrix of E. Let α be a primitive element of GF (q^{k_{B}}), and let G_{θ,α} be the generating matrix of B defined by equation (1). Since G_{B} is also a generating matrix of B, there exist a non-singular matrix U such that G_{B} = UG_{θ,α}.

We also know that the matrix

G = ( \begin{matrix}G_{θ,α} & … & 0 & A_{β_{1,1}}G_{θ,α} & … & A_{β_{1,r_{E}}} G_{θ,α} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & G_{θ,α} & A_{β_{k_{E} ,1}}G_{θ,α} & … & A_{β_{k_{E} ,r_{E}}} G_{θ,α} \end{matrix} )

is a generating matrix of G. If we multiply each bloc-line of G by U, the resulting matrix is

( \begin{matrix}G_{B} & … & 0 & UA_{β_{1,1}}U^{−1}G_{B} & … & UA_{β_{1,r_{E}}} U^{−1}G_{B} \\ & ... & & ⋮ & ... & ⋮ \\ 0 & … & G_{θ,α} & UA_{β_{k_{E} ,1}}U^{−1}G_{B} & … & UA_{β_{k_{E} ,r_{E}}} U^{−1}G_{B} \end{matrix} )

and is still a generating matrix of C. Furthermore this matrix coincide with G_{C} on a set of information position, it is thus equal to G_{C}. We then have for all pair (i, j)

UA_{β_{i,j}}U^{−1}G_{B} = G_{i,j} = H_{i,j}G_{B}

Since G_{B} is a matrix of rank k_{B}, we have

H_{i,j} = UA_{β_{i,j}}U^{−1}

for all pair (i, j). This proves the first part of the lemma.

Let U′ and β′_{i_{0},j_{0}} be such that

H_{i_{0},j_{0}} = U′A_{β′_{i_{0},j_{0}}}U^{′−1} = UA_{β_{i_{0},j_{0}}}U^{−1}

The element β′_{i_{0},j_{0}} has the same minimal polynomial as H_{i_{0},j_{0}}, and thus the same as β_{i_{0},j_{0}}. This imply that β′_{i_{0},j_{0}} = β_{i_{0},j_{0}}^{q^{s}} is a conjugate of β_{i_{0},j_{0}}.

For any pair (i, j), we have H_{i,j} = UA_{β_{i,j}}U^{−1}. If F_{q}^{s} is the s-th power of the Frobenius and is identified with its matrix as a vector-space-homomorphism over GF (q), we have

H_{i,j} = UA_{β_{i,j}}U^{−1} = UF_{q}^{−s}A_{β_{i,j}^{q^{s}}}F_{q}^{s}U^{−1}

In particular, if β_{i_{0},j_{0}} is not in a subfield of GF (q^{k_{B}}), we have

H_{i_{0},j_{0}} = UF_{q}^{−s}A_{β_{i_{0},j_{0}}^{q^{s}}}F_{q}^{s}U^{−1} = U′A_{β_{i_{0},j_{0}}^{q^{s}}}U^{−1},

and from Lemma 2, we have U^{′−1}H_{i,j}U′ = A_{β_{i,j}^{q^{s}}} for all pair (i, j). □

There is a small difficulty if no matrix H_{i,j} is such that its minimal polynomial has degree k_{B}. If this happens, we will consider the field GF (q^{m}) generated by all the β_{i,j} (this is possible from the knowledge of the H_{i,j}).

• If m = k_{B}, then a linear combination of some H_{i,j} will provide a matrix H = UA_{β}U that will have a minimal polynomial of degree k_{B}.

• If not, if we replace GF (q^{k_{B}}) by GF (q^{m}) in Lemma 2, it is still true, and it provides a similarly useful result.