DEPARTMENT OF COMPUTER SCIENCE
|CPSC 467b: Cryptography and Computer Security||Handout #9|
|Professor M. J. Fischer||April 12, 2013|
Problem Set 6
Due on Friday, April 19, 2013.
Instructions Work the problems below, prepare your answers in electronic form, and submit your solutions using the submit script on the Zoo. Remember to specify “6” for the problem number argument to submit.
As always, you must properly cite all resources that you use to solve the problems.
Problem 1: Indistinguishability
Happy’s roommate, Naive Nelson, is building a pseudorandom sequence generator. He has found a PRSG G that takes a 128-bit seed s and outputs a bit string x of length 1000. Naive wants to generate bit strings of length ℓ = 100,000, so he creates a new generator G′ that works in stages. His idea is to use G repeatedly, obtaining 1000 bits each time. To avoid getting repetitions of the same 1000-bit string, he uses the last 128 bits of each block as a seed for the next block.
Here is his algorithm for computing G′(s):
In this notation, λ denotes the empty string, || denotes concatenation, and last(k,x) returns the last k bits of x.
Problem 2: Shamir Secret Splitting
Alice is leaving for a year of study abroad. She has surprising news that she wants to share with 12 friends, but she doesn’t want to tell them before she leaves home since she would feel embarrassed to be present when they learn her secret. Although she trusts her friends, they are naturally curious. Moreover, she’s concerned that the parents of two of her friends might discover their shares, and she really doesn’t want the parents to find out what her surprise is.
She decides to split her secret into 12 shares and give one to each friend so that any three or more friends can cooperate to discover the secret, but two are not enough. She uses the (τ,k) threshold scheme that she learned in crypto, distributes the shares, and flies off. Unfortunately, unknown to everyone, one of the shares gets corrupted in transit.
By the time she leaves, three of her friends have gone home to Santa Monica, four have gone on a trip to Las Vegas, and the remaining five are still in New Haven.
Each of the three groups of friends then gets together in person and uses the algorithm presented in class to recover the secret.