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 .