Zooko Wilcox-O'Hearn wrote: > The small-key variant I'm asking about goes back to the ElGamal > verification equation: > > R^s / y^r = g^h mod p > > but instead of solving for R, we solve for y in a similar way: > > y = R^(s/r) / g^(h/r) mod p > > This means that with an ElGamal style (R,s) signature, the verifier > can derive y = g^x mod p. So he doesn't have to know the public key. > Instead of letting the public key be y, we can make it H(y) for some > hash function H. Then the verification is: > > H(y) = H( R^(s/r) / g^(h/r) mod p ) > > We have increased the signature size from twice the size of q to the > sum of the sizes of p and q (which is much bigger, for typical non-EC > DSA groups). But we have decreased the public key from the size of p to > the size of H. > > Now the interesting question is whether H can be the size of the > security > parameter, rather than twice the size like q. Maybe we could use an 80 > bit H. This would make for a very small public key (again at the expense > of a much larger signature). > > The idea would be that y is a fixed target, and a forger needs to come > up with an R,s whose hash matches the hash of y. It's a second preimage > problem, not a collision problem.
Hmm. If collisions on H are possible then an attacker can search for two message/signature pairs with the same signature, (M1, (R,s)) and (M2, (R,s)), such that the solutions for y have colliding hashes: H(R^(s / r) / g^(h_M1 / r) mod p) = H(R^(s / r) / g^(h_M2 / r) mod p) and hence are verifiable by the same public key (their own key, that is, not someone else's). This is a "duplicate signature" attack in the terminology of <http://citeseer.ist.psu.edu/stern02flaws.html>. Is that a valid attack on the intended security properties of Tahoe? I think probably not, provided that no-one expects these signatures to guarantee nonrepudiability. -- David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
