TTS: High-Speed Signatures on a Low-Cost Smart Card

TTS is a genre of multivariate digital signature schemes first proposed in 2002. Its public map is composed of two affine maps sandwiching a Tame Map, which is a map invertible through serial substitution and solving linear equations. We implement the signing and key generation operations for a TTS instance with 20-byte hashes and 28-byte signatures, on popular extant microcontroller cores compatible to the Intel 8051. Our tests demonstrates that TTS can be even faster than SFLASHv2, which is known for its celerity. The sample scheme TTS(20,28) is fast enough for practical deployment on a low-end 8051-based embedded device. A really low-end part like a stock Intel 8051AH running at 3.57 MHz can sign in just 170ms. A better 8051-compatible chip will take a lot less time.Security requirements today demand on-card key generation, and the big public keys of a multivariate PKC create a storage problem. TTS is unusual in that public keys can be synthesized on-card at a decent pace for block-by-block output, using some minimal information kept on-card. Since this does not take much more time than the I/O needed to transmit the public key to a reader, we can avoid holding the entire public key in the limited memory of a smart card. We show that this to be a gain for multivariate PKC’s with relatively few terms per central equation. The literature is not rich in this kind of detailed description of an implementation of a signature scheme — capable of fast on-card public key generation, on a low-cost smart card without a co-processor, and at NESSIE-approved security levels.We look into other theory issues like safeguarding against side-channel attacks, and using unusual techniques for linear algebra under serious space restrictions, which may help implementations of other multivariate PKC’s such as SFLASH.