Check out the new USENIX Web site. Application of one-time Signatures
previous up next 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 tex2html_wrap_inline446 and tex2html_wrap_inline448 are generated. The first one contains tex2html_wrap_inline450 truly random l-bit-numbers tex2html_wrap_inline454 , and the second contains the hash values of these numbers, that is, tex2html_wrap_inline456 . By definition the public key is: tex2html_wrap_inline458 .

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


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

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


and check that tex2html_wrap_inline504 .

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