Security Amplification for Interactive Cryptographic Primitives
Source: New York University
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 the authors study security amplification of interactive cryptographic primitives, such as Message Authentication Codes (MACs), Digital Signatures (SIGs) and pseudorandom functions (PRFs). In particular, they prove direct product theorems for MACs/SIGs and an XOR lemma for PRFs, therefore obtaining nearly optimal security amplification for these primitives.