<p>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 <a href="http://en.wikipedia.org/wiki/Quadratic_residuosity_problem" rel="nofollow">distinguishing squares and non-squares modulo a composite number is hard</a>:</p>

<ol>
<li><a href="http://en.wikipedia.org/wiki/Rabin_signature_algorithm" rel="nofollow">Rabin's signature scheme</a></li>
<li><a href="http://en.wikipedia.org/wiki/Oblivious_transfer" rel="nofollow">Rabin's oblivious transfer</a></li>
<li><a href="http://en.wikipedia.org/wiki/Goldwasser-Micali_cryptosystem" rel="nofollow">Goldwasser–Micali semantically-secure cryptosystem</a></li>
<li><a href="http://en.wikipedia.org/wiki/Blum_Blum_Shub" rel="nofollow">Blum-Blum-Shub pseudorandom generator</a></li>
<li><a href="http://en.wikipedia.org/wiki/Feige-Fiat-Shamir_Identification_Scheme" rel="nofollow">Feige-Fiat-Shamir identification scheme</a></li>
</ol>

<p>And many other schemes. However, note that schemes based on the hardness of discrete log (say, the <a href="http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange" rel="nofollow">Diffie-Helmann protocol</a> or <a href="http://en.wikipedia.org/wiki/ElGamal_encryption" rel="nofollow">Elgamal encryption/signature scheme</a>) will continue to be secure.</p>

CC BY-SA 2.5
2011-02-25T22:48:19.273Z
It seems very likely to me that if factoring is in P, then so is the discrete log problem. Certainly the converse is true.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-26T03:16:25.453Z
@Joe: I have the same feelings, but is there any proof or mathematical evidence?
Sadeq Dousti
CC BY-SA 2.5
2011-02-26T04:33:02.310Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-26T07:31:54.147Z
@Joe: Very interesting! Your comment motivated me to dig more into this, and found [a result by Eric Bach](http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html) which states that "**solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes.**"
Sadeq Dousti
CC BY-SA 3.0
2012-08-21T05:28:00.157Z
Lattice based crypto should hopefully remain secure though.
Antimony
CC BY-SA 3.0
2012-08-22T19:31:44.567Z
@Antimony: Yep. The best quantum algorithms to break any hard lattice problem (CVP, SVP, SIVP, SIS, etc.) is exponential time, so there's hope that these problems (and crypto constructs based on their hardness) are hard, even on quantum machines.
Sadeq Dousti
CC BY-SA 3.0
2011-02-25T03:39:15.293Z
2015-11-12T12:36:12.600Z
2015-11-12T12:36:12.600Z
Sadeq Dousti
<p>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.</p>

CC BY-SA 3.0
2011-09-27T13:11:52.907Z
2011-09-27T13:11:52.907Z
Mohammad Al-Turkistany
<p>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. </p>

<p>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.</p>

<p>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. </p>

CC BY-SA 2.5
2011-02-23T17:12:48.327Z
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.
Peter Taylor
CC BY-SA 2.5
2011-02-24T00:14:51.210Z
@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.
Flávio Botelho
CC BY-SA 2.5
2011-02-24T00:22:20.080Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-24T00:58:08.690Z
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.
Flávio Botelho
CC BY-SA 2.5
2011-02-24T01:12:00.063Z
@Flavio: But non-repudiation doesn't work in the same way, does it?
Joe Fitzsimons
CC BY-SA 2.5
2011-02-24T02:00:23.800Z
@Joe: The issue for me is always the TTP. If the TTP changes my RSA  public key without my consent and issues signatures with it, will i be able to repudiate them? With symmetric ciphers the trust needed in the TTP is even greater... If the TTP is really trusted, then there is non-repudiation.
Flávio Botelho
CC BY-SA 2.5
2011-02-24T02:09:28.557Z
@Flavio: Yes, but you the TTP only comes in when you introduce PKI, so non-repudiation is much stronger in the asymmetric case. Further, the vulnerability you outline above fails if sender and receiver have previously interacted (so that the receiver already has used the sender's public key). There can be no selective repudiation.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-23T15:52:20.673Z
2011-02-23T15:52:20.673Z
Peter Shor 
<p>Factoring is not known to be NP-complete. <a href="https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete">This</a> 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).</p>
<p>So my questions are:</p>
<ol>
<li>Which would be the <i>theoretical</i> consequences of Factoring being in P? How the overall picture of complexity classes would be affected by such a fact?</li>
<li>Which would be the <i>practical</i> consequences of Factoring being in P? Please do not say that banking transactions could be in jeopardy, I already know this trivial consequence.</li>
</ol> 

CC BY-SA 2.5
2011-02-23T16:38:41.657Z
I asked a similar question a few days ago: "What is the power of P with an integer factorization oracle?" http://cstheory.stackexchange.com/questions/4765/p-with-integer-factorization-oracle
Marzio De Biasi
CC BY-SA 2.5
2011-02-24T04:11:08.097Z
Also related: [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/q/167/)
Kaveh
CC BY-SA 2.5
2011-02-24T07:16:34.983Z
@Kaveh, the question already links to that one.
Peter Taylor
<cc.complexity-theory><cr.crypto-security><conditional-results><factoring>
Consequences of Factoring being in P?
Giorgio Camerani
# Consequences of Factoring being in P?

(Asked by: username_0 on 2011-02-23)

Factoring is not known to be NP-complete. [This](https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete) 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.

**Tags:** cc.complexity-theory, cr.crypto-security, conditional-results, factoring

> **Comments:**
> **username_1**: I asked a similar question a few days ago: "What is the power of P with an integer factorization oracle?" http://cstheory.stackexchange.com/questions/4765/p-with-integer-factorization-oracle  
> **username_2**: Also related: [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/q/167/)  
> **username_3**: @username_2, the question already links to that one.  

---

## 3 answers

### Answer by username_8 on 2011-02-23. Score: 33 | Accepted answer

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.

> **Comments:**
> **username_3**: 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.  
> **username_9**: @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.  
> **username_5**: 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.  
> **username_9**: 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.  
> **username_5**: @Flavio: But non-repudiation doesn't work in the same way, does it?  
> **username_9**: @Joe: The issue for me is always the TTP. If the TTP changes my RSA  public key without my consent and issues signatures with it, will i be able to repudiate them? With symmetric ciphers the trust needed in the TTP is even greater... If the TTP is really trusted, then there is non-repudiation.  
> **username_5**: @Flavio: Yes, but you the TTP only comes in when you introduce PKI, so non-repudiation is much stronger in the asymmetric case. Further, the vulnerability you outline above fails if sender and receiver have previously interacted (so that the receiver already has used the sender's public key). There can be no selective repudiation.  

---

### Answer by username_4 on 2011-02-25. Score: 9

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](http://en.wikipedia.org/wiki/Quadratic_residuosity_problem):

1. [Rabin's signature scheme](http://en.wikipedia.org/wiki/Rabin_signature_algorithm)
2. [Rabin's oblivious transfer](http://en.wikipedia.org/wiki/Oblivious_transfer)
3. [Goldwasser–Micali semantically-secure cryptosystem](http://en.wikipedia.org/wiki/Goldwasser-Micali_cryptosystem)
4. [Blum-Blum-Shub pseudorandom generator](http://en.wikipedia.org/wiki/Blum_Blum_Shub)
5. [Feige-Fiat-Shamir identification scheme](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange) or [Elgamal encryption/signature scheme](http://en.wikipedia.org/wiki/ElGamal_encryption)) will continue to be secure.

> **Comments:**
> **username_5**: It seems very likely to me that if factoring is in P, then so is the discrete log problem. Certainly the converse is true.  
> **username_4**: @Joe: I have the same feelings, but is there any proof or mathematical evidence?  
> **username_5**: 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.  
> **username_4**: @Joe: Very interesting! Your comment motivated me to dig more into this, and found [a result by Eric Bach](http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html) which states that "**solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes.**"  
> **username_6**: Lattice based crypto should hopefully remain secure though.  
> **username_4**: @username_6: Yep. The best quantum algorithms to break any hard lattice problem (CVP, SVP, SIVP, SIS, etc.) is exponential time, so there's hope that these problems (and crypto constructs based on their hardness) are hard, even on quantum machines.  

---

### Answer by username_7 on 2011-09-27. Score: 3

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.


---

