Lets work on an example for the garbled circuit discussed in Lecture 17 between Alice and Bob who want to compute f = NAND(a, b). a) (1 points) Suppose 0 and 1 on each wire is encrypted into a 5-bit number (0 to 31). Alice chooses A0 = 7, A1 = 17, B0 = 19, B1 = 3, and O0 = 18, O1 = 6. What are SA and SB? b) (2 points) For the encryption function ek1||k2 (x) = (k1+k2+x) mod 32, show how Alice garbles the circuit. c) (1 points) Suppose Alice chooses a = 1. What Alice should send to Bob as her input? d) (2 points) Suppose Bob chooses b = 0. Show how Bob encrypts his input with Alices help using OT. Assume Alices RSA public key to be (n = 35, e = 5). e) (1 points) Show how Bob computes with the garbled circuit and the encrypted inputs, and then communicates with Alice to determine f. f) (2 points) Show that Bob cannot decide Alices choice of a (assuming OT only reveals B0 but no additional information). As a hint, is it possible for Alice to choose A0 = 17, A1 = 7 while sending Bob exactly the same garbled circuit and inputs?

Garbled Circuit Alice encrypts every gate truth table with the help of the selection bits of its inputs. For the circuit O NAND(A, B) Alice sorts the rows into AB 00, 01,10, 11 Bob cannot tell what are SA and SB Bob can compute Of given Aa and Bb. Locate the row using the first bits of A2 and Bb, and then decrypt with da.|B,0 Could Bob learn A1-a, B1-b, or O1-f from the table? Garbled Circuit Alice encrypts every gate truth table with the help of the selection bits of its inputs. For the circuit O NAND(A, B) Alice sorts the rows into AB 00, 01,10, 11 Bob cannot tell what are SA and SB Bob can compute Of given Aa and Bb. Locate the row using the first bits of A2 and Bb, and then decrypt with da.|B,0 Could Bob learn A1-a, B1-b, or O1-f from the table