[Cryptography] List of Proven Secure Ciphers / Hashes

[Jerry Leichter]

On Sep 4, 2014, at 2:13 AM, Stephan Neuhaus <stephan.neuhaus at tik.ee.ethz.ch> wrote:

> On 2014-09-03 12:17, Lodewijk andré de la porte wrote:
>> asserting P!=NP is a prerequisite for all crypto, but it isn't proven.
> 
> I'm not sure why this should be so.  Presumably you mean that the security of all cryptography depends on P != NP.  That may be true for all *current* crypto (I don't know), but if you could find an encryption algorithm that would be provably as difficult to break as a random problem in NEXP - NP, then even if P = NP, your algorithm would still be safe.
Consider the simple (technically incorrect, but one can formalize this) description of a problem being in NP:  If you can somehow guess a solution, you can verify that it is, indeed, a solution in polynomial time.

*Asymmetric* cryptography is in NP because given cipher text C and a guessed private key Kprivate, I can test whether Kprivate is the "right" key by computing E_Kpublic(D_Kprivate(C)) == C.  (If the encryption includes some random element, I need to do the test the other way around - D(E(msg)) == msg.)

For symmetric cryptography, this trick doesn't work:  Without the public key, I have no way, in general, of testing whether a guessed key is the correct one.  Yes, *in practice*, material with some kind of internal structure - say, English text - is easy to recognize.  If I guess an AES key and decryption of 10 blocks all produce recognizable English, it's overwhelmingly probable that I've got the right key.  But that's not what the *theory* is about.  To be in NP, it would have to be able to possible to confirm my guess even if the material being encrypted was completely random.

> NP just isn't the hardest class of problems out there.
Indeed not (though if P=NP, hierarchy of harder problems does collapsed).  But there are plenty of harder problems out there.

Symmetric crypto avoids being in NP by a kind of a slight of hand (the non-checkability of the results).  But it's exactly this that allows one-time-pads to be provably secure:  For a given cipher text, any possible input of the same length corresponds to a key of that length.  An attacker has no way to check which of all the possible outputs is actually "right".

BTW, this has an interesting connection with the "encrypt then MAC" vs. "MAC then encrypt" "debate" (in quotes because the mathematics was actually settled long ago).  If you MAC then encrypt, an attacker has a way to check if an alleged decryption is valid or not.  This doesn't *quite* say that encryption after a MAC is in NP, since there may be many guessed key/MAC-key pairs that happen to produce decryptions that have a valid MAC, and there's no way to choose among them.  But it comes much closer than encrypt then MAC, which leaks no information about whether the decryption is valid.
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140904/c13089c3/attachment.bin>