twitter facebook rss

Cryptography and quantum computing

Posted by on September 29, 2016.

Yes, I know I complained about it at the beginning, and I’ve dealt with it elsewhere, but I suppose I really have to address it. (There actually are a number of issues about cryptography and quantum computing that the popular media never touches on.)

A good deal of confusion exists about the possibility and capability of quantum computing, particularly in regard to the field of cryptography. There are those who say that quantum computers will destroy the possibility of strong encryption, and others who assert that quantum computing will make decryption by an outside party impossible. Proponents of both positions will state their cases firmly, and generally without ever coming to agreement.

While there are many possibilities for the use of quantum technologies in regard to cryptography, so far the field has concentrated on quantum communication channels. Through the use of single photons as data carriers a system may be devised so that secret keys may be derived despite communications being observable by all parties, or such that the two communicating parties can determine whether any eavesdropping is taking place, or both. That’s what I’ve described in detail in another article. The bottom line is, it’s an elegant theory, but practical realities have turned up all kinds of implementation details (it’s always the implementation, isn’t it?) that create all kinds of possibilities for attacks.

The concept of superposition is one of the reasons that quantum computing is so tied, in the mind of the security professional, to cryptography. The application is obvious: build a quantum computer with a thousand qubits, and you will be instantly able to decrypt an encrypted message with every possible thousand bit key, since all possible keys can be simultaneously represented in the machine.

This idea is not only generally attractive, it has, in fact, been formalized, in an algorithm by Peter W. Shor, as far back as 1994. (Actually, his algorithm requires a computer with two thousand cubits if you want to attack thousand bit keys. And it doesn’t attack the keys themselves, it helps you do prime factorization. So it only works against RSA encryption.)

And, of course, there are certain large governmental bodies with large research budgets that are very interested in any paper that mentions the possibility of using quantum computing for decryption purposes. Therefore, a great many research papers mention this possibility.

I should possibly also mention at this point: you remember those two thousand qubit quantum computers that we’d need? Well, the largest commercially available quantum processors only have a thousand qubits. And they won’t run the Shor algorithm, because they are just quantum processors, not full quantum computers. And the test-bed full quantum computers are still straining at the dozen qubit size. So we have a ways to go yet before we get universal crypto cracking quantum computers.

But, given the feeling that current encryption algorithms may be susceptible to attack by quantum methods, work on new algorithms tractable by neither classical nor quantum computing would be indicated as a useful field of study. Indeed, while the prime factorization of large numbers is seen as a threat to the RSA algorithm, it is by no means obvious that other currently used algorithms are equally at risk. The need for assessment of non-factoring algorithms, and the development of new algorithms, is manifest.

We are all aware of the importance of randomness in using and operating cryptographic systems. As no less than John von Neumann pointed out, you can’t generate random numbers with computer algorithms. The generation of random numbers is too important to be left to chance (as said Robert Coveyou). Quantum devices may be of benefit to cryptography in terms of generation of randomness. Most quantum machinery is delicate and subject to significant issues of noise. We can turn this to our advance by capturing and processing that noise. In addition, numerous quantum structures can be established with indeterminate outcomes, and can be used as automated “coin-flipping” devices. (Using these structures is not always easy: care should be taken to ensure that the devices are not somehow biased because of careless construction. Even this problem can be used to advantage: we may be able to use a biased, but random, keystream in certain situations where we may either be correcting for biased data, or attempting to disguise the nature of the traffic or the type of encryption. We can, of course, bias pseudorandom streams, but a biased but still random stream may be an advantage.)

Implementation problems have always been the greatest source of problems and weaknesses in cryptographic systems. Analysis of implementation vulnerabilities is not a straightforward task. The use of quantum computing to improve simulation of a system may be able to identify these types of flaws in operation.

Leave a Reply

Your email address will not be published. Required fields are marked *

Submitted in: Expert Views, Insights, News_encryption, Rob Slade, Security |