# Information theoretic message authentication code (MAC)

Let's $\ a,b\$ be two (pseudo)random independent values, and $m$ be a message, where $a,b,m \in \mathtt{F}_p$, where $p$ is a large prime number.

Question 1: Is $\ am+b\$ an information theoretic MAC?

if yes

Question 2: Is there any paper/textbook uses it?

• You need $a \neq 0 \pmod p$. – CodesInChaos Feb 7 '17 at 14:35
• This is the single block special case of polynomial MACs. See Poly1305 or GHash. – CodesInChaos Feb 7 '17 at 14:37
• If $a,b$ are pseudorandom and not truly random, then it cannot be information theoretic. – Yehuda Lindell Feb 7 '17 at 14:59
• Unless a pair $a, b$ is used for only one message, it can't be informational theoretic (or even practically secure). And, changing the key for each message isn't a standard property of MACs. – poncho Feb 7 '17 at 22:01

Just collecting some of the comments, if you make sure that $a$ and $b$ are chosen uniformly at random with $a \neq 0 \mod p$, then the given function is a information-theoretic MAC, basically because it satisfies the following property:
If $h_k(m) = am + b$ with $k= (a,b)$ and $\tau$ is the codomain of $h_k$, then for all $m\neq m'$ and $t,t'\in\tau$ we have $$\operatorname{Pr}[h_k(m) = t \ \wedge\ h_k(m') = t'] = \frac{1}{|\tau|^2}$$ (probability taken over random choice of $k$)
When a function satisfy this property we say it is a strongly universal function, and the main result is that such a function is a $1/|\tau| -$secure MAC, that is, the advantage of an attacker is at most $1/|\tau|$ (notice we can not ask for this advantage to be zero because any adversary can always try to guess a valid tag).
• If I have two messages $m_0, m_1$ and get the MAC values for those two messages $h_k(m_0)$ and $h_k(m_1)$, I can compute the MAC $h_k(m_2)$ for any message $m_2$. How is this information-theoretic? – poncho Feb 7 '17 at 23:08