International Association
for Cryptologic Research

We present new ideas for decreasing the size of secure memory needed for hardware implementations of

hash-sequence based signatures proposed recently by Buldas, Laanoja and Truu (in the following referred to as BLT).

In their scheme, a message $m$ is signed by time-stamping a concatenation $m\\| z_t$ of the message and the one-time

pseudo-random password $z_t$ intended to sign messages at a particular time $t$.

The signature is valid only if the time-stamp points to the same time $t$. Hence, the one time passwords cannot be abused after their use.

To efficiently and securely implement such a scheme at the client side, dedicated hardware is needed and thereby, the solutions that save the (secure) memory and computational time are important. For such schemes, the memory consumption directly depends on the efficiency of the \\emph{hash sequence reversal algorithms}.

The best known reversal algorithm for the BLT scheme uses $O(\\log^2 \\ell)$ memory.

This means that for a signing key that is valid for one year (i.e. $\\ell\\approx 2^{25}$ with one-second time resolution), the device needs to store about $25^2=625$ hash

values which for SHA-256 hashing algorithm means about $20$ K bytes of secure memory.

Another problem with hash sequence reversal algorithms is that they mostly assume that the signature device is always

connected to the computer or has an independent power supply. This is a serious limitation for smart-card implementations of the scheme.

We show first that a mini Public Key Infrastructure in the signature device can be used to lower the memory consumption about twice.

There is a master key (i.e. a hash sequence) that is used to certify short term (about five minutes) signing keys

so that a signature consists of a short term certificate which is a hash chain in the master hash tree (used to authenticate the master hash sequence), and a hash chain that is used to authenticate a particular hash value $z_t$ in the sequence.

We also discuss how to implement hash sequence signatures in devices that have no power supply and are not regularly connected to

computers, such as smart-cards which are often used as personal digital signature devices. General-purpose cryptographic smart-cards also have many

restrictions that limit the use of hash sequence signatures. For example, their hashing speed is relatively low: up to 500 hashing steps per second;

their secure memory is of limited size, etc. This all combined with irregular usage patterns makes the use of hash sequence signatures questionable.

We show why the hash sequence signature (in its original form) cannot be used as the CA signature in the mini PKI solution.

Finally, we propose a new type of hash sequence signature that is more suitable for smart-card implementations.