Schnorr's signature scheme comes out of patent in a little under a
year. It has the attractive qualities that the signatures need only
be of length 3k bits, where the best attack known requires around 2^k
operations, and there is a reduction from forging Schnorr signatures
to breaking the discrete logarithm problem in the associated group.
Unfortunately the best reduction I can find is that in this paper:
http://citeseer.ist.psu.edu/ohta98concrete.html
and that still shows a reduction that gets much worse as the number of
hash function queries goes up - the reduction is not tight at all, in
fact it leaves open the possibility of an attack on Schnorr trillions
of times easier than breaking the associated DL problem.
The reductions for factorization-based signature schemes are much
better. Unfortunately those schemes lead to signatures thousands of
bits long.
There are some interesting schemes out there which have both small
signatures and tight reductions. Unfortunately those schemes all seem
to rely on elliptic curves with special structures and/or have less
well established "hard problems" underlying their reductions, such as
the hardness of the computational Diffie-Hellman problem in "gap
Diffie-Hellman" groups in which decisional Diffie-Hellman is easy but
no fast CDH algorithm is known.
Are there any schemes which have a tight reduction to a well-
established problem like the discrete logarithm problem in Schnorr
groups, and which result in smallish signatures of around the same
size as Schnorr/DSS signatures?
I know that there's lots of interesting stuff happening in random-
oracle-free schemes at the moment, but I'm just as happy with a scheme
that uses random oracles in the reduction as one that doesn't.
Thanks!
