Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

This is a homework question, therefore I'm not expecting full solutions, just general guidance.

I want to build a one-time MAC using universal hashing.

I defined my hash functions as:

$$h_{a,b}:\begin{array}{lll} \mathbb{F}_{2^{n}} & \to & \mathbb{F}_{2^{n}}\\ x & \mapsto & ax+b \end{array}$$ for $$a\in\mathbb{F}_{2^{n}}\backslash\left\{ 0\right\}$$, $$b\in\mathbb{F}_{2^{n}}$$

Where $$\mathbb{F}_{2^{n}}=GF\left(2^{n}\right)$$ means the galois field/finite field of size $$2^n$$.

These functions have 0 probability of collision for two distinct messages. However, in order to use these functions as a one-time MAC, I need to show security which is defined for the following game with adversary $$A$$:

An oracle generates a secret key $$a,b$$, then $$A$$ can choose exactly one message $$m$$ to query, that the oracle tags for $$A$$ with $$h_{a,b}\left(m\right)$$). Then $$A$$ has to generate a message $$m'\neq m$$ and tag $$t'$$ such that $$h_{a,b}\left(m'\right)=t'$$.

Security is defined as for any efficient (polynomial) adversary $$A$$ allowed only one query (as described), there exists a negligible function such that the probabilty of $$A$$ winning the game is at most that negligible function.

This is where I'm stuck. I have intuition, but can't formulate a formal proof. I know that if $$A$$ decides to query with message 0, then he knows what b is, since $$a\cdot0+b=b$$, but then he's left with guessing $$a$$ (need to show here he can't do it other than randomly guessing). And if he decides to query message $$m$$ that is not 0, he could at most calculate $$\left(a\cdot m+b\right)m^{-1}=a+bm^{-1}$$ which is the same problem (more or less) as $$am+b$$.

I would love some direction on how to approach such proof of showing finding such message with a viable tag, reduces to guessing at best (therefore showing an upper bound that is negligible).

Thanks!

• AFAIK, the $A$ is allowed the play this game many times? – kelalaka Jan 22 '19 at 6:43
• @kelalaka He's concerned with the concept of one-time MACs – Daniel Jan 22 '19 at 10:59

1 Answer

You are in the right direction.

First, some intuition. The idea is that $$y = ax+b$$ constitutes a line, and if you need two points in order to fully determine it. However, if you only know one point, and if you don't have any additional information, then it is not possible to determine which line is it since there are "infinitely many" lines passing through the given point (of course, since we're on a finite field there are finitely many, but you get the idea).

Now, for the formalization, imagine that $$A$$ queries the oracle on some $$m$$ to get $$t = a\cdot m + b$$ (let's ignore how $$A$$ chose $$m$$, maybe it was crafted in some way, perhaps $$m=0$$ as you said, but this will turn out to be irrelevant). We claim that if $$A$$ successfully crafts another message-tag pair $$(m',t')$$ with $$m=m'$$, then it is because $$A$$ guessed $$a$$, which is not possible since it was chosen at random from a large enough domain. Now, this is argued easily by something I already mentioned: given two different points on a line, you can get the line and therefore the coefficients $$a,b$$. In other words, once you fix $$(m,t)$$ with $$t = a\cdot m+b$$, getting a new $$(m',t')$$ allows an adversary to find $$a$$ as $$a = (m-m')^{-1}\cdot(t-t')$$. This finishes the argument.

• Thanks for your answer! I'm not sure I entirely understand the argument and would appreciate further help. For example, $\left(m',t'\right)$ do indeed set $a,b$, but $a,b$ can have multiple $\left(m',t'\right)$, so the problems are not entirely equivalent. – Ungoliant Jan 22 '19 at 14:15
• Right, what I said was a little bit misleading, sorry. Indeed, after you fix $(m,t)$, having another $(m',t')$ yields $(a,b)$, but it's not like having $(a,b)$ fully determines one $(m',t')$. However, having $(a,b)$ does determine of course all possible $(m',t')$. In any case, that's not really needed for the argument. What part of the argument is generating confusion in particular? – Daniel Jan 22 '19 at 14:21
• You're claiming guessing $\left(m',t'\right)$ means guessing $a,b$, which I assume is in order to say guessing $\left(m',t'\right)$ is as hard as guessing $a,b$, but it's not. I guess you could still argue that we have $2^n$ possible pairs to guess (out of $2^{2n}$), though I'm still not sure what is the justification for assuming you have to guess the pair... – Ungoliant Jan 22 '19 at 14:36
• I see the confusion, and I recognize it's a mistake from my side. Let's put it this way. As you show in the description, getting $b$ is easy for the adversary by setting $m=0$ in the first query, so my claim won't be that generating a new pair is as hard as guessing $(a,b)$, but it is as hard as guessing only $a$. To show this, fix $(m,t)$. If you guess another $(m',t')$ then you guess $a$ because $(t'-t) = a\cdot(m-m')$, and you can solve for $a$ from there. This goes in accordance to the intuition: one point in a line does not reveal the slope, which is $a$. – Daniel Jan 22 '19 at 14:48