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 $\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 factorization 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 in the security parameter. 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 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 $\Z_N$ with unknown factorization of $N$. Instead, we detour this problem by using NaccacheStern 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 privacypreserving set union protocol. Our construction improves the complexity than the previous without an honest majority. It can be also used for a constant round multiset union protocol and a private set intersection protocol even when decryptors do not possess a superset of the resulting set.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 htsm1138 @ snu ac kr
 History
 20130708: last of 2 revisions
 20120907: received
 See all versions
 Short URL
 https://ia.cr/2012/526
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/526, author = {Jung Hee Cheon and Hyunsook Hong and Hyung Tae Lee}, title = {Invertible Polynomial Representation for Private Set Operations}, howpublished = {Cryptology ePrint Archive, Paper 2012/526}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/526}}, url = {https://eprint.iacr.org/2012/526} }