While thinking about Zooko's problem with needing small keys, I seem to have recalled an idea for a DSA variant that uses small keys. I can't remember where I heard it, maybe at a Crypto rump session. I wonder if anyone recognizes it.
Let the DSA public key be y = g^x mod p. DSA signatures are defined by: r = g^k mod p mod q s satisfies sk - rx = h mod q Let's define R = g^k mod p. Then r = R mod q. The verification raises both sides of the "s" equation to the g power: g^(sk) / g^(rx) = g^h mod p, or equivalently: R^s / y^r = g^h mod p The old ElGamal signature would have been (R,s) (and maybe wouldn't have used a subgroup). Then this second equation would be the verification (substituting R for r in the "y" exponentiation works because the exponent arithmetic is implicitly mod q). But DSA improved this by using (r,s) which is smaller. We can't substitute r for R globally in the verification equation, it won't work. But we can solve for R: R = g^(h/s) * y^(r/s) mod p and take this mod q: r = R mod q = g^(h/s) * y^(r/s) mod p mod q which is the conventional DSA verification equation. 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. One issue is that there are many keys in the world, and perhaps a forger is happy to forge anyone's signature. (Or more to the point, a verifier really wants to trust all signatures out there.) Then the forger only needs to match one of H(y) for any of potentially millions or billions of y values, and this reduces his work by a factor equal to the number of keys. So we probably do have to boost the key size up to accommodate this issue. But it could still probably be smaller than for even ECDSA keys. Anyway, that's the concept. Does anyone recognize it? Hal Finney --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
