We propose message authentication codes (MACs) that combine a block cipher and an additional (keyed or unkeyed) permutation. Our MACs are provably secure if the block cipher is pseudorandom and the additional permutation has a small differential probability. We also demonstrate that our MACs are easily implemented with AES and its 4-round version to obtain MACs that are provably secure and 1.4 to 2.5 times faster than the previous MAC modes of AES such as the CBC-MAC-AES.
['Kazuhiko Minematsu', 'Yukiyasu Tsunoo']
Provably secure MACs from differentially-uniform permutations and AES-Based implementations