Paper 2013/577

Secure Two-Party Computation with Reusable Bit-Commitments, via a Cut-and-Choose with Forge-and-Lose Technique

Luís T. A. N. Brandão

Abstract

A Secure Two Party Computation (S2PC) protocol allows two parties to compute over their combined private inputs, as if intermediated by a trusted third party. In the active model, security is maintained even if one party is malicious, deviating from the protocol specification. For example, a honest party retains privacy of its input and is ensured a correct output. This can be achieved with a cut-and-choose of garbled circuits (C&C-GCs), where some GCs are verified for correctness and the remaining are evaluated to determine the circuit output. This paper presents a new C&C-GCs-based S2PC protocol, with significant advantages in efficiency and applicability. First, in contrast with prior protocols that require a majority of evaluated GCs to be correct, the new protocol only requires that at least one evaluated GC is correct. In practice this reduces the total number of GCs to approximately one third, for the same statistical security goal. This is accomplished by augmenting the C&C with a new forge-and-lose technique based on bit commitments with trapdoor. Second, the output of the new protocol includes reusable XOR-homomorphic bit commitments of all circuit input and output bits, thereby enabling efficient linkage of several S2PCs in a reactive manner. The protocol has additional interesting characteristics (which may allow new comparison tradeoffs). The number of exponentiations is only linear with the number of input and output wires and a statistical parameter -- this is an improvement over protocols whose number of exponentiations is proportional to the number of GCs multiplied by the number of input and output wires. It uses unconditionally hiding bit commitments with trapdoor as the basis of oblivious transfers, with the circuit evaluator choosing a single value and the circuit constructor receiving two (a sort of 2-out-of-1 oblivious transfer, instead of the typical 1-out-of-2). The verification of consistency of circuit input and output keys across different GCs is embedded in the C&C structure.

Note: This is the full version -- an extended abstract will appear at ASIACRYPT 2013.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2013
Keywords
secure two-party computationcut-and-choosegarbled circuitsforge-and-losehomomorphic bit-commitments with trapdoor
Contact author(s)
luis papers @ gmail com
History
2013-09-14: received
Short URL
https://ia.cr/2013/577
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/577,
      author = {Luís T.  A.  N.  Brandão},
      title = {Secure Two-Party Computation with Reusable Bit-Commitments, via a   Cut-and-Choose with Forge-and-Lose Technique},
      howpublished = {Cryptology ePrint Archive, Paper 2013/577},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/577}},
      url = {https://eprint.iacr.org/2013/577}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.