Short One-Time Signatures

The authors present a new one-time signature scheme having short signatures. The new scheme is also the first one-time signature scheme that supports aggregation, batch verification, and which admits efficient proofs of knowledge. It has a fast signing algorithm, requiring only modular additions, and its verification cost is comparable to ECDSA verification. These properties make the scheme suitable for applications on resource-constrained devices such as smart cards and sensor nodes. A One-Time Signature (OTS) scheme is a digital signature scheme that can be used to sign one message per key pair.