Polynomial Factorization and Its Applications
다항식 인수분해와 그 응용

Cited 0 time in Web of Science Cited 0 time in Scopus
자연과학대학 수리과학부
Issue Date
서울대학교 대학원
학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2013. 2. 천정희.
Polynomial representations which represent a set by a polynomial over a ring~$\Z_{\sigma}$ for a composite integer~$\sigma$ enable us to construct efficient private set operation protocols by combining with some additive homomorphic encryption scheme. However, a polynomial representation has a limitation due to the hardness of polynomial factorizations over $\Z_{\sigma}$. It makes hard to recover a corresponding set from a resulting polynomial in some private set operation protocols.

We provide two representations of a set by a polynomial over $\Z_{\sigma}$ which enable us to uniquely factorize a polynomial satisfying some criteria. The first suggestion works on a ring $\Z_{N}$ for RSA modulus $N$, a message space of Paillier encryption. To do this, we mediate between sizes of modulus $N$ and elements in the domain so that each element in the domain is to be a small root of a certain polynomial over $
\Z_{\sigma}$ and apply Coppersmith small root finding algorithm.

In case of our second suggestion, it works on a ring $\Z_{\sigma}$ for a product $\sigma$ of small primes, a message space of Naccache-Stern encryption. While the factorization of $N$ is secret in Paillier encryption, the factorization of $\sigma$ is public. Hence, we can obtain many candidates of roots of polynomial using a polynomial factorization algorithm working on prime fields and Chinese remainder theorem. In our suggestion, to remove irrelevant candidates, we adopt a special encoding function which supports early abort strategy. As a result, we can efficiently recover a corresponding set from a polynomial in $\Z_{\sigma}[x]$ whose roots locates in the image of our encoding function.

As applications of our polynomial representations, we obtain a constant-round private set union protocols. Our construction improves the complexity than the previous best result without an honest majority assumption. We also consider a private set intersection protocol in storage model, in which the owners of sets and the recipients are separated.
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.