[cryptography] What's the state of the art in factorization?

Jonathan Katz jkatz at cs.umd.edu
Thu Apr 22 22:18:38 EDT 2010


On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:

> On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves <sneves at dei.uc.pt> wrote
> (on the cryptography at metzdowd.com list):
>> [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

As one of the authors of the above paper, I have an obvious interest in 
this thread. =)

> Later I discovered this paper [2] which appears to be an improvement
> on that one in terms of performance (see Table 1 in [2]) while still
> having a tight reduction to the Computational Diffie-Hellman (CDH)
> problem. Strangely, this paper [2] doesn't appear to have been
> published anywhere except as an eprint on eprint.iacr.org. I wonder
> why not. Is there something wrong with it?

While I don't know of any attack, the proof of security does not appear to 
be correct.

On the other hand, there is one published scheme that gives a slight 
improvement to our paper (it has fewer on-line computations): it is a 
paper by Chevallier-Mames in Crypto 2005 titled "An Efficient CDH-Based 
Signature Scheme with a Tight Security Reduction".



More information about the cryptography mailing list