Workshop on cryptography in the quantum age

Abstract: Side-channel attacks as well as recently discovered flaws in the design of modern CPU's (Meltdown/Spectre) pose a real threat to our ability to run secure/private computation without information leakage. In this talk I shall survey some results on classical leakage-resilient cryptography; the connection to fault-tolerant quantum computation; and point out a unique advantage of quantum communication and quantum computation in their ability to detect information leakage.

Abstract: It would be highly desirable to have detectors that would accurately give the exact photon number in a pulse of light. For high photon numbers this will probably have to remain a dream, but for photon numbers between, say, 0-10, there are already claims of such resolution in fabricated detectors. Such a detector resolution would enable accurate characterization of photon sources used in QKD, and the existence of such detectors would enable new QKD protocols incorporating the photon number as a degree of freedom. However, making a detector that has the ability to predict the incident photon number from the measured signal is non-trivial and requires a high system quantum efficiency and a low dark count. In the talk we delineate the requirements and discuss figures of merit for photon number resolving detectors.

(joint with Divesh Aggarwal, Troy Lee, Miklos Santha, and Marco Tomamichel)
Abstract: The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. We investigate the risk posed to Bitcoin and other cryptocurrencies in particular. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer within 10 years, by the most optimistic estimates. As countermeasures, we analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also briefly review the available post-quantum signature schemes which could best meet the security and efficiency requirements of blockchain applications.

Abstract: In this talk, I will present the newly established Wallenberg center for quantum technology (WACQT). This is a 10 year effort that aims at building a 100 qubit quantum processor using superconducting circuits. The structure and goals of this center will be presented. On the more scientific side, I will present our efforts to improve the quality of superconducting qubits, and our plans for how to scale up to many qubits. If time allows, I will also present a few experiments where qubits are placed in unusual environments. In particular I will show how a qubit can be coupled to sound in terms of surface acoustic waves, and what happens if you place an artificial atom in the form of a superconducting qubit in front of a mirror.

Abstract: Modern public-key cryptography is mostly based on the hardness of Factoring and computing discrete logarithms. However, due to Shor’s algorithm, large scale Quantum computer if and when they become available would put these systems at risk, with the danger of compromising the security of all computer applications. In this talk, we present one of the numerous candidates systems to address this threat. It is mainly based on the hardness of recognizing integral numbers of the form f*(g^(-1)) mod P where P is a large Mersenne prime and f, g two integers with low Hamming weight in their binary decomposition.

Abstract: A quantum race is a competition between two or more quantum computers to solve a computational problem. Compared to races between classical computers, a major novelty in the quantum setting is that players do not know if they have solved the problem until they measure their quantum state. This question of "when to measure" presents an interesting strategic problem. We develop a game-theoretic model of a quantum race, and find an approximate Nash-equilibrium where all players play the same strategy. In the two-party case, we further show this strategy is nearly optimal in terms of payoff amongst all Nash equilibria where all players play the same strategy. We discuss the application of our results to the mining of Bitcoin by quantum computers, as Bitcoin mining can be viewed as a race to solve a computational search problem. This is joint work with Maharshi Ray and Miklos Santha.

Abstract: Entanglement distribution will be an important capability for future quantum networks linking sensors and computing nodes. Entanglement can also be a fundamental source of entropy for cryptography. I will discuss on-going efforts in Singapore to building entanglement distribution networks over metropolitan fiber systems, but also how to link these different systems together using constellations of small satellites.

This talk is part of the STIAS Public Lecture Series, find more information here.

Abstract: Grover's algorithm provides quantum computers a quadratic advantage over classical computers for searching in an arbitrary data-set. Bitcoin mining falls into this category of a search problem. It has been previously argued that the only side-effect of quantum mining would be an increased difficulty, due to this quadratic speed-up which can be applied to Bitcoin mining. In this work we argue that a crucial argument in the analysis of Bitcoin's security breaks down when quantum mining is performed. Classically, a Bitcoin fork occurs rarely, when two miners find a block almost at the same time: only if both miners are unaware of the other's block, due to propagation time effects. The situation differs dramatically when quantum miners use Grover's algorithm. Grover's algorithm repeatedly applies a procedure called a Grover iteration. More iterations provide a quadratically higher chance of finding a block. Crucially, a miner does not have to choose how many iterations to apply in advance. Suppose Alice receives Bob's new block. To maximize her revenue, she should stop applying Grover iterations and measure her state. Her hope is that her block (rather than Bob's) would become part of the longest chain. This strong correlation between the miners' actions, and the fact that they all measure their state at the same time, may lead to more forks. This is known as a security risk for Bitcoin. We propose a mechanism which, we conjecture, prohibits this form of quantum mining, and circumvents the high rate of forks.
More details: arXiv:1804.08118

Abstract: The notion of obfuscation is a powerful idea in cryptography, but the most ideal variant -- Virtual Black Box obfuscation -- is impossible to achieve classically. Even though some other impossibility results in the quantum case have been found, whether it's possible to use quantum information to obfuscate (classical) circuits is still open.
Fully homomorphic encryption is a key tool in many proposed constructions involving obfuscation in the classical world. For instance, it can boost obfuscation of log-depth circuits to polynomial-size ones. Having in mind recent progress in quantum homomorphic encryption (QHE), it's natural to ask in what way QHE might help us in the quest to obfuscate \emph{quantum} circuits.
In this talk, I will give an overview of a research line in progress: we try to find out whether QHE can boost the power of obfuscated classical circuits to the obfuscation of quantum circuits. I will sketch the progress we have made, and the technical obstacles that still remain to fully solve this question.

Abstract: Loophole free Bell test is a long term goal for the research of quantum foundation. Moreover, it can find immediate applications in device independent quantum information processing. Here, I shall give a review on our recent work on Bell test based on the random number generated from cosmic photon and device independent quantum random number generation.

Abstract: Quantum machine learning is at the crossroads of two of the most exciting current areas of research - quantum computing and classical machine learning - fields which throughout the last decade have benefitted from borrowing concepts, ideas and tools from each other. In this talk, we survey a selection of results on the subtopic of quantum neural networks, an area that hopes to build on the enormous impact that classical neural networks have had in recent years. The area is still in its infancy, with many fundamental questions yet to be answered. We hope this talk may inspire further development in the area, and help to build connections to other areas such as cryptography.