[tor-talk] NSA supercomputer

[Andrea Shepard]

On Fri, Apr 05, 2013 at 04:45:57PM -0700, Andrea Shepard wrote:
> [1] Since you can test whether a key is correct in polynomial time using two
> blocks of ciphertext, search for keys is in NP and being able to rigorously
> prove security for a block cipher would imply P != NP as a corollary.

Apologies; I have slightly mis-spoken here.  This implication would only
hold if the problem were NP-complete, which I do not believe is known to
be the case for any cipher.  Proving such lower bounds is still, however,
beyond the capabilities of present mathematics.

-- 
Andrea Shepard
<andrea at torproject.org>
PGP fingerprint: 3611 95A4 0740 ED1B 7EA5  DF7E 4191 13D9 D0CF BDA5
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20130405/559714be/attachment.pgp>