A new one-time signature scheme from syndrome decoding

Paulo S.  L.  M.  Barreto; Rafael Misoczki

Paper 2010/017

A new one-time signature scheme from syndrome decoding

Paulo S. L. M. Barreto and Rafael Misoczki

Abstract

We describe a one-time signature scheme based on the hardness of the syndrome decoding problem, and prove it secure in the random oracle model. Our proposal can be instantiated on general linear error correcting codes, rather than restricted families like alternant codes for which a decoding trapdoor is known to exist.

Note: Improved security model from EUF-NMA to EUF-1CMA.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: one-time digital signatures syndrome decoding problem post-quantum cryptography
Contact author(s): pbarreto @ larc usp br
History: 2010-01-18: last of 2 revisions; 2010-01-12: received; See all versions
Short URL: https://ia.cr/2010/017
License: CC BY

BibTeX

@misc{cryptoeprint:2010/017,
      author = {Paulo S.  L.  M.  Barreto and Rafael Misoczki},
      title = {A new one-time signature scheme from syndrome decoding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/017},
      year = {2010},
      url = {https://eprint.iacr.org/2010/017}
}