Quasi-Cyclic Low-Density Parity-Check Codes in the McEliece Cryptosystem

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

Quasi-Cyclic Low-Density Parity-Check Codes in the McEliece Cryptosystem Marco Baldi, Franco Chiaraluce

Roberto Garello, Francesco Mininni

Dipartimento di Elettronica, Intelligenza Artificiale e Telecomunicazioni Università Politecnica delle Marche, Ancona, Italy Email: {m.baldi, f.chiaraluce}@univpm.it

Dipartimento di Elettronica Politecnico di Torino, Torino, Italy Email: {garello, francesco.mininni}@polito.it

Abstract—In this paper, a new variant of the McEliece cryptosystem, based on Quasi-Cyclic Low-Density Parity-Check (QCLDPC) codes, is studied. In principle, such codes can substitute Goppa codes, originally used by McEliece; their adoption, however, is subject to cryptanalytic evaluation to ensure sufficient system robustness. The authors conclude that some families of QC-LDPC codes, based on circulant permutation matrices, are inapplicable in this context, due to security issues, whilst other codes, based on the “difference families” approach, can be able to ensure a good level of security against intrusions, even if very large lengths are needed.

I. I NTRODUCTION Since many years, error correcting codes have gained an important place in cryptography. In particular, just in 1978, McEliece proposed a public-key cryptosystem based on algebraic coding theory [1] that revealed to be very secure. The rationale of the McEliece algorithm, that adopts a generator matrix as the private key and a linear transformation of it as the public key, lies in the difficulty of decoding a large linear code with no visible structure, that in fact is known to be an NP complete problem [2]. The original McEliece cryptosystem is still unbroken, as no algorithm able to realize a total break in an acceptable time has been presented up to now. A vast body of literature exists on local deduction attacks, i.e., attacks finalized to find the plaintext of intercepted ciphertexts, without knowing the secret key. Despite the advances in the field, however, the work factors required for this kind of violation remain very high, and quite intractable in practice. Moreover, the system is two or three orders of magnitude faster than RSA, the latter being, probably, the most popular public key algorithm currently used. A variant of the McEliece cryptosystem, due to Niederreiter [3], is even faster. As a counterpart, however, the McEliece system also shows some drawbacks, that can justify the limited interest most cryptographers have devoted to it till today; among them, the large length of the key and the low transmission rate. The current scenario of error correcting codes is dominated by low-density parity-check (LDPC) codes; thus, it seems interesting to investigate possible application of this kind of codes in the McEliece framework. The idea to adopt LDPC codes in the public-key cryptosystem was first explored in [4]; however, the main task of that paper was to demonstrate that the usage of LDPC codes in place of Goppa codes does not permit to reduce the key length.

In this paper, we slightly modify the system proposed in [4] and study possible application of Quasi-Cyclic (QC) LDPC codes. QC-LDPC codes should, in principle, overcome both the major drawbacks of the original McEliece cryptosystem, but their adoption must be subject to cryptanalytic evaluation. QC-LDPC codes are easily encodable, and have been included in some recent telecommunication standards [5], [6]. We suggest an algebraic technique to design a very large number of equivalent codes with fixed length and rate, which is the pre-requisite for their application in cryptosystems. The design method is described in Section II, where QC-LDPC codes are introduced in general terms and we report an overview of some design techniques. In Section III, the McEliece system using LDPC codes is reviewed, and the role of its matrix components is discussed. In Section IV a hint of the cryptanalysis of the new system is carried out, by considering some attacks specifically targeted to LDPC codes. II. Q UASI -C YCLIC LDPC CODES Quasi-Cyclic codes have been studied since many years [7], but they did not find a great success in the past because of their inherent decoding complexity in classic implementations. Nowadays, however, the encoding facilities of QC codes can be combined with new efficient LDPC decoding techniques, thus yielding QC-LDPC codes. The dimension k and the length n of a QC code are both multiple of a positive integer p, i.e. k = p · k0 and n = p·n0 ; the information vector u = [u0 , u1 , . . . , uk−1 ] and the codeword vector c = [c0 , c1 , . . . , cn−1 ] can be divided into p sub-vectors of size k0 and n0 , respectively, so that u = [u0 , u1 , . . . , up−1 ] and c = [c0 , c1 , . . . , cp−1 ]. In a QC code every cyclic shift of n0 positions of a codeword yields another codeword; since every shift of n0 positions is led by a cyclic shift of k0 positions of the corresponding information word, it can be easily shown that Quasi-Cyclic codes are characterized by the following form of the generator matrix G, where each block Gi has size k0 × n0 :   G0 G1 . . . Gp−1  Gp−1 G0 . . . Gp−2    (1) G= .  .. .. ..  ..  . . .

1-4244-0353-7/07/$25.00 ©2007 IEEE

G1

G2

...

G0

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

This leads to an efficient encoder implementation, consisting in a barrel shift register of size p, followed by a combinatorial network and an adder. It can be easily proved that the parity-check matrix H is also characterized by the same “circulant of blocks” form, in which each block Hi has size (n0 − k0 ) × n0 = r0 × n0 . A row and column rearrangement can be applied that yields the alternative “block of circulants” form, here shown for the parity-check matrix H:  c  H0,0 Hc0,1 . . . Hc0,n0 −1  Hc1,0  Hc1,1 . . . Hc1,n0 −1   H= .  (2) . . . .. . . ..  ..  c c c Hr0 −1,0 Hr0 −1,1 . . . Hr0 −1,n0 −1 In this expression, each block Hci,j is a p × p circulant matrix and, therefore, can be associated to a polynomial ai,j (x) ∈ GF2 [x]mod (xp + 1), with maximum degree p − 1 and coefficients taken from the first row of Hci,j : i,j

a

(x) =

ai,j 0

i,j 2 i,j 3 i,j p−1 + ai,j 1 x + a2 x + a3 x + · · · + ap−1 x

(3)

A. QC-LDPC codes based on Circulant Permutation Matrices A widespread family of QC-LDPC codes has parity-check matrices in which each block Hci,j = Pi,j is a circulant permutation matrix or the null matrix of size p; circulant permutation matrices can be represented through the value of their first row shift pi,j . Many authors have proposed code construction techniques based on this approach (see [8] and [9] for example) and LDPC codes based on permutation matrices have been even included in the IEEE 802.16e standard [5]. Another reason why these codes have met success is their implementation facility [10]. The parity-check matrix of these codes can be represented through a “model” matrix Hm , of size r0 × n0 , containing the shift values pi,j (pi,j = 0 represents the identity matrix, while pi,j = −1 the null matrix). The code rate is R = k0 /n0 and it can be varied arbitrarily through a suitable choice of r0 and n0 . On the other hand, the local girth length for these codes cannot exceed 12, and the imposition of a lower bound on the local girth length reflects on a lower bound on the code length [9]. The rows of a permutation matrix sum into the all-one vector, so these parity-check matrices cannot have full rank. Precisely, every parity-check matrix contains at least r0 −1 rows that are linearly dependent on the others, and the maximum rank is r0 (p − 1) + 1. A common solution to ensure the full rank consists in imposing the lower triangular (or quasi-lower triangular) form of the matrices, similarly to what done in the IEEE 802.16e standard [5]. B. QC-LDPC codes based on Difference Families When designing a QC-LDPC code, the parity-check matrix H should have some properties that optimize the behavior of the belief propagation-based decoder. First of all, the sparse character of H reflects on the maximum number of non-zero coefficients of each polynomial ai,j (x). Then, short length

cycles must be avoided in the Tanner graph associated with the code. The latter requirement can be ensured, through algebraic arguments, when H is a single row of circulants (i.e. r0 = 1), and the corresponding code rate is R = (n0 − 1)/n0 :   H = Hc0 Hc1 · · · Hcn0 −1 (4) Let (G, +) be a finite group of order v, D a subset of G, and µ and λ positive integers, with v > µ ≥ 2. A (v, µ, λ)-difference family (DF) is a collection [D1 , . . . , Dt ] of µ-subsets of G, called “base blocks”, such that every non-zero element of G appears exactly λ times as a difference of two elements from a base block. Difference families can be used to construct QC-LDPC codes [11]. In particular, if we consider the difference family [D1 , · · · , Dn0 ], a code based on it has the following form for

the polynomials of the circulant matrices c H0 , · · · , Hcn0 −1 : ai (x) =

µ 

xdij

,

i ∈ [1; n0 ]

(5)

j=1

where dij is the j-th element of Di whose dimension is µ. With this choice, the designed matrix H is regular (it has column weight dv = µ and row weight dc = n0 · dv ) and all the elements in the difference family are used. By adopting difference families with λ = 1 in construction (5), the resulting code has a Tanner graph free of 4-length cycles [11]. Some theorems ensure the existence of difference families with λ = 1, but they apply only for particular values of the group order, so putting heavy constraints on the code length. We have recently proposed to overcome such constraints by relaxing part of the hypotheses of these theorems and then refining the outputs through simple computer searches, according to a “Pseudo Difference Families” approach [12]; other authors have proposed an alternative technique, based on “Extended Difference Families”, that ensures great flexibility in the code length [13]. Finally, a multi-set with the properties of a difference family can be constructed by a (constrained) random choice of its elements; we call this a “Random Difference Family” or RDF [14]. Such approach is adopted in the present paper. A first requirement when using an error correcting code in a cryptosystem concerns the possibility to choose it at random among a very large class of equivalent codes. This way, an opponent, even aware of the code parameters (i.e. length and rate), neither knows (obviously) the private key nor is able to obtain it through a brute force attack. When considering LDPC codes, their equivalence needs to be verified under message passing decoding, whose performance does not depend only on the weight spectrum. Generally speaking, two codes exhibit almost identical performance when they have equal (or very similar): i) code length and rate, ii) parity-check matrix density, iii) nodes degree distributions and iv) girth length distribution in the Tanner graph associated with the code. All these parameters can be kept constant in QCLDPC codes based on RDFs; moreover, the cardinality of a

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

set of equivalent codes with fixed parameters can be evaluated, through probabilistic arguments [15], and is approximately:  n0 n 0 −1 d v −1 p − j 2 − p(mod2) + p dv

l=0

j=1

(j−1)2 2



+ ldv (dv − 1)

p−j (6)

Noting by C {RDF (n0 , dv , p)} this quantity, very high values of it can be achieved, even for (relatively) short codes. As an example, by assuming p = 210, n0 = 4 (which implies n = 840 and R = 3/4), and dv = 5, we have C {RDF (4, 5, 210)} ≈ 2113 . From the cryptanalysis point of view, however, we should observe that an attack could be made on each Hci block, which is equivalent to say that the maximum number of trials for an eavesdropper results from setting n0 = 1 in expression (6). Hence, for preserving high cardinalities, longer codes should be considered. As an example, by setting p = 2000 and dv = 13, we have C {RDF (1, 13, 2000)} ≈ 2108 , high enough to discourage a brute force attack on a single submatrix. III. T HE P ROPOSED C RYPTOSYSTEM A. System description Bob, in order to receive encrypted messages, randomly chooses an RDF (n0 , dv , p) and generates the corresponding parity-check matrix H. This way, Bob is provided with a secret QC-LDPC code that, like all the others with the same parameters, is able to correct t errors, with high probability, under belief propagation decoding (the choice of t will be discussed next). Bob also chooses an r×r non-singular dense circulant “transformation” matrix, T, and obtains the new matrix H
= T · H, that, obviously, has the same null space of H. He then derives a generator matrix, G, corresponding to H
, in row reduced echelon form, and makes it available in the public directory: G is Bob’s public key and it is completely described by its (k + 1)-th column, that is a k-bit vector. On the contrary, H and T form the private (or secret) key, that is owned by Bob only. The system requires also a k × k non-singular “scrambling” matrix S, that is suitably chosen and publicly available (it can be even embedded in the algorithm implementation). Also matrix S has the “block of circulants” form, and its role is to cause propagation of residual errors at the eavesdropper’s receiver, leaving the opponent in the most uncertain condition (that is equivalent to guess the plaintext at random). For this purpose, it must be sufficiently dense in its turn. When Alice wants to send an encrypted message to Bob, she fetches G from the public directory and calculates G
= S−1 · G. Then, she divides her message into k-bit blocks and encrypts each block u as follows: x = u · G
+ e

(7)

where x is the encrypted version of u and e is a random vector of t intentional errors. At the receiver side, Bob uses its private key for decoding. In the ideal case of a channel that does not introduce additional

Figure 1. Performance attainable by H and by H
for a code with n = 8000, k = 6000 and dv = 13.

errors, by a suitable choice of t, all errors can be corrected with high probability (in the extremely rare case of an LDPC decoder failure, message resend is requested). Belief propagation decoding, however, works only on sparse Tanner graphs, free of short length cycles; therefore, in order to exploit the actual correction capability, the knowledge of the sparse parity-check matrix H is essential. By applying the decoding  algorithm  on the ciphertext x, Bob can derive u · G
= u · S−1 · G . On the other hand, as G is in row reduced echelon form, the first k coordinates of this product reveal directly u · S−1 , and right multiplication by S permits to extract the plaintext u as desired. The eavesdropper Eve, that wishes to intercept the message from Alice to Bob and is not able to derive matrix H from the knowledge of G, is, as expected, in a much less favorable position. Even if H
could be derived from G, it is made unsuitable for LDPC decoding through the action of matrix T. This aspect will be deepened in the next subsection. Moreover, we observe that H
is dense and this implies, for Eve, large decoding complexity. B. Choice of t LDPC codes are very powerful but, in general, it is not easy to explicitly determine the decoding radius for an LDPC code with belief propagation decoding. So, one cannot find “a priori” the exact value of the parameter t. However, once having fixed the code parameters, the value suitable for t can be estimated through simulation. An example is shown in Fig. 1 for a code with n = 8000, k = 6000 (p = 2000) and dv = 13. Simulation has been executed over a channel that adds t errors (randomly distributed) in each codeword of a sequence long enough to ensure a satisfactory confidence level for the results, and determining the residual Bit Error Rate (BER) and Frame Error Rate (FER) values, when decoding by either matrix H or matrix H
= T · H. The logarithmic SumProduct Algorithm has been adopted, and likelihoods have been initialized coherently with the channel model. Decoding by H
represents the opponent’s point of view: in this case, a sparse T (same column weight as H) has been

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

adopted; by employing denser T’s (as may be required for security issues) the performance of H
would be even worse. From the figure, we see that, decoding by H, the number of residual bit and frame errors becomes rapidly vanishing on the left of the knee at t ≈ 120. Because of the waterfall behavior of the curves, we can reasonably state that, for t = 40, both the BER and the FER assume negligible values (impossible to simulate), i.e., decoding is practically error free. So, it seems realistic to assume t = 40 as an estimate of the considered LDPC code correction capability. This does not ensure that all possible combinations of t = 40 (or even less) errors are corrected when decoding by H, but gives sufficient guarantee that residual errors are extremely rare. From the figure we see that, instead, 40 intentional errors cannot be efficiently corrected by using H
: an eavesdropper achieves the same BER performance of the uncoded transmission (under the same assumption of channel average error probability t/n). In other words, its decoder is useless. It should be noted, however, that, from a cryptographic point of view, a BER on the order of 5 · 10−3 , like that achievable for t = 40 when using matrix H
, is unacceptable. So, it is necessary to reinforce bad decoding by means of a scrambling action able to “propagate” the residual errors after decoding; this is the role of matrix S, and it is discussed in the next subsection. C. Choice of matrix S The residual errors after decoding are “propagated” by the subsequent product by S, so that, at the output of the eavesdropper’s decoder, not only the FER is equal to 1 (which means that all decoded sequences contain at least one erred bit) but also the BER is practically equal to 1/2 (that is the most uncertain condition for an opponent). Similarly to T, also S has to be rather dense, for doing, at the best, this error propagating action. If we consider the information part of the vector decoded ˜, ˜ , it can be expressed as u ˜ = u · S−1 + e by an opponent, u ˜ is the corresponding part of the residual errors vecwhere e tor. After the descrambling process, the decoded message is ˆ=u ˜ ·S = u+˜ u e ·S; therefore the scrambling matrix S operates directly on the residual errors, causing their propagation. Really, the extent of the propagation effect can be predicted through simple combinatorial arguments, under the hypothesis that S is randomly generated [14]. At the same time, this prediction permits to design the features of matrix S (its density, in particular, for a given size) that are compatible with the achievement of a satisfactory security level. Following the procedure described in [14], we have calculated, as an example, that, for n = 8000, k = 6000 and t = 40, an S matrix with density of about 20% is sufficient to ensure maximum error “propagation” action (that consists in having a BER nearly equal to 1/2, the most uncertain condition for an opponent). On the other hand, it is expected that the scrambling action has an impact also for the authorized user (Bob). Its (rare) residual errors are propagated as well, thus causing a slight degradation in the error correction performance, that, however, is compensated by the possibility to make the system secure.

IV. S YSTEM CRYPTANALYSIS Many potential attacks can be considered for the cryptanalysis of the McEliece system based on LDPC codes. All the attacks conceived for the original McEliece cryptosystem still apply; among these, brute force attacks, information set decoding attacks, message resend attacks and attacks based on minimum weight codewords searches. However, we have verified that the classic countermeasures to these attacks still apply to the new version of the cryptosystem and, with a suitable choice of the system parameters, all they remain unfeasible (for example, n = 8000, k = 6000 and t = 40 are suitable choices for this purpose). For the sake of brevity, we do not report details on work factors of such attacks; a more extensive analysis will be included in [16]. In this paper, we limit to discuss some attacks targeted to LDPC codes, and QC-LDPC codes, in particular, with the aim to show that circulant permutation matrixes are inapplicable, while codes based on RDFs can be used, though requiring rather large lengths. A. Density Reduction Attack [4] Let hi be the i-th row of matrix H and h
j the j-th row of matrix H
= T · H, and let (GF2n , +, ×) be the vector space of all the possible binary n-tuples with the operations of addition (i.e. the logical “XOR”) and multiplication (i.e. the logical “AND”). Let us define “orthogonality” in the following sense: two binary vectors u and v are orthogonal, i.e. u ⊥ v, iff u × v = 0. From the cryptosystem description, it follows that: h
j = hi1 + hi2 + . . . + hiz where z represents the Hamming weight of each row (column) of T. We can suppose that many hi are mutually orthogonal, due to the sparsity of matrix H. Let h
j a = hia1 + hia2 + . . . + hiaz and h
j b = hib1 + hib2 + . . . + hibz be two distinct rows of H
and hia1 = hib1 = hi1 [that happens when T has two non-zero entries in the same column (i1 ), at rows j a and j b .] In this case, it may happen that: h
j a × h
j b = hi1 (that occurs, for example, when hia1 ⊥ hib2 , . . . , hia1 ⊥ hibz , . . . , hiaz ⊥ hib1 , . . . , hiaz ⊥ hibz ). Therefore, a row of H could be derived as the product of two rows of H
. At this point, if the code is quasi-cyclic with the considered form, its whole parity-check matrix can be derived, due to the fact that the other rows of H are simply block-wise circular shifted versions of the one obtained through the attack. Even when the analysis of all possible couples of rows of H
does not reveal a row of H, it may produce a new matrix, H

, sparser than H
, able to allow efficient LDPC decoding. Alternatively, the attack can be iterated on H

and it can succeed after a number of iterations > 1; in general, the attack requires ρ−1 iterations when not less than ρ rows of H
have in common a single row of H. This attack procedure can be even applied on a single circulant block of H
, say H
i , to derive its can corresponding block Hi of H, from which T = H
i · H−1 i be obtained. We have verified elsewhere [15] that the attack can be avoided through a proper selection of matrix T, but this

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

approach forces constraints on the code parameters. In this work, following [4], we propose instead to resort only to matrix T density. Let us suppose that the attack is carried out on the single block H
i (it can be easily generalized for the whole H
). The first iteration of the attack, for the considered case of H
i circulant, is equivalent to calculate the periodic autocorrelation of the first row of H
i . When H
i is sparse (i.e. T is sparse) the autocorrelation is everywhere null (or very small), except for a limited number of peaks that reveal the couple of rows of H
i able to give information on the structure of Hi . On the contrary, when H
i is dense (suppose with one half of symbols 1), the autocorrelation is always high, and no information is available for the opponent. In this case, Eve is in the same condition as to guess at random. The relevant point is that to have a dense matrix H
, in the proposed system, does not affect the public key length: matrix G remains described completely by its (k + 1)-th column. B. Attack to codes based on Circulant Permutation Matrices Let the private key H be formed by r0 × n0 circulant permutation or null matrices Pi,j of size p and have lower triangular form, to ensure full rank. For the sake of clarity, we consider a simple example with r0 = 3 and n0 = 6:   0 0 P1,1 P1,2 P1,3 P1,4 0  (8) H =  P2,1 P2,2 P2,3 P2,4 P2,5 P3,1 P3,2 P3,3 P3,4 P3,5 P3,6 We assume that all Pi,j ’s are non null. The public key is obtained as H
= T · H, where T consists of r0 × r0 square circulant dense blocks Ti,j , each of size p. Although the exact knowledge of the private key would ensure correct decoding, for the eavesdropper it suffices to find a couple of matrices (Td , Hd ), with the same dimensions of (T, H), such that H
= Td ·Hd , and Hd is sparse enough to allow efficient belief propagation decoding. This can be accomplished considering that, given an invertible square matrix Z of size r = p · r0 , the following relationship holds: H
= T · H = T · Z · Z−1 · H = Td · Hd

(9)

where Td = T · Z and Hd = Z−1 · H. If we separate H in its left (r × k) and right (r × r) parts, H = [Hl |Hr ], a particular choice of Z coincides with the lower triangular part of H, i.e., for the considered example:   0 0 P1,4 0  (10) Z = Hr =  P2,4 P2,5 P3,4 P3,5 P3,6 With this choice of Z, Hd assumes a particular form, namely:  −1  Hd = [Hdl |Hdr ] = H−1 (11) r · [Hl |Hr ] = Hr · Hl |I where the right part of Hd is an identity matrix of size r = p·r0 . From this, it follows that: H
= Td · Hd = [Td · Hdl |Td ]

(12)

Eq. (12) is the starting point for the eavesdropper: looking at H
, she immediately knows Td and, hence Hd , both corresponding to the choice of Z expressed by Eq. (10). Moreover, it can be proved that Hd , so found, can be sparse enough to allow efficient belief propagation decoding. Because of the Hd definition, its sparsity depends on that of Z−1 . Actually, for the considered example, we have:   0 0 Z1,1 −1 −1 0  Z = Hr =  Z2,1 Z2,2 (13) Z3,1 Z3,2 Z3,3 where Z1,1 = PT = PT = PT 1,4 , Z2,2 2,5 , Z3,3 3,6 , T T T T Z2,1 = P2,5 P2,4 P1,4 , Z3,2 = P3,6 P3,5 P2,5 and Z3,1 = T T T T PT 3,6 P3,4 P1,4 +P3,6 P3,5 P2,5 P2,4 P1,4 , and orthogonality of permutation matrices has been used. It follows that the main diagonal of Z−1 contains permutation matrices; the underlying diagonal contains products of permutation matrices, i.e. permutation matrices again; the following one contains sums of permutation matrices. The same analysis holds for an arbitrary r0 : the blocks Zi+j,1+j , i ∈ [2; r0 ] , j ∈ [0; r0 − i] have column (row) weight 2i−2 . It follows that, when r0 is small, Z−1 is sparse and, consequently, Hd is sparse as well; so it could be used by Eve for efficient decoding. Furthermore, the attack can continue and aim at obtaining another matrix, Hb , that has the same density of H and, therefore, can produce a total break of the cryptosystem. This new matrix corresponds to another choice of Z, namely Z = Z∗ , that, for the considered example, has the following form:   0 0 P1,4 0  P2,5 Z∗ =  0 (14) 0 0 P3,6 For this choice of Z, Hb has the same density of H and each of its rows is a permuted version of the corresponding row of H. Hb is in row reduced echelon form. An attack that aims at finding Hb can be conceived by analyzing the structure of Hd in the form (11), with H−1 r expressed by Eq. (13). It can be noticed that the first row of Hd equals that of H multiplied by PT 1,4 , so it corresponds to the first row of Hb . The second row of Hd equals that of H multiplied by PT 2,5 plus a shifted version of the first row of Hb . The third row of Hd equals that of H multiplied by PT 3,6 plus two shifted versions of the first row of Hb and a shifted version of the second row of Hb . Therefore, the attack can exploit a recursive procedure. When sparse matrices are added, it is highly probable that their symbols “1” do not overlap. For this reason, in a sum of rows of Hb , the contributions of shifted versions of known rows can be isolated through correlation operations and, therefore, eliminated. This permits to deduce each row of Hb from the previous ones and, this way, derive the entire Hb . Obviously, the hypothesis of non-overlapping elements is most likely verified when the blocks of H are sparse and r0 is not too high. For example, we have found that matrices with r0 = 6

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.

and p = 40 (i.e. density of the blocks 0.025) are highly exposed to a total break. This is not a trivial case; for example, the codes included in the IEEE 802.16e standard [5] have p ∈ [24; 96] and r0 = 6 when the code rate is 3/4. The risk is even emphasized by the fact that most useful codes have H matrices that contain a high number of null blocks, in order to allow efficient belief propagation decoding. Therefore, the density of Z−1 and, hence, Hd is reduced and the attack is simpler. An attack of this kind is addressed to LDPC codes based on circulant permutation matrices, whilst it is not applicable to LDPC codes based on difference families (described in Section II-B); for this reason, the latter appear more secure. C. Attack to the Dual Code At the present stage of cryptanalysis, the most dangerous attack for every instance of the McEliece cryptosystem based on LDPC codes rises from the fact that an opponent knows the dual of the secret code contains very low weight codewords and can directly search for them, thus recovering H. The dual of the secret code can be generated by H; therefore it has at least Adc ≥ r codewords with weight dc . Each of them completely describes H and, if known, allows the opponent to break the system by gathering the private key. From a cryptographic point of view, Adc should be known in order to precisely evaluate the work factor of the attack, but this is not, in general, a simple task. However, we can consider that it is dc  n and that sparse vectors most likely sum into denser vectors. Therefore, we will consider Adc = r in the following. One of the most efficient probabilistic algorithms for finding low weight codewords is due to Stern [17], and has been recently applied to LDPC codes by Hirotomo et al. [18]. The algorithm works on the parity-check matrix of a code and has two parameters, q and l, that represent the number of matrix columns and rows considered at each iteration, respectively. Optimal values for q and l can be derived considering their influence on the total number of binary operations needed for finding a codeword of given weight. If we suppose that the algorithm is performed on the dual of the secret code, with length n and dimension kd (i.e. redundancy rd = n − kd ), the probability of finding, in one iteration, a codeword with weight w, supposed unique, is: w n−w  w−qn−kd /2−w+q   n−kd −w+2q q q kd /2−q kd /2−q l  n  Pw = · · n−k  n−k /2 kd /2

d

kd /2

d

l

If the code contains Aw codewords with weight w, the probability to find one of them becomes Pw,Aw ≤ Aw Pw , and the average number of iterations needed by a successful −1 . On the other hand, each iteration of the search is m = Pw,A w algorithm requires  2

2qrd kdq/2 kd /2 rd3 2 + kd rd + 2ql N= + 2 2l q binary operations; so, the total work factor can be estimated as W F = mN . If we consider the following choice of the system parameters: n = 8000, kd = 2000, w = dc = n0 · dv = 52,

Aw = 2000, the minimum work factor, that corresponds to (q, l) = (3, 38), is 235.7 . It is evident that such system would be exposed to a total break. This attack is particularly insidious since the work factor of Stern’s algorithm mainly depends on the relative weight searched; in order to increase it, we should adopt denser paritycheck matrices. On the other hand, however, such matrices must be sparse enough to ensure the absence of 4-length cycles and allow efficient belief propagation decoding. This means that it is possible to obtain high work factors only by employing relatively large codes. For example, if we choose n = 72000, r = kd = 24000, n0 = 3 (R = 2/3) and dv = 41 (dc = 123), we have W F = 280.9 (minimum for q = 3, l = 53), that ensures a satisfactory system robustness. R EFERENCES [1] R. J. McEliece, “A public-key cryptosystem based on algebraic coding theory.” DSN Progress Report, pp. 114–116, 1978. [2] E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems,” IEEE Trans. Inform. Theory, vol. 24, pp. 384–386, May 1978. [3] H. Niederreiter, “Knapsack-type cryptosystems and algebraic coding theory,” Probl. Contr. and Inform. Theory, vol. 15, pp. 159–166, 1986. [4] C. Monico, J. Rosenthal, and A. Shokrollahi, “Using low density parity check codes in the McEliece cryptosystem,” in Proc. IEEE ISIT 2000, Sorrento, Italy, Jun. 2000, p. 215. [5] 802.16e 2005, IEEE Standard for Local and Metropolitan Area Networks - Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems - Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, IEEE Std., Dec. 2005. [6] IEEE P802.11 Wireless LANs WWiSE Proposal: High throughput extension to the 802.11 Standard, IEEE Std. IEEE 11-04-0886-00-000n, Aug. 2004. [7] R. Townsend and E. J. Weldon, “Self-orthogonal quasi-cyclic codes,” IEEE Trans. Inform. Theory, vol. 13, pp. 183–195, Apr. 1967. [8] R. Tanner, D. Sridhara, and T. Fuja, “A class of group-structured LDPC codes,” in Proc. Int. Symp. Commun. Theory and Appl., ISCTA 01, Ambleside, UK, Jul. 2001. [9] M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, vol. 50, pp. 1788–1793, Aug. 2004. [10] D. Hocevar, “LDPC code construction with flexible hardware implementation,” in Proc. IEEE ICC 2003, vol. 4, Anchorage, Alaska, May 2003, pp. 2708–2712. [11] S. Johnson and S. Weller, “A family of irregular LDPC codes with low encoding complexity,” IEEE Commun. Lett., vol. 7, pp. 79–81, Feb. 2003. [12] M. Baldi and F. Chiaraluce, “New quasi cyclic low density parity check codes based on difference families,” in Proc. Int. Symp. Commun. Theory and Appl., ISCTA 05, Ambleside, UK, Jul. 2005, pp. 244–249. [13] T. Xia and B. Xia, “Quasi-cyclic codes from extended difference families,” in Proc. IEEE Wireless Commun. and Networking Conf., vol. 2, New Orleans, USA, Mar. 2005, pp. 1036–1040. [14] M. Baldi, F. Chiaraluce, and R. Garello, “On the usage of quasi-cyclic low-density parity-check codes in the McEliece cryptosystem,” in Proc. First Int. Conf. on Commun. and Electron. (ICCE’06), Hanoi, Vietnam, Oct. 2006, pp. 305–310. [15] M. Baldi, “Quasi-cyclic low-density parity-check codes and their application to cryptography,” Ph.D. dissertation, Università Politecnica delle Marche, Ancona, Italy, Nov. 2006. [16] M. Baldi and F. Chiaraluce, “Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes,” in preparation. [17] J. Stern, “A method for finding codewords of small weight,” in G. Cohen and J. Wolfmann, Coding Theory and Applications, Springer-Verlag, Ed., no. 388 in Lecture Notes in Computer Science, 1989, pp. 106–113. [18] M. Hirotomo, M. Mohri, and M. Morii, “A probabilistic computation method for the weight distribution of low-density parity-check codes,” in Proc. IEEE ISIT 2005, Adelaide, Australia, Sep. 2005, pp. 2166–2170.