Paper 2015/1004

Security Analysis of Cryptosystems Using Short Generators over Ideal Lattices

Shinya Okumura, Shingo Sugiyama, 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.

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Short generatorsCyclotomic fieldsLog-unit latticesDirichlet L-functions
Contact author(s)
s-okumura @ imi kyushu-u ac jp
s-sugiyama @ imi kyushu-u ac jp
yasuda @ imi kyushu-u ac jp
takagi @ imi kyushu-u ac jp
History
2015-11-17: last of 2 revisions
2015-10-16: received
See all versions
Short URL
https://ia.cr/2015/1004
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1004,
      author = {Shinya Okumura and Shingo Sugiyama and Masaya Yasuda and Tsuyoshi Takagi},
      title = {Security Analysis of Cryptosystems Using Short Generators over Ideal Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1004},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1004}},
      url = {https://eprint.iacr.org/2015/1004}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.