# How long to reestablish PKI if Diffie Hellman and Factoring are in classical $P$?

Supposing there is a classical (no need quantum) $$O(\log N)$$ algorithm to factor integers $$N$$ and supposing there is a classical (no need quantum) $$O(\log p)$$ algorithm to find $$g^{xy}$$ given $$g^x$$ and $$g^y$$ over cyclic groups of cardinality $$O(p)$$ (which includes elliptic curve cryptography) where the constants in $$O(\log N)$$ and $$O(\log p)$$ are very small then current $$PKI$$ breaks apart.

What alternatives are there to reboot the internet with a new public key infrastructure and how long would such an effort take?

1. I would think certain post quantum cryptosystems will also be deemed useless.

2. Note I am not assuming Discrete Logarithm is broken and since equivalence between Diffie Hellman and Discrete Logarithm Problem is still open I believe we will have something similar to PQC situation but not identical.

• The term you're looking for is most likely "Post-Quantum Cryptography" which deals with (slightly weaker) versions of exactly this. – SEJPM Nov 9 '20 at 10:50
• I don't believe that ECDSA (or EdDSA) would be broken in the scenario you give; did you want to posit that DLog also had a fast solution? – poncho Nov 9 '20 at 14:44
• No only diffie hellman en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman assumed broken. – 1.. Nov 9 '20 at 14:55
• Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken? – 1.. Nov 9 '20 at 14:57

Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken?

Of course we can; we have a number of signature algorithms that do not rely on either factoring or DH (or Discrete Log, for that matter)

how long would such an effort take?

That's the hard question; while efforts are currently underway (because of the possibility of Quantum Computers, which would be able to solve all the problems you have listed), it's not expected to fully replace RSA or E*DSA[1] for perhaps 10-20 years (10 years would be when the large majority of PKI would be "postquantum"; 20 years would be the time it'd likely take to convince every obscure webserver to convert).

In your scenario, all this would need to be drastically sped up. The time that'd take would have to be an estimate; there are the problems that'd need to be solved (and I'll focus in on the PKI piece; there are other pieces, such as key exchange, uses of signatures disconnected from the global PKI, and more advanced crypto, such as IBE and PAKE, that would also need to be addressed).

• We'd need to select a signature algorithm; such an effort is currently underway, however we're hoping to have two or three more years to gather information to allow us to make an informed choice; in your scenario, we can't wait that long. I'm guessing the community would pick one (likely either Falcon or Dilithium) in a month or two - those two are the most likely, because testing has shown that neither would slow down TLS significantly, and the best evidence we have now show them likely to be secure (and we're hoping to firm up that last statement in the next few years).

• The various PKI vendors would need to issue new root public keys using this new method (and distribute them). How long this would take is more a question about internal company politics more than practicalities; some CA vendors will jump on the ball immediately; others (based on my conversations I've had with them over the years) are more likely to ignore the problem until forced to by customer demand.

• Various browsers (and software libraries, such as OpenSSL) would need to incorporate these new methods and root public keys (and somehow deal with older websites that haven't updated yet). From my experience, all the major browser vendors are likely to be fairly quick about this. On the other hand, other clients (which might not be presented as browsers to the user) might be considerably slower to update.

• Various websites would need to have new certificates issued to them, and to use the new signature method. That's a long pole - the major websites (Google, Amazon) and website hosting services (CloudFlare) are likely to be quick about this. On the other hand, there is a large number of smaller, not that well maintained servers that will be quite reluctant to upgrade (even if they are still being actively maintained).

Going through this list, my guess is that a significant amount of the web traffic would likely to be protected by an upgraded PKI in perhaps 6 months (of fairly intensive work by the community); however there will be some traffic that won't be for years...

[1]: E*DSA is my personal terminology for the collection ECDSA, EdDSA, Schnorr signatures and similar schemes.

• E*DSA is not broken in my scenario right? We are not breaking discrete logarithm. So perhaps sooner? My posting is different from PQC. Assume only Diffie-Hellman and factoring are broken. – 1.. Nov 9 '20 at 20:49
• @1.. I misread your comment; in that comment, you said [Link] was broken; I read that as ECDSA; obviously, it's ECDH. If E*DSA is still unbroken, well, we can switch to that (a lot of the infrastructure is still there); however many of the practical aspects would still remain. In addition, we're likely to move a bit more quickly to postquantum (the concern would be if ECDH is broken, ECDLog might not be that far behind...), however we wouldn't be in quite so much of a panic – poncho Nov 9 '20 at 21:04
• How many months in this mid-apocalyptic scenario? 1 week? – 1.. Nov 9 '20 at 21:30
• @1..: my guess: still several months in this scenario (getting large companies to move quicker than that won't happen, and there are several large companies involved); however likely not as many as the 6 months I guessed earlier... – poncho Nov 9 '20 at 21:33
• What applications require dh or factoring and cannot be accomplished by E*DSA? Web, email, download software, financial transactions, settling authenticated entry? Is there listing? – 1.. Nov 10 '20 at 2:44