Tuesday, 20 February 2018

Quantum security from an uncertainty game

The uncertainty principle of quantum theory limits how much Eve can predict about the outcomes of two incompatible measurements on Adam's state.

We will consider a guessing game that shows security against an eavesdropper Eve who can prepare quantum states but otherwise store and process classical information only. For example, Eve is allowed to make measurements on a qubit during its transmission but she does not possess any quantum memory for storing quantum states that she might entangle with the qubit.

In such a setting, Eve's actions effectively chooses the state of the qubit sent to Adam, since she would know as much as she can about the qubit if she had prepared it herself. This situation can be analyzed in terms of the following guessing game, to be played by Adam and Eve:

1. Eve prepares a qubit $| \psi \rangle$ and sends it to Adam.
2. Adam chooses a uniformly random bit $\theta$. If $\theta = 0$, Adam measures $| \psi \rangle$ in the standard basis $\{ |0\rangle, |1\rangle \}$. If $\theta = 1$, Adam measures $| \psi \rangle$ in the Hadamard basis $\{ |+\rangle, |-\rangle \}$, where $|\pm\rangle = (|0\rangle \pm |1\rangle )/ \sqrt{2}$.
3. Adam records a bit value $x$ as his measurement outcome. (By convention, $|+\rangle$ corresponds to bit value 0.)
4. Adam reveals the measurement basis $\theta$ to Eve.

Eve wins the game if she correctly guesses the value of $x$.

Saturday, 10 February 2018

Delegated quantum computation

Suppose Alice wants to perform a quantum computation. She can implement some basic quantum gates on the state $|0\rangle$ but she does not own a fully-functional quantum computer. Bob runs a company that sells time on their quantum computer and thus offers his services to Alice. But Alice does not trust Bob. In particular, she does not want Bob to learn her quantum state at any point during the calculation. Is there a way for Bob to help Alice securely? Yes, this is a problem that can be solved by delegated computation.

In the task of delegated computation, Alice has an input $|q\rangle$ and a classical description $\mathsf{C}$ of the quantum circuit and she wants to obtain the output $\mathsf{C}(|q\rangle)$. Alice and Bob exchange a few messages, at the end of which Bob obtains a result $|r\rangle$, which he sends to Alice. Ideally, we want the protocol to be correct, verifiable, and blind.

The protocol is said to be correct if Alice accepts Bob's result and $|r\rangle = \mathsf{C}(|q\rangle)$ when both parties are honest. The protocol is said to be verifiable if for any cheating Bob, Alice either aborts or  finds $|r\rangle = \mathsf{C}(|q\rangle)$. The protocol is said to blind if for any cheating Bob, at the end of the protocol, Bob learns nothing about $|q\rangle$ or $\mathsf{C}$.

Thursday, 1 February 2018

A simple protocol for quantum oblivious transfer

One of the goals in cryptography is to allow parties who do not trust each other to solve problems together. One important problem that can be solved using such a secure multiparty computation is called secure function evaluation (SFE).

In SFE, we have two parties Alice and Bob who each hold some private data. Alice wants to use Bob's data to compute some function on her side, while Bob wants to use Alice's data to compute some function his side. The goal is to allow Alice and Bob to compute their functions without having to reveal their secrets.

We can describe a SEF protocol as follows: Denote Alice's secret input by $x$ and Bob's secret input by $y$. Alice and Bob can send messages to each other. At the end of the protocol, Alice outputs $a$ and Bob outputs $b$. Alice wants to compute the function $A(x,y)$ while Bob wants to compute $B(x,y)$.

If the protocol is correct, then $a = A(x,y)$ and $b = B(x,y)$ for honest Alice and Bob. If the protocol is secure, then Alice cannot know anything about Bob's input $y$ except what she might deduce from $A(x,y)$. Similarly, Bob cannot know anything about Alice's input $x$ except what he might deduce from $B(x,y)$.

Let us consider an example of SFE called oblivious transfer (OT). In an OT protocol, Alice has two input bit strings $s_0$ and $s_1$, and Bob has input bit $t$. Alice does not need to compute anything but Bob wants to retrieve $s_t$. An OT protocol is secure if Alice does not find $t$ and also if Bob only gets one of Alice's strings.

Suppose Alice has a database with two records $s_0$ and $s_1$. Bob wants to retrieve one of the records but he does not want Alice to find out which one. Meanwhile, Alice is willing to grant Bob access to one record, but not to the entire database. This is a practical problem that can be solved with OT.

Sunday, 31 December 2017

Grover's algorithm for the unstructured search problem

After Peter Shor showed how quantum computers can factor numbers efficiently, interest surged in finding other problems which quantum methods solved faster than the best known classical techniques. In 1996 Lov Grover developed such a quantum algorithm for solving the unstructured search problem.

In a generic search problem, we are given a set $S$ of $N$ items. Some of the items in the set are marked. Our task is to find a marked item in the set $S$.

You can think of a search problem like looking up a name in a list. In most cases, the list will be arranged in a way that makes finding names easier. For example, a list of names is often sorted alphabetically. Here we are talking about a list with no discernible ordering. In this case, the best we could do is to check each entry for the desired name.

Monday, 28 August 2017

Quantum speed-up in Simon's problem

It has been said that quantum computers will allow us to perform certain computations faster than the regular PCs of today. While this sounds like a remarkable technological advance, it is necessary to clarify what is meant by this:

1. A recipe for solving a computational problem is called an algorithm.  In order to compare the speed of classical and quantum algorithms, we need a way of counting computational steps for classical and quantum algorithms that is fair to compare.

2. How many steps an algorithm needs depends on whether it receives an easy or hard instance of the problem.  Typically we are interested in algorithms that work the best on average. Another issue is that for the algorithms that we do know, we don't usually know if they are the best that we can do (you can sometimes prove a classical algorithm is optimal by using lower-bound arguments). So here  we are really comparing quantum methods with best as-of-yet classical methods. Put differently, it maybe the case (though many believe it unlikely) that classical and quantum computers have the same computational power; we just have not found the best classical algorithms that match the performance of quantum ones.

Here I will describe a problem for which quantum computers have a distinct advantage over classical ones. It is an example of what is called a black-box problem in computer science.

Thursday, 22 September 2016

The BB84 protocol for quantum key distribution

The most successful application of quantum theory to cryptography is quantum key distribution (QKD). The goal of QKD is to generate an identical string of bits that is privately shared between two parties, which we shall call Alice and Bob.

The particular QKD scheme that we will describe was proposed by Charles Bennett and Gilles Brassard in 1984, and is often referred to as BB84.

The protocol has two main parts, a quantum and classical phase. In the quantum phase, Alice sends single photons to Bob over some public quantum channel. In the classical phase, Alice and Bob need to talk to each other over an authenticated classical channel, that is, it can be public but they need to verify that they are talking to the correct person.

Friday, 15 July 2016

The CHSH game and quantum entanglement

A simple setting for demonstrating the usefulness of entanglement involves a two-player game known as the CHSH game. The game is a variant of an experimental setup (by Clauser, Horne, Shimony and Holt) that is often used to illustrate Bell's theorem.

We shall call the two players 2 players Alice and Bob. We will also have Charlie as a referee that decides if Alice and Bob wins the game. They can decide on any strategy before the game commences but they cannot communicate with each other once the game starts.

To begin, Charlie picks two uniformly random bits $x$ and $y$, and gives $x$ to Alice and $y$ to Bob. Alice answers the referee with bit $a$, while Bob replies with bit $b$. After getting $a$ and $b$, Charlie checks whether

$a \oplus b = xy  \mod{2}$,

that is, that the XOR of the output bits $a$ and $b$ is equal to the AND of input bits $x$ and $y$. If so, then Alice and Bob win the game.