Application of one-time Signatures
One-time signature basics
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 
.