Polynomial Factorization and Its Applications

Abstract

Polynomial representations which represent a set by a polynomial over a ring~$\Z_{\sigma}$ for a composite integer~$\sigma$ enable us to construct efficient private set operation protocols by combining with some additive homomorphic encryption scheme. However, a polynomial representation has a limitation due to the hardness of polynomial factorizations over $\Z_{\sigma}$. It makes hard to recover a corresponding set from a resulting polynomial in some private set operation protocols.

We provide two representations of a set by a polynomial over $\Z_{\sigma}$ which enable us to uniquely factorize a polynomial satisfying some criteria. The first suggestion works on a ring $\Z_{N}$ for RSA modulus $N$, a message space of Paillier encryption. To do this, we mediate between sizes of modulus $N$ and elements in the domain so that each element in the domain is to be a small root of a certain polynomial over $ \Z_{\sigma}$ and apply Coppersmith small root finding algorithm.

In case of our second suggestion, it works on a ring $\Z_{\sigma}$ for a product $\sigma$ of small primes, a message space of Naccache-Stern encryption. While the factorization of $N$ is secret in Paillier encryption, the factorization of $\sigma$ is public. Hence, we can obtain many candidates of roots of polynomial using a polynomial factorization algorithm working on prime fields and Chinese remainder theorem. In our suggestion, to remove irrelevant candidates, we adopt a special encoding function which supports early abort strategy. As a result, we can efficiently recover a corresponding set from a polynomial in $\Z_{\sigma}[x]$ whose roots locates in the image of our encoding function.

As applications of our polynomial representations, we obtain a constant-round private set union protocols. Our construction improves the complexity than the previous best result without an honest majority assumption. We also consider a private set intersection protocol in storage model, in which the owners of sets and the recipients are separated.