Public Verifiable MPC

Introduction

Secure Multiparty Computation (MPC) allows

$n$ parties

$P_1,\dots ,P_n$ to securely evaluate a joint function

$f(x_1,\dots ,x_n)$ while keeping the secret input

$x_i$ private to its owner

$P_i$. MPC comes with two main flavors of security, namely Semi-honest and Active Security:

• Semi-Honest (SEM} only guarantees security if the adversary acts according to the protocol, i.e., one will not deviate from the protocol but only tries to break privacy from the MPC transcript that is available to it;

• Active Security (ACT) is a stronger security setting than SEM that guarantees the security of the MPC protocol even if the adversary acts arbitrarily.

Generic MPC is enabled through two approaches: Secret-Sharing (SS) and Garbled-Circuit (GC). We focus on the latter due to its attractive property of constant round complexity (where round complexity is an important factor for blockchain model due to bottleneck in block generation time.)

Efficiency of Actively Secure Garbled Circuit.

ACT for GC is trivially available through the usage of Zero-Knowledge-Proof, yet even with optimizations, it is necessary to prove a statement with 19 clauses conjunction per gate. Cut-and-Choose is another approach for ACT in which the Garbler prepares

$k$ circuits in total, and the Evaluator can choose

$t$ to test and only accepts if all

$t$ circuits are valid. Yet the preparation of many circuits and the testing for validity yield concrete inefficiency and become unreasonable when the circuit size is large. Another approach is through Authenticated Garbling, which will be our focus due to its efficiency compared with the previous two.

Yet, these classical flavors of security only take into consideration the parties that participate in the MPC protocol itself, i.e., only

$P_1,\dots ,P_n$ can verify the security of the MPC protocol.

Verifiable MPC.

We consider a somewhat added-on setting, in which an external party, let us call it Verifier, can verify the security of the MPC protocol, and we call protocols in this setting Verifiable MPC (V-MPC). The security verification can come in 4 flavors:

• Designated Verifier (DV-MPC): A single Verifier who potentially has some private state can verify the protocol execution to be secure.

• Collaborative Verifiable (CV-MPC) A set of Verifiers who potentially have some private states can jointly (according to some access structure) verify the security of the protocol (CV-MPC can be considered as a thresholdized version of DV-MPC.)

• Multi Verifier (MV-MPC) A set of Verifiers who potentially have some private states can individually verify the protocol's security. Such verification flavor is also called Crowd-Verifiable MPC.

• Publicly Verifiable (PV-MPC) Any external Verifier without any secret state can verify the security of the protocol (possibly with aid from some Common Random String CRS).

We focus on the last setting, which is also the strongest one: Publicly Verifiable MPC. Its motivation is to run an MPC protocol among

$n$ parties, and the output will be acknowledged by the vast external verifiers of a blockchain consensus network.

Verifiability vs Auditability.

Disregard the verifiability flavor, to make an MPC verifiable, there are two approaches:

• Verifiable Output (VO) where the output of the MPC is made verifiable, while
• Auditable Transcript (AT) where the transcript of the MPC is made verifiable.
  We distinguish that the VO flavor is independent while the VT one depends on the MPC protocol.

Let us consider the Shuffle functionality. The Shuffle functionality runs between

$n$ parties

$P_1,\dots ,P_n$ each with a secret input

$x_1,\dots ,x_n$ starting as an ordered list of

$O_0=\{x_1,\dots ,x_n\}$. The functionality runs in

$n$ rounds, in each round

$R_i$, party

$P_i$ sends a permutation

${\pi }_i$ to Shuffle in which the functionality will apply to obtain

$O_i={\pi }_i(O_{i-1})$. Finally, the functionality outputs

$O_n$. Verifiability VO only asks for the quality of the output, i.e., that

$O_n$ is a permutation of

$O_0$. In contrast, Auditability VT asks for the correctness of the process, i.e., that

$O_n$ is a permutation of

$O_0$ through a series of permutation

${\pi }_1,\dots ,{\pi }_n$.

Verifiable MPC

For VO-MPC, we can leverage Collaborative Zero-Knowledge Proof (co-ZKP, between

$P_1,\dots ,P_n$) to produce a ZK proof that the output

$y=f(x_1,\dots ,x_n)$ while keeping the

$x_1,\dots ,x_n$ private to

$P_1,\dots ,P_n$. In the literature, co-ZKP can be achieved by thresholdizing any existing ZKP, demonstrated by Collaborative Zero-Knowledge Succinct Argument of Knowledge (co-zkSNARKs). Yet, there are potential Co-ZKP based on other ZKP such as: MPC-In-The-Head (MPCitH: seminal work IKOS07, Other MPCitH techniques, VOLE-IZK (DVZK with fast prover time and small memory), or VOLE-In-The-Head (a.k.a the public coin Verifier version of VOLE-IZK).

DV-MPC can leverage any private coin Verifier (Co-) ZKP, CV-MPC is achievable through thresholdizing the Verifier state in the private coin Verifier (Co-) ZKP, MV-MPC can be obtained by running multiple DV-MPC instances, and PV-MP can utilize any public coin verifier ZKP.
Fortunately, all existing Co-ZKP is constant rounds protocols. Thus, the round complexity of the VO-MPC only depends on the underlying MPC protocol, i.e., a Secret-Sharing-based (SS) VO-MPC will yield linear round complexity while a Garbled-Circuit-based (GC) VO-MPC will have constant-round complexity.

Auditable MPC

For AT-MPC, we need the transcript auditable while keeping the privacy of the protocol execution. In general, for both SS-based and GC-based AT-MPC, the transcript can be made auditable through Additively-Homomorphic Commitment (COM, such as Pedersen) or Verifiable MAC (V-MAC) on each computation step. If the COM or V-MAC in the AT-MPC is publicly verifiable, then we have PV-MPC. COM-based has worse concrete efficiency than V-MAC-based AT-MPC due to the first operating on groups while the latter only operates on rings. One can consider ACT a special case of DV/MV AT-MPC where the Verifier is a party in the MPC protocol. Hence, if the ACT mechanism can be publicly verifiable, we will also obtain PV-MPC. As in VO-MPC, an SS-based AT-MPC will yield linear round complexity, while a GC-based VT-MPC can potentially yield a constant round complexity. This last one is also our main research question:

Can we pick a GC-based protocol that is actively secure (such as WRK17, KRRW18, DILO22, or CWYY23) and make such active security public verifiable and obtain constant round publicly auditable MPC?

An attempt with SNARK-ing AES

For PV-MPC, we conducted benchmarking of proving AES128 encryption to test feasibility of the approach where garbled circuit execution (garbling and evaluation) is proven by zkSNARKs. AES128 is a core building block for efficient garbled circuit implementation but is thought to be inefficient to handle inside zkSNARKs at the time. We tried to test if the state of the art lookup argument can improve that to somewhat feasible efficiency.
The circuit is constructed mostly using 8bit-wise operations lookups and s-box lookups and column, row shifts. You can find the code here.
The benchmark is taken using different SNARK backend implemented on halo2, the most prominent one was hyperplonk+logup which we could generate proofs for 6k fixed key AES128 calls in 2 minutes. The result showed that this approach is far too inefficient ATM for real usecase.

We stopped working on this approach because there were no alternative practical implementations for efficient SNARK/STARK on whicn bit/bytes operations can be handled very efficiently at the time.
Although, recently we have seen more and more efficient STARK protocol for smaller field proposed. Those protocols might be the savior for this approach in near future.

Making VOLE-GC Publicly Auditable

We picked the basic blueprint of the actively secure Garbled Circuit protocol, namely, WRK17, which relies on V-MAC. We then adopted VOLEitH (with SoftSpokenOT) to make the utilized V-MAC public auditable. We obtained a Constant Round Publicly Auditable Garbled Circuit Protocol with inherited security and efficiency from both WRK17 and VOLEitH.

There are potential improvements in KRRW18, DILO22, or CWYY23, but we see non-trivial composition of such improvements and VOLEitH, for example they may require Learning-Parity-With-Noise assumption while SoftSpokenOT is incompatible with LPN. We leave such composition to future work.

Please refer to our formal technical report here for details.

This is an informal dumped log for quick understanding.