On Analysis of Recovering Short Generator Problems via Upper and Lower Bounds of Dirichlet L-functions: Part 2

In recent years, some fully homomorphic encryption schemes and cryptographic multilinear maps have been constructed by using short generators and ideal lattices arising from \(2^k\)th cyclotomic fields. Moreover, these systems are expected to have resistance to the attacks by quantum computers. The security of some of such cryptosystems depends on the principal ideal problem (PIP) and the recovering short generator problem (RSGP). Biasse and Song showed a quantum algorithm solving PIP on arbitrary number fields in polynomial time under GRH. On the other hand, Campbell et al. explain an algorithm solving RSGP on \(2^k\)th cyclotomic fields. Their algorithm is analyzed independently by Cramer, Ducas, Peikert and Regev/Okumura, Sugiyama, Yasuda and Takagi. Their analyses suggest that RSGP on \(2^k\)th cyclotomic fields is solved easily for practical parameters, and that cryptosystems of which the security is based on PIP and RSGP may not be post-quantum cryptosystems. Important tools in their analyses are upper and lower bounds of special values of Dirichlet L-functions at 1. In this paper, we give a survey on their analyses and explain some cryptographic and number theoretic open problems on RSGP.