DEPARTMENT OF COMPUTER SCIENCE
|CPSC 461b: Foundations of Cryptography||Handout #2|
|Professor M. J. Fischer||February 9, 2009|
Problem Set 1
Due in class on Thursday, February 19, 2009.
Problem 1 Chernoff bound – application 1
Consider a biased coin with probability p = 1∕3 of landing heads and probability 2∕3 of landing tails. Suppose the coin is flipped some number n of times, and let Xi be a random variable denoting the ith flip, where Xi = 1 means heads, and Xi = 0 means tails. Use the Chernoff bound to determine a value for n so that the probability that more than half of the coin flips come out heads is less that 0.001.
Problem 2 Chernoff bound – application 2
At the Yale-Harvard hockey game on February 6, Yale made 50 shots on the Harvard goal and scored 5 times, whereas Harvard made 15 shots on the Yale goal and scored only once. Assume that both teams had equally good goalies and that for each team, the probability is p = 0.1 of a shot scoring a goal. Clearly, the expected number of goals is np, where n is the number of shots. For Yale, the actual number of goals g exactly matched the expectation, but for Harvard with 15 shots, the actual number of goals (1) fell considerably short of the expected number (1.5).
The purpose of this problem is to assess how unusual it is that Harvard scored fewer than the expected number of goals given the number of shots on the goal and the assumed success probability of each shot. In the following, let n = 15, g = 1, p = 0.1, and q = Pr[# goals after n shots ≤ g]. We wish to find a “good” upper bound on q.
Problem 3 Derandomization
Let M be a ppTM that accepts a language L and runs in time p(n) for some polynomial p(⋅). Let x be an input string of length n and r a random choice string of length p(n) ≫ n. Let δ(x,r) = 1 if M(x,r), the output of M with coin toss sequence r, gives the correct answer about x’s membership in L, and let δ(x,r) = 0 otherwise. Suppose Pr[M(Un,Up(n)) is correct] = 1 - 2∕2n.
How large can we make the success probability of M(Un,r) by setting the second input of M to a fixed string r? That is, what is the best lower bound on
that is implied by the given information, where maxr is taken over all binary strings of length p(n)?
[Note: This problem generalizes a fact used in the proof of Theorem 4, section 11, lecture notes 3.]
Problem 4 One-way functions and the -versus- question
[Textbook, Chapter 2, Exercise 3.]