. .

..

⎣. ¦

. .

.

. . .

. . . Q’1’2

0 0 n0

By calculating the inverse of G¤k and considering its circulant block at po-

sition (i, j), the eavesdropper can easily obtain Qi Si,j , being Si,j the circulant

block at position (i, j) in matrix S. Because of the isomorphism, this matrix

corresponds to the polynomial:

gi,j (x) = qi (x) · si,j (x) mod (xp + 1) (8)

where polynomials qi (x) and si,j (x), in turn, correspond to the blocks Qi and

Si,j , respectively.

Due to the fact that both Qi and Si,j are sparse (they have row/column weight

m), the vector of coe¬cients of gi,j (x) is obtained as the cyclic convolution of two

sparse vectors containing the coe¬cients of qi (x) and si,j (x). For this reason, it is

highly probable that gi,j (x) has exactly m2 non-null coe¬cients, and its support

contains at least one shift xla · qi (x), 0 ¤ la ¤ p ’ 1 [11]. This is the initial point

for three di¬erent attack strategies that, starting from the knowledge of gi,j (x),

aim at revealing part of the secret key. They are brie¬‚y described next.

OTD1 Attack Strategy. The ¬rst attack strategy consists in enumerating all

the m-tuples that belong to the support of gi,j (x). Each m-tuple is then validated

through inversion of its corresponding polynomial and multiplication by gi,j (x).

If the resulting polynomial has exactly m non-null coe¬cients, the considered

m-tuple corresponds to a shifted version of qi (x) with very high probability. For

the speci¬ed numerical values, this attack requires a work factor of 250.3 binary

operations.

A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes 251

OTD2 Attack Strategy. The second attack strategy is based on the periodic

autocorrelation of the coe¬cients vector of gi,j (x). In fact, it is highly probable

that the Hadamard product of the polynomial gi,j (x) with a d-shifted version of

itself, gi,j (x) — gi,j (x), results in a shifted version of qi (x), for a speci¬c value of

d

d. For this reason, the eavesdropper can calculate all the possible gi,j (x) — gi,j (x)

d

and check whether the resulting polynomial has support with weight m. This

attack requires a work factor of 236 binary operations, that could be even further

reduced by calculating the periodic autocorrelation of the coe¬cients of gi,j (x)

(this can be made through e¬cient algorithms), in order to ¬nd the value of d.

OTD3 Attack Strategy. The third attack strategy consists in considering the

i-th row of the inverse of G¤k , that is:

Ri = [Qi Si,0 |Qi Si,1 | . . . |Qi Si,n0 ’2 ] (9)

and the linear code generated by

’1

· Ri = I|S’1 Si,1 | . . . |S’1 Si,n0 ’2 .

GOT D3 = (Qi Si,0 ) (10)

i,0 i,0

Such code admits an alternative generator matrix in the following form:

GOT D3 = Si,0 GOT D3 = [Si,0 |Si,1 | . . . |Si,n0 ’2 ] (11)

that coincides with a block row of matrix S. Since matrix S has been chosen

sparse, the code contains low weight codewords. Precisely, GOT D3 has row weight

equal to m(n0 ’ 1), that is very small compared to the code length.

Low weight codewords can be e¬ectively searched through Stern™s algorithm

[15] and its variants [4]. Once having found matrix S, a signi¬cant part of the

secret key can be revealed by using (7). For the present choice of the system

parameters, searching for low weight codewords in the code generated by GOT D3

would require, on average, 232 binary operations.

3.2 First Variant of the Cryptosystem

The fundamental issue that validates the three OTD attack strategies relies in

the fact that both S and Q are sparse and that matrix Q has block-diagonal

form.

However, the three OTD attacks can be countered by adopting dense S ma-

trices, without altering the remaining system parameters. For example, S could

have row/column weight approximately equal to k0 p/2, with odd weight blocks

along the main diagonal, and even weight blocks elsewhere, in order to assure

non-singularity of S, so that no further check is needed.

The adoption of dense S matrices prevents the eavesdropper from obtaining

Qi and Si,j , even knowing Qi Si,j . In this case, in fact, the probability that

gi,j (x) has exactly m2 non-null coe¬cients, and that its support contains that

of at least one shift of qi (x) becomes extremely small. Furthermore, when S

is dense, the code generated by GOT D3 does not contain any more low weight

codewords, so all the three OTD attacks strategies are countered.

252 M. Baldi, M. Bodrato, and F. Chiaraluce

This modi¬cation has no e¬ect on the number of errors to be corrected by

the secret code, since the error spreading is only due to matrix Q, that is kept

sparse (with row/column weight m).

On the other hand, the choice of a dense S in¬‚uences complexity of the decod-

ing stage, that, however, can be reduced by resorting to e¬cient computation

algorithms for circulant matrices. Complexity of the cryptosystem with dense S

will be evaluated in Section 7.

As concerns matrix Q, the OTD attacks demonstrate that the choice of the

block-diagonal form is weak from the security viewpoint, so we avoid it in the

revised versions of the cryptosystem. For example, an alternative choice would

consist in obtaining Q from a matrix of n0 — n0 = 4 — 4 circulant blocks with

weight 2, except those along the main diagonal, that have weight 1, and by

permuting randomly its block rows and columns.

In this case, the inclusion of very low weight blocks in matrix Q could seem

a ¬‚aw. However, the absence of the block-diagonal structure prevents from at-

tacking each single block, and attacking a whole row or column would be too

3

involved (it would require p p ≈ 281 attempts).

2

3.3 Second Variant of the Cryptosystem

In this second variant, we adopt the following set of parameters: n0 = 3, dv = 13

and p = 8192. The increased security level is achieved at the cost of a slightly

decreased transmission rate, from 0.75 to 0.67, that, however, remains higher

than in the original version. On the other hand, the reduction in the total number

of circulant blocks permits to double their size without increasing the key length.

Both the private and the public codes, in this system, have dimension k0 p =

16384 bits and length n0 p = 24576. By means of numerical simulations, we have

veri¬ed that such QC-LDPC codes are able to correct up to more than 470 errors

per frame. For such reason, it has been possible to choose t = 40 and m = 11

for this variant of the cryptosystem.

Matrix Q is formed by n0 — n0 = 3 — 3 circulant blocks with size p, and has

row/column weight equal to m = 11. In this case, a possible choice consists in

obtaining Q from a matrix of n0 — n0 circulant blocks with weight 4, except

those along the main diagonal, that have weight 3, and by permuting randomly

its block rows and columns. In this case, attacking a whole row or column of Q

2

would require p p ≈ 2131 attempts.

4 3

Matrix S, instead, is formed by k0 — k0 = 2 — 2 circulant blocks with size p

and it is dense, with row/column weight approximately equal to k0 p/2. All its

blocks have even row/column weight, except those along the main diagonal, that

have odd weight, in order to allow non-singularity of the matrix.

3.4 Other Attacks

Having discussed above the OTD attack, in the following we list some of the

other most important attacks with their corresponding work factor for the second

cryptosystem variant, in order to assess its security. For a thorough description

A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes 253

of all the attack techniques already considered, we refer the interested reader to

[16]. where it is also proved that they are avoided for the parameters chosen in

the previous version of the cryptosystem (and, hence, in the ¬rst variant here

proposed).

Brute force attacks. Brute force attacks could be tempted by enumerating all

possible secret matrices H. However, the number of equivalent QC-LDPC codes

with the proposed choice of the system parameters is > 2386 . Even considering