Cryptography Reference
In-Depth Information
Monoidic Codes in Cryptography
Paulo S.L.M. Barreto
1
,
, Richard Lindner
2
, and Rafael Misoczki
3
1
Departmento de Engenharia de Computacao e Sistemas Digitais (PCS)
Escola Politecnica, Universidade de Sao Paulo, Brasil
pbarreto@larc.usp.br
2
Technische Universitat Darmstadt, Department of Computer Science
Hochschulstraße 10, 64289 Darmstadt, Germany
rlindner@cdc.informatik.tu-darmstadt.de
3
Project SECRET, INRIA-Rocquencourt
Domaine de Voluceau, 78150 Rocquencourt, France
rafael.misoczki@inria.fr
Abstract.
At SAC 2009, Misoczki and Barreto proposed a new class of
codes, which have parity-check matrices that are quasi-dyadic. A special
subclass of these codes were shown to coincide with Goppa codes and
those were recommended for cryptosystems based on error-correcting
codes. Quasi-dyadic codes have both very compact representations and
allow for ecient processing, resulting in fast cryptosystems with small
key sizes. In this paper, we generalize these results and introduce quasi-
monoidic codes, which retain all desirable properties of quasi-dyadic
codes. We show that, as before, a subclass of our codes contains only
Goppa codes or, for a slightly bigger subclass, only Generalized Sri-
vastava codes. Unlike before, we also capture codes over fields of odd
characteristic. These include wild Goppa codes that were proposed at
SAC 2010 by Bernstein, Lange, and Peters for their exceptional error-
correction capabilities. We show how to instantiate standard code-based
encryption and signature schemes with our codes and give some prelim-
inary parameters.
Keywords:
post-quantum cryptography, codes, ecient algorithms.
1
Introduction
In 1996, conventional public-key cryptography deployed in practice was shown
to be susceptible to feasible attacks, if suciently large quantum computers were
ever built. In order to counter such attacks preemptively, several computational
problems resistant to quantum computer attacks have been studied for their
usage as foundation of cryptographic security [BBD08].
One promising candidate of such computational problems is the syndrome
decoding problem. McEliece showed in 1978 how to construct a public-key en-
cryption scheme based on the problem of decoding binary Goppa codes to their
Supported by the Brazilian National Council for Scientific and Technological Devel-
opment (CNPq) under research productivity grant 303163/2009-7.
