Another look at tightness

Sanjit Chatterjee, Alfred Menezes and Palash Sarkar
Selected Areas in Cryptography - SAC 2011, Lecture Notes in Computer Science, 7118 (2012), 293-319.

Abstract: We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption and disk encryption schemes in the multi-user setting.

Proceedings paper       Eprint paper (corrected and updated)