CTO Articles

Home > News > CTO Articles

Published in IT World
E-Business in the Enterprise – July 20, 2004

Quantum computing: A two-edged sword for security

By Sean Mc Grath

Quantum mechanics is weird. Really, really weird. You think some reality TV shows are weird? I can assure you, you haven't seen anything until you have seen quantum mechanics strut its stuff.

Quantum mechanics is a field in which science and philosophy collide very violently. The force of the collision sends potent particles of wonder, bewilderment, awe and incredulity flying in all directions.

Computing is not immune to shrapnel wounds from these collisions. In particular, cryptography is a field of computing in which quantum mechanics looks set to make life a lot more difficult and a lot simpler at the same time. Weird, I know, but hey, that's quantum mechanics for you.

Keeping data from prying eyes is big business. Math boffins have devised fiendishly clever ways of making data intelligible during transmission. Many of these methods are based on the deceptively simple idea of trapdoor functions[1]. Simply put, a trapdoor function is a calculation that is easy to perform one way but very hard to reverse. One such function is multiplying two humongous prime numbers to yield a third humongous number. It turns out that determining what the original prime numbers were, given only the result of the multiplication, is really hard. There is no known systematic way to do it other than the brute force approach of trying all the combinations. Even with a brute force approach, the time involved (for suitably large numbers) is astronomical, regardless of the CPU power at your disposal.

Enter the quantum computer[2]. A quantum computer is weird. Really, really weird. In the quantum world, there is no such thing as a straight answer to a straight question. Instead, all possible answers appear to co-exist until you measure one of them. Don't strain too hard on that one, you might burst a blood vessel. Suffice it to say that with enough math and physics boffins, you can theoretically arrange things so that a quantum computer would look through all the possible answers to a trapdoor function in a reasonable amount of time[3].

If quantum computing comes to pass, then basically, much of the world's existing lore on cryptographic techniques will need to be revisited. Trapdoor functions may have a back door.

Weirdly, at the same time that quantum computing is shedding doubts on the safety of trapdoor based encryption it is simultaneously solving one of the biggest deployment problems with trapdoor based encryption. Encrypted messages are only as secure as the keys used to encode them. If the private keys are compromised, the whole system is compromised. This issue of key management and key distribution has been a stumbling block in the pragmatics of Public Key Cryptography for many years now.

When it comes to key distribution, the weirdness of quantum mechanics can be put to good use. When transmitting keys, we need to know for sure that nobody is snooping on the conversation. One of the mind-bending aspects of quantum mechanics is that the mere act of observing something - measuring it - potentially changes it. You might need to lie down for a moment and think about that one.

So, given this wonderful if bizarre fact, imagine a conversation consisting of particles of light (photons) slinging to and fro on a fiber optic cable. The data I send down the fiber to you will literally be different if someone else monitors it en route[4]. Given sufficient physics kit, we can use this to ensure that our key distribution is safe.

How ironic it would be, if quantum mechanics were to solve the key distribution problem, only to make that problem moot by smashing the viability of the the trapdoor functions that lead to it.

[1] http://www.worldhistory.com/wiki/T/Trapdoor-function.htm
[2] http://www.cs.caltech.edu/~westside/quantum-intro.html
[3] http://www.themilkyway.com/quantum/FinalReport/FactorisationOfNumbers.html
[4] http://www.nature.com/cgi-taf/DynaPage.taf?file=/nature/journal/v418/n6895/full/418270a_r.html