Fast Hash-Based Signatures on Constrained Devices

Digital signatures are one of the most important applications of microprocessor smart cards. The most widely used algorithms for digital signatures, RSA and ECDSA, depend on finite field engines. On 8-bit microprocessors these engines either require costly coprocessors, or the implementations become very large and very slow. Hence the need for better methods is highly visible. One alternative to RSA and ECDSA is the Merkle signature scheme which provides digital signatures using hash functions only, without relying on any number theoretic assumptions. In this paper, we present an implementation of the Merkle signature scheme on an 8-bit smart card microprocessor. Our results show that the Merkle signature scheme provides comparable timings compared to state of the art implementations of RSA and ECDSA, while maintaining a smaller code size.