YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

CPSC 461b: Foundations of Cryptography Notes 22 (rev. 1)
Professor M. J. Fischer April 14, 2009



Lecture Notes 22

58 Simple Application of Oblivious Transfer

Consider the problem of privately evaluating a Boolean function f(x,y), where x is private to Alice and y is private to Bob. This corresponds to privately computing the functionality

F(x,y) = (f(x,y),f(x,y)).

Here’s the protocol.

  1. Alice, with private input x ∈{0,1}, prepares a table T :
       |
 y |f(x,y)
-0-|f(x,0)--
   |
 1 |f(x,1)

    She doesn’t know y, but she does know that the correct value f(x,y) is in her table. It’s either f(x,0) or f(x,1).

  2. Bob, with private input y, obtains line y of the table using OT12. Bob outputs f(x,y) without learning x.
  3. Bob sends f(x,y) to Alice, who also outputs it.

While this functionality seems almost too trivial to be interesting, it’s really not. For example, if f(x,y) = x y and Alice knows x = 0, then the answer f(x,y) does not tell her Bob’s value y, so it’s important that the protocol also not leak y in this case. Similarly, when Bob requests the value corresponding to row 0, he gets no information about x when the result f(x,0) = 0 comes back. (In fact he knew that already before getting row 0 from Alice.)

59 Private Circuit Evaluation using Shares

We now generalize the example of section 58 to any function ¯z = f(¯x,¯y ), where ¯x, ¯y , and ¯z are bit strings of lengths nx, ny, and nz, respectively, and f(¯x,y¯ ) is computed by a polynomial size Boolean circuit with nx + ny input wires and nz output wires. The corresponding functionality is

F(¯x,¯y) = (f(¯x,¯y),f(¯x,¯y)).

Alice furnishes the (private) input data to the first nx input wires. Bob furnishes the input data for the remaining ny input wires. Alice and Bob should learning nothing about each other’s inputs or the intermediate values of the circuit, other than what is implied by their own inputs and the nz output values.

A non-private evaluation of the circuit associates a Boolean value σw with each wire of the circuit. The input wires are associated with the corresponding input values. Let G be a gate with input wires u and v and output wire w that computes the Boolean function g(x,y). If σu is the value on wire u and σv the value on wire v, then the value on wire w is g(σuv). A complete evaluation of the circuit first assigns values to the input wires and then works its way down the circuit, assigning a value to the output wire of any gate whose inputs have already received values.

To carry out the evaluation privately, we split the value σw on each wire w into two random shares aw and bw. Neither share alone gives any information about σw, but together they allow σw to be computed as aw bw.

We now describe how Alice and Bob obtain their shares while maintaining the desired privacy. There are three cases, depending on whether w is an input wire controlled by Alice, an input wire controlled by Bob, or the output wire of a gate G.

Input wire controlled by Alice:
Alice knows σw. She generates a random share aw ∈{0,1} for herself and sends Bob his share bw = aw σw.
Input wire controlled by Bob:
Alice chooses a random share aw ∈ {0,1} for herself. She prepares a table T such that T[0] = aw and T[1] = aw 1. She uses OT12 to send T[σw] to Bob, who takes his share to be bw = T[σw].
Output wire of a gate G:
Let the input wires to G be u and v as before, and let g(x,y) be the function computed by G. Alice chooses a random share aw ∈{0,1} for herself. She computes the table
T[0,0] =   aw ⊕ g(au,av)

T[0,1] =   aw ⊕ g(au,av ⊕ 1)
T[1,0] =   aw ⊕ g(au + 1,av)
T[1,1] =   aw ⊕ g(au + 1,av + 1)
(Equivalently, T[r,s] = aw g(au r,av s) for r,s ∈{0,1}.) Alice sends T[bu,bv] = aw g(σuv) to Bob using OT14, who takes his share to be bw = T[bu,bv].

After having computed shares for all of the wires, Alice and Bob exchange their shares aw and bw for each output wire w.

Remarks:

  1. Alice and Bob’s shares for w are both independent of σw. This follows because Alice’s share is always chosen uniformly and independently at random, and Bob’s share is always the XOR of Alice’s random bit aw with something independent of of aw.
  2. This protocol requires ny executions of OT12 to distribute the shares for Bob’s inputs, and one OT14 for each gate in the circuit.1
  3. We emphasize that this protocol assumes semi-honest parties.
  4. This protocol generalizes readily from 2 to m parties. (The textbook in fact presents only the m-party version, which, although similar, is considerably more difficult to understand.)
  5. Bob does not even need to know what function each gate G computes. All he has to do is to use his private inputs or shares to request the right line of the table in each of the several OT protocols.

60 Private Circuit Evaluation using Garbled Circuits

A very different approach to private circuit evaluation is the use of garbled circuits. The idea here is that Alice prepares a garbled circuit in which each wire has associated with it a tag corresponding to 0 and a tag corresponding to 1. Associated with each gate are templates that allow the tag that represent the correct output value to be computed from the tags representing the input values. This is all done in a way that keeps hidden the actual values that the tags represent.

After creating the circuit, Alice, who knows all of the tags, uses OT12 to send Bob the tags corresponding to values on the input wires that he controls. She also sends him the tags corresponding to the values on the input wires that she controls. Bob then evaluates the circuit all by himself, computing the output tag for each gate from the tags on the input wires. At the end, he knows the tags corresponding to the output wires. Alice knows which Boolean values those tags represent, which she sends to Bob (either before or after he has evaluated the circuit). In this way, Bob learns the output of the circuit, which he then sends to Alice.

In greater detail, for each wire w, Alice generates two n-bit tags sw0 and sw1. Tag sw0 consists of an (n - 1)-bit random string followed by 0, and tag sw1 consists of an (n - 1)-bit random string followed by 1. The last bit of each tag is called its type. Alice also generates a random isomorphism τw : {sw0,sw1}→{0,1} that gives the correspondence between the pair of tags on a wire and the pair of Boolean values that they represent.

The tags are used as the keys for an encryption function E(). Let G(u,v) be a gate with input wires u and v and output wire w that computes the Boolean function g(x,y). With each pair of tag types i,j ∈{0,1}, we associate a template TG[i,j] = Esui(Esvj(sw)), where sw ∈{sw0,sw1}. The type of sw, that is, whether sw = sw0 or sw = sw1, is determined by the Boolean values σu = τu(sui) and σv = τv(svj). Namely, sw is chosen so that τw(sw) = g(σuv). Thus, template TG[i,j] represents the row in the truth table for g(σuv), but the correspondences between i and σu and between j and σv are both random and can’t be determined without knowing τu and τv. The garbled circuit attaches to each gate the four templates TG[0,0],TG[0,1],TG[1,0],TG[1,1].

Now, suppose Bob knows tags su ∈{su0,su1} and sv ∈{sv0,sv1} corresponding to input wires u and v of gate G. By looking at the last bit of su and sv, he can determine their types i and j, respectively. He next looks up the template TG[i,j] = Esu(Esv(sw)). Since he knows su and sv, he is able to decrypt this to obtain sw. In this way, he is able to recover the tag corresponding to the output value of G. He still doesn’t know the Boolean value that sw represents (which is τ(sw)), but he is able to proceed with the garbled circuit evaluation. Assuming Alice has published τw for each output wire w, then Bob is able to interpret the tag he computes for each output wire and learn its value.

There remains the problem of how Bob gets the tags corresponding to the input wires. For the wires controlled by Alice, she just sends the appropriate tags to Bob (but not the values that they represent). Thus, if Alice controls input wire u and its value is x, she sends Bob τu-1(x). For the wires that Bob controls, Alice uses OT12 to send him the appropriate tags. Thus, if Bob controls input wire v and its value is y, Alice prepares a table T[0] = τv-1(0) and T[1] = τv-1(1) and uses OT12 to send T[y] to Bob.

Remarks:

  1. The fact that Alice doesn’t learn anything about Bob’s private inputs follows from the fact that the only communication from Bob to Alice is in the OT12 protocol steps used to distribute the tags for the wires that Bob controls. The fact that Bob doesn’t learn anything about Alice’s private inputs or the intermediate values of the circuit follows from the fact (not so easily proved) that Bob doesn’t know the correspondence between tags and Boolean values and also that Bob is only able to decrypt one of the four templates associated with each gate.
  2. The security of the protocol relies on properties of the encryption function that we have not stated.
  3. This protocol requires only ny executions of OT12 and hence should be considerably faster to implement than the share-based protocol.
  4. This protocol also assumes semi-honest parties.
  5. This protocol does not obviously generalize to more than two parties.
  6. As with the share-based protocol, Bob does not need to know what function each gate G computes. All he needs to carry out his end of the protocol is the list of templates associated with each gate.

61 Homomorphic Encryption

An encryption function E() is said to be homomorphic with respect to an operator if one can compute E(x y) from E(x) and E(y) without decrypting either ciphertext.

Several well-known cryptosystems have a homomorphic property.

RSA
E(x y) = (xy)e mod n = xe ye mod n = E(x) E(y) mod n.
ElGamal
             rx+ry      rx+ry
E(xy)  =   (g     ,(xy)h     )
       =   (grx,xhrx) ⋅(gry,yhry)
       =   E(x) ⋅E(y),
where on pairs means componentwise multiplication.
Goldwasser-Micali
Public key is n = pq, y ∈ QNRn, E(b) = r2yb mod n for random r.
E (b1) ⋅E(b2) mod n  =   (r2yb1)(r2yb2) mod n
                         1   2 b21+b2
                    =   (r1r2) y     mod n
While this is not equal to E(b1 b2) = (r1r2)2yb1b2, is equal to r2yb1b2 for some possibly different choice of r. Hence, E(b1) E(b2) is a valid encryption of b1 b2, as desired.
Benaloh
This generalizes the Goldwasser-Micali scheme to give
  ∑k       ∏k
E (   bi) =    E (bi)
   i=1      i=1

As with Goldwasser-Micali, this is a randomized encryption scheme, so equality means only that the product is one of the possible encryptions of the sum of the bi’s.

One application of homomorphic encryption is to verifiable secret ballot elections. Each voter i has a vote bi. To cast the vote, the voter computes ci = E(bi) using the public encryption function of the voting authority and submits ci. Here we assume the Benaloh scheme. The voting authority publishes the ci’s for all of the voters, gives the tally t = bi, and gives the random string that shows E(t) = i=1kE(bi). Any voter can check that her own vote appears and can check that this equation holds, but she cannot determine anyone else’s votes. This makes sense in the situation where the voting authority is trusted to respect the privacy of votes but is not trusted to count the votes correctly. Much more is needed to turn this idea into a plausible voting system.

62 Flipping a Coin into a Well

The goal here is to compute the functionality F(1n,1n) = (b,b), where b ∈{0,1} is uniformly distributed and n is a security parameter. If aborts are possible, we also have to allow the possibility of (b,).

Figure 62.1 gives a very simple protocol based on bit-commitment.


Alice Bob



1. Chooses b1 ∈{0,1}, s ∈{0,1}n,
c1 = Cs(b1).  c
-→1
2.  b1
← - Chooses b2 ∈{0,1}.
3. Outputs b1 b2. (-b1→,s)
4. If c1 = Cs(b1) outputs b1 b2
else outputs .

Figure 62.1: Flipping a coin into a well.


This is just a sample of a protocol that, like zero-knowledge proof systems, is designed to work against a malicious adversary. How to prove the correctness of such protocols in general could be the topic of another course.