Cryptology ePrint Archive: Report 2015/948

A Provably Secure Short Signature Scheme from Coding Theory

Maryam Rajabzadeh Asaar, Mahmoud Salmasizadeh, Mohammad Reza Aref

Abstract: Signatures with partially message recovery in which some parts of messages are not transmitted with signatures to make them shorter are useful where bandwidth is one of the crucial concern and especially in case of signing short messages in applications such as time stamping, certified email services and identitybased cryptosystems. In this paper, to have quantum-attackresistant short signatures, a signature scheme with partially message recovery from coding theory is proposed. The security of the proposed scheme is proved under Goppa Parametrized Bounded Decoding and the Goppa Code Distinguishing assumptions in the random oracle model. Relying on the partially message recovery property, the proposal is shorter than the Dallot signature scheme, the only provably secure and practical code-based signature scheme. We should highlight that our scheme can be used as a building block of code-based signature schemes with additional properties since it compared to Dallot signature scheme not only improves its communication overhead but also it preserves its signature efficiency.

Category / Keywords: public-key cryptography / code-based signatures, signatures with message recovery, provable security, random oracle model

Date: received 28 Sep 2015

Contact author: mar61_rh at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20150928:195803 (All versions of this report)

Short URL: ia.cr/2015/948

Discussion forum: Show discussion | Start new discussion