本科毕业设计（论文）
外文翻译
Implementing Gentryrsquo;s Fully-Homomorphic
Encryption Scheme
Author:Craig Gentry and Shai Halevi
Country:American and Israel
Originate:IBM Research
Abstract. We describe a working implementation of a variant of Gen-tryrsquo;s fully homomorphic encryption scheme (STOC 2009), similar to the variant used in an earlier implementation effort by Smart and Ver-cauteren (PKC 2010). Smart and Vercauteren implemented the underly-ing “somewhat homomorphic” scheme, but were not able to implement the bootstrapping functionality that is needed to get the complete scheme to work. We show a number of optimizations that allow us to implement all aspects of the scheme, including the bootstrapping functionality.
Our main optimization is a key-generation method for the underlying somewhat homomorphic encryption, that does not require full polynomail inversion.This reduces the asymptotic complexiry from ~O（n2.5）to （n1.5） when working with dimension-n lattices(and practically reducing the time from many hours/days to a few seconds/minutes).Other optimizations include a batching technique for encryption, a careful anal-ysis of the degree of the decryption polynomial, and some space/time trade-offs for the fully-homomorphic scheme.
We tested our implementation with lattices of several dimensions, cor-responding to several security levels. From a “toy” setting in dimension 512, to “small,” “medium,” and “large” settings in dimensions 2048, 8192, and 32768, respectively. The public-key size ranges in size from 70 Megabytes for the “small” setting to 2.3 Gigabytes for the “large” setting. The time to run one bootstrapping operation (on a 1-CPU 64-bit machine with large memory) ranges from 30 seconds for the “small” setting to 30 minutes for the “large” setting.
1 Introduction
Encryption schemes that support operations on encrypted data (aka homomor-phic encryption) have a very wide range of applications in cryptography. This concept was introduced by Rivest et al. shortly after the discovery of public key cryptography [12], and many known public-key cryptosystems support either addition or multiplication of encrypted data. However, supporting both at the same time seems harder, and until very recently all the attempts at constructing so-called “fully homomorphic” encryption turned out to be insecure.
In 2009, Gentry described the first plausible construction of a fully homomor-phic cryptosystem [3]. Gentryrsquo;s construction consists of several steps: He firs constructed a “somewhat homomorphic” scheme that supports evaluating low-degree polynomials on the encrypted data, next he needed to “squash” the de-cryption procedure so that it can be expressed as a low-degree polynomial which is supported by the scheme, and finally he applied a “bootstrapping ” transforma-tion to obtain a fully homomorphic scheme. The crucial point in this process is to obtain a scheme that can evaluate polynomials of high-enough degree, and at the same time has decryption procedure that can be expressed as a polynomial of low-enough degree. Once the degree of polynomials that can be evaluated by the scheme exceeds the degree of the decryption polynomial (times two), the scheme is called “bootstrappable” and it can then be converted into a fully homomorphic scheme.
Toward a bootstrappable scheme, Gentry described in [3] a somewhat homo-morphic scheme, which is roughly a GGH-type scheme [6,8] over ideal lattices. Gentry later proved [4] that with an appropriate key-generation procedure, the security of that scheme can be (quantumly) reduced to the worst-case hardness of some lattice problems in ideal lattices.
This somewhat homomorphic scheme is not yet bootstrappable, so Gentry described in [3] a transformation to squash the decryption procedure, reducing the degree of the decryption polynomial. This is done by adding to the public key an additional hint about the secret key, in the form of a “sparse subset-sum” problem (SSSP). Namely the public key is augmented with a big set of vectors, such that there exists a very sparse subset of them that adds up to the secret key. A ciphertext of the underlying scheme can be “post-processed ” using this additional hint, and the post-processed ciphertext can be decrypted with a low-degree polynomial, thus obtaining a bootstrappable scheme.
Stehlacute; and Steinfeld described in [14] two optimizations to Gentryrsquo;s scheme, one that reduces the number of vectors in the SSSP instance, and another that can be used to reduce the degree of the decryption polynomial (at the expense of introducing a small probability of decryption errors). We mention that in our implementation we use the first optimization but not the second1. Some improvements to Gentryrsquo;s key-generation procedure were discussed in [9].
1.1 The Smart-Vercauteren Implementation
The first attempt to implement Gentryrsquo;s scheme was made in 2010 by Smart and Vercauteren [13]. They chose to implement a variant of the scheme using “principal-ideal lattices ” of prime determinant. Such lattices can be represented implicitly by just two integers (regardless of their dimension), and moreover Smart and Vercauteren described a decryption method where the secret key is represented by a single integer. Smart and Vercauteren were able to imple-
剩余内容已隐藏，支付完成后下载完整资料
英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[278261]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
