Score:4

How is a "quantum safe" algorithm fundamentally different from the current "secure" crypto algorithms (pre-quantum)?

ke flag

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?

DannyNiu avatar
vu flag
http://dx.doi.org/10.6028/NIST.IR.8105
Maarten Bodewes avatar
in flag
Cross posted to [Quora](https://www.quora.com/unanswered/How-is-a-quantum-safe-algorithm-fundamentally-different-from-the-current-secure-crypto-algorithms-which-are-pre-quantum-post-quantum-cryptography-crypto), please indicate it when cross posting to non-[se] sites. See for a discussion [here](https://meta.stackexchange.com/q/141823/176060)
jester avatar
ke flag
@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 =/
Maarten Bodewes avatar
in flag
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.
Score:3
gb flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.