Is Integer Factorization Harder Than RSA Factorization?

Could there be encryption standards that rest on an NP-hard problem other than integer factorization?

• Similar to how RSA is secure because of the difficulty of integer factorization, could there be an encryption standard that's secure based on, say, travelling salesman or any other hard problem?

• Answer:

  There is no cryptosystem whose security is known to be equivalent to an NP-hard problem.  See   In particular, integer factorization is not believed to be NP-hard. However, there are several hard problems used other than factoring.  The most common example is the Discrete Logarithm Problem (DLP) and its cousins, the Diffie-Hellman problems (CDH,DDH,etc).  The discrete logarithm problem is roughly: given ggg and gxgxg^x in some group (say, the nonzero integers modulo some prime, or an elliptic curve), to find the exponent xxx. The Diffie-Hellman problems are things like: given g,gx,gyg,gx,gyg,g^x,g^y, compute gxygxyg^{xy}.  Diffie-Hellman problems can be solved if you know the discrete log, and while that's often the best way we know for solving them, we can't prove that it's the best.  This is kind of like how the RSA problem (find an eth root mod N) is not quite the same as factoring, but people say "factoring" because that's usually the best way to solve it. There are other problems for other fancy cryptosystems: solving certain equations in many variables, or finding the shortest nonzero vectors in a lattice, or removing the noise from certain kinds of coding systems.  None of these are widely used, but they may be important if a quantum computer is invented, and in the meantime they're used in certain niches. Then of course, there are the more ad-hoc problems, like "given y, find some x such that SHA256(x) = y".