[tahoe-dev] What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

[Jonathan Katz]

On Wed, 28 Apr 2010, Zooko O'Whielacronx wrote:

> Anyway, although this is not one, there do exist proposals for public
> key crypto schemes where breaking the scheme implies solving a worst
> case instance of a supposedly hard problem, right?

Not to worst-case hardness of an NP-complete problem, no. Quite the 
contrary, there has been some body of work showing that a result of this 
sort is unlikely. (Though, as with all things related to complexity theory 
where our state of knowledge is so limited, such a statement must be taken 
wit ha grain of salt. In any case, such a result is well beyond anything 
we can currently prove.)

> 2. some kind of strong argument that it really is secure (the gold
> standard would be reduction to a worst-case instance of an NP-complete
> problem)

See above.