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. http://crypto.stanford.edu/~dabo/abstracts/timedcommit.html 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 [EMAIL PROTECTED]
