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

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

Here’s the protocol.

- Alice, with private input x {0,1}, prepares a table T :
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).

- Bob, with private input y, obtains line y of the table using OT
_{1}^{2}. Bob outputs f(x,y) without learning x. - 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.)

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

Alice furnishes the (private) input data to the first n_{x} input wires. Bob furnishes the input data for the
remaining n_{y} 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 n_{z} 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(σ_{u},σ_{v}). 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 a_{w}
and b_{w}. Neither share alone gives any information about σ_{w}, but together they allow σ_{w} to be computed as
a_{w} ⊕ b_{w}.

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 a_{w}{0,1} for herself and sends Bob his share b_{w}= a_{w}⊕ σ_{w}. - Input wire controlled by Bob:
- Alice chooses a random share a
_{w}{0,1} for herself. She prepares a table T such that T[0] = a_{w}and T[1] = a_{w}⊕ 1. She uses OT_{1}^{2}to send T[σ_{w}] to Bob, who takes his share to be b_{w}= 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 a
_{w}{0,1} for herself. She computes the table_{w}⊕g(a_{u}⊕r,a_{v}⊕s) for r,s {0,1}.) Alice sends T[b_{u},b_{v}] = a_{w}⊕g(σ_{u},σ_{v}) to Bob using OT_{1}^{4}, who takes his share to be b_{w}= T[b_{u},b_{v}].

After having computed shares for all of the wires, Alice and Bob exchange their shares a_{w} and b_{w} for each
output wire w.

Remarks:

- 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 a_{w}with something independent of of a_{w}. - This protocol requires n
_{y}executions of OT_{1}^{2}to distribute the shares for Bob’s inputs, and one OT_{1}^{4}for each gate in the circuit.^{1} - We emphasize that this protocol assumes semi-honest parties.
- 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.)
- 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.

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 OT_{1}^{2} 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 s_{w}^{0} and s_{w}^{1}. Tag s_{w}^{0} consists of an
(n - 1)-bit random string followed by 0, and tag s_{w}^{1} 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} : {s_{w}^{0},s_{w}^{1}}→{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 T_{G}[i,j] = E_{sui}(E_{svj}(s_{w})), where s_{w} {s_{w}^{0},s_{w}^{1}}. The type of s_{w},
that is, whether s_{w} = s_{w}^{0} or s_{w} = s_{w}^{1}, is determined by the Boolean values σ_{u} = τ_{u}(s_{u}^{i}) and
σ_{v} = τ_{v}(s_{v}^{j}). Namely, s_{w} is chosen so that τ_{w}(s_{w}) = g(σ_{u},σ_{v}). Thus, template T_{G}[i,j] represents the
row in the truth table for g(σ_{u},σ_{v}), 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 T_{G}[0,0],T_{G}[0,1],T_{G}[1,0],T_{G}[1,1].

Now, suppose Bob knows tags s_{u} {s_{u}^{0},s_{u}^{1}} and s_{v} {s_{v}^{0},s_{v}^{1}} corresponding to input wires u and
v of gate G. By looking at the last bit of s_{u} and s_{v}, he can determine their types i and j, respectively. He
next looks up the template T_{G}[i,j] = E_{su}(E_{sv}(s_{w})). Since he knows s_{u} and s_{v}, he is able to decrypt this
to obtain s_{w}. 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 s_{w} represents (which is τ(s_{w})), 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 OT_{1}^{2} 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 OT_{1}^{2} to send T[y] to
Bob.

Remarks:

- 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 OT
_{1}^{2}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. - The security of the protocol relies on properties of the encryption function that we have not stated.
- This protocol requires only n
_{y}executions of OT_{1}^{2}and hence should be considerably faster to implement than the share-based protocol. - This protocol also assumes semi-honest parties.
- This protocol does not obviously generalize to more than two parties.
- 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.

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 = x^{e}⋅ y^{e}mod n = E(x) ⋅ E(y) mod n. - ElGamal
- Goldwasser-Micali
- Public key is n = pq, y QNR
_{n}, E(b) = r^{2}y^{b}mod n for random r._{1}⊕ b_{2}) = (r_{1}r_{2})^{2}y^{b1⊕b2}, is equal to r^{2}y^{b1⊕b2}for some possibly different choice of r. Hence, E(b_{1}) ⋅ E(b_{2}) is a valid encryption of b_{1}⊕ b_{2}, as desired. - Benaloh
- This generalizes the Goldwasser-Micali scheme to give
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 b

_{i}’s.

One application of homomorphic encryption is to verifiable secret ballot elections. Each voter
i has a vote b_{i}. To cast the vote, the voter computes c_{i} = E(b_{i}) using the public encryption
function of the voting authority and submits c_{i}. Here we assume the Benaloh scheme. The voting
authority publishes the c_{i}’s for all of the voters, gives the tally t = ∑
b_{i}, and gives the random
string that shows E(t) = ∏
_{i=1}^{k}E(b_{i}). 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.

The goal here is to compute the functionality F(1^{n},1^{n}) = (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.

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.