Xiao Wang (MIT): Covert Security with Public Verifiability: Simpler, Faster, and Leaner

Friday, October 12, 2018 - 10:30am to 12:00pm
Hewlett, G882
Xiao Wang, MIT
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 (say, 1/2). It
provides more realistic guarantees than semi-honest security with
significantly less overhead than is required by malicious

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

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., 488 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.