Challenging Question for the Build a Secure MAC with Special Properties
Here is a construction that appears to meet all your criteria:

We will assume that:


$k \ge 2^{n+1}$
$MAC'_k(a | b)$ is a standard deterministic MAC (e.g. HMAC) of the string $(a | b)$


Then,

$\mathsf{Gen}$ generates a random $MAC'$ key

$\mathsf{Mac}$ is defined as $\mathsf{MAC}_k(a_1, a_2) = (t_1, t_2)$ where $t_1 = a_1 + MAC'_k( a_1, a_2)$, $t_2 = a_2 + MAC'_k(a_1, a_2)$

Within $\mathsf{Verify}$, we have:

$g(K, a_i) = (K, a_i)$

$f((K, a_i), (t_1, t_2))$ defined as:


If $0 \le t_2 + a_i - t_1 &lt; 2^n$ and $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$, then the result is $0, \mathsf{Success}$
If $0 \le t_1 + a_i - t_2 &lt; 2^n$ and $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$, then the result is $0, \mathsf{Success}$
The result is $1, a_i$ otherwise.


Showing that most of the conditions hold is straight-forward; showing that this resists forgery is slightly involved.  To start, the MAC will declare success only if both sides have either $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$ or $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$ (because the MAC of the pair $(a, a)$ is forbidden.

Now, if the two sides satisfy opposite relations (say, $a_1$ satisfies the first, and $a_2$ satisfies the second, then simple algebra gives us:

$$t_1 - a_1 = t_2 - a_2 = MAC'_k( a_1, a_2 )$$

That is, to generate this forgery, the attacker must successfully predict $MAC'_k( a_1, a_2 )$.

Alternatively, if the two sides satisfy the same relation, for example, both sides satisfy the first, namely we have both:

$$MAC'_k( a_1, t_2 + a_1 - t_1 ) = t_1 - a_1$$

$$MAC'_k( a_2, t_2 + a_2 - t_1 ) = t_1 - a_2$$

This implies that the attacker has found two MAC inputs with the relation:

$MAC'_k( a + \delta, b + \delta ) = MAC'(a, b) + \delta$

This is not believed to be feasible without knowing the MAC key.