[Cryptography] List of Proven Secure Ciphers / Hashes

[Miroslav Kratochvil]

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.

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

SYND has security reduction to general Syndrome Decoding problem (SD is
known to be NP-Hard). Almost the same reduction applies to general McEliece
asymmetric cryptography. Even some fast non-general McE systems are proven
NP-Hard, for example the Qausi-Dyadic variant.
slides here, there is also a paper I can't find now:
http://math.ucalgary.ca/sac/files/sac/u5/26_misoczki.pdf

I'm not sure whether the same thing can be applied to hash functions,
there's FSB hash based on the hardness of the same assumption (SD), but I'm
not sure whether similar security proof would be effective there, given the
limited size of "input" - at least there were some problems that removed
the original FSB from the first round of Sha-3. :D


Anyway, for the other folks here - I always wanted to ask - can RSA be
reduced to some at-least-pretty-hard complexity class?

-mk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140915/9515f8d2/attachment.html>