# MPC Study Group: Authenticated Garbling

In this week’s zoom meetup we looked at “Authenticated garbling and efficient maliciously secure two-party computation” by Wang et al. (2017) [WRK17].

These are my personal study notes, so please refer to the references to verify any information in this post. The content of this post is mostly based on [WRK17].

## Garbled Circuits

We covered garbled circuits in our first session of the MPC study group. The version that we presented was secure against semi-honest adversaries, but not against malicious adversaries. One example to show this, the circuit generator $P_1$ may encode the wire-labels in the garbled gates arbitrarily, thus $P_1$ can control the output of the gates. The circuit evaluator $P_2$ can return arbitrary output to $P_1$, this would not be detected by $P_1$.

In order to deal with malicious adversaries we look at authenticated garbling [WRK17]. The idea is to use authenticated secret sharing that is additively homomorphic. Using this the parties cooperate to generate the garbled circuit. The preprocessing phase does a lot of the heavy lifting, generating beaver triples and more that are used for the circuit generation. Admittedly, I found this to be a tricky paper to read, and I am still working on understanding it fully. It was very helpful to read [NNOB12] which this paper derives from. For this overview I will instead present the more abstract form from [EKR17].

## Distributed Garbling

The garbled table of an AND gate will have the form (we’ll explain what the elements mean in a moment):

- $e_{0,0} = H(k_a^0 || k_b^0) \oplus k_c^{p_c \oplus p_a * p_b}$
- $e_{0,1} = H(k_a^0 || k_b^1) \oplus k_c^{p_c \oplus p_a * \overline{p_b}}$
- $e_{1,0} = H(k_a^1 || k_b^0) \oplus k_c^{p_c \oplus \overline{p_a} * p_b}$
- $e_{1,1} = H(k_a^1 || k_b^1) \oplus k_c^{p_c \oplus \overline{p_a} * \overline{p_b}}$

How are the elements generated and what do they mean?

- Wire labels $k_i^0$, $k_i^1$:
- $P_1$ chooses random wire labels of length $\kappa$.

- $p_a$, $p_b$, $p_c$:
- Input pointer bits representing the value false (and $\overline{p_a}$ represents true).
- The pointer bits are generated randomly, such that neither party knows the pointer bits.
- The pointer bits are authenticated.
- $[p_a]$ is the authenticated $p_a$.
- $P_1$ (the generator) holds a uniform global key $\Delta _1$, and $P_2$ holds $\Delta _2$.
- $P_1$ holds for an authenticated bit (the bit is not known to either $P_1$ or $P_2$): $[p_a]_1 = $
- $<$
- $p_{a, 1},$
- $K_1[p_a],$ // uniform random key
- $T = K_2[p_a] \oplus p_a \Delta _2,$ // MAC tag
- $>$

- Whereas, $P_2$ holds: $[p_a]_2 = $
- $<$
- $p_{a, 2},$
- $K_2[p_a],$
- $T = K_1[p_a] \oplus p_a \Delta _1,$
- $>$

- Such that $p_{a, 1} \oplus p_{a, 2} = p_a$ // $p_{a, i}$ is a secret-share.
- Note that the shares are additive.

- $H$:
- Random oracle hash function.

The above garbled table can be expanded and rewritten as:

- $e_{0,0} = H(k_a^0 || k_b^0) \oplus k_c^0 \oplus (p_c \oplus p_a * p_b) \Delta $
- $e_{0,1} = H(k_a^0 || k_b^1) \oplus k_c^0 \oplus (p_c \oplus p_a * \overline{p_b}) \Delta $
- $e_{1,0} = H(k_a^1 || k_b^0) \oplus k_c^0 \oplus (p_c \oplus \overline{p_a} * p_b) \Delta $
- $e_{1,1} = H(k_a^1 || k_b^1) \oplus k_c^0 \oplus (p_c \oplus \overline{p_a} * \overline{p_b}) \Delta $

The observation to be made is that $P_1$ knows the left side of $e_{\alpha, \beta}$:

- $H(k_a^\alpha || k_b^\beta) \oplus k_c^0$

Whereas the parties hold additive shares of the right side:

- $(p_c \oplus p_a * p_b) \Delta$

Hence the garbled table is shared between the two parties.

We didn’t cover the form of XOR gates, and how the garbled circuit is generated, and later evaluated.

## Performance

This paper put a lot of effort towards improving the performance. For the function independent and function dependent pre-processing the communication and computation complexity is:

- $O(|C|)$

For the online phase:

- Communication complexity: $O(|I| + |O|)$
- Computation complexity: $O(|C|)$

## References

- [WRK17] Wang X, Ranellucci S, Katz J. Authenticated garbling and efficient maliciously secure two-party computation. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security 2017 Oct 30 (pp. 21-37). URL
- [NNOB12] Nielsen JB, Nordholt PS, Orlandi C, Burra SS. A new approach to practical active-secure two-party computation. In Annual Cryptology Conference 2012 Aug 19 (pp. 681-700). Springer, Berlin, Heidelberg.
- [EKR17] Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security. 2017 Jan;2(2-3).