[3063] in cryptography@c2.net mail archive
Re: Fail stop signatures question
daemon@ATHENA.MIT.EDU (Anonymous)
Fri Jul 24 05:44:02 1998
Date: Thu, 23 Jul 1998 21:56:48 +0200
From: Anonymous <nobody@replay.com>
To: cryptography@c2.net
There was a question asked about the usefulness of fail-stop signatures.
It is always good to go to the source literature and look at the protocols
in detail to get a better understanding, especially in a case like this
where Bruce is just summarizing the basic concept.
BTW a couple of other references are Eurocrypt 89, The Dining
Cryptographers in the Disco, and Eurocrypt 90, A Remark on a Signature
Scheme Where Forgery can be Proved. I'm basing this description on
the latter.
Start with an old one-time signature scheme. Alice wants to sign some
messages. Ahead of time, she chooses a one way function g and a bunch
of random values r_i_j for j = 0 and 1. She publishes:
g(r_0_0),g(r_0_1), g(r_1_0),g(r_1_1), g(r_2_0),g(r_2_1), ...
This is just a bunch of hashes of random values, considered in pairs.
Then, to sign a message m composed of bits b_0, b_1, b_2, ..., she
publishes the r_0_0 or r_0_1 according to whether b_0 is 0 or 1, and
likewise in general for b_i. In other words, if the first bit is a 0
she reveals r_0_0, so that the verifier can see that g(r_0_0) is the
first element of the first pair. If the second bit is a 1 she reveals
r_1_1 so that the verifier can see that g(r_1_1) is the second element
of the second pair. For each bit she similarly opens one of the pair
of commitments. She never reuses the r_i_j values, so each message
starts where the previous one left off in the list of commitment pairs.
If you've never seen this signature you will probably be mostly struck
by how wasteful and impractical it is, but it does show how little
theoretical mechanism is needed to create a signature. All we have to
assume is the existence of a one way function.
To make a fail stop signature, the function g must be chosen so that
if g(x)=y then there are a very large number of x values which produce
the same y. It must be such that Alice can't find two x values which
hash to the same y, just as before.
Now, Alice uses this hash function to sign in the same way. If Bob
wants to forge a signature, all he knows is the g(r_i_j) values.
He can, we suppose, search and find a value which hashes to g(r_i_j)
(or in some contexts, he may have a back door in g which lets him find
duplicates easily). But the point is, he is unlikely to hit upon r_i_j.
There is no way for him to know which of the many possible values is
Alice's. So when Bob publishes his forged signature, Alice can reveal
r_i_j as another value which hashes to the same thing as Bob's value.
Since we assume that Alice can't find two values which hash to the same y,
this proves that Bob's message was a forgery.
The point is that with this kind of signature, knowing Alice's earlier
choices of r_i_j tells nothing about the later ones. This addresses
the concern raised earlier.
