38
$\begingroup$

Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a question is trivial).

So my questions are:

  1. Which would be the theoretical consequences of Factoring being in P? How the overall picture of complexity classes would be affected by such a fact?
  2. Which would be the practical consequences of Factoring being in P? Please do not say that banking transactions could be in jeopardy, I already know this trivial consequence.
Improve this question
$\endgroup$
3

3 Answers 3

Reset to default
33
$\begingroup$

There are pretty much no complexity-theoretic consequences of Factoring being in P. This means that there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far.

Polynomial-time factoring would make it possible to take square roots over $Z_n$ (and also over a much more general class of rings as well), and give polynomial-time algorithms for a number of other number-theoretic problems for which the bottleneck in the algorithm is currently factoring.

As for practical consequences, banking transactions are probably not that much of a problem -- as soon as it was known that factoring was in P, the banks would switch to some other system, probably causing only a brief period of delays while this was being implemented. Decoding past banking transactions would probably not cause serious problems for the banks. A much more serious problem is that all the communication which was previously protected by RSA would now be in danger of being read.

Improve this answer
$\endgroup$
7
  • 42
    $\begingroup$ A bit off-topic, but as soon as it was known that factoring was in P, the banks would switch to some other system is largely wishful thinking. I discovered in December that a company which doesn't do anything except process credit card details was using a variant of Vigenère with a key shorter than some runs of known plaintext. Worse, the technical director of the company wouldn't believe me that it was insecure until I sent him some attack code. MD5, despite being widely considered broken, is still used heavily in banking. $\endgroup$
    – Peter Taylor
    Commented Feb 23, 2011 at 17:12
  • 2
    $\begingroup$ @PeterTaylor, as soon as it was known that factoring was in P, the banks would switch to some other system is largely wishful thinking". With the current cheap price of Flash memory, it is completely feasible to create a One Time Pad solution for banking, users would go from time to time to an ATM to download extra random bytes. RSA is just cheaper and simpler. $\endgroup$
    – Flávio Botelho
    Commented Feb 24, 2011 at 0:14
  • 2
    $\begingroup$ Having strong symmetric ciphers is no replacement for asymmetric ciphers, though it suffices for certain specific tasks. You run into the issue of not being able to use digital signatures, etc. $\endgroup$
    – Joe Fitzsimons
    Commented Feb 24, 2011 at 0:22
  • $\begingroup$ Actually you can have digital signatures with symmetric ciphers! It's just a lot more cumbersome and you need a much greater confidence in the trusted 3rd party. Look up at the Handbook of Applied Cryptography's chapters 11.6 and 11.7. $\endgroup$
    – Flávio Botelho
    Commented Feb 24, 2011 at 0:58
  • $\begingroup$ @Flavio: But non-repudiation doesn't work in the same way, does it? $\endgroup$
    – Joe Fitzsimons
    Commented Feb 24, 2011 at 1:12
9
$\begingroup$

RSA is one of the most important encryption/signature schemes which breaks if FACTORING is in P. However, there are many more. Several (but not all) of them are based on the assumption that distinguishing squares and non-squares modulo a composite number is hard:

  1. Rabin's signature scheme
  2. Rabin's oblivious transfer
  3. Goldwasser–Micali semantically-secure cryptosystem
  4. Blum-Blum-Shub pseudorandom generator
  5. Feige-Fiat-Shamir identification scheme

And many other schemes. However, note that schemes based on the hardness of discrete log (say, the Diffie-Helmann protocol or Elgamal encryption/signature scheme) will continue to be secure.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ It seems very likely to me that if factoring is in P, then so is the discrete log problem. Certainly the converse is true. $\endgroup$
    – Joe Fitzsimons
    Commented Feb 25, 2011 at 22:48
  • $\begingroup$ @Joe: I have the same feelings, but is there any proof or mathematical evidence? $\endgroup$
    – Sadeq Dousti
    Commented Feb 26, 2011 at 3:16
  • 3
    $\begingroup$ There is an easy proof of the converse, since $a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$. Take $c_a = \log_N(a^N \mbox{mod }N)$. So if $p = x + y$ and $q = x - y$, then $x = \frac{c_a + 1}{2}$, and $y = \sqrt{x^2 - N}$, and you have your factors. I don't think there is a known proof of the converse, but I may be wrong. Either way, both are instances of the abelian hidden subgroup problem, and are linked via Euler's theorem, so there are similarities. $\endgroup$
    – Joe Fitzsimons
    Commented Feb 26, 2011 at 4:33
  • 6
    $\begingroup$ @Joe: Very interesting! Your comment motivated me to dig more into this, and found a result by Eric Bach which states that "solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes." $\endgroup$
    – Sadeq Dousti
    Commented Feb 26, 2011 at 7:31
  • $\begingroup$ Lattice based crypto should hopefully remain secure though. $\endgroup$
    – Antimony
    Commented Aug 21, 2012 at 5:28
3
$\begingroup$

A major consequence of Factoring being in $P$ is that multiplication (of two equal size integers) is not one-way function. This would be very surprising result since multiplication is widely believed to be the strongest candidate for one-way function. However, this may not change the picture of complexity classes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.