[Cryptography] List of Proven Secure Ciphers / Hashes

[Jonathan Katz]

On Mon, 15 Sep 2014, Miroslav Kratochvil wrote:

> On Wed, Sep 3, 2014 at 9:04 AM, grarpamp <grarpamp at gmail.com> wrote:
>
>> On Mon, Aug 11, 2014 at 9:27 PM, Tony Arcieri <bascule 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.
>>
>
> I'll completely ignore the discussion about P?NP that spawned here and get
> practical.
>
> Note that many cryptography problems are NP, but not NP-Hard, as reduction
> of a thing that behaves "as weirdly as possible" to something that would
> solve turing machine is usually a challenge. Still, NP-Hard (and therefore
> NP-C) cryptography problems exist, and are usually called "provably secure"
> for this. For me, this is the strongest "security proof" I'm able to
> (sanely) imagine, so I'm going with it.

There is no cryptosystem whose security (in any standard sense) can be 
reduced to an NP-hard problem. The issue, intuitively, is that NP-hardness 
is a *worst-case* notion, whereas we want cryptosystems to be hard *on the 
average*.