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

[cryptodragon.livejournal.com]

Thank you, I've just spent the last hour looking over that algorithm rather than sleeping. :)

[purplerabbits.livejournal.com]

I thought you said forking lemon there for a moment. Which would have made sense. Well, as much sense...

[lovelybug.livejournal.com]

Quite!

[just-becky.livejournal.com]

OOh I love it when you talk dirty! :-D

has a tight reduction to the hardness of DDH
Saucy!

[zwol.livejournal.com]

Could I have a reference to that algorithm, please? I am not finding it.

[ciphergoth.livejournal.com]

http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

You may be interested to note that it's carefully engineered to give the same signature for a given message every time, which helps the security reductions...

[ciphergoth.livejournal.com]

You may be interested to note that it's carefully engineered to give the same signature for a given message every time

although actually, I would not preserve that property in an implementation. The reduction is still pretty tight without it, and without it you can do most of the heavy lifting on signature generation in advance.

[strangerover.livejournal.com]

Damn, and I thought that was a start of a Mornington Crescent post...

[(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.

Saw this, and thought of you :)

[aster13.livejournal.com]

I'm probably just showing up how little i know about cryptography, here (which let's face it, could probably fit on the back of a stamp!) but, in case it's of interest:

http://blog.wired.com/27bstroke6/2007/03/cryptographer_s.html