Elizabeth Yang 1. On page 3, the garbled circuit summary says that "The garbled gate consists of the four resulting ciphertexts, in a random order." Why do the resulting ciphertexts need to be arranged in random order? Explain what would leak if they weren't. For the “AND” example in particular, consider the case where Evan doesn’t want to collaborate, so he should not know whether or not Ginny does. If Ginny gives him the garbled output that is not permuted, Evan may be able to use the lexicographic structure of the table to guess what g is. For instance, in Fig 1, say Ginny does not permute and Evan successfully decodes the third line. If Evan knows that the table entries are in lexicographic order, he can guess that g = 1, as g = 0 would correspond to an earlier line on the list. Therefore, not permuting may leak g to Evan. In general circuits that could be more complicated than AND, it still seems likely that knowing how an output table is organized can let Evan deduce some of Ginny’s information. 2. Garbling schemes like Yao's scheme are "one-time" schemes. Namely, they are secure if an attacker having a garbled circuit receives at most one encoded input for that garbled circuit. What breaks if an attacker receives more than one input? In other words, consider that Giny and Evan want to use garbled circuits to compute the bit-wise AND of two 5-bit numbers. Give an example of two such numbers for which, if Giny gives the encodings to Evan, Evan can compute the encoding of any other 5-bit number. Say Ginny and Evan are using the garbled AND scheme from the paper on each of their 5 input bits of their numbers. Then, if Ginny sends both 00000 and 11111, and Evan chooses any number like 01010 that has at least one of each kind of bit, then Evan will see each possible bit combination (g = 0, e = 0; g = 0, e = 1; g = 1, e = 0; g = 1, e = 1), and he will get the keys for each bit combination. Having access to all 4 possible keys will allow Evan to compute the encoding of every possible combination of inputs.