[Cryptography] List of Proven Secure Ciphers / Hashes

[Jonathan Katz]

On Thursday, September 4, 2014, Jerry Leichter <leichter at lrw.com> wrote:

> On Sep 4, 2014, at 2:13 AM, Stephan Neuhaus <
> stephan.neuhaus at tik.ee.ethz.ch <javascript:;>> 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.


Once you allow known-plaintext attacks, symmetric-key crypto is also in NP.

Even in the ciphertext-only setting, if the underlying plaintext has any
"structure" that can be recognized by an algorithm in P (and the plaintext
is long enough compared to the key length), symmetric-key crypto is in NP.

So basically if P=NP, you are left with the one-time pad and variants.


> > 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 --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140904/1b606499/attachment.html>