In the following, all the operations and polynomials are defined over a finite field of prime order, $\mathbb{F}_p$, where $p$ is a sufficiently large prime number. All polynomials and values below are non-zero.

Let $F(x)= R(x)\cdot \phi(x)+Z(x)$, where the degree of each of the polynomials $R,Z$ and $\phi$ is $d>1$. Also, let $Z$ and $R$ be two polynomials picked uniformly at random from the field. Note $\phi$ is a fixed polynomial.

Question 1: Is $F(x)$ a MAC of $\phi$(x)?

Question 2: Is polynomial $\frac{F'(x)-Z(x)}{R(x)}$ a random polynomial distributed uniformly among polynomials of degree $d$ over $\mathbb{F}_p$? where $F'(x)$ is a fixed polynomial known by the adversary.

  • $\begingroup$ What have you done to try to figure out these questions so far? What's your definition of a MAC for Q1? Obviously if $Z$ and $R$ are random variables then some function of them is also a random variable; in Q2 did you mean to ask about a particular distribution, like whether $(F' - Z)/R$ is uniformly distributed among the degree-$d$ polynomials in $\mathbb F_p[x]$? Can $R$ be zero? $\endgroup$ Oct 17, 2019 at 16:10
  • $\begingroup$ @SqueamishOssifrage Thanks for useful comments. I have edited the question. $\endgroup$
    – Ay.
    Oct 17, 2019 at 16:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.