We investigate the problem of signing short messages using a scheme that minimizes the total length of the original message and the appended signature. This line of research was motivated by several postal scrviccs intcrcstcd by stamping machines capablc of producing digital signatures. Although several message recovery schemes exist, their security is questionable. This paper proposes variants of DSA and ECDSA allowing partial recovery: the signature is appended to a truncated message and the discarded bytes are recovered by the verification algorithm. Still, the signature authenticates the whole message. Our scheme has some form of provable security, based on the random oracle model. Using further optimizations we can lower the scheme's overhead to 26 bytes for a 2-80 security level, compared to forty bytes for DSA or ECDSA and 128 bytes 1024-bit RSA.
['David Naccache', 'Jacques Stern']
Signing on a Postcard