What is Quantum Computing?

In Part I of our blog series on the implication of quantum on cryptography, I described what a quantum bit was, and what operations could be performed on such data. Since their inception a lot of work has been carried out in determining algorithms for quantum computers. The most important, and the ones most relevant to cryptography, are Grover’s Search Algorithm and Shor’s Factoring Algorithm.

First, let’s discuss Grover’s Search algorithm. A classical problem in computing is given a list X of N items to search the list for an item which has a property, which we will call P. Mathematically we are looking for an x in X such that P(x)=1, say. Now if X is an unstructured set then classically the best we can do is take every element in X and test whether P(x)=1. If we suspect only one such x exists then this will take N steps. Cryptographically think of X being the set of keys for AES and P(x) being the function which tests whether the key maps one plaintext to a given ciphertext. Classically we try to define ciphers such that he work effort of finding an x such that this P(x)=1 is given exactly by N.

Quantumly, however we can do a lot better. Grovers’ Search Algorithm can solve the above problem in sqrt(N) steps. This means that quantumly the AES cipher with 128 bit keys only provides 64 bits of security as opposed to 128 bits of security. For block ciphers this means that if we are wishing to protect against quantum attacks we need to double the key sizes.

Another application of Grovers’ Search is to find collisions in hash functions. A collision in a hash function H is a pair of values x and y such that H(x)=H(y), (for more details, read this post on hash functions). A hash function is designed to make finding collisions hard. This is needed in digital signature schemes which hash a message before signing. Since if you can find a collision (x,y), then you can pass off a signature on the message x as a signature on the message y.

Classically, if the output of the hash function is an element from a set X of size N, and the output is essentially random, then the best algorithm to find a collision will take sqrt(N) steps. However, Grovers’ Search algorithm can be adapted to this situation where it allows us to quantumly find a collision in N^{1/3} steps. Thus if our hash functions are to be quantum secure we need to use hash functions with bigger output length.

The most interesting Quantum algorithm is, however, Shor’s Factoring Algorithm. What this algorithm actually does is find the length of a cycle in a finite abelian group. Shor’s Algorithm can solve this problem in polynomial time, something which we do not know how to do on a classical computer. All sorts of interesting cryptographic problems can be reduced to finding a cycle length in a finite abelian group. The most important being factoring numbers and finding discrete logarithms. The problem is that factoring and discrete logarithms form the basis of all public key cryptographic systems in use today. Thus, the development of a quantum computer would render all deployed public key algorithms instantly insecure.

So in summary, if a quantum computer was ever built we would have to increase the key lengths of our symmetric ciphers such as AES (say to use AES-256 as opposed to AES-128), and we would need to find new public key algorithms.

Prof. Nigel Smart

Prof. Nigel Smart

Nigel Smart, Unbound Co-Founder, is a Professor at KU Leuven, Belgium. He is a world-renowned expert in applied cryptography, and was the Vice President of the International Association of Cryptologic Research. In the past, Nigel worked at Hewlett-Packard Laboratories developing advanced encryption technologies. He has also been involved in developing many standards, and has worked with both industry and government on applying cryptography to solve critical security problems.

Subscribe to BLOG