Application of one-time Signatures

**One-time signature basics**

**Previous:** Application of one-time Signatures
** Up:** Application of one-time Signatures
** Next:** The current implementation

One-time signature scheme was first introduced by
Lamport [DH76, Lam79] and more efficient schemes have been
proposed since then [Mer87, Mer89].

We will assume here that the hash function *h* produces *l* bits and
the message digests to be signed are *n*-bit long. The first step
involved is the creation of a key-pair which will be used to sign a
file only once; for this purpose, two arrays and
are generated. The first one contains truly random *l*-bit-numbers , and
the second contains the hash values of these numbers, that is, . By definition the public key is: .

The second step is to compute the signature of a file *f* whose hash
is noted . The signature of *f* is simply an array
whose *N* components are:

where the 's are the binary digits of and the
's the binary digits of a checksum . This
checksum prevents attacks in which an opponent could produce a file
*f*' such that all the `1' in are also in but some `0' in
have been replaced by `1'. Once the signature is generated, the
private key should be destroyed.

Given *f*, and *K*, verifying the signature implies:
compute , *c*, construct an array such that:

and check that .

Fabien A.P. Petitcolas, Computer Laboratory, University of Cambridge