Seth Schoen's Hard to Verify Signatures

David Wagner daw at
Wed Sep 8 16:37:22 EDT 2004

Hal Finney wrote:
>[...] "hard to verify signature" [...]
>Choose the number of modular squarings, t, that you want the verifier
>to have to perform.  Suppose you choose t = 1 billion.  Now you will
>sign your value using an RSA key whose exponent e = 2^t + 1.
>The way you sign, even using such a large e, is to compute
>phi = (p-1)*(q-1) and to compute e' = e mod phi, which can be done using
>about 30 squarings of 2 mod phi.  You then compute the secret exponent
>d as the multiplicative inverse mod phi of e', in the standard way that
>is done for RSA keys.  Using this method you can sign about as quickly
>as for regular RSA keys.
>However, the verifier has a much harder problem. [...] To verify [...]
>will require t = 1 billion modular squaring operations.

This signature scheme has an interesting property: once you've done
the lengthy computation, you can quickly prove to someone else that
the signature is valid.  In particular, there is a short and easy to
prove that the signature is valid, based on listing x, x^2, x^4, x^16,
x^256, x^65536, ..., x^e and giving a zero knowledge proof that your
list is correct.  The details can be found here (see esp. Section 3):
  D. Boneh, M. Naor, "Timed Commitments", CRYPTO 2000.
The signer can also create a proof like this if he wants.  Note that
Boneh and Naor consider a somewhat similar but not equivalent notion of
timed signatures, which may also be of interest.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list