Fairplay - Secure Two-Party Computation System

Fairplay - Secure Two-Party Computation System

Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
USENIX 2004 [pdf] [bibtex]

This paper describes the first implementation of a usable secure two-party computation tool. They show its utility for research by benchmarking various implementations of oblivious transfer. MNPS04 also introduces the Point-and-Permute optimization.

Components of the Fairplay System

  • A C-like function definition language called SFDL.
  • A boolean circuit language called SHDL.
  • Garbling mechanisms for both parties.

SFDL and SHDL are necessarily highly limited. In order to not reveal anyone's input, in SFDL there can be no recursion or pointers, loops must always run the same number of times, and both branches of conditionals must be evaluated. Likewise, in SHDL there are no registers, loops or gotos, and each gate can be used only once.

Fairplay Evalutation Procedure

  1. Users write an SFDL program.
  2. SFDL program is translated to SHDL circuit file. Resulting circuit is optimized.
  3. SHDL is parsed to Java.
  4. Bob constructs ⚠ {$ m $} garbled circuits and sends them to Alice, who picks one to be evaluated.
  5. Bob exposes the secrets of the other garbled circuits to Alice, who verifies them.
  6. Bob sends his input to Alice in garbled form.
  7. Bob and Alice use OT to determine Alice's garbled input.
  8. Alice evaluates the circuit and sends Bob his garbled output.
  9. Each party decodes their garbled output and prints the result.

In their description of the way Bob constructs the garbled circuit, a new optimization is casually presented.

Why is Point-and-Permute needed?

In unoptimized 2PC, the garbled tables must be ordered randomly. This is to prevent an attacker from deducing what the truth-value of a wire-label is from its position in the table. The downside is that it requires that the encryption scheme have a range function. That is, there must be some way to tell if a key can decrypt a given ciphertext. This limits the choices of an encryption scheme. Point-and-Permute is a way to avoid needing a range function.

Point-and-Permute Procedure

  1. Bob (the party garbling the circuit) assigns a random permutation of ⚠ {$ \{0,1\} $} to the true and false wire-labels of each wire. This is called the permutation bit. It is appended to the wire-label.
  2. Bob uses the permutation bit of each wire to build the garbled tables. For instance, the first entry will be the ciphertext corresponding to the two input-wires that both have a permutation bit of ⚠ {$ 0 $}.
  3. When Alice evaluates a gate in the circuit, she uses the permutation bits of her input wires to determine which ciphertext in the garbled table she can decrypt.

Thanks to Point-and-Permute, Fairplay can use efficient hash-based encryption with security under the random oracle method.

Security

They use SHA-1 as their basic cryptographic function. Therefore it must be modeled as a random oracle. The OT protocols used in the experimentation are all based on the random oracle model and the computational Diffie-Hellman assumption. Finally, they use cut-and-choose to reduce the cheating probability of Bob, but Alice only chooses one circuit for evaluation (an area for future study - see Cut-And-Choose).

Categories:

Todo Garbling