Security reductions

[ciphergoth]

For the three or so cryptographers on my friends list:

The Goh-Jarecki-Katz-Wang DDH-based signature scheme not only has a tight reduction to the hardness of DDH - it also has a loose reduction to DL using the forking lemma in the same way as Schnorr. I mention this because it's currently my favourite scheme, and the authors didn't know about the reduction...

Comments

[(Anonymous)]

Cute. You may want to write a short eprint note about this, or if you feel like it that's the kind of thing that could be a PKC or RSA paper. I expect others would be interested to see the reduction, too.

[ciphergoth.livejournal.com]

An eprint note would be about right - it's a very straightforward result, really, the proof is practically identical to the corresponding proof about Schnorr in

http://citeseer.ist.psu.edu/ohta98concrete.html

I'll try to write it up when I have time, which might be a while. I'll also include the other observation I had, which was that if you have a hash function H' which maps the group onto itself, then your public key can be (g^x, H'(g^x)^x), which is a third shorter.

[ciphergoth.livejournal.com]

BTW please at least sign anonymous posts with a nom. I didn't know that anyone in Microsoft Research read my journal... thanks!

[ephermata.livejournal.com]

sorry, that was me. I didn't really notice that I wasn't signed in.