Publications
Detailed Information
Polynomial Factorization and Its Applications : 다항식 인수분해와 그 응용
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 천정희
- Major
- 자연과학대학 수리과학부
- Issue Date
- 2013-02
- Publisher
- 서울대학교 대학원
- Description
- 학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2013. 2. 천정희.
- Abstract
- 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.
- Language
- English
- Files in This Item:
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.