Portal de Periódicos da CAPES

How to Thwart Birthday Attacks against MACs via Small Randomness

2010; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-13858-4_13

1611-3349

Kazuhiko Minematsu,

Coding theory and cryptography

The security of randomized message authentication code, MAC for short, is typically depending on the uniqueness of random initial vectors (IVs). Thus its security bound usually contains O(q 2/2 n ), when random IV is n bits and q is the number of MACed messages. In this paper, we present how to break this birthday barrier without increasing the randomness. Our proposal is almost as efficient as the well-known Carter-Wegman MAC, uses n-bit random IVs, and provides the security bound roughly O(q 3/22n ). We also provide blockcipher-based instantiations of our proposal. They are almost as efficient as CBC-MAC and the security is solely based on the pseudorandomness of the blockcipher.