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.

  • $\begingroup$ So you would be happy with a secure MAC and a pair of (efficiently computable) functions $f,g$ such that $f(g(K,a_1),T)=f(g(K,a_2),T)\iff \mathrm{Vrfy}_K(a_1\parallel a_2,T)$? $\endgroup$
    – SEJPM
    Commented Jul 15, 2018 at 13:30
  • $\begingroup$ Yes, two functions $f, g$ are used in algorithm $\mathsf{Vrfy}$. $\endgroup$
    – Robert
    Commented Jul 15, 2018 at 14:25
  • $\begingroup$ Is the second condition that the resulting values have to be linear combinations strict? That is do you really need this property or are you just asking for it because I labelled your last attempt as a "linear combination" for the lack of a better description? $\endgroup$
    – SEJPM
    Commented Jul 15, 2018 at 14:41
  • $\begingroup$ Yes, I need this property. In fact, we are allowed to use all the symmetric primitives (such as PRF, Hash, PRG, O.W.F, O.W.P, etc). $\endgroup$
    – Robert
    Commented Jul 15, 2018 at 14:48

1 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)$


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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