Clemson University TigerPrints All Dissertations Dissertations 8-2014 Homomorphic Encryption and the Approximate GCD Problem Nathanael Black Clemson University, [email protected] Follow this and additional works at:https://tigerprints.clemson.edu/all_dissertations Part of theApplied Mathematics Commons Recommended Citation Black, Nathanael, "Homomorphic Encryption and the Approximate GCD Problem" (2014).All Dissertations. 1280. https://tigerprints.clemson.edu/all_dissertations/1280 This Dissertation is brought to you for free and open access by the Dissertations at TigerPrints. It has been accepted for inclusion in All Dissertations by an authorized administrator of TigerPrints. For more information, please [email protected]. Homomorphic Encryption and the Approximate GCD Problem A Dissertation Presented to the Graduate School of Clemson University In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy Mathematical Science by Nathanael David Black August 2014 Accepted by: Dr. Shuhong Gao, Committee Chair Dr. Elena Dimitrova Dr. Matthew Macauley Dr. Gretchen Matthews Abstract With the advent of cloud computing, everyone from Fortune 500 businesses to personalconsumerstotheUSgovernmentisstoringmassiveamountsofsensitivedata in service centers that may not be trustworthy. It is of vital importance to leverage the benefits of storing data in the cloud while simultaneously ensuring the privacy of the data. Homomorphic encryption allows one to securely delegate the processing of private data. As such, it has managed to hit the sweet spot of academic interest and industry demand. Though the concept was proposed in the 1970s, no cryptosystem realizing this goal existed until Craig Gentry published his PhD thesis in 2009. In this thesis, we conduct a study of the two main methods for construction of homomorphic encryption schemes along with functional encryption and the hard problems upon which their security is based. These hard problems include the Ap- proximate GCD problem (A-GCD), the Learning With Errors problem (LWE), and various lattice problems. In addition, we discuss many of the proposed and in some cases implemented practical applications of these cryptosystems. Finally, we focus on the Approximate GCD problem (A-GCD). This problem forms the basis for the security of Gentry’s original cryptosystem but has not yet been linkedtomorestandardcryptographicprimitives. Afterpresentingseveralalgorithms intheliteraturethatattempttosolvetheproblem, weintroducesomenewalgorithms to attack the problem. ii Table of Contents Title Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 The Approximate GCD Problem . . . . . . . . . . . . . . . . . . . . 11 2.2 Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The LWE Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Gentry’s Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 LWE Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4 Functional Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1 Private Information Retrieval . . . . . . . . . . . . . . . . . . . . . . 73 4.2 Privacy Preserving Computations . . . . . . . . . . . . . . . . . . . . 79 4.3 Functional Encryption Applications . . . . . . . . . . . . . . . . . . . 82 5 Approximate GCD Algorithms . . . . . . . . . . . . . . . . . . . . . 85 5.1 Direct Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Lattice Based Approaches . . . . . . . . . . . . . . . . . . . . . . . . 92 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 iii Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 iv List of Tables 1.1 Functions in a Homomorphic Cryptosystem . . . . . . . . . . . . . . 8 3.1 Early Homomorphic Encryption Schemes . . . . . . . . . . . . . . . . 21 3.2 Gentry Symmetric Key Cryptosystem . . . . . . . . . . . . . . . . . . 26 3.3 Grade School Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Gentry Public Key Cryptosystem . . . . . . . . . . . . . . . . . . . . 40 3.5 Summary of Gentry Approach Cryptosystems . . . . . . . . . . . . . 43 3.6 LWE Symmetric Key SHS . . . . . . . . . . . . . . . . . . . . . . . . 54 3.7 LWE Public Key SHS . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.8 Tokens for wires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.9 Functions in an Attribute-Based Encryption System . . . . . . . . . . 70 5.1 Greedy List Reduction Results . . . . . . . . . . . . . . . . . . . . . . 91 5.2 Standard LLL Reduction Results . . . . . . . . . . . . . . . . . . . . 97 5.3 POST PROCESS Results . . . . . . . . . . . . . . . . . . . . . . . . 102 v List of Figures 1.1 Homomorphic Encryption Overview . . . . . . . . . . . . . . . . . . . 4 1.2 Majority Circuit 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Majority Circuit 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Lattice Basis B = {b ,b } for L . . . . . . . . . . . . . . . . . . . . 12 1 2 2.2 Lattice Basis D = {d ,d } for L . . . . . . . . . . . . . . . . . . . . 12 1 2 3.1 Three for Two Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2 Section 1 Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 AND Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4 AND Gate with Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . 67 vi Notation Symbol Explanation F Denotes any finite field F Denotes the finite field with p elements p N Denotes the set of natural numbers R Denotes the set of real numbers Rn Denotes the set of n-dimensional vectors where each component is an element of R Z Denotes the ring of integers Z Denotes the ring of integers modulo p p Zn Denotes the set of n-dimensional vectors where each component is an p element of Z p x Denotes a vector x Denotes the i-th vector in an indexed set i x Denotes the i-th component of the vector x [i] (cid:107)x(cid:107) Denotes the norm of x, assumed to be the standard Euclidean norm (cid:107)x(cid:107) Denotes the p-norm of x p n (cid:88) (cid:104)x,y(cid:105) Denotes the inner product of x,y ∈ Rn, given by x y i i i=1 det(M) Denotes the determinant of the matrix M (cid:98)a(cid:101) Denotes rounding a to the nearest integer a mod p Denotes reducing a modulo p into the interval (−p/2,p/2] |a| Denotes the binary size of a (i.e. the number of digits in the binary bin representation of a) vii Symbol Explanation a Denotes the i-th bit in the binary representation of a (i) log(a) Denotes the base 2 logarithm of a viii Chapter 1 Introduction Inthelast40years,thecomputerandtheinternethavefundamentallychanged the way data is stored and transferred. During this time, many cryptosystems have been proposed to protect this digital data. Now, the rapid adoption and widespread use of cloud computing is posing a new challenge. Can data be stored and processed remotely without compromising privacy? A solution to this problem is homomorphic encryption. A cryptosystem is a scheme for securing data. Unsecured data is called a plaintext or message, and secured data is called a ciphertext. An encryption function E and an encryption key K are used to secure data and a decryption function D and a decryption key k are used to retrieve data. The functions E and D are such that for the correct keys and a plaintext m. (cid:0) (cid:1) D E(m) = m When the key for encryption and decryption are the same (i.e. K = k), the cryp- tosystem is said to be a symmetric key system. If person A wants to send data to 1