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

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.

-

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 problem some have implantation problem ) 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. –  owlstead 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