HW5

CS151: Intro to Cryptography and Computer Security
Mar 18, 2014
Homework 5
Instructor: Anna Lysyanskaya
Due: Apr 1, 2014
Problem 1: Fun with PRGs
Let G, G1 , G2 : {0, 1}n → {0, 1}2n be PRGs (for every n), and let s, s1 , s2 ∈ {0, 1}k . For each of the
following, prove that it is a PRG or provide a counterexample to show that it is not a PRG.
¯ = x ⊕ 1|x| , i.e. x
¯ is obtained by flipping every bit of x.
a. Ga (s) = G(s), where x
b. Gb (s) = G1 (s) ◦ G2 (s).
c. Gc (s) = G(s1 ) ◦ G(s2 ) where s = s1 (◦)s2 (so s = s1 ◦ s2 , |s1 | =
j
|s|
2
k
l m
, and |s2 | = |s|
2 ).
Problem 2: Hardcore Bits
Consider the following definition of a hardcore bit:
Definition 1. Let G be a key generation algorithm. Let BPK be an efficiently computable Boolean
function BPK : DomainPK 7→ {0, 1}; note that potentially both the description of BPK and the domain DomainPK may depend on the public key PK ← G(1k ). Let fPK : DomainPK 7→ RangePK be
any efficiently computable function from domain DomainPK to range RangePK . BPK is a hardcore
bit of fPK if the following two distributions are indistinguishable:
D0 (1k ) = {PK ← G(1k ), x ← DomainPK : fPK (x), BPK (x)}
D1 (1k ) = {PK ← G(1k ), x ← DomainPK : fPK (x), BPK (x) ⊕ 1}
Show that any one-to-one function that has a hardcore bit must be one-way.
Note: to help convince yourself this is true, try to think of a many-to-one function with a hardcore
bit that is not one-way.
Problem 3: Hardcore Bits in RSA
We saw in class that the least-significant bit of the message for RSA encryption is hard-core; that
is, given an RSA modulus n, the public exponent e and an encryption y = xe mod n, it is hard to
distinguish LSB(x) from random.
We can also show that the most-significant bit is hard-core, where the most-significant bit is
defined as
0 if x < n/2
M SB(x) =
1 if x > n/2
Prove that if the least-significant bit is hard-core, so is the most-significant bit. In other words,
given an oracle A that on input (n, e, y = xe mod n) outputs M SB(x) with non-negligible probability, construct an oracle B to output LSB(x) with non-negligible probability.
Hint:
Consider what happens to LSB(2x, n) given that we know n is odd.
HW 5-1
Problem 4: One-Way Functions Under XOR
Let f1 and f2 be OWFs with the same-size output (i.e., if |x1 | = |x2 |, then |f1 (x1 )| = |f2 (x2 )|). Now
|x|
consider f (x) = f1 (x1 ) ⊕ f2 (x2 ), where x = x1 ◦ x2 so that |x1 | = d |x|
2 e, and |x2 | = b 2 c, and when
XORing strings of unequal length, you can pretend that blank characters at the end of the shorter
strings are 0’s.
a. Assuming that length-preserving one-way functions exist, give an example of OWFs f1 and an
f2 such that f is a OWF, and prove that in this case f is a OWF. You must also show that
your choices of f1 and f2 are OWFs.
b. Assuming that length-preserving one-way functions exist, give an example of OWFs f1 and f2
such that f is NOT a OWF, and prove that in this case f is not a OWF. You must also show
that your choices of f1 and f2 are OWFs.
HW 5-2

Download Report