PV-GC TLDR;

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

We are working on a prototype of our protocol in C++ which put together the code base of emp-ag2pc (Authenticated Garbling) and faest (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 + (Generalized) Half-Gate Optimization.

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\ast 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,\ast )$ 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)\ast (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\ast z_j+{\lambda }_k={\lambda }_k+\widehat{{\lambda }_k}+(z_i+{\lambda }_i)\ast {\lambda }_j+(z_j+{\lambda }_j)\ast {\lambda }_i+(z_i+{\lambda }_i)+(z_j+{\lambda }_j)$
  • B can evaluate and then A sends
    $z_i\ast 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\ast 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\ast 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)

VOLE-in-the-Head

Paper

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

$s{d}_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.