Homework 2 Problem 1: Pseudorandom Generators Problem 2

CSL759: Cryptography and Network Security
Feb 6, 2014
Homework 2
Instructor: Shweta Agrawal
Notation.
Due: Never!
We let || denote the concatenation operator.
Problem 1: Pseudorandom Generators
a. Let G : {0, 1}k → {0, 1}2k be a PRG. Prove that it is also a OWF.
b. Let G : {0, 1}k → {0, 1}k+1 be a PRG. Prove that G0 (x1 ||x2 ) = G(x1 )||G(x2 ) is also a PRG.
c. Let G : {0, 1}k → {0, 1}2k be a PRG. Construct an exponential time adversary who can
distinguish between G(x) and R with probability greater than 1/2.
d. In the PRG construction we saw in class, the hardcore bit h(x) was output at every step while
f (x) was fed forward to the next PRG. If we instead output the first bit of f (x) and fed the
remaining k bits to the next PRG, would this still be secure? If yes, provide a proof. If no,
provide an attack (or reasoning for insecurity).
Problem 2: Hardcore bit
Construct a function which is one way but no bit of its input it hardcore.
Problem 3: One Way Functions
Suppose that g(x) is a length preserving one-way function. Let x = x1 ||x2 where |x1 | = |x2 | .
For the following functions, use a reduction to prove that the function is one-way, or give a
counterexample showing that it is not one-way.
a. f (x) = g(x1 ⊕ x2 ).
|x|
0
if exactly 1 bit of x1 is set to 1,
b. f (x) =
.
0|x1 | ||g(x2 ) otherwise
|x|
0
if at least 1 bit of x1 is set to 1,
c. f (x) =
.
0|x1 | ||g(x2 ) otherwise
Problem 4: RSA
Given an RSA modulus n, an exponent e, and a value y = xe mod n, it is hard to determine whether
the least significant bit of a message (LSB(x)) is 0 or 1.
Now, consider the most significant bit of a message, defined as follows:
0 if x < n/2
M SB(x) =
1 if x > n/2
HW 2-1
Prove that if it is hard to determine whether the LSB is 0 or 1, it is also hard to determine
whether the MSB is 0 or 1. In other words, given an oracle A that on input (n, e, y = xe mod n)
outputs M SB(x) with non-negligible advantage, construct an oracle B to output LSB(x) with
non-negligible advantage.
Hint:
Consider what happens to LSB(2x mod n), given that we know n is odd.
HW 2-2

Download Report