Garbled circuits

From CryptoWiki
Jump to: navigation, search



The concept of the Garbled scheme is very closely connected with the concept of sensitive computing. In cryptography, privacy protocol computation (some sources are defined as secured and secret calculation) - a cryptographic protocol that allows multiple participants to implement mathematical operations that depend on the secret parameters according to their secret parametres, in fact nobody of the participants could not get any useful Information about other people's secret parameters.

The first task of the secured calculation was raised by Andrew Yao in 1982. Two millionaire, Alice and Bob want to find out who among them richer, while they don't want to disclose the exact amount of their welfare. Yao suggested an original way to solve this problem, which was subsequently called the problem of millionaires. Much later, in 2004 Yehuda Lindell and Benny Pinkas gave a mathematically rigorous proof of the correctness of the Yao's. The problem of calculating is closely linked with the task of secret sharing.

There are N participants p1, p2, ..., pN in process of secure calculating, each participant has a secret input data d1, d2, ..., dN, respectively. Members want to find the value of F (d1, d2, ..., dN), where F - known to all the participants of a computable function of N arguments. It is assumed that participants will not all be honest, that is, those who faithfully follow the protocol, but trying to get further information from any intermediate data.

Security Settings

To define the security protocol is need to determine a couple of different requirements, depending on the specific situation. The basic requirements are:

  • Confidentiality. Nobody of the participants should not be able to obtain more information than it is prescribed.
  • Correctness. Each participant must ensure that you receive the correct data.
  • Warranty information. Participants should not be able to interfere with other members to get the output.

G 2.png

The millionaires problem

Alice and Bob want to find out whose fortune is more without disclosing the exact amount of their fortunes. To be specific, we assume that Alice i million, and Bob j, where 1 <i, j <10. To begin with Alice and Bob will need a reliable public-key cryptosystem such as RSA. Let Ea - arbitrary function of the encryption key for a, and Da - a function of decrypting the private key to the public key of a. Let a - Alice's public key. Then, the protocol is as follows:

  • Bob chooses a random integer x in N bits and privately said k = Ea (x).
  • Bob sends Alice the number of k-j + 1
  • Alice considers confidential values ​​yu = Da (k-j + u) for u = 1,2 ..., 10
  • Alice chooses a random prime number p of N / 2 bits so that the number of zu = yu mod (p) differ by at least 2 mod p for all u, and sends the number p to Bob.
  • Alice sends the number z1, z2 ... zi with subsequent numbers zi + 1 + 1 ... z10 + 1 (Numbers are taken by mod p).
  • Bob who knows how much money he compares with the number of x, chosen in the first step, and if they are equal, then Bob concludes that ⩾ i j and i <j otherwise.
  • Bob tells Alice result.


There are two different approaches to the implementation of this protocol. The first approach is typically based on a shared secret and works on the representation of the function calculated as an arithmetic circuit (arithmetic circuit), such as the protocols BGW (Ben-Or, Goldwasser and Wigderson) and CCD (Chaum, Crepeau and Damgard). This approach is typically used when it is known that most of the participants can be trusted (which is possible only when the number of participants more than two). Another approach is function as a logical circuit. This approach was used in the construction of Andrew Yao's distorted circuit (Eng. Garbled circuit, as well as the protocol GMW (Goldreich, Micali and Wigderson).

The method of arithmetic circuit is better suited for operations of addition and multiplication (where participants have a share of secrets, and recreate the secret is possible only if in the case of receipt of information from each of the participants), but poorly suited to perform the comparison. This approach has achieved great success in the project SIMAZP.

Logic circuit if much better for addition and multiplication with less efficiency, but can easily perform binary operations such as comparisons. This second approach, which is based on a system of Andrew Yao in the case of two participants, was implemented by Malkhi in a system of fair play (Eng. Fairplay system). This system also provides the ability to implement the required functionality provided by a high-level programming language as a logical circuit, which is then interpreted by the runtime and safely performed. There is also a system FairplayMP, an extension of Fairplay in case of more than two participants. A significant advantage of the method based on the logical circuit systems is that they are performed for a constant exchange of information, while the advantage of systems based on the method of arithmetic circuit is the ability to perform arithmetic operations (addition and multiplication) fast and easy.

It can be seen that the protocol can uniquely determine whose state is greater and thus participants may not know the status of each other.

The implementation of the scheme could be represented as complicated schemes based on the construction of distorted contours, the idea roots in the works of Andrew Yao. This idea is closely linked with performing the cryptographic technique. This technique is defined as a complicated scheme. While obfuscation scheme is traditionally considered as a method to determine the SFE (evaluation of security functions) or any cryptogrpahic goal in this article, such schemes are regarded as a tool to achieve cryptographic circuit with the necessary level of confidentiality, authenticity and non-repudiation. This will allow for a modular approach to the construction of cryptographic protocols.

Useful example

We assume that the protocol involves 2 participants, i.e. N = 2, and it is necessary to calculate the function F.

  • We represent the function F in the form of a logical circuit that is present the input of F in binary form, and the function implement operations using AND, OR and NOT. Then the input of the logic circuit are fed bits of arguments to the function F, and the circuit consists of logic gates AND, OR, NOT, and the output function F produces the result in binary form.
  • Participant p1 generated for each wire logic, two different random numbers k0 u k1: they are encrypted zero and one in the wire, respectively.
  • Participant p1 creates an encrypted spreadsheet calculations for each circuit.

G 2.png

E{k}(x) denotes the result of the encryption key value of x and k, and D {k}(y) - respectively denotes decryption key ciphertext y and k. It's need to select a symmetric encryption scheme with the next additional feature: when you try to decipher with the wrong key algorithm returns an error. The table has the following meaning: if we know the encrypted value of the signal k1 u k2 on the input wires gate w1 u w2, respectively, then we can calculate the encrypted signal value, calculated for all i = 1 ... 4 value di = D {k_2}(D{ k_1}(ci)). In three cases must be a mistake, but in the fourth we obtain the encrypted value k3 signal at the output of the gate.

  • Participant p1 passes the logic circuit and the encryption table for calculation of circuit party p2.
  • Participant p1 passes to p2 the encrypted value of the input signal wires to the inputs that correspond to the input data of the participant p1.
  • For each input wire wi corresponding to the input data p2, party p1 transmite to p2 protocol forgetful number k_i ^ {b_i}, where bi - bit value of the secret input p2. With this transfer of p1 can not know the value of bi. For each of the wires randomly selected their random numbers as zero and one, the participant p2 will not know what number is zero, and a unit for input wires participant p1, and hence can not learn the input user p1.

Now the party has p2 encrypted logic and encrypted values ​​for all input wires. It calculates the encrypted as described above, all the gates of the circuit one by one, and then transmits the encrypted result p1. Member p1 interprets the results and informs its p2. For simplicity we assume that the protocol involves 2 players, that is, the N = 2, and it is necessary to calculate the function F.

Yao’s Protocol for Two-Party Computation


In the mid 1980’s, Yao presented a constant-round protocol for securely computing any two- party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao’s protocol, along with a rigorous proof of security. Despite the importance of Yao’s protocol to the theory of cryptography, and in particular to the field of secure computation, to the best of our knowledge, this is the first time that an explicit proof of security has been published. In the setting of two-party computation, two parties with respective private inputs x and y, wish to jointly compute a functionality f(x,y) = (f1(x,y),f2(x,y)), such that the first party receives f1(x,y) and the second party receives f2(x,y). This functionality may be probabilistic, in which case f(x,y) is a random variable. Loosely speaking, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The definition of security that has become standard today blends these two conditions. In this paper, we consider the problem of achieving security in the presence of semi-honest (or passive) adversaries who follow the protocol specification, but attempt to learn additional information by analyzing the transcript of messages received during the execution.

Main Aspects

We denote the length of the inputs and the security parameter by n. We say that a function μ(·) is negligible in n (or just negligible) if for every positive polynomial p(·) and all sufficiently large n’s it holds that μ(n) < 1/p(n). Let S be an infinite set and let X = {Xs}s∈S and Y = {Ys}s∈S be distribution ensembles. We say that X and Y are computationally indistinguishable, denoted X ≡c Y , if for every non-uniform probabilistic polynomial-time distinguisher D and all sufficiently large s ∈ S, |Pr[D(Xs) = 1]−Pr[D(Ys) = 1]| is negligible in |s|. Finally, for a probabilistic machine M, we denote by a ← M(x) the event of obtaining a by invoking M on input x and a uniformly chosen random tape.

Yao’s protocol

Let f be a polynomial-time functionality (assume for now that it is deter- ministic), and let x and y be the parties’ respective inputs. The first step is to view the function f as a boolean circuit C. In order to describe Yao’s protocol, it is helpful to first recall how such a circuit is computed. Let x and y be the parties’ inputs. Then, the circuit C(x,y) is computed gate-by-gate, from the input wires to the output wires. Once the incoming wires to a gate g have obtained values α, β ∈ {0, 1}, it is possible to give the outgoing wires of the gate the value g(α, β). The output of the circuit is given by the values obtained in the output wires of the circuit. Thus, essentially, computing a circuit involves allocating appropriate zero-one values to the wires of the circuit. In the description below, we refer to four different types of wires in a circuit: circuit-input wires (that receive the input values x and y), circuit-output wires (that carry the value C(x,y)), gate-input wires (that enter some gate g), and gate-output wires (that leave some gate g).

Secure Two-Party Protocols for Semi-Honest Adversaries

The model that we consider here is that of two-party computation in the presence of static semi- honest adversaries. Such an adversary controls one of the parties (statically, and so at the onset of the computation) and follows the protocol specification exactly. However, it may try to learn more information than allowed by looking at the transcript of messages that it received. Since we only consider static semi-honest adversaries here, we will sometimes omit the qualification that security is with respect to such adversaries only. The definitions presented here are according to Goldreich in.

Two-party computation. A two-party protocol problem is cast by specifying a random process that maps pairs of inputs to pairs of outputs (one for each party). We refer to such a process as a functionality and denote it f : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ × {0, 1}∗, where f = (f1, f2). That is, for every pair of inputs x, y ∈ {0, 1}n, the output-pair is a random variable (f1(x, y), f2(x, y)) ranging over pairs of strings. The first party (with input x) wishes to obtain f1(x,y) and the second party (with input y) wishes to obtain f2(x,y). We often denote such a functionality by (x,y)→􏰁 (f1(x,y),f2(x,y)).Thus,forexample,theoblivioustransferfunctionalityisspecifiedby ((z0, z1), σ) 􏰁→ (λ, zσ), where λ denotes the empty string. When the functionality f is probabilistic, we sometimes use the notation f(x,y,r), where r is a uniformly chosen random tape used for computing f.

Privacy by simulation. Intuitively, a protocol is secure if whatever can be computed by a party participating in the protocol can be computed based on its input and output only. This is formalized according to the simulation paradigm. Loosely speaking, we require that a party’s view inaprotocolexecutionbesimulatablegivenonlyitsinputandoutput.2 Thisthenimpliesthatthe parties learn nothing from the protocol execution itself, as desired.