[tahoe-dev] Fwd: Small-key DSA variant

[Zooko Wilcox-O'Hearn]

Folks:

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.

Regards,

Zooko

http://www.mail-archive.com/cryptography@metzdowd.com/msg10812.html

> 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  
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