Security amplification for interactive cryptographic primitives

Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 6th Theory of Cryptography Conference, TCC 2009, Proceedings
Number of pages18
StatePublished - 2009
Event6th Theory of Cryptography Conference, TCC 2009 - San Francisco, CA, United States
Duration: Mar 15 2009Mar 17 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5444 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th Theory of Cryptography Conference, TCC 2009
Country/TerritoryUnited States
CitySan Francisco, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Security amplification for interactive cryptographic primitives'. Together they form a unique fingerprint.

Cite this