Calling Out Cheaters: Covert Security with Public Verifiability

Gilad Asharov, Claudio Orlandi
ASIACRYPT 2012 [pdf] [bibtex]

In the covert security model of AL10, cheating adversaries are caught by the honest parties with some guaranteed probability. This model provides a somewhat limited deterrent effect, because only the honest participants of the protocol learn of cheating.

This work introduces public verifiability to the covert security model. In this model, whenever a cheating party is caught cheating, the honest parties receive a short proof implicating a cheating participant. This proof can be publicized and verified by anyone, hence giving a stronger deterrent against potential cheating. The main technical challenges are:

  1. Privacy: The proof of cheating should not reveal the honest party's private input to the protocol. The essence of covert security (in the strong explicit-cheat formulation) is violated if the adversary can cheat, get caught, but then learn the honest party's input anyway by inspecting the public proof. More concretely, a proof of cheating cannot simply be a party's entire view.
  2. Defamation-freeness: It should be infeasible to generate a valid proof of cheating that implicates an honest party.
  3. Handling aborts: One way to cheat is to simply abort, but it is difficult to prove that another party aborted a protocol. Hence, the protocol must be designed so that aborting does not affect the covert deterrence factor (i.e., an adversary shouldn't be able to anticipate that it will be caught and then abort just before being caught).

A protocol achieving these properties is presented. The main ingredient is a primitive called signed oblivious transfer. In this primitive, the sender provides two messages {$m_0, m_1$} as well as a signing key {$sk$}, the receiver provides a choice bit {$b$}, and the receiver obtains {$m_b$} as well as a signature {$\sigma_b$} on {$m_b$}. (One can think of the corresponding verification key as common input to this primitive.) Note here that the functionality enforces the correctness of signatures, hence it is not enough to perform a plain OT of signed messages {$(m_0, \sigma_0), (m_1, \sigma_1)$}. Intuitively, the receiver will have no recourse if a malicious sender provides an invalid signature.

A protocol for signed OT is presented, based on the efficient PVW oblivious transfer protocol. The functionality realized by this protocol is a slight variant of the functionality described above.

Finally, a publicly-verifiable covert-secure 2PC protocol is presented. The protocol is essentially the covert-secure protocol of AL10, with minor modifications involving appropriate use of signed OT and some other signatures of protocol messages.