DEPARTMENT OF COMPUTER SCIENCE
|CPSC 467b: Cryptography and Computer Security||Handout #16|
|Professor M. J. Fischer||April 23, 2010|
Problem Set 6
Due on Monday, May 3, 2010.
In the problems below, “textbook” refers to Wade Trapp and Lawrence C. Washington, Introduction to Cryptography with Coding Theory, Second Edition, Prentice-Hall, 2006.
Problem 1: Zero Knowledge
[The following is a modification of Problem 14-3 of the textbook.]
Naive Nelson thinks he understands zero-knowledge protocols. He wants to prove to Victor that he knows the factorization of n (which equals pq for two large distinct primes p and q) without revealing this factorization to Victor or anyone else. Nelson devises the following procedure: Victor chooses a random integer x mod n, computes y = x2 mod n, and sends y to Nelson. Nelson computes a square root s of y (mod n) and sends s to Victor. Victor checks that s2 ≡ y (mod n). Victor repeats this 20 times.
Problem 2: Indistinguishability
Happy Hacker wanted a good source of random bits, so he downloaded a cryptographically secure pseudorandom sequence generator G(s) from the Internet. G maps seeds of length n to binary sequences of length ℓ. Knowing the importance of seeding the generator with truly random bits, he arranged to obtain the seed s from /dev/random. Having done so, he couldn’t see any good reason to “waste” the random bits in s, so he decided to output the string s ⋅ G(s), giving n + ℓ output bits in all. In other words, he built a new pseudorandom number generator G′(s) = s ⋅ G(s).
Unfortunately, G′(s) is not cryptographically secure, even when seeded properly with a truly random seed s. Explain why, and describe a judge J that can distinguish the distribution G′(S) from U. Here, S is the uniform distribution over the seed space, and U is the uniform distribution over binary strings of length n + ℓ.
Problem 3: Shamir Secret Splitting
Let (x1,y1),…,(x5,y5) be shares of a secret s in a (2,5) secret splitting scheme over Zp. Assume one of the shares has been corrupted and does not lie on the dealer’s polynomial, but nobody knows which the bad share is.
For each value of k = 1,…,5, answer the following questions with respect to an arbitrary subset of shares R of size k.
Problem 4: Oblivious Transfer Variant OT1k
The 1-of-k oblivious transfer of a selected secret protocol computes the functionality
This means that Alice initially has k “secrets” s1,…,sk, and Bob initially has the index j of a secret that he would like to know. At the end of the protocol, Bob learns sj but nothing else, and Alice learns nothing. That is, Alice has no information about Bob’s value j, and Bob has no information about any sℓ other than sj.
Figure 1 gives a protocol for OT1k in the semi-honest model.