Challenging Question for the Build a Secure MAC with Special Properties

Question

We would like to ask you to give a construction for requested scheme which provides those properties or give a proof that is not achievable.

[Note that unsuccessful attempts to build such a scheme can be found on the links Is this "linear combination" of PRFs and Hashes a secure MAC? and Is this construction a secure MAC?

Definition (MAC scheme). A message authentication code (or MAC) consists of three probabilistic polynomial-time algorithms $\Pi =(\mathsf{Gen}, \mathsf{Mac}, \mathsf{Vrfy})$ such that:

1. The key-generation algorithm $\mathsf{Gen}$ takes as input the security parameter $1^n$ and outputs a key $K$.

2. The tag-generation algorithm $\mathsf{Mac}$ takes as input a key $K$ and a message $m =a_1||a_2$ (where $a_1, a_2 \in \{0, 1\}^{n}$, and outputs a tag $T=(t_1,t_2)$ (where $t_1,t_2 \in \mathbb{F}^*_q$). Since this algorithm may be randomized, we write this as $T \leftarrow \mathsf{Mac}_K(m)$.

3. The deterministic verification algorithm $\mathsf{Vrfy}$ takes as input a key $K$, a message $m$, and a tag $T$. It outputs a bit $b$, with $b = 1$ meaning valid and $b = 0$ meaning invalid. We write this as $b := \mathsf{Vrfy}_K(m, T)$.

Expected features include:

1. correctness condition: it is required that for every $n$, every key $K$ output by $\mathsf{Gen}(1^n)$, and every $m \in \{0, 1\}^{2n}$, it holds that $\mathsf{Vrfy}_K(m, \mathsf{Mac}_K(m)) = 1$.

2. linear combination: the construction must be provided based on a linear combination of PRFs and Hashes.

3. forge conditions: we redefined the condition of the attacker's success for pair $(m=a_1\mathbin\|a_2,\;T)$, so that $\mathsf{Vrfy}_K(m,T)=1$, $a_1 \neq a_2$, and also $a_1\mathbin\|a_2$ or $a_2\mathbin\|a_1$ did not asked its oracle.

4. validation structure: it is required that algorithm $b := \mathsf{Vrfy}_K(m, T)$ act as follows, where $f$ and $g$ are polynomial-time algorithms: $$f(g(K,a_1),T) \stackrel{?}{=} f(g(K,a_2),T)$$ That is $\mathsf{Vrfy}$ should return $1$ iff the above expression holds and $0$ otherwise.

Answer 1

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 < 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 < 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.