Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Suppose RSA and Discrete Logarithm over any group (including elliptic curves) gets broken what other schemes we have for DEPLOYMENT IMMEDIATELY do we have to rescue the internet from collapse?
So there is no other alternative and pretty much the internet is dead?
I see a lot of alternatives such as SVP based, code based alternatives floating around. Have any of these been standardized?
Since you say
to rescue the internet
I presume you are specifically referring to TLS. With a quick look at the supported Key Agreement Schemes in TLS 1.3, the ongoing draft of TLS, it is clear that all the Key Agreement Schemes are based upon the generalized Discrete Logarithm problem or Integer Factorization. Both of these are broken by Shor's algorithm on Quantum Computers, in the event that the physical constraints limiting the construction of such high bit quantum computers are solved.
However, there are numerous asymmetric cryptosystems that exist with no known efficient quantum algorithm. As you noted, there are multiple based upon the Shortest Vector Problem. In addition there are other systems, such as the Anshel-Anshel Goldfeld Key Exchange, which is based on the difficulty of the conjugation problem on braid groups. There is no known efficient algorithm to solve this.
There are standardizations for several post quantum systems, though they are not slated for inclusion in TLS. The lattice based ones have standardizations, but new variants are continually being proposed with different properties. There are standardizations for the code based schemes.
So there is no other alternative and pretty much the internet is dead?
The alternative would be to hastily adopt an algorithm that has not received enough public scrutiny and may yet still have massive security flaws in it. So, relax. Unless you know something I don't, doom isn't upon us yet and we still have a few years to figure this out.
Several standardization processes are underway.
The US Government's NIST is leading a competition to standardize post-quantum crypto primitives. They are playing a delicate balancing game of needing deployable standards before a large-scale quantum computer is invented (estimated around 2026), but also giving researchers enough time to properly analyse the submitted algorithms. They are targeting ~2023 for standards, which is a compromise on both sides.
The Round 1 submission period ended Nov 30, 2017 and you can see the list of submissions here.
The PQCrypto Project put out a set of recommendations in 2015, basically "if you need to be off RSA and ECC now, here's what to use". These recommendations are starting to be a bit out of date in light of the new algorithms submitted to the NIST competition, but they are conservative choices that, while not standardized, do have mature implementations.
For digital signatures, the family of Hash-Based Signatures (including XMSS, SPHINCS, and their variants) are fairly mature and almost ready for deployment. XMSS has a draft before the IETF which is in V11, and NIST has informally promised to immediately adopt any hash-based signature standard that gets approved by the IETF.
Hash-based signatures, despite their security proofs, have some implementation challenges, so other signature schemes based on lattices, codes, or multi-variate polynomials are in the works as part of the NIST competition.
NTRU maybe? Or McEliece with binary Goppa codes? Just by virtue of them having been around for a long time without any major breaks.
Otherwise you'll need to wait for the dust to settle in the NIST competition.
