# How will Cryptography be changed by Quantum Computing?

I realise this isn't a 'yes or no' question, and I apologise for asking something that could be seen as a discussion thread, but I had to ask.

I'm currently doing an EPQ in CS (specifically how QC will change Cryptography). I'm trying to gather up topics to cover, and so far I've scribbled down -

Effects -

1. National security, classical cryptographic methods (RSA, DSA, AES-256). Including Shor's algorithm.

2. Communications

3. Online services, e.g. BitCoin.

How would we counter this (not sure how better to phrase this) -

1. Lattice-based

2. Multivariate

3. Hash-based signatures

4. Code-based cryptography

Is there anything else you'd recommend me including (as well as the above), or anything in the above you don't think I should include?

Honestly, the list above is a rough, first draft the main bulk of it... so don't it as gospel.

Best regards,

Cameron.

• Search "Post quantum cryptography" for useful material. Also, IMHO, "Will Quantum Computing catch up with Classic, and when?" is a most interesting subject. – fgrieu Sep 2 '12 at 14:00
• That's certainly a very interesting subject matter. What would that involve do you think? Mainly covering the history, and where I think the advancements will end up or something else entirely? In addition, do you not think the first one regarding quantum computing is more focused? – Cameron Allan Sep 2 '12 at 14:09
• if I knew how to meaningfully explore "Will Quantum Computing catch up with Classic, and when?", I would be doing that! Indeed, that seems even harder and less focused than what you are tackling; but more down-to-earth, too. – fgrieu Sep 3 '12 at 7:03
• One of the closest thing to a QC seems to be this – fgrieu Sep 3 '12 at 12:50
• This survey paper is quite a good read on this topic. – jayann Dec 30 '14 at 9:46

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem (such as "find the AES key that gives a reasonable message") scales slower than for a classical computer; this would effectively turn an n-bit key into an n/2-bit key. Fortunately, that would leave AES-256 with an effectively 128-bit key against a quantum attacker, which is still believed unfeasible to crack. Similar considerations apply to hashes. You'd want to increase key lengths and the like, but you could fairly reasonably do that.

The main issue is actually asymmetric cryptography. Unlike symmetric crypto and hashes, asymmetric algorithms have extreme levels of mathematical structure -- they're based on the difficulty of a single hard problem. The two main problems used for this can be solved extremely quickly on a quantum computer; if you tried to increase key lengths to make it take a long time there, it'd take an infeasibly long amount of time for the legitimate user on a classical computer to use the long keys. However, this is something of a historical accident: there's no reason asymmetric crypto has to be easily breakable by a quantum computer, it's just that the most commonly used ones happen to be easily breakable by one. Others may not be; post-quantum cryptography is an active research area, and people are working on algorithms that rely on problems not believed to be efficiently solvable by quantum computers.

• You claim that asymmetric cryptography is especially prone to attacks; doesn't this mean that symmetric key negotiation/exchange will be prone since it uses asymmetric cryptography? It still seems that if you're not using a PSK, you're at risk for attacks. – Clay Freeman Dec 30 '14 at 8:58
• @ClayFreeman Correct. The primary usage of asymmetric crypto is in fact to encrypt a key for symmetric crypto; however, people are working on asymmetric algorithms to resist quantum computers, and other common applications of crypto (e.g. disk encryption) do use a PSK. – cpast Dec 30 '14 at 9:01
• @ClayFreeman The problem is not really that asymmetric encryption is inherently weak against quantum computers. However, the asymmetric schemes that are the most popular and widely used are weak to quantum attacks (e.g., RSA). There are a number of known asymmetric encryption schemes that are believed to not be weak against quantum computers. In particular lattice based encryption schemes based on the LWE problem are getting a lot of attention in the theoretical cryptography world. – Guut Boy Dec 30 '14 at 12:24
• I have heard it said that quantum computers would themselves be capable of a much more secure form of encryption, one that actually enjoys theoretically-proven immunity to cracking rather than relying on the assumption that P does not equal NP (which, I believe, is relevant to the hard math problem you reference in the second paragraph?). I've also heard it said that this form of encryption would be impossible to clandestinely tamper with, as every attempt to read or modify it would leave a trace? I unfortunately do not remember the source of these claims... – KRyan Mar 6 '17 at 20:49
• Isn't that a direct consequence from the BB84 2-round key exchange? Unless I'm missing something, a 2-round key exchange protocol implies the existence of an INDCPA-secure encryption scheme, and the security of BB84 is information-theoretic. – Geoffroy Couteau May 11 '17 at 7:33

Grover's Algorithm would allow searching an unsorted database with N entries in $O(\sqrt{N})$ time rather than in the usual $O(N)$ time.

For AES-256 it currently takes an average of $n/2$ guesses to break, i.e. $2^{255}$. However with quantum computing this can be done in $2^{128}$ time, which is very much faster. And on top of that that's only brute force for AES-256, with the cleverer attacks it can be broken faster still.

$2^{128}$ is still sufficiently slow by a long way. However, AES-256 has a much larger keyspace then standards like DES(fastest classical attack: $2^{39}–2^{43}$, already pretty bad), 3DES or even the smaller keyspace AES-128. These would be broken or become much nearer to broken because of QC.

So we'd probably find a move towards larger key-space standards like AES-256. Which is just what happens anyway with Moore's law (better computers) forcing us off DES already, so maybe QC isn't that groundbreaking. What you need to do is what we always do, which is to find the right balance between performance of our systems and the time to takes to break it, it's just that the balance will shift.

Factoring and RSA is some of the problems that we know a quantum computer should be able to solve efficiently. I.e., yes, RSA would potentially be broken.

However, a quantum computer does not necessarily make all modern cryptography obsolete. For symmetric primitives, such as AES, it is not even known that a quantum computer would make a big difference. So the main challenge is with public-key cryptography. In this area, we do already know of a handful of candidates for post-quantum cryptography which are not based on problems that can be solved efficiently on a quantum computer.

For example lattice based cryptography is one of those candidates that shows a lot of promise. Lattice based crypto is based on lattice problems that are fundamentally different from problems such as factoring, and therefore is not known to be efficiently solvable on a quantum computer. Last I checked the main problem with such systems is that the underlying hardness assumptions are not as well tested as, e.g., RSA so it is hard tell exactly for which parameters the systems can be considered secure.

If you are interested in post-quantum cryptography you might enjoy the book Post Quantum Cryptography which deals with a number of different candidates, such as lattice-, hash- and code- based. The book is from 2009, so it might be a little dated, but I think the material should still be relevant.

in summary :

• for "symmetric" ciphers a 256bit key is fine for QC. attention AES-256 doesn't mean AES with 256 bit blocks ! its about key. AES-256 block size is less secure than AES-128 bit blocks (refer to wikipedia)

• for "asymmetric" ciphers its not ready yet , all current ciphers have their problems (some have security problems, some have implementation problems) and we need some time and attention to fix

• AES with 256 bit blocks does not exist. AES is the standardized form of Rijndael with 128 bit block size. – Maarten Bodewes Jan 3 '13 at 20:53
• Actually, I'm not sure 128 bit blocks would be sufficient if QC's became a reality, I'm not sure if generic distinguishers are affected by Grover's algorithm but it could be something to keep in mind. That said, increasing block and key size is an easy process, coming up with a secure asymmetric algorithm is not. – Thomas Jan 4 '13 at 5:35
• @Thomas QC is reality but what do you mean 128 bit blocks not secure for QC ? i thought Grover is to find key 2x faster , the protocol effected too ?? – mary Jan 4 '13 at 8:35
• @mary They are hardly a practical reality, we don't know if it's physically possible to build a sufficiently large quantum computer. But in any case, a small block size allows you to distinguish the output of a block cipher from a random stream, which is a weakness - I suspect Grover's algorithm would also speed up this type of attack, requiring you to increase the block size accordingly as well. – Thomas Jan 4 '13 at 8:50
• AES is a variant of Rijndael which has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits. Guess someone got confused by the naming. AES-256 means the key is 256 bits long, not the block... which still is made of 128 bits in that case. – e-sushi Jul 30 '13 at 8:39