Seth Schoen's Hard to Verify Signatures

[David Wagner]

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]

Re: Seth Schoen's Hard to Verify Signatures

[Hal Finney]

Hi, Adam - Yes, that's interesting.  Seth Schoen's posting and
subsequent blog entries do compare his goals with hashcash and similar
stamp minting systems; where hashcash wants to make minting expensive
and verification easy, Seth's HTV signatures aim to make signing easy
and verifying expensive.

 I think maybe you have observed an additional simplification.  In my
 case I use sender chooses x randomly (actually hash output of random
 value and resource string), and computes y = x^{x^w} mod n as the work
 function (expensive operation); and z = x^w mod phi(n), y =?  x^z mod
 n as the cheap operation (verification).

 I think your approach could be applied on the encryption side too
 resulting in simpler, faster verification.  Instead it would be:

 x is random, compute y = x^{2^t+1} mod n; verify x =? y^d mod n

The main advantage here I think is that d can be precomputed.  However you
could do the same by using y = x^{2^w} instead of x^{x^w}.  Then you could
precompute z = 2^w mod phi and you would have a single exponentiation
to verify just like in my scheme.  The RSW time-lock-puzzle paper does
it this way, they use 2^w as the exponent where w is the work factor.

Hal

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]