Skip to main content
added 1 character in body
Source Link
Geoffroy Couteau
  • 21.3k
  • 2
  • 50
  • 72

First question: at the end of GMW, the parties can reconstruct the outputs by broadcasting their shares to everyone.

Second question: a garbled circuit cannot be evaluated on plain inputs, we need to encode the inputs as well. In slightly more details, a garbling scheme produces a garbled circuit $(G, \vec K_0, \vec K_1) \gets \mathsf{Garble}(C)$. Here, I view $G$ as "the garbled circuit itself", and $\vec K_0, \vec K_1$ as the vectors of input encodings. That is, if the $i$-th input is equal to a bit $b$, then it is encoded by $K^{(i)}_b$ (the $i$-th entry of $\vec K_b$).

The general idea to get a round-reduced GMW would be the following: let me call $\vec x$ the joint input of all parties, and $C$ the target circuit. The parties use GMW to compute shares of $(G, \vec K_{\vec x})$, where I slightly abuse my notations and denote $\vec K_{\vec x}$ the vector $(K^{(i)}_{x_i})_i$. Here, the input is needed in the computation, because the parties need to obtain the encodings of the input in order to evaluate the garbled circuit! And of course, the other encodings (all keys $K^{(i)}_{1-x_i}$) should remain hidden for security.

Given shares of $(G, \vec K_{\vec x})$, all parties broadcast their shares, reconstruct $(G, \vec K_{\vec x})$, and can get the output $C(\vec x)$ using the garbled circuit evaluation procedure.

Third question: a core feature of Yao's garbled circuit protocol is that all the gates can be garbled in parallel. That is, you don't need to garble first the parents of a gate, then the gate itself: you define the labels for all wires in the circuit, and compute in parallel all the tables of encryptions (for Yao, you have 4 double-encryptions per gate). Therefore, the size of the circuit $D(C,\vec x)$ which outputs $(G, \vec K_{\vec x})$ is proportional to $|C| \cdot \kappa$, but its depth is only the depth of computing a single gate (since thethey can all be computed in parallel), which is independent of $|C|$, and will typically be $O(\kappa)$ using standard symmetric key encryption.

Hope that helped, I'll be happy to add further clarification if needed!

First question: at the end of GMW, the parties can reconstruct the outputs by broadcasting their shares to everyone.

Second question: a garbled circuit cannot be evaluated on plain inputs, we need to encode the inputs as well. In slightly more details, a garbling scheme produces a garbled circuit $(G, \vec K_0, \vec K_1) \gets \mathsf{Garble}(C)$. Here, I view $G$ as "the garbled circuit itself", and $\vec K_0, \vec K_1$ as the vectors of input encodings. That is, if the $i$-th input is equal to a bit $b$, then it is encoded by $K^{(i)}_b$ (the $i$-th entry of $\vec K_b$).

The general idea to get a round-reduced GMW would be the following: let me call $\vec x$ the joint input of all parties, and $C$ the target circuit. The parties use GMW to compute shares of $(G, \vec K_{\vec x})$, where I slightly abuse my notations and denote $\vec K_{\vec x}$ the vector $(K^{(i)}_{x_i})_i$. Here, the input is needed in the computation, because the parties need to obtain the encodings of the input in order to evaluate the garbled circuit! And of course, the other encodings (all keys $K^{(i)}_{1-x_i}$) should remain hidden for security.

Given shares of $(G, \vec K_{\vec x})$, all parties broadcast their shares, reconstruct $(G, \vec K_{\vec x})$, and can get the output $C(\vec x)$ using the garbled circuit evaluation procedure.

Third question: a core feature of Yao's garbled circuit protocol is that all the gates can be garbled in parallel. That is, you don't need to garble first the parents of a gate, then the gate itself: you define the labels for all wires in the circuit, and compute in parallel all the tables of encryptions (for Yao, you have 4 double-encryptions per gate). Therefore, the size of the circuit $D(C,\vec x)$ which outputs $(G, \vec K_{\vec x})$ is proportional to $|C| \cdot \kappa$, but its depth is only the depth of computing a single gate (since the can all be computed in parallel), which is independent of $|C|$, and will typically be $O(\kappa)$ using standard symmetric key encryption.

Hope that helped, I'll be happy to add further clarification if needed!

First question: at the end of GMW, the parties can reconstruct the outputs by broadcasting their shares to everyone.

Second question: a garbled circuit cannot be evaluated on plain inputs, we need to encode the inputs as well. In slightly more details, a garbling scheme produces a garbled circuit $(G, \vec K_0, \vec K_1) \gets \mathsf{Garble}(C)$. Here, I view $G$ as "the garbled circuit itself", and $\vec K_0, \vec K_1$ as the vectors of input encodings. That is, if the $i$-th input is equal to a bit $b$, then it is encoded by $K^{(i)}_b$ (the $i$-th entry of $\vec K_b$).

The general idea to get a round-reduced GMW would be the following: let me call $\vec x$ the joint input of all parties, and $C$ the target circuit. The parties use GMW to compute shares of $(G, \vec K_{\vec x})$, where I slightly abuse my notations and denote $\vec K_{\vec x}$ the vector $(K^{(i)}_{x_i})_i$. Here, the input is needed in the computation, because the parties need to obtain the encodings of the input in order to evaluate the garbled circuit! And of course, the other encodings (all keys $K^{(i)}_{1-x_i}$) should remain hidden for security.

Given shares of $(G, \vec K_{\vec x})$, all parties broadcast their shares, reconstruct $(G, \vec K_{\vec x})$, and can get the output $C(\vec x)$ using the garbled circuit evaluation procedure.

Third question: a core feature of Yao's garbled circuit protocol is that all the gates can be garbled in parallel. That is, you don't need to garble first the parents of a gate, then the gate itself: you define the labels for all wires in the circuit, and compute in parallel all the tables of encryptions (for Yao, you have 4 double-encryptions per gate). Therefore, the size of the circuit $D(C,\vec x)$ which outputs $(G, \vec K_{\vec x})$ is proportional to $|C| \cdot \kappa$, but its depth is only the depth of computing a single gate (since they can all be computed in parallel), which is independent of $|C|$, and will typically be $O(\kappa)$ using standard symmetric key encryption.

Hope that helped, I'll be happy to add further clarification if needed!

Source Link
Geoffroy Couteau
  • 21.3k
  • 2
  • 50
  • 72

First question: at the end of GMW, the parties can reconstruct the outputs by broadcasting their shares to everyone.

Second question: a garbled circuit cannot be evaluated on plain inputs, we need to encode the inputs as well. In slightly more details, a garbling scheme produces a garbled circuit $(G, \vec K_0, \vec K_1) \gets \mathsf{Garble}(C)$. Here, I view $G$ as "the garbled circuit itself", and $\vec K_0, \vec K_1$ as the vectors of input encodings. That is, if the $i$-th input is equal to a bit $b$, then it is encoded by $K^{(i)}_b$ (the $i$-th entry of $\vec K_b$).

The general idea to get a round-reduced GMW would be the following: let me call $\vec x$ the joint input of all parties, and $C$ the target circuit. The parties use GMW to compute shares of $(G, \vec K_{\vec x})$, where I slightly abuse my notations and denote $\vec K_{\vec x}$ the vector $(K^{(i)}_{x_i})_i$. Here, the input is needed in the computation, because the parties need to obtain the encodings of the input in order to evaluate the garbled circuit! And of course, the other encodings (all keys $K^{(i)}_{1-x_i}$) should remain hidden for security.

Given shares of $(G, \vec K_{\vec x})$, all parties broadcast their shares, reconstruct $(G, \vec K_{\vec x})$, and can get the output $C(\vec x)$ using the garbled circuit evaluation procedure.

Third question: a core feature of Yao's garbled circuit protocol is that all the gates can be garbled in parallel. That is, you don't need to garble first the parents of a gate, then the gate itself: you define the labels for all wires in the circuit, and compute in parallel all the tables of encryptions (for Yao, you have 4 double-encryptions per gate). Therefore, the size of the circuit $D(C,\vec x)$ which outputs $(G, \vec K_{\vec x})$ is proportional to $|C| \cdot \kappa$, but its depth is only the depth of computing a single gate (since the can all be computed in parallel), which is independent of $|C|$, and will typically be $O(\kappa)$ using standard symmetric key encryption.

Hope that helped, I'll be happy to add further clarification if needed!