Friday, October 3, 2014

Everybody loves quantum

Today is the last day of the PQC conference in Waterloo, Canada. In combination with the ETSI workshop on standardising post-quantum cryptography next week, the conference and summer school have attracted a varied crowd of cryptography researchers, physicists, government employees and people who care about standards. There were four invited talks this week and in this blog post I will try to summarise two of them. The first one is about quantum computing and the second one is about quantum cryptography. I chose these two because you do not hear too much about them in regular crypto conferences.

The first invited talk was on building a quantum computer by Matteo Mariantoni. He started off by listing the applications for quantum computers, which include quantum simulation of physical and chemical processes, applications to security such as cryptanalysis and quantum crypto, but also a more recent concept aimed at machine learning and artificial intelligence called quantum data processing. His opinion was that we should compare building a quantum computer to things like the Manhattan project, the space race and the current Mars exploration projects. In this comparison, he claims a quantum computer would be easier, cheaper and more useful and he cited how the requirements on technology used in space generated improvements that aid technology for personal use as well.

There are several important steps on the way to an actual quantum computer. Currently, researchers can construct physical qubits, but these are too noisy to carry out any meaningful quantum computation. The solution is to embed the physical qubits into a two-dimensional grid such that they can interact with their nearest neighbours, and to apply error-correcting techniques which eliminate the noise. This forms a single logical qubit. Now, there are some requirements on the physical qubits and gates like fidelity and readout times that need to be met before the logical qubit will actually work. At Waterloo they spent two years optimising their set-up, which is based on superconducting qubits, in order to reach the threshold that allows to create a logical qubit. As an example of why this sort of thing takes two years, he mentioned the task of individually ensuring that none of the screws in the chips with the superconductors are magnetic, which took two months.

Future steps in building a quantum computer consist of performing operations on the single logical qubit, performing operations on multiple logical qubits and eventually combining everything into a quantum computer. His final slide consisted of an estimate of what would be needed to factor a 2000-bit number in 24 hours. It would require 500 million physical qubits, a dedicated nuclear power plant, at least five years of research time and ten years of development time and about 1 billion dollars. The 24 hours is not really a variable in this case, as this comes from the physical implementation of the gates.


The second invited talk was about quantum cryptography, by Nicolas Gisin. He talked about two applications of quantum mechanics in constructive cryptography, Quantum Random Number Generators and Quantum Key Distribution. He briefly described a QRNG based on beam splitters, which is conceptually simple but fundamentally random (if quantum mechanics work). Current implementations provide about 4 Megabits per second of balanced random bits and solutions have been deployed in practice. An interesting observation he made is that there is also research into different approaches for QRNG's, one of which is based on the use of photosensors that are also inside most modern smart phones.

However, the biggest part of the talk was about QKD. QKD is based on the fact that quantum mechanics provides non-local distributed randomness and that it is impossible to clone quantum states, which leads to information-theoretic security. I will not describe the protocol here, but the idea is that Alice and Bob exchange information through quantum states (e.g. encoded in photons), and any information learned by Eve causes a perturbation on these states which can be detected by Alice and Bob. There are even methods that when given a certain amount of tampering by Eve allow Alice and Bob to compress their randomness such that Eve has no information on the result. One issue is that Alice and Bob require to do some communication on a classical channel, which requires authentication to prevent MitM attacks. This leaves two options: use an information-theoretic solution, which requires a pre-shared key or use a computationally secure solution. The first results in a "key-growing" scheme, where a pre-shared key turns into a longer key, which can then be used for future interactions, whereas the second results in a scheme that is secure as long as the authentication is secure at the time of execution. The reason is that the attack has to be active, which means it cannot be launched at a later point in time. Essentially, QKD is immune to any future progress in cryptanalysis of the authentication scheme. Of course, in reality the implementation matters and there have been attacks on existing implementations, similar to side-channel attacks on classical cryptography.

In the remainder of the talk, Nicolas described the state of the art in current implementations as well as the open challenges. A solution using fiber optic cables is limited in distance due to noise caused by spurious refractions inside the cable, whereas solutions through the air are hampered by that pesky atmosphere that allows us to breathe. The maximum range of these solutions appears to vary between about 100-400km. The obvious question then becomes how to extend this. One possibility would be to use a satellite, because the atmosphere does not stretch as far upwards. Alice sends her quantum states to the satellite, the satellite moves through orbit and sends the quantum states to Bob upon reaching him. This solution is also being explored at the University of Waterloo. Another option is to use trusted intermediary nodes where the information is converted to classical and back to quantum before it is sent on. Several countries such as the US and China are already planning such networks. The final option Nicolas mentioned is by using intermediary nodes (no longer trusted) to entangle states over longer distances. However, this solution requires some extra research into storing these entangled states until their counterparts arrive, which is currently not yet possible.

No comments:

Post a Comment