[Cryptography] List of Proven Secure Ciphers / Hashes

[Jonathan Katz]

Let's try to clarify things in an attempt to put this to rest.

Assumption 1: We are talking about asymptotic security (as a function of 
key length), not concrete security. Why? Because if you care about 
concrete security, then P and NP are irrelevant since, as a previous 
person noted, any scheme with some fixed key length k can be broken in 
*constant* time 2^k.

Let's let n -- a parameter! -- denote the length of the key.

Assumption 2: Encryption runs in time polynomial in n.
You can question this assumption, and in fact it might be meaningful to 
allow encryption to run in time  n^{log n}. But this is the assumption I 
am making.

Assumption 3: You want security to hold against all polynomial-time 
adversaries.
You can question this assumption, and in fact it might be meaningful to 
only require security for adversaries running in time n^10 (but not those 
running in time n^11). But this is the assumption I am making.

We must also fix a notion of security. For concreteness, let's use the 
notion of CPA-security (i.e., security against chosen-plaintext attacks); 
see the Katz-Lindell textbook for formal definitions. CPA-security, as 
defined there, already incorporates Assumptions 1, 2, and 3.

Now, what I claim is:
If P=NP, then no public-key or symmetric-key encryption scheme is 
CPA-secure.

On Fri, 5 Sep 2014, Jerry Leichter wrote:

> On Sep 4, 2014, at 9:23 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:
>> Once you allow known-plaintext attacks, symmetric-key crypto is also in NP.
> This is a meaningless statement.  NP has an exact, technical definition.  There's nothing to "allow" or "disallow".
>
> Whether "is in NP" or even "is NP complete" is relevant to cryptography is something one can debate - though not very much, as the answer is clear:  No.  (NP is about the hardest problems in some set.  Knowing that there is *some* hard problem is not particularly useful when what you want to know is that *a particular problem* - reading a particular cipher text, for example - is hard.)
>
> But if you're going to talk about a technical matter, you have to use the language as it's understood in the community.
>                                                        -- Jerry
>
>
>