TY - GEN
T1 - Security amplification for interactive cryptographic primitives
AU - Dodis, Yevgeniy
AU - Impagliazzo, Russell
AU - Jaiswal, Ragesh
AU - Kabanets, Valentine
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70350281850&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350281850&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00457-5_9
DO - 10.1007/978-3-642-00457-5_9
M3 - Conference contribution
AN - SCOPUS:70350281850
SN - 3642004563
SN - 9783642004568
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 128
EP - 145
BT - Theory of Cryptography - 6th Theory of Cryptography Conference, TCC 2009, Proceedings
T2 - 6th Theory of Cryptography Conference, TCC 2009
Y2 - 15 March 2009 through 17 March 2009
ER -