Paper 2015/1067

Public Verifiability in the Covert Model (Almost) for Free

Vladimir Kolesnikov and Alex J. Malozemoff


The covert security model (Aumann and Lindell, TCC 2007) offers an important security/efficiency trade-off: a covert player may arbitrarily cheat, but is caught with a certain fixed probability. This permits more efficient protocols than the malicious setting while still giving meaningful security guarantees. However, one drawback is that cheating cannot be proven to a third party, which prevents the use of covert protocols in many practical settings. Recently, Asharov and Orlandi (ASIACRYPT 2012) enhanced the covert model by allowing the honest player to generate a \emph{proof of cheating}, checkable by any third party. Their model, which we call the PVC (\emph{publicly verifiable covert}) model, offers a very compelling trade-off. Asharov and Orlandi (AO) propose a practical protocol in the PVC model, which, however, relies on a specific expensive oblivious transfer (OT) protocol incompatible with OT extension. In this work, we improve the performance of the PVC model by constructing a PVC-compatible OT extension as well as making several practical improvements to the AO protocol. As compared to the state-of-the-art OT extension-based two-party covert protocol, our PVC protocol adds relatively little: four signatures and an $\approx 67\%$ wider OT extension matrix. This is a significant improvement over the AO protocol, which requires public-key-based OTs per input bit. We present detailed estimates showing (up to orders of magnitude) concrete performance improvements over the AO protocol and a recent malicious protocol.

Note: This is the full version of the proceedings version published at ASIACRYPT 2015.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
secure computationpublicly verifiable covert security
Contact author(s)
amaloz @ cs umd edu
2015-11-03: received
Short URL
Creative Commons Attribution


      author = {Vladimir Kolesnikov and Alex J.  Malozemoff},
      title = {Public Verifiability in the Covert Model (Almost) for Free},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1067},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.