[Cryptography] List of Proven Secure Ciphers / Hashes

[Jerry Leichter]

On Sep 3, 2014, at 3:04 AM, grarpamp <grarpamp at gmail.com> wrote:
>> AES is not
>> proven secure, but rather relies on the fact that nobody presently knows how
>> to break AES for security.
> 
> That's true for a lot (all?) of crypto.
> So what if any ciphers, hashes, asymmetrics, etc make
> up the list of formally proofed secure crypto besides the
> one time XOR? Simple links would suffice.
There are, as far as I know, no ciphers unconditionally proven secure, based only on accepted mathematical axioms and theorems, other than the one-time-pad.

There are a couple of ciphers proven secure given specific non-cryptographic assumptions.  The earliest was probably Rabin's variant of RSA, which is secure if factoring is hard.  (RSA in general is *not* known to be as hard as factoring.)  The difficulty of factoring is arguably an old mathematical hypothesis (though even that is subject to some debate).  Note that Rabin's variant was constructed specifically to allow it to be proven equivalent in difficulty to factoring, but it's not really a practical cipher and as far as I know no one uses it.

Beyond that, all "absolute" proofs of security are reductions to problems that are further and further from pure mathematics and more cryptographic in nature, starting with assumptions about discrete logs (which while mathematical in nature were never really attacked as computational problems until they became of interest to cryptography) and ending with "AES is a pseudo-random permutation".

All asymmetric cryptosystems are in NP, so they can't possibly be secure unless P!=NP, which of course we haven't proven.  I believe there are (specially constructed) systems whose security is NP-complete, but of course again that's not a proof, it's a reduction to a widely-believed but unproven hypothesis.  (And being NP-complete is not in and of itself a proof a security anyway.)

The remainder are proofs of security against particular kinds of attacks - e.g., AES is provably secure against a very broad array of "differential cryptography" style attacks.
                                                        -- Jerry