Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / one-time digital signatures, syndrome decoding problem, post-quantum cryptography

Date: received 12 Jan 2010, last revised 17 Jan 2010

Contact author: pbarreto at larc usp br

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20100118:024246 (All versions of this report)

Short URL: ia.cr/2010/017

Discussion forum: Show discussion | Start new discussion