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 in the $q$-th cyclotomic field for a prime power $q$.
In their analysis, implicit lower bounds of the special values of Dirichlet $L$-functions at 1 are essentially used for estimating some sizes of the dual basis in the log-unit lattice of
the $q$-th cyclotomic field.
Our main contribution is to improve Cramer et al.'s analysis by giving
explicit lower and upper bounds of the special values of
Dirichlet $L$-functions at 1 for any non-trivial even Dirichlet characters modulo $q$.
Moreover, we give various experimental evidence that recovering short
generators of principle ideals in $2k$-th cyclotomic fields
for $k \geq 10$ 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 16 Nov 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: Our current paper improves the analysis of the IACR eprint 2015/313
on October 14.
Note that our previous version on October 15 analyzes
the security of the IACR eprint 2015/313 on April 6.
Version: 20151117:042338 (All versions of this report)
Short URL: ia.cr/2015/1004
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]