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.
展开▼