Paper 2012/526

Invertible Polynomial Representation for Private Set Operations

Jung Hee Cheon, Hyunsook Hong, and Hyung Tae Lee

Abstract

In many private set operations, a set is represented by a polynomial over a ring ${\text{Z}}_{\sigma }$ for a composite integer $\sigma$, where ${\text{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 factorization over ${\text{Z}}_{\sigma }$. That is, it is hard to recover a corresponding set from a resulting polynomial over ${\text{Z}}_{\sigma }$ if $\sigma$ is not a prime. In this paper, we propose a new representation of a set by a polynomial over $$, in which $$ is a composite integer with {\em known factorization} but a corresponding set can be efficiently recovered from a polynomial except negligible probability in the security parameter. Note that $$ 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 $$ whose roots locate in the image of the 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 the secret of the utilized additive homomorphic encryption. This is very hard for Paillier's encryption whose message space is $$ with unknown factorization of $$. Instead, we detour this problem by using Naccache-Stern encryption with message space $$ where $$ 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 an honest majority. It can be also used for a constant round multi-set union protocol and a private set intersection protocol even when decryptors do not possess a superset of the resulting set.