# Proof By Reduction

My question is about this paper:

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 ?

## 1 Answer

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.

That is, this looks like a purely statistical property. You don't need to have a computationally-hard problem (or a simulator, necessarily..) to show that a statistical property holds. For example, the cited paper goes on to encrypt the coefficients of these polynomials (respectively) under an additively homomorphic encryption scheme, for its applications. That's where a computational hardness assumption kicks in (but one isn't needed related to the distribution of these polynomials specifically; they're unconditionally uniformly distributed -- at least in the context of the given paper).

• Thank you for the answer. So, in a full proof we say that as the paper shows the polynomial's coefficients are distributed uniformly random over the field/ring? so we don't need to use a distinguisher to distinguish a random polynomial in the real model with the one in the ideal model? – user153465 Aug 19 '16 at 12:31
• I recommend reading the full version of the paper (I suspect it answers your questions more so than a few sentences here might :)). See: cs.cmu.edu/~leak/papers/set-tech-full.pdf – Daniel Apon Aug 19 '16 at 12:35
• Thank I've already read that. But it does not use full proof. It provides just a short sketch of proof for the PSI protocol. – user153465 Aug 19 '16 at 12:37
• Typically, protocols involving random polynomials are relying on the information-theoretic properties of random polynomials. (I'm unfamiliar with the gory details of Kissner/Song..) For example, here's an important follow-up work on a 'robust' version of PSI that may give you an additional perspective on the same (at least, type of) technique: ece.umd.edu/~danadach/MyPapers/set-int.pdf – Daniel Apon Aug 19 '16 at 12:45
• On a sidenote: coefficients of polynomials are a tricky thing. If you only have a product of polynomials, Gauss' lemma for polynomials has to be considered (for commutative rings in general, see the last section of the wiki page). That's why they probably had to use sums of polynomials (For sums, statistical arguments are much easier to find). – tylo Aug 19 '16 at 17:58