# Proof By Reduction

Privacy-preserving set operations: http://www.cs.cmu.edu/~leak/papers/set-tech.pdf

Let all polynomials be defined over a ring $\mathbb{Z}_p$, where $p$ is a prime number. Here for the sake of simplicity, I picked $p$ instead of $N$ used in the paper.

Assume $p_1,p_2$ are two fixed polynomials of degree $d$. Also, Let $r_1,r_2$ be two randompolynomials of degree $d$.

It is said in $T=p_1\cdot r_1+p_1\cdot r_2=m\cdot gcd(p_1,p_2)$, polynomial $m$ distributed uniformly at random over the polynomial ring.

Note that $gcd(p_1,p_2)$ represents intersection of the two polynomials roots.

Assume we want to use it in a protocol and them proof it. So we use simulation-based proof. So, simulator constructs $T'=m'\cdot gcd(p_1,p_2)$, where $m'$ is a degree $d$ uniformly random polynomial over the ring.

Question: In a full (reduction-based) proof, how to prove that a distinguisher cannot distinguish $m$ from $m'$?

I mean what hard problem we should rely on to show if it can distinguish them it can break the problem ?

From a (hopefully not-too-quick) reading, it seems the "nice" feature of the polynomials $$p_1\cdot r_1 + p_2\cdot r_2$$ [..fixing what I assume was a typo in question above..] is that their coefficients can be shown to be distributed uniformly and independently over the ring $R.$ In particular, this is done using a counting argument in the cited paper's appendix.