Cryptology ePrint Archive: Report 2015/1004

Security Analysis of Cryptosystems Using Short Generators over Ideal Lattices

Shinya Okumura and Shingo Sugiyama and Masaya Yasuda and Tsuyoshi Takagi

Abstract: In this paper, we analyze the security of cryptosystems using short generators over ideal lattices such as candidate multilinear maps by Garg, Gentry and Halevi and fully homomorphic encryption by Smart and Vercauteren. Our approach is based on a recent work by Cramer, Ducas, Peikert and Regev on analysis of recovering a short generator of an ideal of the q-th cyclotomic field from any generator of the ideal for a prime power q. Unfortunately, the main result of Cramer et al. has some flaws since they use an incorrect lower bound of the special values of Dirichlet L-functions at 1. Our main contribution is to correct Cramer et al.'s main result by estimating explicit lower and upper bounds of the special values of Dirichlet L-functions at 1 for any non-trivial Dirichlet characters modulo a prime power. Moreover, we give various experimental evidence that recovering a short generator is succeeded with high probability. As a consequence, our analysis suggests that the security of the above cryptosystems based on the difficulty of recovering a short generator is reduced to solving the principal ideal problem under the number theoretical conjecture so-called Weber's class number problem.

Category / Keywords: public-key cryptography / Short generators, Cyclotomic fields, Log-unit lattices, Dirichlet L-functions

Date: received 15 Oct 2015, last revised 15 Oct 2015

Contact author: s-okumura at imi kyushu-u ac jp; s-sugiyama@imi kyushu-u ac jp; yasuda@imi kyushu-u ac jp; takagi@imi kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Note: This paper analyzes the security of the IACR eprint 2015/313 of the second version on April 6.

Version: 20151016:153619 (All versions of this report)

Short URL: ia.cr/2015/1004

Discussion forum: Show discussion | Start new discussion