An improvement of key generation algorithm for Gentry's homomorphic encryption scheme from ideal lattices

One way of improving efficiency of Gentry's fully homomorphic encryption from ideal lattices is controlling the number of operations, but our recollection is that any scheme which controls the bound has not proposed. In this paper, we propose a key generation algorithm for Gentry's scheme that controls the bound of the circuit depth by using the relation between the circuit depth and the eigenvalues of a basis of a lattice. We present experimental results that show that the proposed algorithm is practical. We discuss security of the basis of the lattices generated by the algorithm for practical use. Some encryption schemes such as the RSA, Paillier (17), and Okamoto-Uchiyama (16) schemes have a homomorphic property. The homomorphic property provides a feature which enables us to deal with encrypted data without be- ing able to decrypt the data. This property has various applications such as to secure voting systems or cross ta- ble generation. Many homomorphic encryption schemes incorporate the homomorphic property for only one oper- ation, i.e., no encryption scheme is capable of evaluating any function. Constructing a fully homomorphic encryp- tion scheme that could evaluate all functions is an impor- tant open problem in cryptography that has persisted for many years. In 2009, Gentry (6) solved this problem by using ideal lattices. Gentry showed that a fully homomor- phic encryption scheme can be constructed in three stages: First, he proposed an abstract construction of homomor- phic encryption schemes for some functions. Second, he embodied the idea with ideal lattices. We call this scheme Gentry's basic scheme. Third, he proposed how to extend the scheme so that it has a fully homomorphic property. We call this scheme Gentry's full scheme. Here, we concentrate on the basic scheme. This is because the efficiency of the full scheme is much lower than that of the basic scheme. We consider that we can construct a practical full scheme by improving the basic scheme. The key generation algorithm of Gentry's basic scheme generates random basis of ideal lattices as the private key. A bound for the number of operations depends on these ba- sis. Then, it is difficult to handle the number of executable operations in advance. Therefore, we must repeat the key generation until the scheme can handle the desired num- ber of operations. In other words, controlling the bound enables us to construct efficient Gentry's scheme. Then, the problem naturally arises regarding how to handle the number of operations before generating the keys. In this paper, we address this problem by proposing a key generation algorithm that controls the bound of the circuit depth by using the relation between the circuit depth and the eigenvalues of a basis of a lattice. That is, the proposed key generation algorithm enables us to create a practical homomorphic encryption scheme for a given number of op- erations. We discuss security of the basis of the lattices generated by the algorithm for practical use. Also, we de- scribe an efficient implementation of Gentry's scheme and show that the proposed algorithm is practical based on ex- perimental results.