Lightweight One-Time Signature for Short Messages

Abstract

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.