Hacker News new | past | comments | ask | show | jobs | submit login

The assumption needed is even stronger than the complexity-class question: even if you proved integer factorization was not in P, that wouldn't be enough, since you need integer factorization to be almost always hard in every instance of the problem. Or at least you must have some way to identify and exclude the easy-to-solve instances.

Example: SAT-solving is NP-complete, but nonetheless heuristic SAT solvers are very good in practice, which makes its hardness too weak for cryptographic use. That can be ameliorated by trying to identify a more specific subset of "actually hard to solve SAT" (some of the research on the SAT "phase transition" aims at this), but it's pretty difficult. A few problems like integer factorization seem to have just arrived with this apparent always-hard property, but attempts to engineer it have been less successful, hence to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function (even though Diffie & Hellman suggested that as a research agenda way back in 1976).

I wrote an essay on that subject a few years ago, since the reverse question also comes up in AI discussions: http://www.kmjn.org/notes/nphard_not_always_hard.html




There were some attempts to make the knapsack problem into an encryption system. But the early attempts were broken, then patched up and re-broken etc, and nobody has invested enough time into breaking the latest efforts, so cryptographers don't trust it.


"to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function"

Not used in practice, but such a result was presented by Atjai and Dwork:

https://dl.acm.org/citation.cfm?id=258604


An interesting thing about this is that you can transform the integer factorization problem into SAT quite easily (I have code that does it). The resulting SAT problems seem to be hard to solve for heuristic SAT solvers once you get beyond a very small number of bits for the integer sizes.


I'm not very familiar with the literature, but there are some people using SAT solvers in that manner to do a kind of automated cryptanalysis. Here's one paper that encoded the DES procedure into a SAT problem, and looked at how SAT solvers fare on it: http://www.ing.unitn.it/~massacci/papers/mass-marr-00-JAR.pd...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: