Security amplification is an important problem in Cryptography: starting with a ``weakly secure'' variant of some cryptographic primitive, the goal is to build a ``strongly secure'' variant of the same primitive. This question has been successfully studied for a variety of important cryptographic primitives, such as one-way functions, collision-resistant hash functions, encryption schemes and weakly verifiable puzzles. However, all these tasks were non-interactive. In this work we study security amplification of {\em interactive} cryptographic primitives, such as message authentication codes (MACs), digital signatures (SIGs) and pseudorandom functions (PRFs). In particular, we prove direct product theorems for MACs/SIGs and an XOR lemma for PRFs, therefore obtaining nearly optimal security amplification %constructions for these primitives.
Our main technical result is a new Chernoff-type theorem for what we call {\em Dynamic Weakly Verifiable Puzzles}, which is a generalization of ordinary Weakly Verifiable Puzzles which we introduce in this paper.