The Multi-user Security of MACs via Universal Hashing in the Ideal Cipher Model

The security of block-cipher-based hash-then-encrypt-type message authentication codes (MACs) has been proven with universal hash functions. Thus, the security of the underlying hash functions has been evaluated with the pseudo-random-permutation assumption, i.e., the block ciphers are replaced with random permutations to which an adversary cannot directly access. Due to a hybrid argument, this replacement offers tight multi-user bounds regarding online security. However, it degrades its offline security depending on the number of users \(u\) : from \(k\) bits (key size) to \(k- \log _2 u\) bits. We thus revise the definitions of universal hashing, \(\epsilon _1\) -regular and \(\epsilon _2\) -almost XOR universal, by involving ideal cipher, and show that multi-user security of several hash-then-encrypt-type MACs does not degrade from the single-user security.