# 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 pulbic 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 a 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. Commented Feb 3, 2015 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$? Commented Feb 3, 2015 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. Commented Feb 3, 2015 at 16:18
• cs.berkeley.edu/~dawnsong/papers/p598-ateniese Commented Feb 3, 2015 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 Commented Feb 3, 2015 at 16:26