Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

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}$

share|improve this answer
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
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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