Honorific Security: Efficient Two-Party Computation with Offloaded Arbitration and Public Verifiability

Abstract

In the secure two-party computation (2PC), an adversary is often categorized as semi-honest or malicious, depending on whether it follows the protocol specifications. Covert security (Aumann and Lindell, 2010) first looks into the “middle ground”, such that an active adversary who cheats will be caught with a predefined probability. Other security notions, such as publicly auditable security (Baum et al., 2014) and (robust) accountability family (Küsters et al., 2010; Graf et al., 2023; Rivinius et al., 2022), achieve public verifiability as a stronger security guarantee by relying on heavy offline and online constructions with zero knowledge proofs and (or) a bulletin board functionality. In this work, we propose a new security notion called honorific security, where an external arbiter can identify the cheater without a bulletin board. Specifically, we delay and outsource the verification steps to the arbiter, so that the original online computation is thus accelerated. We show that a maliciously secure garbled circuit (GC) (Yao, 1986) protocol can be constructed with only slightly more overhead than a passively secure protocol. Our construction performs up to 2.37 times and 13.30 times as fast as the state-of-the-art protocols with covert and malicious security, respectively.