Guest column: The impact of quantum computers on cryptography

There are two broad flavours of encryption technology: symmetric key cryptography and asymmetric key cryptography. Symmetric key cryptography is the older and more familiar flavour. In this case, both parties who wish to communicate secretly with one another must first share a common secret key. Then they will each use the key to encrypt information for the other party and use the same key to decrypt the information they receive. Although very secure and fast symmetric algorithms have been developed, the main difficulty in the security of any symmetric scheme is the sharing of the secret key without it being discovered. This is particularly important in a situation where you want to share the key across a public medium like the internet.

Asymmetric cryptography, which was first developed during the 1970s, uses separate keys for encryption and decryption. One key is kept secret and the other key can be made public. For this reason it is also known as public key cryptography. Because the public key can be distributed freely without a need for secrecy, this simplifies the key distribution problem, and also allows for some interesting applications. If I share the encryption key but keep my decryption key private, then anyone can send me a secret message, but only I can read it. It's like having a secure post office box that only I have the key to. On the other hand I could share the decryption key and keep the encryption secret. In this case I can encrypt a message and everyone can decrypt it. This may seem strange to start with, but the point is that because the message decrypts with my public key it proves that it was encrypted with my private key which is only known to me. This acts as a digital signature.

In practice, public keys are not shared in the raw, but instead they are embedded in special objects called digital certificates. A digital certificate binds a public key to its owner which is digitally signed by a trusted third party called a certificate authority (CA). If you receive a certificate and you trust the CA and the policies they use for issuing certificates, then you can extract the public key from the certificate and use it to send encrypted messages to the owner. Certificates solve the problem of knowing who the public key really belongs to. Instead of having to trust everyone who may present you with a public key, you can instead trust a small number of CAs.

Asymmetric cryptography is much more mathematically complex and thus slower than symmetric cryptography. In fact asymmetric cryptography is only really practical for encrypting small pieces of information so in practice it is used as part of a hybrid system that uses both symmetric and symmetric cryptography working together. Earlier we discussed that one of the drawbacks of a symmetric scheme is how to share the secret key over a possibly insecure link. The solution we use is to encrypt the symmetric key using an asymmetric key. One of the most important examples of this is the SSL protocol used to encrypt browser sessions.

Whenever you connect to a secure site protected by SSL (sites which start with https:// instead of http://) such as your internet banking site, your computer actually performs a cryptographic protocol with the server using digital certificates which allows the entire session to be encrypted. The bank's server sends your browser a copy of its digital certificate. Your browser looks at the certificate and decides whether it trusts the certificate (which depends on whether it has been issued by a known CA).

If the CA is trusted, then the bank's public key is extracted from the certificate. The browser then generates a random secret key and encrypts it using the bank's public key. This encrypted key can then be sent back to the server over the internet without danger of being read in transit. The bank server decrypts the encrypted key from the browser using its private key and uses the secret key that the browser has shared with it to initiate an encrypted session using fast symmetric cryptography.

This all sounds very complicated, but the enormous success of SSL has been due to the fact that it all occurs entirely in the background without any need for interaction with the user. Next time you open an SSL session in your browser, try double clicking on the padlock symbol (in the lower right hand corner of your browser screen for IE). This will give you details about the digital certificate that was used to create the encrypted session.

We all use cryptography every day, and most of us do so without knowing it. If we rely on it so much, is there any danger that the security of current cryptosystems could be compromised? Certainly the consequences could be dire if all electronic commerce were suddenly rendered insecure. Although still many years away, it turns out that there is such a threat. Current cryptographic techniques are all based around advanced mathematics, but the cryptography of the future is likely to pass to the realm of the physicists.

Physicists have come up with the theoretical notion of a quantum computer which could break virtually all known cryptographic algorithms. The properties of quantum physics that allow particles to be in two states simultaneously can be harnessed to solve problems in parallel with the same speed that could be done if they were tackled sequentially. It turns out that most of the mathematical problems that are at the heart of our current cryptographic systems are perfectly suited to being tackled by quantum computers. The power of quantum computers would lead to a new age of computing in which previously intractable problems could be solved in an instant and will have a revolutionary effect on all our lives.

Although quantum computers are still very much in their infancy, theorists have already developed algorithms that could be run on a quantum computer if one were to exist. Perhaps by coincidence the first algorithms to be developed are exactly what is required to break current cryptosystems. The first, Shor's algorithm, can be adapted to crack virtually all existing public key cryptographic algorithms that are considered to be secure today. Shor's algorithm would allow a quantum computer to solve factoring problems (used by the RSA algorithm), the discrete logarithm problem (used by the El Gamal algorithm) and even certain versions of the elliptic curve discrete logarithm problem (used in elliptic curve cryptography). A second algorithm known as Grover's algorithm provides a way for a quantum computer to search an unsorted list, a method which could be used to crack symmetric ciphers.

In a world of quantum computers then, we would need to abandon most of the algorithms that are in use today. Instead we would have to start using other public key encryption algorithms which are not vulnerable to quantum methods. For example there are some lesser known public key algorithms that are believed to be immune to Shor's algorithm (for example the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system).

Help is also at hand from quantum physics itself. This technology actually uses the properties of quantum physics to make it secure even from quantum computers. In fact quantum encryption techniques are far more advanced than quantum computers and commercial systems already exist for quantum key exchange and are in use today. It is certainly reasonable to assume that quantum encryption will be practical long before quantum computers become a reality.

Much effort is being expended into building a working Quantum computer, but it is likely to be many years before it becomes a reality. Although the advent of quantum computers would be the nail in the coffin for many of the cryptographic algorithms in use today, there are other algorithms and technologies ready to take their place. I believe we can look forward to an age of quantum computers rather than needing to fear that they will make our computing insecure.

Robin Balean is solutions architect for VeriSign Australia.