6
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ not much, most alternatives are still experimental / lack deployment / implementations / standardization. $\endgroup$ – SEJPM♦ Jul 31 '17 at 19:38
  • 1
    $\begingroup$ You could try breaking it yourself. Then you'd gain more confidence ! $\endgroup$ – Ravindra HV Jul 31 '17 at 19:58
  • 2
    $\begingroup$ This borderlines a “What if ___ happened?” Q mixed with a list-type Q where As would tend to list currently "under development" alternatives. Tip: You could limit things down and pull this a bit more on-topic by describing what research you did and what you found. That shows you took time trying to help yourself, saves us from reiterating obvious answers, and helps you get more relevant, on-point answers. At worst it might help you frame “a better question”; at best it might even answer it. $\endgroup$ – e-sushi Jul 31 '17 at 22:48
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I think that links to the standards for the mentioned schemes would improve the helpfulness of your answer $\endgroup$ – Ella Rose Aug 4 '17 at 20:24
  • 1
    $\begingroup$ If where talking about proposed modifications to TLS, there's datatracker.ietf.org/doc/draft-whyte-qsh-tls13 $\endgroup$ – poncho Aug 4 '17 at 20:50
  • $\begingroup$ Woah thats awesome, I had no idea that existed! I think thats the correct answer here. Should I delete this answer and you post that as an answer, or should I edit this answer? $\endgroup$ – Ninja_Coder Aug 4 '17 at 21:03
  • 1
    $\begingroup$ @Ninja_Coder: if you are looking for something which is standardized, well, that's not it; it's been proposed, but it's not even an IETF official work item (and probably won't be until TLS 1.3 is officially put to bed) $\endgroup$ – poncho Aug 4 '17 at 23:35
1
$\begingroup$

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.

NIST PQ Crypto competition

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.

European Union's PQCrypto Project

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.

Signatures

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.

Encryption

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.

Improve this answer
$\endgroup$
0
$\begingroup$

yes, Lattice Based Cryptography.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ That's not a standard, though. From a quick look it does not seem to discuss standards either. $\endgroup$ – otus Dec 3 '17 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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