Ragesh Jaiswal

Security Amplification for Interactive Cryptographic Primitives

Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal and Valentine
Kabanets (appearing at TCC'09)

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 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 for these primitives.

Our main technical result is a new Chernoff-type theorem for what we
call Dynamic Weakly Verifiable Puzzles, which is a generalization of
ordinary Weakly Verifiable Puzzles which we introduce in this paper.