Paper 2011/371

Monoidic Codes in Cryptography

Paulo S. L. M. Barreto, Richard Lindner, and Rafael Misoczki

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 efficient 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 Srivastava 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 preliminary parameters.

Note: Change of notation, corrected typos, more references and sections rearrangement.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Work to appear in PQCrypto'2011
Keywords
post-quantum cryptographycodesefficient algorithms.
Contact author(s)
rlindner @ cs tu-darmstadt de
History
2011-09-16: last of 8 revisions
2011-07-10: received
See all versions
Short URL
https://ia.cr/2011/371
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/371,
      author = {Paulo S.  L.  M.  Barreto and Richard Lindner and Rafael Misoczki},
      title = {Monoidic Codes in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2011/371},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/371}},
      url = {https://eprint.iacr.org/2011/371}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.