The polynomial approximate common divisor problem and its application to the fully homomorphic encryption

详细信息    查看全文

• 作者：Jung Hee Cheon ; ^{jhcheon@snu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Hyunsook Hong ^{hongsuk07@snu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Moon Sung Lee ^{moolee@snu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Hansol Ryu ^{sol8586@snu.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Polynomial approximate GCD problem ; Chinese remainder theorem ; Fully homomorphic encryption ; Large integer arithmetic ; SIMD operation
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：1 January 2016
• 年：2016
• 卷：326
• 期：Complete
• 页码：41-58
• 全文大小：467 K

文摘

We propose and examine the approximate polynomial common divisor problem, which can be viewed as a polynomial analogue to the approximate integer common divisor problem. Since our problem is rather new, we perform extensive cryptanalysis, applying various known attacks against the structurally similar problems. Moreover, we propose a small root finding algorithm for multivariate modular equation system, and apply it to the proposed problem. Those analyses confirm that the proposed problem is difficult with appropriate parameters.

Additionally, we construct a simple somewhat homomorphic encryption scheme, which can efficiently accommodate large message spaces. When the evaluation of a low degree polynomial of very large integers is required, our scheme is more efficient than the recent RLWE-based scheme, YASHE, by Bos et al. (2013). In particular, multiplication is ten times faster when evaluating degree-10 polynomial of 1638-bit integers. We convert this scheme to a leveled fully homomorphic encryption scheme by applying Brakerski’s scale invariant technique, and the resulting scheme has features similar to the variant of van Dijk et al.’s scheme by Coron et al. (2014). Our scheme, however, does not use the subset sum, which makes its design much simpler.