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. _______________________________________________ tahoe-dev mailing list tahoe-dev@allmydata.org http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev