Fast key generation for Gentry-style homomorphic encryption |
| |
Affiliation: | 1. School of Information Science and Engineering, Shandong University, Jinan 250010, China;2. National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China |
| |
Abstract: | The key issue of original implementation for Gentry-style homomorphic encryption scheme is the so called slow key generation algorithm. Ogura proposed a key generation algorithm for Gentry-style somewhat homomorphic scheme that controlled the bound of the evaluation circuit depth by using the relation between the evaluation circuit depth and the eigenvalues of the primary matrix. However, their proposed key generation method seems to exclude practical application. In order to address this problem, a new key generation algorithm based on Gershgorin circle theorem was proposed. The authors choose the eigenvalues of the primary matrix from a desired interval instead of selecting the module. Compared with the Ogura's work, the proposed key generation algorithm enables one to create a more practical somewhat homomorphic encryption scheme. Furthermore, a more aggressive security analysis of the approximate shortest vector problem (SVP) against lattice attacks is given. Experiments indicate that the new key generation algorithm is roughly twice as efficient as the previous methods. |
| |
Keywords: | homomorphic encryption circuit depth key generation Gershgorin circle theorem |
本文献已被 ScienceDirect 等数据库收录! |
|