Cryptography Reference
In-Depth Information
WildMcElieceIncognito
Daniel J. Bernstein
1
, Tanja Lange
2
, and Christiane Peters
3
1
Department of Computer Science
University of Illinois at Chicago, Chicago, IL 60607{7045, USA
djb@cr.yp.to
2
Department of Mathematics and Computer Science
Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands
tanja@hyperelliptic.org
3
Department of Mathematics
Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
c.p.peters@mat.dtu.dk
Abstract. The wild McEliece cryptosystem uses wild Goppa codes over
finite fields to achieve smaller public key sizes compared to the original
McEliece cryptosystem at the same level of security against all attacks
known. However, the cryptosystem drops one of the confidence-inspiring
shields built into the original McEliece cryptosystem, namely a large pool
of Goppa polynomials to choose from.
This paper shows how to achieve almost all of the same reduction in
key size while preserving this shield. Even if support splitting could be
(1) generalized to handle an unknown support set and (2) sped up by a
square-root factor, polynomial-searching attacks in the new system will
still be at least as hard as information-set decoding.
Furthermore, this paper presents a set of concrete cryptanalytic chal-
lenges to encourage the cryptographic community to study the security
of code-based cryptography. The challenges range through codes over
F
2
;F
3
;:::;F
32
, and cover two different levels of how much the wildness
is hidden.
Keywords:McEliece cryptosystem, Niederreiter cryptosystem, Goppa
codes, wild Goppa codes, list decoding.
1Introduction
The McEliece cryptosystem [15] is based on classical Goppa codes (correspond-
ing to genus-0 AG codes) overF
2
. A code is built using a Goppa polynomial
*
This work was supported by the Cisco University Research Program, by the Na-
tional Institute of Standards and Technology under grant 60NANB10D263, by the
Danish Council for Independent Research under the Technology and Production
Sciences (FTP) grant 11-105325, and by the European Commission under Con-
tract ICT-2007-216676 ECRYPT II. This work was started while the third author
was with Technische Universiteit Eindhoven and continued during her employ-
ment at the University of Illinois at Chicago. Permanent ID of this document:
cd39ef08c48d12b29da6b9db66559c41
. Date: 2011.09.10.
