Vlad Kolesnikov, Georgia Institute of Technology

Abstract

The notion of covert security for secure two-party computation serves as a compromise between the traditional semi-honest and malicious security definitions. Roughly, covert security ensures that cheating behavior is detected by the honest party with reasonable probability. It provides more realistic guarantees than semi-honest security with significantly less overhead than is required by malicious security.

The rationale for covert security is that it dissuades cheating by parties that care about their reputation and do not want to risk being caught. Further thought, however, shows that a much stronger disincentive is obtained if the honest party can generate a publicly verifiable certificate of misbehavior when cheating is detected. While the corresponding notion of publicly verifiable covert (PVC) security has been explored, existing PVC protocols are complex and less efficient than the best-known covert protocols, and have impractically large certificates.

We propose a novel PVC protocol that significantly improves on prior work. Our protocol uses only ``off-the-shelf'' primitives (in particular, it avoids signed oblivious transfer) and, for deterrence factor 1/2, has only 20-40% overhead (depending on the circuit size and network bandwidth) compared to state-of-the-art semi-honest protocols. Our protocol also has, for the first time, constant-size certificates of cheating (e.g., 354 bytes long at the 128-bit security level).

As our protocol offers strong security guarantees with low overhead, we suggest that it is the best choice for many practical applications of secure two-party computation.

This is joint work with Cheng Hong (Alibaba Group), Jonathan Katz (UMD), Wen-jie Lu (University of Tsukuba) and Xiao Wang (MIT and Boston University).

Video