Instructor: Daniele Micciancio (UCSD)

Randomized Encodings

A Randomized Encoding for a class of functions F = {f:X -> Y} is defined by three efficient algorithms (encode,decode,simulate) such that

decode(encode(f,x,r)) = f(x)
simulate(f,f(x)) ~ {encode(f,x,r) | r <- R}

The last condition in the definition may be interpreted as equality, statistical closeness or computational indistinguishability of probability distributions.

Intuitively, encode maps a function f to a randomized function f'(x;r) = encode(f,x,r) that is equivalent to f in the sense that f(x) can be computed from f'(x;r), and the distribution f'(x;R) can be computer from f(x). Usually randomized encodings are used to turn an arbitrary function f into an easier to compute one f'.

Note: The first condition decode(encode(f,x,r)) = f(x) is usually interpreted as a correctness property, while the second one as a security property. We used a simulation based definition of security. One may also formulate the weaker indistinguishability requirement that for all f(x0) = f(x1), we have {encode(f,x0,r) | r <- R} ~ {encode(f,x1,r) | r <- R}.

Bootstrapping Functional Encryption

Randomized encodings can be used to expand the set of functions to which a functional encryption scheme (or other cryptographic primitive) can be applied to. Here we consider the application of randomized encoding to functional encryption.

Let (Setup',KDer',Enc',Dec') be a functional encryption scheme for a class of functions F', and (encode,decode,simulate) a randomized encoding mapping function f (in some set F) to a function f'(.,.) in F'. We define a new functional encryption scheme (Setup,KDer,Enc,Dec) as follows:

Setup() = Setup'()
KDer(sk,f) = KDer'(sk,encode(f,.,.))
Enc(pk,x) = { Enc'(pk,(x,r)) | r <- R }
Dec(fk,c) = decode(Dec'(fk,c))

Correctness is easy to check: for any keys (pk,sk) <- Setup() = Setup'(), we have

Dec(KDer(sk,f),Enc(pk,x)) = decode(Dec'(KDer'(sk,encode(f,.,.)),Enc'(pk,(x,r))))
                          = decode(encode(f,x,r)) = f(x)

What about security? We prove that if FE' is NA-SIM secure, then FE is also NA-SIM secure (using the standard, simulation-based, definition of randomized encoding.)

Questions:

• Can you prove that if FE' is AD-SIM secure, then FE is also AD-SIM secure?
• Can you prove that if FE' is (NA or AD) IND secure, then FE is also (NA or AD) IND secure?
• If yes, is it enough assume the randomized encoding is IND secure?
• If no, can you prove the implication for some natural strengthening of IND security?

Yao Garbled Circtuits

Building blocks:

Garbled circuits can be implemented using just a pseudorandom generator, but, conceptually, it is best to think of them as using the following two primitives:

• A private key one-time encryption scheme (Enc, Dec). For example, Enc(k, m)=G(k)⊕m where G is a pseudorandom generator.
• A secret sharing scheme (Share, Rec) that splits a key k into two random shares (s₀, s₁)←Share(k) such that Rec(s₀, s₁)=k reconstructs the key. The security property is that the individual distribution of each share is independent of k, i.e., (s₀, __) ← Share(k) and (s₀, __) ← Share(0) produce identical distributions, and similarly for (__, s1)←Share(k) and (__, s1)←Share(0). As a concrete example, one may define Share(k)=(s, k ⊕ s) (for a randomly chosen s) and Rec(s₀, s₁)=s₀ ⊕ s₁)

Circuits

In order to define garbled circuits, and the associated randomized encoding, we need first to provide a formal definition of (boolean) circuit. We consider circuits with labeled wires W and gates G. For simplicity, we fix the set Y of output wire labels, and write In(C) for the input wires of a circuit C. Each circuit C computes a function from {0, 1}^In(C) to {0, 1}^Y. Circuits, their input wires and evaluation functions, are defined as follows:

• Base case: the trivial circuit C = Id has input wires In(Id)=Y, no gates, and computes the identity function over {0, 1}^Y.
• Inductive case: given a circuit C, sublist of input wires W ⊆ In(C), and new gate g with input wires {g₀, g₁}, one can build a new circuit C′=(g/W/C) with inputs In(C′) = {g₀, g₁}∪(In(C)\W) that computes the function C′(X)=C(X[y/W]) where y = g(X[g₀],X[g₁]) is the output of gate g, and X[y/W] is the input vector obtained from X by assigning all the wires in W to y.

Circuit Garbling

The garbling of a circuit C consists of

• A list of garbled tables T_g[0, 1][0, 1], one for each gate g in the circuit, and each table consisting of of 4 ciphertexts.
• A list containing a random bit r_w and 4 secret key shares s_w[0, 1][0, 1] for each input wire w ∈ In(C).

Garbled circuits are defined by induction on the circuit size as follows. For the base case, Garble(Id)=[(0, 0, 0)]_w, i.e., r_w = 0 and s_w[0, 1][0, 1]=0 for all output wires w ∈ In(Id)=Y. (The value of s_w is irrelevant, and may be defined arbitrarily.) For the inductive case, Garble(g/W/C) is computed as follows:

• Compute (r, s, T)←Garble(C) for the subcircuit C

• Pick random bits r_g0, r_g1, random keys k_g[x₀][x₁], and generate the secret shares (s_g0[x₀][x₁],s_g1[x₁][x₀]) ← Share(k_g[x₀][x₁]) for all x₀, x₁ ∈ {0, 1}.

• Let T_g[x₀][x₁]=Enc(k_g[x₀][x₁],m[W]) where m[W] is the list of messages m[w]=(a_w, s_w[a_w]) with a_w = g(x₀ − r_g0, x₁ − r_g1)+r_w and w ∈ W.

• Output (r, s, T) extended with T_g and with r_W, s_W replaced by r_g0, r_g1 and s_g0, s_g1.

Randomized Encoding

The randomized encoding of C on input X[In(C)] is obtained by garbling the circuit (r, s, T)←Garble(C), computing a_w = X[w]+r_w for all w ∈ In(C), and producing the encoding encode(C)=({a_w, z_w}_{w ∈ In(C)}, T) where z_w = s_w[a_w].

The decoding function uses the tables T to compute a_w and z_w = s_w[a_w] for all wires, and outputs the value decode(a, z, T)=[a_w]_w ∈ Y of the output wires. More specifically, in the base case C = Id, decode(a, z, []) = [a_w]_w ∈ Y can extract the output values directly from the input. In the inductive case (g/W/C), decode(a, z, T)

• parses (a_g0, a_g1, a′) = a, (z_g0, z_g1, z′) = z and (T_g, T′) = T,

• computes k′_g = Rec(z_g0[a_g1],z_g1[a_g0]) and (a_W, z_W)=Dec(k′_g, T_g[a_g0][a_g1])

• extends a′,z′ with a_W, z_W, and calls decode((a′,a_W),(z′,z_W),T).

It can be easily verified by substitution and induction that the randomized encoding is correct, i.e., decode(encode(C, X)) = C(X) for any circuit C and input X.

Security

In order to prove security, we need to give a simulator such that for any circuit C and input X, simulate(C, C(X)) is computationally indistinguishable from encode(C, X). The simulator works similarly to the garbling/encoding procedure, but encrypting the same message in each entry of the tables. The base case C = Id is trivial: on input X[Y], the simulator outputs (X[i],0, 0) for all i ∈ In(C)=Y. In the inductive case, simulate(g/W/C, X[Y])

• Computes (a, z, T)←simulate(C, X[Y])

• Pick random bits a_g0, a_g1, random keys k_g[x₀][x₁], and generate the secret shares

  • (z_g0[a_g1],z_g1[a_g0]) ← Share(k_g[a_g0][a_g1])
  • (z_g0[¬a_g1],_____) ← Share(0)
  • (_____,z_g1[¬a_g0]) ← Share(0)

• Let T_g[x₀][x₁]=Enc(k_g[x₀][x₁],m[W]) where m[W] is the list of messages m[w]=(a_w, z_w) for w ∈ W

• Output (a, z, T) extended with T_g and with a_W, z_W replaced by a_g0, a_g1 and z_g0, z_g1.

Notice that the main difference between the simulation procedure and encode(C, X) is that the four entries of the table T_g[x₀][x₁] encrypt the same message as T_g[a_g0][a_g1]. Since the keys k_g[x₀][x₁] with (x₀, x₁)≠(a_g0, a_g1) are used only for encryption, and each is used only once, we may use the indistinguishability property of the one-time encryption scheme to let the simulator encrypt the same messages as the encoding procedure. Once that is done, by the security properties of the secret sharing scheme, one may replace the definition of z_g0[¬a_g1] and z_g1[¬a_g0] with (z_g0[¬a_g1],__)←Share(k_g[a_g0][¬a_g1]) and (__, z_g1[¬a_g0]) ← Share(k_g[¬a_g0][a_g1]). The output of the resulting program is identically to the encoding procedure. Formally, the proof of security consists of a hybrid argument that performs the above operations for the first n levels of recursion.