Seth Schoen's Hard to Verify Signatures

David Wagner daw at cs.berkeley.edu
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.
  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 majordomo at metzdowd.com



More information about the cryptography mailing list