[Cryptography] List of Proven Secure Ciphers / Hashes

[R. Hirschfeld]

> Date: Wed, 10 Sep 2014 17:34:34 +1200
> From: Peter Gutmann <pgut001 at cs.auckland.ac.nz>
> 
> "R. Hirschfeld" <ray at unipay.nl> writes:
> 
> >Showing P = NP (unlikely!) might indeed have little immediate impact on
> >crypto practice.  It depends on the nature of the proof.  If it's by giving a
> >practical efficient poly-time algorithm for an NP-complete problem, that's a
> >game changer.
> 
> OK, I'll change the scenario slightly:
> 
>   The aliens still land tomorrow and announce "There was another gunman on the
>   grassy knoll, we were responsible for the Mary Celeste (sorry about that)",
>   but this time they finish with "here's a way of efficiently solving SAT.
>   See you in another billion years or whenever they stop re-running Cheers,
>   whichever comes sooner".
> 
> Same question as last time.

Translate your factoring instance into a SAT instance via a poly-time
(or log-space) reduction.  (There are probably simple direct ways to
do this but in the worst case use the Cook's Theorem construction.)
Solve the SAT instance using the alien algorithm.  Rinse and repeat.
Rejoice because although some crypto is broken, many useful problems
thought to be hard have become easy.

Ray

P.S. I guess you may need to use a decision version of factoring and
then do a binary search to solve the function version, resulting in an
increase in running time by a logarithmic factor.