HW1 Clarifications
Problem 2: the notation $max_{T \subseteq U} f(T)$ can be rewritten as $max({f(T)}_{T \subseteq U})$, if that is clearer. In short, it means for all subsets T of U, compute f(T), and then output the greatest value among the values of f(T). In this case, $f(T) = |Pr[X \in T] - Pr[Y\in T]|$
Problem 7: when I say ciphertexts completely reveal the plaintext with probability 1, I mean that
it should be possible for a human to extract the plaintext from any ciphertext using no more than
a pencil and paper, and it shouldn’t take a human very long to do this. The point here is to
design the most intuitively insecure scheme that satisfies this definition.
Problem 8a: you may use the requirement for perfect correctness in both parts of this problem,
Problem 6a,b: You can assume that Gen, Enc, and Dec are all efficient algorithms. We had not discussed the meaning of efficiency at the time that the homework was assigned, so I was a bit loose with notation, but you can also assume that Gen gets 1^n as input. This implies that there must be some upper bound on the number of random coins that Gen, Enc, and Dec can read from their random tapes.
Problem 6c: Here I am asking for a short proof that if there is a randomized distinguisher that violates the conditions of perfect indistinguishability, then there is also a deterministic distinguisher that does the same. I am asking only for you to show that such a distinguisher must exist; it does not need to be efficient, nor is there any requirement that its code be efficiently computable.
if it helps.