4
$\begingroup$

I recently read that work is being done to develop "quantum safe" algorithms for encryption / hashing.

Presumably, these will have fundamental differences from the current "non-quantum safe" algorithms in use today (RSA, DH, AES, ChaCha20, Poly1305, SHA2/SHA3, etc.).

What fundamental differences enable algorithms to be "quantum safe"? Are quantum-safe algorithms any more vulnerable in non-quantum computers?

$\endgroup$
4
  • $\begingroup$ dx.doi.org/10.6028/NIST.IR.8105 $\endgroup$ – DannyNiu Jul 22 at 2:13
  • $\begingroup$ Cross posted to Quora, please indicate it when cross posting to non-Stack Exchange sites. See for a discussion here $\endgroup$ – Maarten Bodewes Jul 22 at 9:21
  • 1
    $\begingroup$ @MaartenBodewes Hrmm, good find. However... I did not post that to Quora. I much prefer StackExchange's Q&A format than Quora's. Is there a way to find out who did? I'm not seeing an author listed on the Quora link =/ $\endgroup$ – jester Jul 22 at 19:44
  • $\begingroup$ Oh, are there scalpers of StackOverflow questions? Could well be, although most of our questions would have too much info. Maybe they are trying there to see if they can answer here if they get a reply. $\endgroup$ – Maarten Bodewes Jul 22 at 21:09
3
$\begingroup$

so I guess you are referring to Post-Quantum (PQ) algorithms. This topic is not so much about hashing (SHA3, etc..) or block ciphers (AES, etc..) since both are kinda well understood in a PQ-scenario, and seem to be provable secure (and probably just need to increase the bits, due to Grover's algorithm) but it is about asymmetric cryptography.

When we talk about asymmetric cryptography we basically mean, that you have a public key and a private key, and you can encrypt with one of them, and decrypt with the other. Asymmetric cryptography is also fundamental to signatures.

So quantum safe (or post quantum)-algorithms are mostly concerned about that: asymmetric cryptography.

The main difference to asymmetric crypto which is used these days is the underlying problem of the algorithms. Taking RSA for example, the hardness comes from the problem, that it is hard to find the prime factors of a large enough number. However with a quantum computer this problem could be solved in polynomial time with Shor's algorithm and thus would be broken. Shor's algorithm could also be used to solve the discrete logarithm problem, which also plays an important role in today's modern cryptography.

These quantum safe algorithms you are talking about try to utilize different underlying problems (based on lattices, codes, ...) where no algorithm from a quantum (and non quantum) computer which can solve them is known yet.

Currently there is a NIST PQ Competition going, which tries to find and standardize such algorithms. There are several papers and presentations about that topic, in case you want to dig deeper.

Edit: Maarten Bodewes pointed out Tanja Lange's videos about the underlying problems in PQ-Cryptography, which I will link here.

New contributor
Reppiz is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0

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.