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.
The main reason OT is interesting is because it has been shown that we can solve any SFE problem just by using a secure OT protocol as many times as needed. Unfortunately, it is also known that you cannot perform classical OT protocols perfectly: you will need to assume that a cheating party has some computational or physical limitations. But as long as these assumptions are reasonable, it allows us to construct OT protocols that are good enough in practice.
Here we describe a simple quantum protocol for OT. Informally, the protocol works as follows: Alice will encrypt her two secret bit strings using a one-time pad, which encrypts a message by adding it to a random secret key. Alice will send qubits to Bob in order to generate the keys to be used for encryption, in such a way that Alice has two keys, but Bob only has one key. Alice sends the two encrypted messages to Bob and Bob will be able retrieve one of the secrets using his key.
Now we will define the steps in our protocol more precisely. For concreteness, we will take Alice's input strings $s_0$ and $s_1$ to be three-bit messages in our example, but generalizing to $n$ bits is straightforward.
 |
| In oblivious transfer, Alice has 2 input strings $s_0$ and $s_1$ and Bob has an input bit $t$, and Bob has to output $s_t$. For our example, we will consider 3-bit messages for $s_0$ and $s_1$ |
We will take our qubits to be in the form of photon polarization, which can be prepared in two different bases using polarization filters, namely the $+$ filter for vertical and horizontal polarizations, and the $\times$ filter for diagonal polarizations. We have previously seen these qubit states and measurements in the BB84 protocol for quantum key distribution.
 |
| Alice and Bob have to decide on how to assign bit values to qubits encoded in different bases. Here we consider a qubit in the form of the polarization of a photon, where a qubit basis corresponds to filters oriented along different angles. We will use the $+$ filter and the $\times$ filter, which correspond to the computational basis and the Hadamard basis, respectively. |
For Alice to generate two random keys, she need to choose a random $2n$-bit string $k$, and a random $2n$-bit string $\theta$ that has $n$ 0s and $n$ 1s. In this case, $k$ denotes the bit values and $\theta$ denotes the basis or filter.
 |
| Alice picks a random string for each filter. She also picks a random sequence of filters that determines the order in which the bits of the random strings are sent to Bob. In practice, Alice would pick two random bit strings, one for the bit values and the other for the bases, which needs equal numbers of 0s and 1s. |
What happens is that Alice prepares photon $i$ in the state $| k_i \rangle_{\theta_i}$, where $\theta_i = 0$ indicates a qubit for the $+$ filter (computational basis states $|0\rangle$ and $|1\rangle$), while $\theta_i = 1$ indicates a qubit for the $\times$ filter (Hadamard basis states $|0\rangle_1 = |+\rangle$ and $|1\rangle_1 = |-\rangle$, where $|\pm\rangle = ( |0\rangle \pm |1\rangle )/\sqrt{2}$).
 |
| The bit strings $k_0$ and $k_1$ and the sequence of filters help determine the photon polarization that Alice should send to Bob, and in what order. |
If we match the bits of $\theta$ with $k$, then Alice can denote by $k_0$ the bits in $k$ that align with 0s in $\theta$, and by $k_1$, the bits that align with the 1s in $\theta$.
We needed $k_0$ and $k_1$ to be of the same length as the input strings, which is why we needed $\theta$ to have the same number of 0s and 1s. In our example, the bits in $\theta$ corresponds to the sequence of $+$ and $\times$ filters that Alice used to prepare the photons that she will send to Bob.
 |
| Bob picks a filter $\theta$ and measure each qubit he gets from Alice using this filter. He records the outcomes of his measurements in the string $y$. |
Alice sends the qubits one by one to Bob. If $t = 0$. Bob measures each qubit with the $+$ filter and if $t = 1$ he measures each qubit with the $\times$ filter. He records the outcomes into the string $\tilde{k}$.
 |
| Waiting some time after Bob receives all the qubits sent by Alice, Alice will send the random sequence of filters described by the string $\theta$. Bob can then check which qubits were measured with the correct filter, which means Alice and Bob have the same bit value in those positions. |
Bob confirms that he has received and measured each qubit. After some time has passed, Alice sends the bit string $\theta$ so Bob can identify the positions in $\tilde{y}$ where $\theta_i = \tilde{\theta}$, that is, he finds the qubits where they used the same filter. Let $\tilde{k}_t$ denote the bit string obtained from those positions.
 |
| Alice can encode her inputs $s_0$ and $s_1$ with a one-time pad using her random keys $k_:0$ and $k_1$. Alice computes the strings $m_j = k_j \oplus s_j$ for $j=0,1$ and sends $m_0$ and $m_1$ to Bob. |
Alice computes $m_0 = k_0 \oplus s_0$ and $m_1 = k_1 \oplus s_1$ ($\oplus$ is the bitwise XOR operation) and sends $m_0$ and $m_1$ to Bob. Finally, Bob can compute his desired string using $s_t = m_t \oplus \tilde{k}_t$.
 |
| Bob can compute the desired input string $s_t$ by using his key string to decrypt $m_t$. He has only one key so he can only open one of the two encrypted messages. |
It is easy to check that the protocol works for honest Alice and Bob. To see that it is secure, first let us consider a cheating Alice, who wants to find $t$. Observe that $t$ is not communicated in the protocol; in fact, Bob does not send messages to Alice. So there is no way for Alice to learn $t$.
How about a cheating Bob? If you think about it for a little while, you might find out that the protocol is not secure if Bob has a means for storing qubits reliably. Such a quantum memory allows him to postpone measuring his qubits until after Alice reveals the string $\theta$. Bob can then measure each photon in his quantum memory using the correct filter, allowing him to recover both $k_0$ and $k_1$.
So unfortunately, it turns out that you cannot perform OT perfectly: you will need to impose some limitations on at least one of the cheating parties. Here we can use a physical assumption for limiting Bob.
Since much of the present-day technology for quantum memory is still quite new and untested, it is reasonable to assume that there is a limit to how many qubits Bob can reliably store in his quantum computer. By making sure there is a sufficient delay between Alice sending the qubits and revealing the bases $\theta$, Bob will be forced to measure some of the qubits that he cannot store in memory.
To quantify security, we need to know how much Bob can learn about $k_0$ and $k_1$ given his limited capacity for storing qubits. This involves a computation involving Bob's min-entropy of the bit strings $k_0$ and $k_1$, which goes beyond our scope here.
Still it follows from such an analysis that we can be secure against cheating Bob if $q \le m - \log^2 m$, where $q$ is the number of qubits Bob can store in his quantum memory, and $m$ is total number of qubits Alice sends to Bob in our OT protocol. Since $\log^2 n$ grows more slowly than $n$, we see that security is possible just by sending several more qubits than Bob can store.
Reference:
Charles Bennett, Gilles Brassard, and Claude Crépeau, Practical Quantum Oblivious Transfer, in CRYPTO '91 LNCS vol. 576 (1992) 351-366.
No comments:
Post a Comment