[145275] in cryptography@c2.net mail archive
Re: What's the state of the art in digital signatures? Re: What's
daemon@ATHENA.MIT.EDU (Jonathan Katz)
Fri Jul 9 12:34:54 2010
Date: Thu, 29 Apr 2010 21:18:19 -0400 (EDT)
From: Jonathan Katz <jkatz@cs.umd.edu>
To: "Zooko O'Whielacronx" <zookog@gmail.com>
cc: cryptography@metzdowd.com,
Discussion of cryptography and related <cryptography@randombit.net>,
tahoe-dev <tahoe-dev@allmydata.org>
In-Reply-To: <l2qcd6401a1004282251g57ad28e5obbaefd3703622844@mail.gmail.com>
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.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
