Quantum computing and the future of cryptography

[Duda Jarek]

Physics most probably allows for non-classical computation methods, which makes parallel computation of all possible inputs - like becoming more and more realistic quantum computers.

I think we should widely discuss if it's a real threat and if yes - how to design cryptosystems resistant to such eventualities.

Especially that we wouldn't know if someone would use it...

Here is one discussion of this type:

http://www.ecrypt.eu.org/stream/phorum/read.php?1,1021,page=1

I wanted to start here one. Please share Your opinions and links to interesting discussions on this topic.

 

There is know Shor's algorithm which breaks RSA. Generally cryptosystems have always a 'weakness' that make them prone to brute force attacks - that there is a key which properly decrypts the message. To make such attack we can use that there is practically only one key which makes that message decrypted with it has some significant correlation.

So using a quantum computer we could use entangled all possible keys to decrypt the message, check for correlations and somehow extract some information about the correct key.

This extraction is more difficult than it looks, but assuming that it's impossible could be dangerous.

 

Quantum computers are extremely difficult to make and they most probably will be limited to relatively small number of qbits and time they can sustain entanglement - so I think that we can protect against imaginable QC by enforcing large amount of required computation. To make such cryptosystem practical, this computations should be done only once - specifically for given key. The next advantage of such preintialized cryptosystem, like based on asymmetric numeral systems, is that now the processing of the data can be extremely fast.

 

Do You think it's a real threat?

How strong it is - can be used only for some algebraic attacks or even for brute force?

How to protect against such eventualities?

What about public key cryptography???

[bascule]

Brute force is already an untenable solution. One of my favorite quotes from Bruce Schneier in Applied Cryptography talked about how there are more potential 1024-bit pubkeys than there are atoms in the universe (someone correct me here if there are more than 10^1023 atoms in the universe). You're always going to need to reduce the size of your search space, and that's going to be a largely algorithm-specific procedure. Shor's algorithm isn't going to help you out cracking Elliptic Curve Cryptography.

 

Cryptography is an arms race. On the one hand the algorithms need to be fast enough to be used practically on modern hardware, but also secure enough that they can't be cracked by modern hardware. And thanks to Moore's Law, the speed of modern hardware increases exponentially.

 

Unless we find a solution for the P=NP problem I think we will have no trouble continuing to design more advanced algorithms which operate on larger and larger keys.

[Duda Jarek]

I see that You believe that the only real algorithmic advantage of QC is the Shor's algorithm.

Probably You are right, but ... QC can theoretically make all calculations at once (is almost nondeterministic Turing machine) and the only problem is with the extraction. I'll show how to enhance it, but it would be strange if basic QC wouldn't already allow for more, maybe even solving NP in polynomial time. Observe that if someone would find a way, he could not necessary tell it loud, but for example try to became rich...

 

In such case 1024 bit key would be a piece of cake - elongating key may be not enough. Especially that I believe that we could easily protect private key cryptosystems against such eventualities by using preinitialized ones.

But designing public key cipher is much more difficult and I have no idea how to make a protected one???

 

The next argument that we should take such scenarios seriously is that maybe basic QC is not the only possibility for massive parallel computation physics gives us. First of all there is so called Feynman-Stueckelberg effect

http://groups.google.com/group/sci.physics.research/browse_thread/thread/9d10b4e5cbda1108

which hasn't been taken seriously, but maybe it will change in a few months in LHC ... but such computer would require (huge?) accelerator.

 

The other option can be (quantum) loop computers

http://forums.devshed.com/security-and-cryptography-17/new-computation-method-which-could-endanger-used-cryptosystems-580926.html

I'm strongly confused about this idea, especially for classical computers.

But ... if used for quantum computation, such feedback should amplify the correct solution (wavefunction), making the rest of them vanish.

It couldn't be standard approach to QC in which we use some sequence of for example external fields on some lattice of atoms.

 

We would need a circuit which allows to sustain entanglement of many calculations.

Observe that similarly to benzene, (-CH=CH-) sequence can be in quantum superposition with shifted one (=CH-CH=) - we could use such molecule as a wire for qbits. Unfortunately it has some resistance, but there are know such superconductors also.

We know also transistors made of single molecule - they are irreversible so would destroy entanglement, but there should be possible also quantum gates made this way.

The question is if such molecular quantum computers could sustain entanglement for practically long time ... There is also problem with auxiliary variables - we need a lot of them because in QC all calculations has to be reversible. They cannot be sent in the loop - they should be treated in some special way to not destroy the entanglement...

... but maybe ?

 

Probably physics doesn't allow to solve NP in polynomial time, but I'm far from being sure of it.

And I believe that preinitialized cryptosytems should be practically protected against all presented hypothetical possibilities. And this protection is achieved practically for free.

Edited February 18, 2009 by Duda Jarek

[bascule]

But designing public key cipher is much more difficult and I have no idea how to make a protected one???

 

There are already many, many designs. About 10 years ago I remember some teenage girl won a science fair for desiging a pubkey crypto system. Her algorithm was much slower and more memory intensive than RSA.

 

My argument is not that quantum techniques will not be applied to cracking cryptography. I expect in the future we'll have general purpose quantum computers which we can target using something similar to SIMD instructions to perform massively parallel computations.

 

The problem is that I sincerely doubt there will be a general purpose make-quantum-break-crypto computer.

 

How would you use quantum computers to attack elliptic curve cryptography, for example?

[Duda Jarek]

Ok - I was too pessimistic - we should be able to make protected and practical hybrid systems - public key cipher for very short message like a key for a secret-key cipher or a hash value for authorization.

 

Most generally, public key is a parameter of some transformation which is extremely difficult to reverse. But there is the private key - some kind of 'clues' which make this reverse easy.

So if someone could solve quickly NP problems:

- he could try all possible 'clues' and for example check if for some block encrypting and then decrypting gives the same block. If yes - he could try a few more different blocks to be sure it's the correct private key, but there is also more dangerous attack:

- searching not for these 'clues' but straightforward for the reverse function: having encrypted message in a form of independent blocks, for each block he could try to encode all possible input blocks with the public key to get the given block.

 

So to protect it in analogy to secret-key ciphers, we rather have to make that encoding already require extremely large amount of calculations. The problem is that this time these huge calculations cannot be just made while initialization like before, but has to be made for each block - it could be practically used only for extremely short messages, like the key for a private key cipher or a hash value.

[bascule]

Ok - I was too pessimistic - we should be able to make protected and practical hybrid systems - public key cipher for very short message like a key for a secret-key cipher or a hash value for authorization.

 

That's the primary way public key crypto is applied today (and for the past few decades), aside from using it for message signing.

 

Pubkey algorithms are generally much slower than private key streaming ciphers. So pubkey crypto is only used to exchange a shared private secret, namely the key to be used for the streaming cipher.

[bascule]

Something else to add to this which a friend and I were discussing tonight:

 

It's not like quantum computing is only going to assist people trying to break cryptographic algorithms. What happens when your encryption algorithm itself can make use of quantum computing?

 

I'm curious what computational physicists would come up with if they turned their attention to creating cryptographic ciphers employing quantum computation. Maybe someone around here has heard of such a thing?

[Duda Jarek]

Quantum cryptography was believed to be ultimately safe, but in fact if someone for example could connect himself in the middle of such optic cable and can intercept the classical communication, he could say A that he is B and use their protocol to receive the massage. Then he can say B that he is A and using the same protocol to send some own message.

So in fact safeness of quantum cryptography relies on safeness of classical cryptography - channels and authentication.

 

I believe You mean something different - use for coding a hypothetical computer which can quickly solve some NP problems - which in each step chooses behavior analyzing some exponential number of possibilities.

But if physics allows to quickly solve NP problems without restrictions, we could add to the set of these possibilities all possible keys (to find such that gives nontrivial correlations) - we still could break it.

If there are restrictions for time and memory need of verification - we can easily exceed any limit using preinitialized cipher like based on ANS.

 

About public key cryptography - You are right, but if there will be such computer (with restrictions), to make it safe we would have to ensure that every step of encoding requires large number of computations (much more than for RSA).

[bascule]

I believe You mean something different - use for coding a hypothetical computer which can quickly solve some NP problems - which in each step chooses behavior analyzing some exponential number of possibilities.

But if physics allows to quickly solve NP problems without restrictions, we could add to the set of these possibilities all possible keys (to find such that gives nontrivial correlations) - we still could break it.

 

The goal here would be for someone with knowledge of quantum computation to specifically design a cipher around some sort of quantum property which allows for extremely complex computations in a short amount of time, and also with the goal that quantum computation cannot be easily applied to cracking the cipher.

[Duda Jarek]

As I've argumented - if there is a possibility of quickly solving NP problems without restrictions - such cryptosystem could be still easily broken. If physics allow for that - the only safe will be based on one-time pad.

If not - there will be for example restriction for time and number of entangled qbits - in that case classical ciphers (preinitialized) can be already made safe.