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?

Improve this question
$\endgroup$
4
  • $\begingroup$ dx.doi.org/10.6028/NIST.IR.8105 $\endgroup$
    – DannyNiu
    Commented Jul 22, 2021 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 ♦
    Commented Jul 22, 2021 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
    Commented Jul 22, 2021 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 ♦
    Commented Jul 22, 2021 at 21:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

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

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