5 Conclusion

In this paper, we discussed alternative constructions for the AES S-box using

normal bases for GF(16) over GF(2). We worked out example implementations

showing that our normal bases can compete with the results of Canright. Of

course, the ¬nal size of the S-box depends on the size of the multiplication in

GF(16) and on the complexity of the basis transformations as well. As shown in

Section 4.2, also the target technology in¬‚uences the ¬nal count on the imple-

mentation cost. Therefore, our normal bases should at least be considered when

designing small AES S-box implementations.

Using Normal Bases for Compact Hardware Implementations 245

We did not check all possible cases, since the result can only be a specialized

implementation for a single target technology. Further, the best basis does not

only depend on the hardware size but on other optimization constraints such

as low power, timing and throughput as well. However, using our normal bases

new promising alternatives for hardware designers of compact AES S-boxes are

available.

References

1. Austria Microsystems. Standard Cell Library 0.35µm CMOS (C35),

http://asic.austriamicrosystems.com/databooks/c35/databook c35 33

2. Canright, D.: A very compact Rijndael S-box (May 2005),

http://web.nps.navy.mil/∼ dcanrig/pub.

3. Canright, D.: A Very Compact S-Box for AES. In: Rao, J.R., Sunar, B. (eds.)

CHES 2005. LNCS, vol. 3659, pp. 441“455. Springer, Heidelberg (2005)

4. Certicom. F24 with Optimal Normal Basis Representation,

http://www.certicom.com/index.php?action=ecc tutorial,math9 1

5. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and their Applications.

Cambridge University Press, New York (1986)

6. Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: A Systematic Evaluation of

Compact Hardware Implementations for the Rijndael S-Box. In: Menezes, A. (ed.)

CT-RSA 2005. LNCS, vol. 3376, pp. 323“333. Springer, Heidelberg (2005)

7. Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., Wilson, R.M.: Optimal Normal

Bases in GF (pn ). Discrete Appl. Math. 22, 149“161 (1989)

8. Paar, C.: E¬cient VLSI Architectures for Bit-Parallel Computation in Galois

Fields. PhD thesis, Institute for Experimental Mathematics, University of Essen

(1994)

9. Rijmen, V.: E¬cient Implementation of the Rijndael S-box (2000),

www.iaik.tugraz.at/RESEARCH/krypto/AES/old/∼ rijmen/rijndael/sbox.pdf

10. Rudra, A., Dubey, P.K., Jutla, C.S., Kumar, V., Rao, J.R., Rohatgi, P.: E¬cient

rijndael encryption implementation with composite ¬eld arithmetic. In: Ko¸, C.K.,

c¸

Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 171“184. Springer,

Heidelberg (2001)

11. Satoh, A., Morioka, S., Takano, K., Munetoh, S.: A Compact Rijndael Hardware

Architecture with S-Box Optimization. In: Boyd, C. (ed.) ASIACRYPT 2001.

LNCS, vol. 2248, pp. 239“254. Springer, Heidelberg (2001)

12. Tillich, S., Feldhofer, M., Großsch¨dl, J., Popp, T.: Area, Delay, and Power Char-

a

acteristics of Standard-Cell Implementations of the AES S-Box. Journal of Signal

Processing Systems 50(2), 251“261 (2008)

13. Wolkerstorfer, J., Oswald, E., Lamberger, M.: An ASIC Implementation of the AES

SBoxes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 67“78. Springer,

Heidelberg (2002)

A New Analysis of the McEliece Cryptosystem

Based on QC-LDPC Codes

Marco Baldi1 , Marco Bodrato2 , and Franco Chiaraluce1

1

DEIT, Universit` Politecnica delle Marche

a

Ancona, Italy

{m.baldi,f.chiaraluce}@univpm.it

2

Centro Vito Volterra, Universit` di Roma Tor Vergata

a

Roma, Italy

bodrato@mail.dm.unipi.it

Abstract. We improve our proposal of a new variant of the McEliece

cryptosystem based on QC-LDPC codes. The original McEliece cryp-

tosystem, based on Goppa codes, is still unbroken up to now, but has

two major drawbacks: long key and low transmission rate. Our variant is

based on QC-LDPC codes and is able to overcome such drawbacks, while

avoiding the known attacks. Recently, however, a new attack has been

discovered that can recover the private key with limited complexity. We

show that such attack can be avoided by changing the form of some con-

stituent matrices, without altering the remaining system parameters. We

also propose another variant that exhibits an overall increased security

level. We analyze the complexity of the encryption and decryption stages

by adopting e¬cient algorithms for processing large circulant matrices.

The Toom-Cook algorithm and the short Winograd convolution are con-

sidered, that give a signi¬cant speed-up in the cryptosystem operations.

Keywords: McEliece cryptosystem, QC-LDPC codes, Cryptanalysis,

Toom-Cook, Winograd.

1 Introduction

The McEliece cryptosystem is a public-key cryptosystem based on algebraic

coding theory [1] that revealed to have a very high security level. It adopts a

generator matrix as the private key and one transformation of it as the public

key, while its security lies in the di¬culty of decoding a large linear code with

no visible structure, that is known to be an NP complete problem [2].

The original McEliece cryptosystem is still unbroken, in the sense that a to-

tal break attack has never been found, and even local deduction attacks remain

quite intractable in practice [3,4]. Moreover, the system is two or three orders of

magnitude faster than competing solutions, like RSA, that is among the most

popular public key algorithms currently in use. Despite this, the McEliece cryp-

tosystem has been rarely considered in practical applications; this is due to the

fact it exhibits two major drawbacks: i) large size of the public key and ii) low

transmission rate (that is about 0.5).

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 246“262, 2008.

c Springer-Verlag Berlin Heidelberg 2008

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

In his original formulation, McEliece used Goppa codes of length n = 1024,

dimension k = 524, and minimum distance dmin of at least 101, that are able to

correct t = 50 errors. Several attempts have been made, later on, for overcoming

the drawbacks of the original system and/or further reducing the complexity,

but the adoption of alternative families of codes has not been possible without

compromising the system security. Generalized Reed-Solomon (GRS) codes, in

particular, were initially considered for an important variant of the McEliece

cryptosystem, proposed by Niederreiter [5], but they revealed to be unsecure.

On the other hand, when employing Goppa codes, the Niederreiter cryptosys-

tem shows some advantages: it has equivalent security to that of the McEliece

system, for codes with the same parameters [6], but it requires a key size more

than halved (when considering the values reported above), a transmission rate

slightly increased, and the possibility to use a public key in systematic form. For

these reasons, though renouncing to use GRS codes, the Niederreiter system is

considered a good alternative to the McEliece system.

A clever technique for increasing the transmission rate has been proposed by

Riek [7], and consists in mapping additional information bits onto the intentional

error vector. This approach could increase signi¬cantly the transmission rate,

but requires the introduction of an additional encoding and decoding stage to

implement a positional code on error vectors.

Low-Density Parity-Check (LDPC) codes represent the state of the art in for-

ward error correction techniques, and permit to approach the theoretical Shan-

non limit [8], while ensuring limited complexity. Quasi-cyclic (QC) LDPC codes

are a particular class of LDPC codes, able to join low complexity encoding of

QC codes with high-performing and low-complexity decoding techniques based

on the belief propagation principle. Several classes of QC-LDPC codes have been

proposed up to now, all having in common the parity-check matrix structure,

that is formed by sparse circulant blocks.

In a recent work, we have proposed to adopt a particular family of QC-LDPC

codes in the McEliece cryptosystem to reduce the key size and increase the trans-

mission rate [9]. We have shown such variant is able to counter all the general

attacks, and even new attacks that can compromise the security of previous

LDPC-based versions of the cryptosystem, like that proposed in [10].

Very recently, however, Otmani, Tillich and Dallot developed a new attack

that, exploiting a ¬‚aw in the transformation from the private key to the public

key, is able to recover the secret key with very high probability [11]. They pre-

sented three attack strategies, that will be denoted as OTD1, OTD2 and OTD3

in the following. In the same work, the authors also proved that a previous pro-

posal for the adoption of quasi-cyclic (but not LDPC) codes for shortening the