Secure Multiparty Delegated Classical Computation

It provides a method for computing nonlinear multivariable functions using only linear classical computing and limited manipulation of quantum information To demonstrate this protocol, the pairwise AND function is computed and can be used as a building block for other functions.

Assumptions

The clients have limited computational capabilities, namely access to linear XOR functionalities.

Outline

Main Routine

The server sends an ancilla bit to the first client. The first client performs the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi/2} rotation along Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} -axis according to his input bit and $\pi$ rotation accordingto his random bit for security. He then sends the qubit to the next client who performs the same rotation according to his bits. This process if followed until all clients have performed their operations. Now, one of the client performs the conjugate transpose of the $\pi /2$ rotation on the qubit based on the global XOR of all the inputs which he gets by the XOR routine. The state now prepared is the value of the function XORed with the XOR of the random bits of all clients. The clients now announce the random bits with the help of which the final result is calculated.

XOR Routine

The clients choose random bits whose XOR is their input bit and send each such random bit to each client. The clients now perform the XOR of the received bits. To calculate the global XOR, the send their results to the designated client who then performs the XOR of all the received bits to get the global XOR.

Notations

$C_{i}$ : Client with index $i$ .
$x_{i}$ : Input bit of $i^{th}$ client.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} : Random bit of $i^{th}$ client.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_y(\theta)} : Rotation around $y$ -axis in Bloch sphere by angle $\theta$ .
$U$ : Operator for performing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi/2} rotation around Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} -axis in Bloch Sphere.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} : Operator for performing $\pi$ rotation around Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} -axis in Bloch Sphere.

Hardware Requirements

Basic state preparation and measurement devices.
Access to secure classical channels.

Properties

The input of each client remains hidden from the other clients and from the server.
The server performs the computation without learning anything about the result.
As long as at least two clients are honest, it is enough to guarantee the secrecy of the independent inputs.

Pseudo Code

To compute $f(x_{1},x_{2},...,x_{n})=\Sigma _{i,j=1}^{n}x_{i}x_{j}\forall i\neq j$ ,

Main Routine

The server generates an ancilla bit $|0\rangle$ and sends it to client $C_{1}$ .
For $i=1$ $i=1$ to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} :
1. $C_{i}$ applies $V^{r_{i}}U^{x_{i}}$ on the received qubit and sends it to client $C_{i+1}$ .
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n} applies $V^{r_{n}}U^{x_{n}}$ on the received qubit.
Any client then applies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (U^\dagger)^{\oplus_i x_i}} .
$(U^{\dagger })^{\oplus _{i}x_{i}}\underbrace {V^{r_{n}}U^{x_{n}}} _{{\mathcal {C}}_{n}}...\underbrace {V^{r_{2}}U^{x_{2}}} _{{\mathcal {C}}_{2}}\underbrace {V^{r_{1}}U^{x_{1}}} _{{\mathcal {C}}_{1}}|0\rangle =|r\oplus f\rangle$
The resulting state is now sent to the server who measures the outcome $r\oplus f$ and announces it.
The clients locally compute XOR of the random bits of other clients.
They then perform the operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = r \oplus (r \oplus f)} to get the result.

XOR Routine

For $i,j=1,\dots ,n$ $i,j=1,\dots ,n$
1. Each client $C_{j}$ chooses random bits $x_{j}^{i},~r_{j}^{i}\in \{0,1\}$ , such that $x_{j}=\bigoplus _{i=1}^{n}x_{j}^{i}$ and $r_{j}=\bigoplus _{i=1}^{n}r_{j}^{i}$ and sends $x_{j}^{i}$ and $r_{j}^{i}$ to client $C_{i}$ .
2. Each client $C_{i}$ then computes ${\tilde {x}}_{i}=\bigoplus _{j=1}^{n}x_{j}^{i}$ and ${\tilde {r}}_{i}=\bigoplus _{j=1}^{n}r_{j}^{i}$ .
To perform the operation $U^{\dagger }$ , the clients send Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{x}_i} to the designated client, who computes the global XOR.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigoplus_{i=1}^n x_i=\bigoplus_{i=1}^n \tilde{x}_i }
When server announces </math>r \oplus f</math>, all clients broadcast </math>\tilde{r}_i</math> to calculate </math>r</math> and know the value of </math>f</math>.