The CMZ13 paper defines two algebraic MACs which can be used to construct credentials, \(\mathsf{MAC_{GGM}}\) and \(\mathsf{MAC_{DDH}}\), which are proved secure in the generic group model and under the decisional Diffie-Hellman assumption, respectively. However, \(\mathsf{MAC_{DDH}}\) is more expensive and as noted in the paper, there is no reason to believe that \(\mathsf{MAC_{GGM}}\) is not also secure under DDH, although there is no proof.

For reasons of efficiency we use \(\mathsf{MAC_{GGM}}\). As noted in the paper, this is a generalization of a 2012 construction due to Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, and Daniel Wichs. It is defined as follows:

  • Setup. Choose \(\mathbb G\) a group of prime order \(p\). The messages will be elements of \(\mathbb F_p^n\), i.e., \(n\)-tuples of field elements in \(\mathbb F_p\).

  • Key Generation. Choose \( \mathbf x = (x_0, x_1, \ldots, x_n) \xleftarrow{\$} \mathbb F_p^{n+1} \).

  • MAC. Given a message \(\mathbf m \in \mathbb F_p^n\), choose \(P \xleftarrow{\$} \mathbb G \setminus \{ 0 \} \) and compute \(Q = \langle \mathbf x, (1) || \mathbf m \rangle \cdot P\). The tag is \((P, Q)\).

  • Verify. Given a message \(\mathbf m \in \mathbb F_p^n\) and a purported tag \( (P,Q)\), accept if \(P \neq 0\) and \(Q = \langle \mathbf x, (1) || \mathbf m \rangle \cdot P\), otherwise reject.

Notice that although the tag \( (P,Q) \) witnesses the integrity of the message \(\mathbf m\), the tag itself is malleable: given \( r \in \mathbb F_p^\times\), \( (rP, rQ) \) also satisfies the verification equation. When used as part of an anonymous credential, this will be used to re-randomize the tag.