International Association
for Cryptologic Research

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.