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?

  • 1
    $\begingroup$ You need $a \neq 0 \pmod p$. $\endgroup$ – CodesInChaos Feb 7 '17 at 14:35
  • 4
    $\begingroup$ This is the single block special case of polynomial MACs. See Poly1305 or GHash. $\endgroup$ – CodesInChaos Feb 7 '17 at 14:37
  • 5
    $\begingroup$ If $a,b$ are pseudorandom and not truly random, then it cannot be information theoretic. $\endgroup$ – Yehuda Lindell Feb 7 '17 at 14:59
  • 1
    $\begingroup$ 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. $\endgroup$ – 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).

| improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – poncho Feb 7 '17 at 23:08
  • $\begingroup$ @poncho This is one-time information-theoretic. I don't know about any other information-theoretic definition (this definition comes from Katz-Lindell book) $\endgroup$ – Daniel Feb 7 '17 at 23:08
  • $\begingroup$ IMHO, if it doesn't meet the standard definition of a Message Authentication Code, it probably should be called something else; possibly a Universal Hash function... $\endgroup$ – poncho Feb 7 '17 at 23:16
  • 2
    $\begingroup$ @poncho I partially agree with you, but consider for example OTP: it is information-theoretic secure using a one-time game, it makes certain sense to involve an analogous scenario for the MAC context (but I am aware that the MAC security definition involves oracle access, which is not the case for EAV-secrecy). However, I'm a beginning on this, so I really do not know. $\endgroup$ – Daniel Feb 7 '17 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.