Paper 2006/088

On the Feasibility of Consistent Computations

Sven Laur and Helger Lipmaa


In many practical settings, participants are willing to deviate from the protocol only if they remain undetected. Aumann and Lindell introduced a concept of covert adversaries to formalize this type of corruption. In the current paper, we refine their model to get stronger security guarantees. Namely, we show how to construct protocols, where malicious participants cannot learn anything beyond their intended outputs and honest participants can detect malicious behavior that alters their outputs. As this construction does not protect honest parties from selective protocol failures, a valid corruption complaint can leak a single bit of information about the inputs of honest parties. Importantly, it is often up to the honest party to decide whether to complain or not. This potential leakage is often compensated by gains in efficiency---many standard zero-knowledge proof steps can be omitted. As a concrete practical contribution, we show how to implement consistent versions of several important cryptographic protocols such as oblivious transfer, conditional disclosure of secrets and private inference control.

Note: 2006-11-07: This is a thoroughly rewritten version of the previous eprint with the same number called 'On Security of Sublinear Oblivious Transfer'. While the basic protocol itself has not changed, almost everything else is new. 2008-09-30: A paper that was in comatosis for two years. The current version is thoroughly rewritten. 2010-03-12: The full version of the PKC 2010 paper.

Available format(s)
Publication info
Published elsewhere. PKC 2010 (this is the full version)
Consistencyequivocal and extractable commitmentoblivious transferprivate inference control
Contact author(s)
lipmaa @ research cyber ee
2010-03-12: last of 5 revisions
2006-03-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sven Laur and Helger Lipmaa},
      title = {On the Feasibility of Consistent Computations},
      howpublished = {Cryptology ePrint Archive, Paper 2006/088},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.