Welcome to the resource topic for 2012/526
Title:
Invertible Polynomial Representation for Private Set Operations
Authors: Jung Hee Cheon, Hyunsook Hong, 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 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 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.
ePrint: https://eprint.iacr.org/2012/526
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .