Key Size (bytes) 67072 32750 256 6144 6144

Information Bits 524 276 1024 12288 16384

Transmission Rate 0.5117 0.5681 1 0.75 0.6667

Enc Ops per bit 514 50 2402 658 776

Dec Ops per bit 5140 7863 738 112 4678 8901

Table 1 reports the characteristics of the two proposed variants of McEliece

cryptosystem based on QC-LDPC codes, both secure against the known attacks.

The ¬rst variant (noted as QC-LDPC McEliece 1) adopts the choice of the system

parameters we have already proposed in [9], with the only di¬erence of p = 4096

instead of 4032. We have considered p coincident with a power of two in this

version because, for such values, a circulant matrix with odd row/column weight

is always non-singular, as shown in the Appendix A. The choice of p = 4096 in-

stead of 4032, however, has no e¬ect on the system security. In the second variant

(noted as QC-LDPC McEliece 2), the system parameters have been changed in

order to increase the system security level. For the sake of comparison, also the

original McEliece, the Niederreiter and the RSA cryptosystems are considered.

The key length for the Niederreiter cryptosystem coincides with the number of

bits in the non-systematic part of matrix H.

From the security viewpoint, these systems are not equivalent: the ¬rst pro-

posal exhibits a security level of 271 binary operations, while the second one

exceeds the threshold of 280 binary operations, that is currently considered as

an up to date technology limit. The ¬rst three solutions are instead assumed

with their standard parameters [4]. In such case, the McEliece and Niederreiter

cryptosystems are not able to reach a similar security level; however, more secure

versions would yield increased complexity.

It results from the table that both the proposed variants of McEliece cryp-

tosystem based on QC-LDPC codes represent a trade-o¬ between the original

McEliece cryptosystem (and its Niederreiter version) and other cryptosystems,

like RSA. In fact, they represent an advance in overcoming the drawbacks of the

original McEliece cryptosystem: they have very smaller public keys and increased

transmission rate. With respect to RSA, the proposed cryptosystems have the

advantage of very lower complexity, that is only slightly increased with respect

to the original McEliece version (that, moreover, has a lower security level).

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

8 Conclusions

We have elaborated on an implementation of the McEliece cryptosystem based

on QC-LDPC codes we have proposed for overcoming the main drawbacks of its

original version, that has been recently discovered to be subject to dangerous

attacks. We have described how these attacks exploit the sparse character of some

constituent matrices, together with their diagonal form, and we have proposed

two new variants of the cryptosystem that do not allow the application of such

attack techniques. As typical in cryptography, this does not exclude that further

attacks might be conceived in the future. So, an e¬ort should be made for getting

a coding based cryptographic construction with a supporting proof of security,

similar to what done in the related area of lattice based cryptography [27]. For

the time being, based on our knowledge, we can say that possible progress in

cryptanalysis of the proposed system will require the de¬nition of substantially

new strategies.

We have also reported complexity estimates based on the Toom-Cook method

for polynomials in GF (2)[x]. They can be partially extended to other cryptosys-

tems, such as NTRU, where polynomials modulo (xn ± 1) are used, and ECC

on GF (2n ). For both these systems, the use of Karatsuba™s and Winograd™s fast

convolution were proposed [28,29], and the Toom-Cook method could be applied

as well, even if its e¬ect should be not as impressive as in the proposed system.

The promising results obtained with Toom-Cook have their main reason in

the use of matrices. The additional cost of fast multiplication methods is quite

big, that is the reason why they are e¬ective only for big operands. Numeri-

cal examples given in Section 5.5 show that, for deep recursion, more than half

the cost of a single product comes from evaluation and interpolation. This cost,

however, is reduced in the proposed cryptosystem, because only a few evalua-

tions and interpolations are needed for a set of multiplications, so that deepest

recursion and biggest saving are possible.

The application of the Toom-Cook method permits to reduce the encryption

and decryption complexity of the proposed cryptosystems that, furthermore, are

able to overcome the main drawbacks of the original McEliece cryptosystem in

terms of key size and transmission rate. For these reasons, they can be seen

as a valuable trade-o¬ between the original McEliece cryptosystem and other

widespread solutions, like RSA.

References

1. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN

Progress Report, 114“116 (1978)

2. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of

certain coding problems. IEEE Trans. Inform. Theory 24, 384“386 (1978)

3. Lee, P., Brickell, E.: An observation on the security of McEliece™s public-key cryp-

tosystem. In: G¨nther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275“

u

280. Springer, Heidelberg (1988)

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

4. Canteaut, A., Chabaud, F.: A new algorithm for ¬nding minimum-weight words

in a linear code: application to McEliece™s cryptosystem and to narrow-sense BCH

codes of length 511. IEEE Trans. Inform. Theory 44, 367“378 (1998)

5. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl.

Contr. and Inform. Theory 15, 159“166 (1986)

6. Li, Y.X., Deng, R., Wang, X.M.: On the equivalence of McEliece™s and Niederre-

iter™s public-key cryptosystems. IEEE Trans. Inform. Theory 40, 271“273 (1994)

7. Riek, J.: Observations on the application of error correcting codes to public key

encryption. In: Proc. IEEE International Carnahan Conference on Security Tech-

nology. Crime Countermeasures, Lexington, KY, USA, October 1990, pp. 15“18

(1990)

8. Richardson, T., Urbanke, R.: The capacity of low-density parity-check codes under

message-passing decoding. IEEE Trans. Inform. Theory 47, 599“618 (2001)

9. Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece cryptosys-

tem based on QC-LDPC codes. In: Proc. IEEE ISIT 2007, Nice, France, June 2007,

pp. 2591“2595 (2007)

10. Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in

the McEliece cryptosystem. In: Proc. IEEE ISIT 2000, Sorrento, Italy, June 2000,

p. 215 (2000)

11. Otmani, A., Tillich, J.P., Dallot, L.: Cryptanalysis of two McEliece cryptosystems

based on quasi-cyclic codes. In: Proc. First International Conference on Symbolic

Computation and Cryptography (SCC 2008), Beijing, China (April 2008)

12. Gaborit, P.: Shorter keys for code based cryptography. In: Proc. Int. Workshop on

Coding and Cryptography (WCC 2005), Bergen, Norway, March 2005, pp. 81“90

(2005)

13. Richardson, T., Urbanke, R.: E¬cient encoding of low-density parity-check codes.

IEEE Trans. Inform. Theory 47, 638“656 (2001)

14. Neal, R.M.: Faster encoding for low-density parity check codes using sparse matrix

methods (1999), http://www.cs.toronto.edu/∼ radford/ftp/ima-part1.pdf.

15. Stern, J.: A method for ¬nding codewords of small weight. In: Wolfmann, J., Cohen,

G. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106“113. Springer, Heidelberg

(1989)

16. Baldi, M., Chiaraluce, F.: LDPC Codes in the McEliece Cryptosystem (September

2007), http://arxiv.org/abs/0710.0142

17. Karatsuba, A.A., Ofman, Y.: Multiplication of multidigit numbers on automata.

Soviet Physics Doklady 7, 595“596 (1963)

18. Toom, A.L.: The complexity of a scheme of functional elements realizing the mul-

tiplication of integers. Soviet Mathematics Doklady 3, 714“716 (1963)

19. Cook, S.A.: On the minimum computation time of functions. PhD thesis, Dept. of

Mathematics, Harvard University (1966)

20. Bodrato, M., Zanoni, A.: Integer and polynomial multiplication: Towards optimal

Toom-Cook matrices. In: Brown, C.W. (ed.) Proceedings of the ISSAC 2007 Con-

ference, July 2007, pp. 17“24. ACM Press, New York (2007)

21. Cantor, D.G.: On arithmetical algorithms over ¬nite ¬elds. Journal of Combinato-

rial Theory A 50, 285“300 (1989)

22. Sch¨nhage, A.: Schnelle Multiplikation von Polynomen uber K¨rpern der Charak-

o ¨ o

teristik 2. Acta Informatica 7, 395“398 (1977)

23. Brent, R.P., Zimmermann, P., Gaudry, P., Thom´, E.: Faster multiplication in

e

GF(2)[x]. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS,

vol. 5011, pp. 153“166. Springer, Heidelberg (2008)

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

24. Bodrato, M.: Towards optimal Toom-Cook multiplication for univariate and mul-

tivariate polynomials in characteristic 2 and 0. In: Carlet, C., Sunar, B. (eds.)

WAIFI 2007. LNCS, vol. 4547, pp. 116“133. Springer, Heidelberg (2007)

25. Jebelean, T.: An algorithm for exact division. Journal of Symbolic Computation 15,

169“180 (1993)

26. Winograd, S.: Arithmetic Complexity of Computations. CBMS-NSF Regional Con-

ference Series in Mathematics, vol. 33. SIAM, Philadelphia (1980)

27. Micciancio, D.: Generalized compact knapsacks, cyclic lattices and e¬cient one-

way functions. Computational Complexity 16, 365“411 (2007)