# Using Permutation polynomial to compute a MAC

Is the following MAC secure?

For a block $y_i$ in a file, we defined a MAC as follows: $Mac_i:PRF(k,i) \cdot g^{y_i \cdot r_i} \bmod p$.

Where $p$ is a prime number, $g \in \mathbb{G}$,$PRF(k,i)$ is a pseudorandom function whose output is distributed uniformly random over $\mathbb{G}$, $k$ is a $l$ bit key, and $i$ is index of value $y_i$ in the file .

** More importantly, we define a polynomial ring $R[x]$ and $f(x) \leftarrow R[x]$. Where $f(x)$ is a linear permutation polynomial that has the form $ax+b$, where $a,b$ are picked uniformly random from $R$. We define $r_i$ as: $f(x_i)=r_i$ where $x_i \in \textbf{x}$, and $\textbf{x}$ is a pubic vector and $R$ is $\mathbb{Z_p}$.

It is clear that if $r_i$ is picked randomly the above Mac would be secure for a file. So when we define a mac for a block at index $i$ in different file, we change the key $k$ to $k'$. However, here I use a permutation polynomial and by definition its output is distributed uniformly random in $\mathbb{Z_p}$ and I make the elements in $\textbf{x}$ public (for some computation which is not the focus of this conversation).

So I pick the polynomial,$f$, once for a file, and for each block $i$, I evaluate $f$ at the corresponding value in $\textbf{x}$, so $r_i=f(x_i)$. Note that there are $|R|^2-|R|$ different linear polynomials in the field $R$.

Please let me know if it needs more explanation.

It is clear that if $r_i$ is picked randomly the above Mac [defined in the second paragraph] would be secure.

Actually, that's not at all clear. I would claim that if I were given that values of $Mac_i(a)$ and $Mac_i(b)$, I could compute the value of $Mac_i(x)$ for any $x$, as long as $a-b$ is relatively prime to $p-1$. To do this, I need the value of $p$, $a$ and $b$, but not $k$, $r_i$, or for that matter, $g$.

To do this, I would compute $X = Mac_i(a) / Mac_i(b) \bmod p$; that value is $X = PRF(k,i) \cdot g^{a \cdot r_i} / PRF(k,i) \cdot g^{b \cdot r_i} = (g^r_i)^{a-b}$

I then compute $X^{(a-b)^{-1}}$, giving me the value $Y = g^r_i$.

I then compute $Z = Mac_i(a) / Y^a = PRF(k,i) \cdot g^{a \cdot r_i} / g^{r_i \cdot a} = PRF(k,i)$

Once I've done that, I can compute the $Mac_i$ of an arbitrary value $Mac_i(x) = Z \cdot Y^x = PRF(k,i) \cdot g^{r_i \cdot x}$

• Thanks for your answer, but that $Mac_i$ is for the block residing at position $i$ in the file denoted by $\textit{file_1}$ (it should have been more clearer in the question). So for the next file we change the Key, $k$ to $k'$. Thus, here we only consider Macs for different indices of a file. – user13676 Feb 3 '15 at 16:12
• @user13676: So, you compute $Mac_i$ only once (for a specific $i, k$ pair)? If so, why don't you use the simpler construction $a_i \cdot y_i + b_i \bmod p$, for secret $a_i, b_i$? – poncho Feb 3 '15 at 16:14
• Yes, it is more less similar to tags in PDP (provable data possession), but we try to use a linear permutation polynomial to generate the random exponent and the vector $\textbf{x}$ is public. – user13676 Feb 3 '15 at 16:18
• cs.berkeley.edu/~dawnsong/papers/p598-ateniese – user13676 Feb 3 '15 at 16:20
• We cannot use the tag you suggested because our tags (Macs) are gonna verify the computations, where $a_i$ and $b_i$ cannot be changed for each index – user13676 Feb 3 '15 at 16:26