Why Publicly Verifiable Covert MPC Is a Game‑Changer for Secure Computation

Alibaba's Twin‑Star Security Lab, in collaboration with the University of Maryland, recently had a paper titled Covert Security with Public Verifiability: Faster, Leaner, and Simpler accepted at Eurocrypt 2019, marking the first top‑conference paper from a Chinese company in the field of secure multi‑party computation (MPC).

Secure Multi‑Party Computation (MPC), proposed by Yao in 1986, enables multiple distrustful data owners to jointly compute a function while revealing nothing beyond the output. It allows data to be valuable without exposing raw content, which is crucial in the data‑driven era.

The article first introduces Oblivious Transfer (OT) as a basic building block. Using a travel‑agency example, it shows how a buyer can obtain a specific piece of information without the seller learning which piece was requested, and vice versa, by encrypting all items and allowing the buyer to decrypt only the chosen one.

Next, the concept of Garbled Circuits (GC) is explained. Every logical gate is encrypted with unique wire keys, turning a clear circuit into a garbled one that can be evaluated only with matching keys. The process of generating, encrypting inputs, exchanging encrypted values, and evaluating the circuit is described in detail.

The security models for MPC are then discussed. The semi‑honest model assumes parties follow the protocol but may try to infer extra information, while the malicious model allows arbitrary deviation. The article points out that pure GC schemes are only secure under the semi‑honest model.

To bridge the gap, the Publicly Verifiable Covert (PVC) model is introduced. PVC adds a probabilistic deterrent: each party’s actions are signed, and a cheating party has at least a 50% chance of being caught and publicly exposed. This model, originally proposed at Asiacrypt 2012 and refined later, offers a practical trade‑off between security and efficiency.

A concrete PVC protocol is outlined: parties generate two random seeds, use OT to exchange them, build two garbled circuits (GC1 and GC2), hash and sign the circuits, and allow the receiver to verify consistency. If the sender cheats, the receiver can detect the inconsistency with probability ≥50%.

Experimental results show that the PVC scheme can compute the Hamming distance between two million‑dimensional vectors in about 2.5 seconds, comparable to semi‑honest performance while providing stronger security guarantees.

In summary, the collaboration produced the first publicly verifiable covert MPC solution, combining near‑half‑honest efficiency with a deterrent against cheating, making secure two‑party computation more practical for large‑scale data applications.