Lightweight One-Time Signature for Short Messages

Dae Hyun YUM  Pil Joong LEE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.7   pp.1567-1575
Publication Date: 2011/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1567
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
cryptography,  digital signature,  one-time signature,  

Full Text: PDF(268.3KB)>>
Buy this Article

One-time signature schemes have been used as an important cryptographic tool for various applications. To generate a signature on a message, the state-of-the-art one-time signature requires roughly one hash function evaluation and one modular multiplication. We propose a new one-time signature scheme for short messages that needs only one integer multiplication (i.e., without modular reduction or hash function evaluation). Theoretically, our construction is based on a generic transformation from identification protocols secure against active attacks into secure one-time signature schemes for short messages, where the Fiat-Shamir technique is not used. To obtain efficient instantiation of the transformation, we prove that the GPS identification protocol is secure against active attacks, which may be of independent interest.