[Cryptography] List of Proven Secure Ciphers / Hashes

[Jerry Leichter]

On Sep 7, 2014, at 8:09 AM, R. Hirschfeld <ray at unipay.nl> 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".
> Although the OP was perhaps not very precise, I think something along
> the lines of the following is meant: if S is a (polynomial-time)
> symmetric encryption function, then {<x,y> | exists k: S(x,k) = y} is
> in NP (just nondeterministically guess the key k and verify that the
> plaintext x yields the ciphertext y).
Suppose S(x,k) is AES(x || R, k), where R is a random bit string of the same length as x.  (This is a simplified version of the randomness you need to add to get semantic security anyway.)  You can try all the keys you like, but you're unlikely to every get back a value that equals y.

You can fix this by guessing k and checking Sinverse(y,k) = x.  That's in NP (though you should be careful about specifying the "n" of concern, as the size of all three of x, y, and k enter into the picture).  But realize that this is a rather artificial problem, and tells you nothing about attacks without exactly chosen plaintext.

I'd actually state this in a different way, which makes it clearer what you've actually done.  Suppose we are given an oracle Sinverse(.,k).  Then relative to this oracle, the problem of inverting S(.,k) is in NP.  Of course, it's in NP *relative to that oracle*, not the generic NP - and that's a huge difference, since we've known for years that there are oracles relative to which P=NP, and others for which P!=NP.
                                                        -- Jerry