Seth Schoen's Hard to Verify Signatures

[Hal Finney]

Hi, David - I had thought about that short-validity-proof but I don't
believe it works.  It works for the signer but not for the verifier.

> 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 timeline proof is based on the standard ZK proof of two equal
discrete logs.  In this case we have (x, x^(2^(2^n))) as one pair and
(x^(2^(2^n)), x^(2^(2^(n+1)))) as the other.  In each case the 2nd number
is the first number raised to the 2^(2^n) power.

The standard ZK proof for dual discrete logs works as follows.
We have y=g^u and z=h^u and want to prove that we know such a u.
We choose a random k and commit with v=g^k and w=h^k.  We then create
a challenge c by hashing various relevant values; at a minimum
c = hash(v,w).  Then we create a response r=c*u+k.  The verification is
g^r==y^c*v and h^r==z^c*w.

This works fine for the signer as all the values can be less than phi.
But for the verifier who does not know phi, the problem is that the
values are too big.  u in this case is 2^(2^n) from my example above,
where 2^n will be the number of squarings the verifier must do, no doubt
a billion or more likely billions of billions, as we get to the last
step in the timeline.  And further, r will be of the same order as u.
Then running the verification requires computing g^r and h^r, which
will take approximately 2^n squarings.  But that is how many squarings
it took to compute these timeline elements in the first place.  So the
2nd verifier cannot verify the ZK proof created by the first verifier
in much less time than the first verifier took to compute the values
the slow way.

I think the paper you pointed to by Boneh and Naor actually has a
different approach which works better.  The recipient gets a value
which, once he does the long work of decryption, will turn into a valid
signature.  And the timeline provides a ZK proof that it will work out
that way.  Then you'd want to make the ZK proof be designated verifier
so that the recipient can't show it around.  This way the recipient
is assured that if he does the work he will get the sig; and once he
gets the sig he can show it; but until he does the work he doesn't have
anything he can show.

I haven't read the paper for a few years so I'm not sure I'm remembering
it right; these extensions might be in a subsequent paper.  I think in
particular the ability to recover a vanilla signature was follow-on work.
But the basic idea is in the Boneh and Naor paper.

Hal

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com