I realise this isn\'t a \'yes or no\' question, and I apologise for asking somet
ID: 650327 • Letter: I
Question
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 -
National security, classical cryptographic methods (RSA, DSA, AES-256). Including Shor's algorithm.
Communications
Online services, e.g. BitCoin.
How would we counter this (not sure how better to phrase this) -
Lattice-based
Multivariate
Hash-based signatures
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?
Explanation / Answer
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.