[Cryptography] List of Proven Secure Ciphers / Hashes

[Kristian Gjøsteen]

15. sep. 2014 kl. 12:17 skrev Miroslav Kratochvil <exa.exa at gmail.com>:

> 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. 
> 
> My favorite is SYND/XSYND which is a (symmetric) stream cipher proven NP-C.
> http://www.unilim.fr/pages_perso/philippe.gaborit/isit_synd_rev.pdf

I skimmed the paper. My impression is that you are over-selling it.

Based on existing work on decoding random linear codes, the best known algorithm for decoding a word of weight 32 encoded using a random code of length 8192 requires ~ 2^150 work.

We assume that regular words are as hard to decode as random words.

We assume that quasi-cyclic codes are as hard to decode as random codes, for regular words.

Then this paper has a theorem saying that we can rule out any distinguisher using time at most 2^63 with advantage 2^-10 that uses 2^30 bits of key stream.

Compare with AES-128 in counter mode. Using only 2^23 blocks, we can ignore collision attacks, and the best known attacks with advantage 2^-10 require work 2^118 or thereabouts. I would guess that AES has seen rather more analysis than the various assumptions that this scheme is based on.

The end result: If you want assurance, go with AES in counter mode, rather than this scheme.

-- 
Kristian Gjøsteen