YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 461b: Foundations of Cryptography | Handout #8 | |

Professor M. J. Fischer | April 8, 2009 | |

Problem Set 3

Due in class on Thursday, April 16, 2009.

Problem 1 Computational indistinguishability preserved by efficient algorithms

[Textbook, Chapter 3, Exercise 2.]

Problem 2 Smoothness of probability mass

[Textbook, Chapter 3, Exercise 12.]

Problem 3 Modifications of a pseudorandom generator

[Textbook, Chapter 3, Exercise 15.]

Problem 4 Role of error in interactive proofs

[Textbook, Chapter 4, Exercise 5.]

Problem 5 Secrecy of commitment based on one-way permutations

A bit-commitment scheme based on a one-way permutation is presented in section 48.1 of lecture notes 19. A partial proof of secrecy is presented, but the task of showing that the constructed algorithm A′ has the desired advantage is left to the reader. Complete the proof by defining a suitable non-negligible function ϵ′(n) and showing that A′(f(s)) has the required advantage at guessing b(s).