[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [tor-talk] NSA supercomputer

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
PGP fingerprint: 3611 95A4 0740 ED1B 7EA5  DF7E 4191 13D9 D0CF BDA5

Attachment: pgpbP5INOOKPe.pgp
Description: PGP signature

tor-talk mailing list