International Association
for Cryptologic Research

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.