Abstract:
Let the AEAD-mode MGM be used only for integrity protection, and the nonce is fixed. We prove that the obtained algorithm (MGM-PRF) is a pseudorandom function (PRF) and hence a secure MAC (message authhentication code). When using a cipher with a block of $n=64$ bits (“Magma”) and the probability of forgery at most $\pi_{\mathrm{mac}}=2^{-10}$ algorithm MGM-PRF can process $q\leq2^{26}$ messages of $l\leq2^{26}$ blocks each ($q\cdot l\leq2^{52}$) with a single key.
Similarly, but with minor modifications, from the AEAD-mode MGM2 (CTCrypt 2021), we construct the MGM-PRF algorithm, which can protect the integrity of messages up to $l\leq2^{63}$ blocks long ($q\cdot l\leq2^{89}$).
Going beyond the birthday paradox bound (BBB, $q>2^{\frac{n}{2}}$) is possible by doubling the internal state of the cryptoalgorithm. We propose a new BBB-secure PRF MGM-PRF, which essentially consists of applying MGM-PRF twice in parallel to a single message and summing the results. SUM-MGM uses a single encryption key with which it can securely protect $q\leq2^{37}$ messages, up to $l\leq2^{38}$ blocks long ($q\cdot l\leq2^{75}$).
The results are obtained by using the H-coefficient method, PRP-PRF Lemma is not used.