<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 3, 2014 at 9:04 AM, grarpamp <span dir="ltr"><<a href="mailto:grarpamp@gmail.com" target="_blank">grarpamp@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Mon, Aug 11, 2014 at 9:27 PM, Tony Arcieri <<a href="mailto:bascule@gmail.com">bascule@gmail.com</a>> wrote:<br>
> AES is not<br>
> proven secure, but rather relies on the fact that nobody presently knows how<br>
> to break AES for security.<br>
<br>
That's true for a lot (all?) of crypto.<br>
So what if any ciphers, hashes, asymmetrics, etc make<br>
up the list of formally proofed secure crypto besides the<br>
one time XOR? Simple links would suffice.<br></blockquote><div><br></div><div>I'll completely ignore the discussion about P?NP that spawned here and get practical.<br><br></div><div>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. <br></div><div><br>My favorite is SYND/XSYND which is a (symmetric) stream cipher proven NP-C.<br><a href="http://www.unilim.fr/pages_perso/philippe.gaborit/isit_synd_rev.pdf">http://www.unilim.fr/pages_perso/philippe.gaborit/isit_synd_rev.pdf</a><br></div><div><br></div><div>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.<br></div><div>slides here, there is also a paper I can't find now: <a href="http://math.ucalgary.ca/sac/files/sac/u5/26_misoczki.pdf">http://math.ucalgary.ca/sac/files/sac/u5/26_misoczki.pdf</a><br></div><div><br></div><div>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<br><br><br></div><div>Anyway, for the other folks here - I always wanted to ask - can RSA be reduced to some at-least-pretty-hard complexity class?<br><br></div><div>-mk<br><br></div></div></div></div>