3
$\begingroup$

Classical asymmetric cryptography is commonly based on the Discrete Logarithm Problem and Integer Factorization, which are known to be solvable with a quantum computer if it has the ability to run Shor's algorithm, or an algorithm that solves these is devised to run on a classical computers.

Nowadays we know this is impossible to come at least in a few decades. But that doesn't imply that a passive eavesdropper gathers key exchange handshake packets where the symmetric key is negotiated.

The eavesdropper could decrypt the communications associated with these key negotations once the aforementioned quantum computer is built. For example, in the past, cryptosystems that were being used ended up being vulnerable to attacks so a specialized attacker could recover all the stored private information during years.

The evident matter here is that moving to post-quantum cryptographic schemes in the present would stop an attacker in the future to recover private information once conventional asymmetric schemes are broken. I know these schemes are being analyzed right now i.e NIST calling for new post-quantum crypto schemes.


Q1: Is there any institution or government in the present implementing for example NTRU, SIKE or multivariate crypto schemes on their communication establishment to prevent past private information recovery?

Q2: What would be a good estimation on time (i.e years) to move on to these post-quantum cryptographic schemes? I mean, we cannot wait until these attacks are possible on a theoretical capable quantum-computer.

$\endgroup$
8
  • 5
  • $\begingroup$ @SqueamishOssifrage as always fast and concrete. Thanks for the references, the information provided there is strongly related to what i was looking for. $\endgroup$
    – kub0x
    Nov 5, 2019 at 6:57
  • $\begingroup$ I don't think we can objectively answer Q2, and personally I don't see the use of answering Q1: what exactly would it prove? Undoubtedly we can find an instance of PQC used for experimentation, but I presume you mean in actual deployment? $\endgroup$
    – Maarten Bodewes
    Nov 5, 2019 at 12:23
  • $\begingroup$ @MaartenBodewes: Yes I mean in actual deployment. That would prevent an eavesdropper to recover the symmetric key used to encipher private information once the underlying problems of conventional asymmetric cryptography are solvable by a theoretical quantum computer. It makes sense that in these years relevant institutions change their crypto to PQ schemes. Anyways I'm pretty satisfied with the information given by Ossifrage. Feel free to post an answer to my question if you want to. $\endgroup$
    – kub0x
    Nov 5, 2019 at 13:59
  • $\begingroup$ Squeamish prefers "they/them" actually, so using "Mr" is presumptuous (I've gone ahead and removed that part of your comment). I clicked some of the links, but I don't see any mention of actual deployment, so how can that satisfy your question? $\endgroup$
    – Maarten Bodewes
    Nov 5, 2019 at 14:05

1 Answer 1

7
$\begingroup$

Question #1:

Is there any institution or government in the present implementing for example NTRU, SIKE or multivariate crypto schemes on their communication establishment to prevent past private information recovery?

Answer:

Currently the Open Quantum Safe (OQS) project has been launched to support the development and prototyping of post-quantum cryptography or quantum-resistant cryptography.

They have implemented liboqs, an open source C library for quantum-resistant cryptographic algorithms based on the selected NIST Round 2 candidates (such as NTRU, SIKE, and MQDSS (which is multivariate crypto scheme) at GitHub repository.

Question #2:

What would be a good estimation on time (i.e years) to move on to these post-quantum cryptographic schemes? I mean, we cannot wait until these attacks are possible on a theoretical capable quantum-computer.

Answer:

(1) The Open Quantum Safe (OQS) project co-leader, Michele Mosca published an article Cybersecurity in an Era with Quantum Computers: Will We Be Ready? in IEEE Security & Privacy (Volume 16, Issue 5, September/October 2018) to "estimate a 1/7 chance of breaking RSA-2048 by 2026 and a 1/2 chance by 2031."

(2) The Closing Remarks of Second PQC Standardization Conference held by NIST in August 2019, NIST PQC Standards - Next Steps states that

“NIST should not be aiming to conclude the process and have standards written by 2022. This is simply too fast to get proper answers.... Much more research is needed.”

(3) NIST will give a presentation at the eighth annual International Cryptographic Module Conference (ICMC20) on April 29, 2020 to report an update on the NIST Post-Quantum Cryptography Standardization process. .

Towards PQC Standardization—An Update

"As we proceed to the third-round selection, this presentation shares what has been learned in evaluating the first and second round candidates. It addresses some critical issues and discusses transition and migration strategies."

$\endgroup$

Your Answer

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

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