International Association
for Cryptologic Research

In many private set operations, a set is represented by a polynomial over a ring $\\Z_\\sigma$ for a composite integer $\\sigma$, where $\\Z_\\sigma$ is the message space of some additive homomorphic encryption. While it is useful for implementing set operations with polynomial additions and multiplications, a polynomial representation has a limitation due to the hardness of polynomial factorizations over $\\Z_\\sigma$. That is, it is hard to recover a corresponding set from a resulting polynomial over $\\Z_\\sigma$ if $\\sigma$ is not a prime.

In this paper, we propose a new representation of a set by a polynomial over $\\Z_\\sigma$, in which $\\sigma$ is a composite integer with {\\em known factorization} but a corresponding set can be efficiently recovered from a polynomial except negligible probability. Note that $\\Z_\\sigma[x]$ is not a unique factorization domain, so a polynomial may be written as a product of linear factors in several ways. To exclude irrelevant linear factors, we introduce a special encoding function which supports early abort strategy. As a result, our representation can be efficiently inverted by computing all the linear factors of a polynomial in $\\Z_\\sigma[x]$ whose root locates in the image of encoding function.

When we consider group decryption as in most private set operation protocols, inverting polynomial representations should be done without a single party possessing a factorization of $\\sigma$. This is very hard for Paillier\'s encryption whose message space is $\\Z_N$ with unknown factorization of $N$. Instead, we detour this problem by using Naccache-Stern encryption with message space $\\Z_\\sigma$ where $\\sigma$ is a smooth integer with public factorization. As an application of our representation, we obtain a constant round privacy preserving set union protocol. Our construction improves the complexity than the previous without honest majority assumption. It can be also used for constant round multi-set union protocol and private set intersection protocol even when decryptors do not possess a superset of the resulting set.