In this paper, we shortly describe the three OTD attacks, and analyze the

¬‚aw in the private-public key map that originates them. We propose a ¬rst

variant of the cryptosystem that is able to counter such attacks by adopting a

di¬erent form for its constituent matrices, without altering other parameters.

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

Furthermore, we present a second variant of the cryptosystem that provides

overall increased security.

In addition, we study the application, in this new version of the cryptosystem,

of e¬cient algorithms for computation on large circulant matrices, that permit

to reduce its encryption and decryption complexity. The main question concerns

encoding, that, in the case of QC codes, can be implemented through a barrel

shift-register with hardware complexity that increases linearly with the code

length. However, the total number of operations can still be high, thus re¬‚ecting

in latency issues. A common solution to this problem consists in searching for

sparse generator matrices [13,14]. Though this is possible for suitably designed

codes, such approach is unsuitable for codes randomly designed for the use in

cryptographic systems. In this case, however, e¬cient computation algorithms

can limit the number of operations. In this paper, we consider two possible

choices of e¬cient multiplication algorithms, namely, the Toom-Cook algorithm

and the short Winograd convolution, that actually yield reduced complexity.

2 Notation

Let F = GF (m) be the Galois ¬eld of order m, with m a prime power.

A p — p Toeplitz matrix A over F is de¬ned as follows:

⎡ ¤

a0 a1 a2 · · · ap’1

⎢ a’1 a0 a1 · · · ap’2 ⎥

⎢ ⎥

⎢ a’2 a’1 a0 · · · ap’3 ⎥

A=⎢ ⎥. (1)

⎢. .⎥

. . ..

⎣. ..¦

. .

. . . .

a1’p a2’p a3’p · · · a0

It is called circulant if ∀i, ai = ai’p . In this work we restrict our analysis to

binary circulant matrices, that is, we consider m = 2.

There is a natural isomorphism between the algebra of p—p circulant matrices

with entries in the ¬eld F and the ring of polynomials F[x]/(xp + 1). If we denote

by X the matrix with entries:

1 if j ’ i ≡ 1 (mod p)

Xi,j = , (2)

0 if j ’ i ≡ 1 (mod p)

the isomorphism maps the matrix X to the monomial x and the generic circulant

p’1 p’1

matrix i=0 ±i Xi to the polynomial i=0 ±i xi ∈ F[x]/(xp + 1). This isomor-

phism can be extended to matrices with circulant blocks, as will be shown in the

next section.

3 Improved McEliece Cryptosystem Based on QC-LDPC

Codes

In order to hide the secret code™s structure, we have recently proposed a variant of

the McEliece cryptosystem working as follows. Bob, in order to receive encrypted

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

messages, randomly chooses a code in a family of (n0 , dv , p) QC-LDPC codes

based on Random Di¬erence Families [9], by selecting its parity-check matrix

H, and produces a generator matrix G in reduced echelon form. Matrix H is

formed by a row {H0 , . . . , Hn0 ’1 } of n0 binary circulant blocks with size p and

row/column weight dv , and it is part of Bob™s private key. Matrix G, instead, is

formed by a k — k identity matrix I (with k = k0 · p and k0 = n0 ’ 1), followed

by a column of k0 binary circulant blocks with size p. If we suppose Hn0 ’1 to

be non-singular, G can be obtained as follows:

⎡ ¤

T

H’1’1 · H0

n0

⎢ ⎥

T

H’1’1 · H1

⎢ ⎥

G = ⎢I ⎥.

n0

(3)

⎢ ⎥

.

.

⎣ ¦

.

T

H’1’1 · Hn0 ’2

n0

The remaining part of Bob™s private key is formed by two other matrices: a

k — k non-singular matrix S and a sparse n — n non-singular matrix Q. S and

Q are regular matrices, formed by k0 — k0 and n0 — n0 blocks of p — p binary

circulants, respectively. Q has row/column weight m.

By exploiting the isomorphism introduced in Section 2, the generator matrix

G can be seen as a k0 — n0 matrix with entries in the ring of polynomials

R = GF (2)[x]/(xp + 1); S and Q are invertible matrices on the same ring with

size k0 — k0 and n0 — n0 , respectively.

Then, Bob computes the public key as follows:

G = S’1 · G · Q’1 . (4)

It should be noted that G preserves the quasi-cyclic structure of G, due to the

block circulant form of S and Q.

G is made available in a public directory. Alice, who wants to send an en-

crypted message to Bob, extracts G from the public directory and divides her

message into k-bit blocks. If u is one of these blocks, Alice obtains the encrypted

version as follows:

x = u·G +e= c+e .

In this expression, e is a vector of intentional errors randomly generated, with

length n and weight t .

When Bob receives the encrypted message x, he ¬rst computes:

x = x · Q = u · S’1 · G + e · Q . (5)

Vector x is a codeword of the LDPC code chosen by Bob (corresponding to

the information vector u = u · S’1 ), a¬ected by the error vector e · Q, whose

maximum weight is t = t · m. If t and m are suitably chosen, Bob is able to

correct all the errors with very high probability, by means of LDPC decoding,

thus recovering u , and then u through a post-multiplication by S.

In the version of QC-LDPC based McEliece cryptosystem proposed in [9], we

¬xed n0 = 4, dv = 13, p = 4032, m = 7 and t = 27. Both S and Q were chosen

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

sparse, and their non-null circulant blocks had row/column weight equal to m.

In particular, the following block-diagonal form for Q was adopted:

⎡ ¤

Q0 0 0 0

⎢ 0 Q1 0 0 ⎥

⎢ ⎥

Q=⎢ ⎥ (6)

..

⎣0 0 ¦

.0

0 0 0 Qn0 ’1

that, jointly with its low density, gives raise to the ¬‚aw exploited by the OTD

attack, shortly described in the following subsection. In addition, as pointed out

in [11], matrix S should contain some null blocks in order to be non-singular.

3.1 The OTD Attack

The adoption of a sparse S and a sparse block-diagonal Q implies that, by

simply selecting the ¬rst k columns of the public key G , obtained through

the transformation (4) with G in the form (3), an eavesdropper can derive the

following matrix:

⎡ ¤

Q’1 0 ... 0

0

⎢0 ⎥

Q’1 . . . 0

⎢ ⎥

1

’1