[tahoe-dev] Fwd: Small-key DSA variant
zooko at zooko.com
Wed Aug 26 16:04:39 UTC 2009
Hal Finney posted a crypto idea to cryptography at metzdowd.com which
might be relevant to Tahoe-LAFS's needs for future capability
designs. Here is the link and a copy of his letter.
> From: hal at finney.org ("Hal Finney")
> Date: Wednesday, August,2009-08-26 8:05:53 0 MDT
> Hi Zooko, that's fine, go ahead and repost it. I should have cross
> posted it originally to tahoe-dev but I forgot.
From: hal at finney.org
Subject: Small-key DSA variant
Date: Tuesday, August,2009-08-25 12:51:31 0 MDT
To: cryptography at metzdowd.com
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
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
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
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
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
keys. So we probably do have to boost the key size up to accommodate
issue. But it could still probably be smaller than for even ECDSA keys.
Anyway, that's the concept. Does anyone recognize it?
More information about the tahoe-dev