# PV-GC TLDR;

In this research we aim at combining [Authenticated Garbling](#Authenticated-Garbling) and [VOLE-in-the-Head](#VOLE-in-the-Head) techniques to make Garbled Circuit publicly verifiable.

We are working on a [prototype of our protocol](https://github.com/namnc/emp-ag2pc-pg) in C++ which put together the code base of [emp-ag2pc](https://github.com/emp-toolkit/emp-ag2pc) (Authenticated Garbling) and [faest](https://github.com/faest-sign/faest-ref) (VOLE-in-the-Head).

# Introduction to Garbled Circuit

Garbled Circuit (GC) protocol consists of two parties called Garbler (G) and Evaluator (E). In GC-based MPC the Garbler G will encrypt (garble) the circuit and send the encrypted circuit C along with its decryption keys (that correspond to G's private inputs but look random to the Evaluator E) and let the Evaluator E obtain its decryption keys (via Oblivious Transfer, that correspond to the Evaluator E's private input but without the Garbler G learning which keys are obtained). Then the Evaluator E can decrypt the garbled circuit C to obtain the final result (and send it back to the Garbler G if necessary). GC-based MPC is constant round so network latency is not an important factor here. The bottleneck in this approach is the size of the garbled circuit C and thus network bandwidth is key to scalability of GC-based MPC.

> For more information also see an in-depth description of Garbled Circuit: [Primer to GC and Optimizations](https://hackmd.io/frMushaeSESma2OEdNseRQ) + [(Generalized) Half-Gate Optimization](https://hackmd.io/h7Tcx6ZkQzKNyQO5uUeqjw).

# Authenticated Garbling

Authenticated Garbling is a technique in which the Evaluator can "authenticate" the garbled circuit sent by the Garbler such that it can detect any deviation from the protocol and abort if necessary.

- Authenticated shared bits: 2 instances of VOLE (between A and B) for $\mathbf{v} = \mathbf{a}\beta + \mathbf{c}$ (A sender), and $\mathbf{w} = \mathbf{b}\alpha + \mathbf{d}$ (B sender); during evalaution of $i$-th wire (output $z_i = x_i * y_i$), B learns $a_i + b_i + z_i$
- Authenticated parallel AND (*) (circuit independent): use the VOLE instances to come up with

- Authenticated circuit wires (circuit dependent) via Authenticated Garbling:


- For XOR: trivial just XOR the authenticated bits (also done locally by evaluator without communication)
- For AND:
- Gate $G(i,j,k,*)$ where i and j are indice of inputs and k is index of output
- $\hat{a}_k,\hat{b}_k$ are authenticated bit SHARES of $(a_i + b_i)*(a_j + b_j)$
- $\lambda_k = a_k + b_k$
- $\hat{\lambda}_k = \hat{a}_k + \hat{b}_k$
- Both parties need know $\lambda_i + z_i$ then can compute $z_i * z_j + \lambda_k = \lambda_k + \hat{\lambda_k} + (z_i + \lambda_i)*\lambda_j + (z_j + \lambda_j)*\lambda_i + (z_i + \lambda_i) + (z_j + \lambda_j)$
- B can evaluate and then A sends $z_i*z_j + \lambda_k$ and B verifies that equals to $z_k + \lambda_k$

- How to compute $\lambda_i + z_i$
- WRK (base version focus on authentication)
- A computes a table for all four cases of ($\lambda_i + z_i$,$\lambda_j + z_j$,$z_i*z_j+\lambda_k$)
- two GCs, one for evaluation (normal GC) and one for authentication (use mask $\lambda$ and hide only $z_i + \lambda_i$ and $z_i*z_j+\lambda_k$)
- KKRW
- use half gate for 1st GC
- add one communication round to enable batching of correct garbling (less communication in total)

On how to generate the VOLE instances

> See more at
[Authenticated Garbling for Active Secure Garbled (Boolean Circuit)](https://hackmd.io/zW4zneG5TAKaFjq3rANF8g)

# VOLE-in-the-Head

> [Paper](https://faest.info/faest-spec-v1.1.pdf)

VOLE-in-the-Head is a technique that allows generation of public verifiable VOLE instances. VOLEitH makes use of All-but-One Vector Commitment.


To open one seed $sd_i$ one can simply send its path sibblings.


# Public Verifiable Garbled Circuit

We simply generate VOLE instances of Authenticated Garbling using VOLE-in-the-Head technique to make the Garbled Circuit not only authenticated to the Evaluator but also to the public verifier.