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.
Category / Keywords: cryptographic protocols / Date: received 6 Sep 2012 Contact author: htsm1138 at snu ac kr Available formats: PDF | BibTeX Citation Version: 20120907:182217 (All versions of this report) Discussion forum: Show discussion | Start new discussion