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

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
Asiacrypt 2013 [pdf] [bibtex]
summary contributed by Luís Brandão

Overview

The paper presents a new cut-and-choose mechanism for 2PC, achieving statistical security ⚠ {$2^{-s}$} with only ⚠ {$\sim s$} garbled circuits. The protocol also results in commitments of the inputs and outputs of each party, thus allowing a straightforward way to link the output and input of consecutive 2PC executions.

The solution follows a standard a cut-and-choose approach, in which the circuit-constructor (Alice) builds several garbled circuits. The circuit-evaluator (Bob) chooses a random subset of circuits to be checked for correctness, while the remaining are evaulated. In the new approach, denoted forge-and-lose, Alice can successfully cheat (i.e., Bob into an incorrect output) only if all checked circuits are correct and all evaluation circuits have been maliciously crafted. This is as improvement over previous approaches that require the majority of evaluation circuits to be correct. In practice, for a fixed statistical security goal this reduces the minimum number of garbled circuits by a factor of about 3.1.

The new technique provides a strong deterrent against malicious behavior by Alice, by allowing Bob to recover the input of Alice in case she tries to induce Bob into an erroneous output. Specifically, an output inconsistent across different garbled circuits (i.e., with at least one forged element) leads Bob to non-interactively find a trapdoor with which it can recover the input of Alice, then allowing him to compute the correct final output. The technique therefore has similarities to L13, and consequently achieves similar parameters for the number of garbled circuits. However, the techniques are substantially different, deserving future exploration of efficiency tradeoffs.

At high level, this work differs from L13 in the following:

  • it uses a "2-out-of-1" type of oblivious transfer as a basis of the solution to deal with the input bits of Bob (instead of the traditional 1-out-of-2 type);
  • for a suggested instantiation based on Blum integers, the number of exponentiations is ⚠ {$O(s+m)$} rather than ⚠ {$O(sm)$}, where ⚠ {$s$} is the cut-and-choose security parameter and ⚠ {$m$} the number of input bits;
  • the problem of ensuring input consistency and avoiding a selective failure attack by Alice is solved within the cut-and-choose approach, with the help of a "connector" structure that acts as a kind of commitment to a relation between bit commitments and wire-keys, being partially opened in different ways for each type of challenge.

Group instantiation

To achieve 128 bits of security, and assuming intractability of deciding quadratic residuosity, the paper suggests instantiating several cryptographic primitives with 3,072-bit Blum integers. This is larger than 256-bit moduli of elliptic-curve groups used in other protocols with security based on intractability of discrete-log and decision Diffie-Hellman problems. Nonetheless, the communication complexity estimated in the paper is competitive with that estimated in [Lindell-13], for the case of S2PC of a AES-128 circuit. Furthermore, the paper also estimates the communication complexity of S2PC of a SHA-256 circuit, highlighting how the proportional overhead brought by group elements decreases while increasing the size of the circuit (i.e., number of non-XOR gates) in comparison with the number of input and output wires. Since the BitComs are only used outside of the circuits, the technique is compatible with the typical garbled-gate based optimizations, such as Free-XOR and garbled-row reduction.

Cut-and-choose configurations

The paper contains a table relating several concrete values of statistical security with concrete configurations of cut-and-choose partitions. For the case of a majority-based correctness criterion (not the focus of the paper), it reviews as 123 the minimum number of circuits (74 for "verification", 49 for "evaluation") necessary to achieve statistical security of 40 bits (compare with 125, previously calculated in [Shelat-Shen-11]). For the case of a forge-and-lose type of technique, it shows varying configurations between fixed and variable number of each type of instances, which may be useful depending on computational and communication tradeoffs between "verification" and "evaluation" instances. For example, to achieve 40 bits of statistical security, while restricting the number of "evaluation" circuits to be at most 20 or 8, respectively, it is sufficient to use 41 or 123 circuits, respectively.

Oblivious transfers (OTs)

In traditional S2PC protocols, the wire-keys corresponding to input bits of Bob are obtained via 1-out-of-2 OTs, in which Alice "sends" two possible values and Bob "receives" only one of his choice, out of the two, without Alice knowing which one. In contrast, this paper follows a reverse approach, with the parties executing "2-out-of-1" OTs at the level of BitComs. Here, Bob selects one value (an opening of a BitCom) and then leads Alice to learn two values (the two possible openings). The technique is based on an unconditionally hiding and equivocable bit-commitment scheme, instantiated in a group where each square (a BitCom) has two "non-trivially correlated" square-roots (the openings), each being an encoding of a different bit. On on hand, Bob cannot find two square-roots of the same square, as finding such collision can be reduced to an (assumed to be) intractable problem (e.g., integer factorization). On the other hand, Alice knows a trapdoor that allows computation of the two square-roots (i.e., equivocation). Apart from a setup phase to decide the public parameters (and the trapdoor of Alice), conceptually this OT can be non-interactive. Nonetheless, depending on the outer protocol in which the OT is used, care is needed to avoid a selective failure attack by Bob. In the S2PC protocol presented in the paper, Bob gives a ZKPoK of a square-root of each square. This guarantees that, as a result of what Alice does with the computed square-roots, Bob does not learn more than what he is supposed to (e.g, use Alice as an oracle for deciding quadratic residuosity). In terms of expensive-computation primitives, each OT requires one exponentiation only by Alice (to compute the square-root), but not by Bob. The paper does not explore how to achieve OT-extension (i.e., amortizing the number of exponentiations) in case of many 2-out-of-1 OTs.

Connectors

In the beginning of the protocol, each party uses an unconditionally hiding and equivocable BitCom scheme (of which the other party knows the respective trapdoor) to commit to each of her own input bits. Then, the relation between each BitCom (called outer-BitComs) and the two respective wire-keys of each garbled circuit is ensured using a "connector" structure. The main challenge to solve in the overall connection arises from the duality between what needs to be revealed in "verification" and in "evaluation" challenges. To solve the conflicting requirements between the two types of challenges, the connector incorporates other BitComs (called inner BitComs) that allow splitting in two the path between BitComs and wire-keys. In this way, in the reply to each type of challenge, Alice reveals only part of the path, but never the full path. The specific "connector" construction varies between the wire type (input of Alice, input of Bob, output of Bob), but in all of them the statistical nature of the cut-and-choose is used to probabilistically ensure the correctness of the revealed wire-keys and the privacy of the respective underlying bits.

Other links

conference presentation slides

Categories:

CutAndChoose