In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for $n$ times, the receiver's advantage in guessing the encrypted bit is negligibly close to $1-(1-\eps)^n$.
Our results for hardness amplification follow just by observing that some of the known proofs for Yao's lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch.
Category / Keywords: foundations / Commitment schemes, Hardness amplification and degradation, Secrecy amplification and degradation, Oblivious transfer, XOR lemmas Publication Info: TCC 2008 Date: received 6 Mar 2008 Contact author: shaih at alum mit edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20080311:035056 (All versions of this report) Discussion forum: Show discussion | Start new discussion