Revision History for: Secure Multiparty Delegated Classical Computation
- 2025-06-24 at 21:55 by JuliaM
implements Secure Delegated Computation
Introduction
This protocol [1] provides a method for computing nonlinear functions involving multiple variables 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.
Outline
The protocol consists of two routines:
Main Routine
The server sends an ancilla bit to the first client. The first client performs the $\\\pi/2$ rotation along the $y$-axis according to his input bit and a $\\\pi$ rotation according to 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 continues until all clients have performed their operations.
Now, one of the clients performs the conjugate transpose of the $\\\pi/2$ rotation on the qubit based on the global XOR of all the inputs, which he gets via 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 then perform the XOR of the received bits.
To calculate the global XOR, they send their results to the designated client, who then performs the XOR of all the received bits to get the global XOR.
Assumptions
The clients have limited computational capabilities, namely access to linear XOR functionalities.
Requirements
Network Stage: Prepare-and-measure
- Basic state preparation and measurement devices.
- Access to secure classical channels.
The separate resources for client and server are as follows: (pictures)
Notation
- $C_i$: Client with index $i$
- $x_i$: Input bit of $i^{\\\text{th}}$ client
- $r_i$: Random bit of $i^{\\\text{th}}$ client
- $R_y(\\\theta)$: Rotation around $y$-axis in the Bloch sphere by angle $\\\theta$
- $U$: Operator for performing $\\\pi/2$ rotation around the $y$-axis in the Bloch sphere
- $V$: Operator for performing $\\\pi$ rotation around the $y$-axis in the Bloch sphere
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.
Technical Description
Output: compute $$ f(x_1, x_2, \\\dots, x_n) = \\\sum_{i,j=1}^{n} x_i x_j \\\quad \\\forall i \\\ne j $$
Main Routine
- The server generates an ancilla bit $|0\\\rangle$ and sends it to client $C_1$.
- For $i = 1$ to $n – 1$:
- Client $C_i$ applies $V^{r_i} U^{x_i}$ on the received qubit and sends it to client $C_{i+1}$.
- Client $C_n$ applies $V^{r_n} U^{x_n}$ on the received qubit.
- Any client then applies $(U^\\\dagger)^{\\\oplus_i x_i}$. $$ (U^\\\dagger)^{\\\oplus_i x_i} \\\underbrace{V^{r_n} U^{x_n}}_{C_n} \\\cdots \\\underbrace{V^{r_2} U^{x_2}}_{C_2} \\\underbrace{V^{r_1} U^{x_1}}_{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 the XOR of the random bits of the other clients.
- They then perform the operation $f = r \\\oplus (r \\\oplus f)$ to get the result.
XOR Routine
- For $i, j = 1, \\\dots, n$:
- 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 \\\quad \\\text{and} \\\quad r_j = \\\bigoplus_{i=1}^{n} r_j^i$, and sends $x_j^i$ and $r_j^i$ to client $C_i$.
- Each client $C_i$ then computes: $\\\tilde{x}_i = \\\bigoplus_{j=1}^{n} x_j^i \\\quad \\\text{and} \\\quad \\\tilde{r}_i = \\\bigoplus_{j=1}^{n} r_j^i$
- To perform the operation $U^\\\dagger$, the clients send $\\\tilde{x}_i$ to the designated client, who computes the global XOR: $$ \\\bigoplus_{i=1}^{n} x_i = \\\bigoplus_{i=1}^{n} \\\tilde{x}_i $$
- When the server announces $r \\\oplus f$, all clients broadcast $\\\tilde{r}_i$ to calculate $r$ and know the final value of $f$.
Experimental Implementations
No content has been added to this section, yet!
Further Information
No content has been added to this section, yet!
References
- Clementi, Marco, Anna Pappa, Andreas Eckstein, Ian A. Walmsley, Elham Kashefi, and Stefanie Barz. “Classical multiparty computation using quantum resources.” Physical Review A 96, no. 6 (2017): 062317.
- 2025-05-21 at 12:55 by JuliaM
implements Secure Delegated Computation
Introduction
This protocol [1] provides a method for computing nonlinear functions involving multiple variables 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.
Outline
The protocol consists of two routines:
Main Routine
The server sends an ancilla bit to the first client. The first client performs the $\\\pi/2$ rotation along the $y$-axis according to his input bit and a $\\\pi$ rotation according to 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 continues until all clients have performed their operations.
Now, one of the clients performs the conjugate transpose of the $\\\pi/2$ rotation on the qubit based on the global XOR of all the inputs, which he gets via 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 then perform the XOR of the received bits.
To calculate the global XOR, they send their results to the designated client, who then performs the XOR of all the received bits to get the global XOR.
Assumptions
The clients have limited computational capabilities, namely access to linear XOR functionalities.
Requirements
Network Stage: Prepare-and-measure
- Basic state preparation and measurement devices.
- Access to secure classical channels.
The separate resources for client and server are as follows: (pictures)
Notation
- $C_i$: Client with index $i$
- $x_i$: Input bit of $i^{\\\text{th}}$ client
- $r_i$: Random bit of $i^{\\\text{th}}$ client
- $R_y(\\\theta)$: Rotation around $y$-axis in the Bloch sphere by angle $\\\theta$
- $U$: Operator for performing $\\\pi/2$ rotation around the $y$-axis in the Bloch sphere
- $V$: Operator for performing $\\\pi$ rotation around the $y$-axis in the Bloch sphere
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.
Technical Description
Output: compute $$ f(x_1, x_2, \\\dots, x_n) = \\\sum_{i,j=1}^{n} x_i x_j \\\quad \\\forall i \\\ne j $$
Main Routine
- The server generates an ancilla bit $|0\\\rangle$ and sends it to client $C_1$.
- For $i = 1$ to $n – 1$:
- Client $C_i$ applies $V^{r_i} U^{x_i}$ on the received qubit and sends it to client $C_{i+1}$.
- Client $C_n$ applies $V^{r_n} U^{x_n}$ on the received qubit.
- Any client then applies $(U^\\\dagger)^{\\\oplus_i x_i}$. $$ (U^\\\dagger)^{\\\oplus_i x_i} \\\underbrace{V^{r_n} U^{x_n}}_{C_n} \\\cdots \\\underbrace{V^{r_2} U^{x_2}}_{C_2} \\\underbrace{V^{r_1} U^{x_1}}_{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 the XOR of the random bits of the other clients.
- They then perform the operation $f = r \\\oplus (r \\\oplus f)$ to get the result.
XOR Routine
- For $i, j = 1, \\\dots, n$:
- 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 \\\quad \\\text{and} \\\quad r_j = \\\bigoplus_{i=1}^{n} r_j^i$, and sends $x_j^i$ and $r_j^i$ to client $C_i$.
- Each client $C_i$ then computes: $\\\tilde{x}_i = \\\bigoplus_{j=1}^{n} x_j^i \\\quad \\\text{and} \\\quad \\\tilde{r}_i = \\\bigoplus_{j=1}^{n} r_j^i$
- To perform the operation $U^\\\dagger$, the clients send $\\\tilde{x}_i$ to the designated client, who computes the global XOR: $$ \\\bigoplus_{i=1}^{n} x_i = \\\bigoplus_{i=1}^{n} \\\tilde{x}_i $$
- When the server announces $r \\\oplus f$, all clients broadcast $\\\tilde{r}_i$ to calculate $r$ and know the final value of $f$.
Experimental Implementations
No content has been added to this section, yet!
Further Information
No content has been added to this section, yet!
References
- Clementi, Marco, Anna Pappa, Andreas Eckstein, Ian A. Walmsley, Elham Kashefi, and Stefanie Barz. “Classical multiparty computation using quantum resources.” Physical Review A 96, no. 6 (2017): 062317.
- 2025-05-21 at 12:55 by JuliaM
implements Secure Delegated Computation
Introduction
This protocol [1] provides a method for computing nonlinear functions involving multiple variables 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.
Outline
The protocol consists of two routines:
Main Routine
The server sends an ancilla bit to the first client. The first client performs the $\\\pi/2$ rotation along the $y$-axis according to his input bit and a $\\\pi$ rotation according to 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 continues until all clients have performed their operations.
Now, one of the clients performs the conjugate transpose of the $\\\pi/2$ rotation on the qubit based on the global XOR of all the inputs, which he gets via 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 then perform the XOR of the received bits.
To calculate the global XOR, they send their results to the designated client, who then performs the XOR of all the received bits to get the global XOR.
Assumptions
The clients have limited computational capabilities, namely access to linear XOR functionalities.
Requirements
Network Stage: Prepare-and-measure
- Basic state preparation and measurement devices.
- Access to secure classical channels.
The separate resources for client and server are as follows: (pictures)
Notation
- $C_i$: Client with index $i$
- $x_i$: Input bit of $i^{\\\text{th}}$ client
- $r_i$: Random bit of $i^{\\\text{th}}$ client
- $R_y(\\\theta)$: Rotation around $y$-axis in the Bloch sphere by angle $\\\theta$
- $U$: Operator for performing $\\\pi/2$ rotation around the $y$-axis in the Bloch sphere
- $V$: Operator for performing $\\\pi$ rotation around the $y$-axis in the Bloch sphere
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.
Technical Description
Output: compute $$ f(x_1, x_2, \\\dots, x_n) = \\\sum_{i,j=1}^{n} x_i x_j \\\quad \\\forall i \\\ne j $$
Main Routine
- The server generates an ancilla bit $|0\\\rangle$ and sends it to client $C_1$.
- For $i = 1$ to $n – 1$:
- Client $C_i$ applies $V^{r_i} U^{x_i}$ on the received qubit and sends it to client $C_{i+1}$.
- Client $C_n$ applies $V^{r_n} U^{x_n}$ on the received qubit.
- Any client then applies $(U^\\\dagger)^{\\\oplus_i x_i}$. $$ (U^\\\dagger)^{\\\oplus_i x_i} \\\underbrace{V^{r_n} U^{x_n}}_{C_n} \\\cdots \\\underbrace{V^{r_2} U^{x_2}}_{C_2} \\\underbrace{V^{r_1} U^{x_1}}_{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 the XOR of the random bits of the other clients.
- They then perform the operation $f = r \\\oplus (r \\\oplus f)$ to get the result.
XOR Routine
- For $i, j = 1, \\\dots, n$:
- 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 \\\quad \\\text{and} \\\quad r_j = \\\bigoplus_{i=1}^{n} r_j^i$, and sends $x_j^i$ and $r_j^i$ to client $C_i$.
- Each client $C_i$ then computes: $\\\tilde{x}_i = \\\bigoplus_{j=1}^{n} x_j^i \\\quad \\\text{and} \\\quad \\\tilde{r}_i = \\\bigoplus_{j=1}^{n} r_j^i$
- To perform the operation $U^\\\dagger$, the clients send $\\\tilde{x}_i$ to the designated client, who computes the global XOR: $$ \\\bigoplus_{i=1}^{n} x_i = \\\bigoplus_{i=1}^{n} \\\tilde{x}_i $$
- When the server announces $r \\\oplus f$, all clients broadcast $\\\tilde{r}_i$ to calculate $r$ and know the final value of $f$.
Experimental Implementations
No content has been added to this section, yet!
Further Information
No content has been added to this section, yet!
References
- Clementi, Marco, Anna Pappa, Andreas Eckstein, Ian A. Walmsley, Elham Kashefi, and Stefanie Barz. “Classical multiparty computation using quantum resources.” Physical Review A 96, no. 6 (2017): 062317.