Implementation of Homomorphic Encryption Technique Apurva Sachan Department of Computer Science and Engineering National Institute of Technology Rourkela Rourkela-769 008, Odisha, India Implementation of Homomorphic Encryption Technique Thesis submitted in partial fulfilment of the requirements for the degree of Master of Technology in Computer Science and Engineering (Specialization: Information Security) by Apurva Sachan (Roll No. 212CS2115 ) under the supervision of Prof. A. K. Turuk Department of Computer Science and Engineering National Institute of Technology Rourkela Rourkela, Odisha, 769 008, India June 2014 Department of Computer Science and Engineering National Institute of Technology Rourkela Rourkela-769 008, Odisha, India. Certificate This is to certify that the work in the thesis entitled Implementation Of Ho- momorphic encryption technique by Apurva Sachan is a record of an original research work carried out by her under my supervision and guidance in partial fulfillment of the requirements for the award of the degree of Master of Technology with the specialization of Information Security in the department of Computer Science and Engineering, National Institute of Technology Rourkela. Neither this thesis nor any part of it has been submitted for any degree or aca- demic award elsewhere. Place: NIT Rourkela Dr. A. K. Turuk Date: June 2, 2014 Professor, CSE Department NIT Rourkela, Odisha Acknowledgment I owe my personal gratitude to the people who support me to build this thesis with the direct and indirect help from the lots of people. First and foremost, I am very much thankful for my supervisor Dr. A. K. Turuk, for his endless support and advice during the work. He appreciate my ideas and let me work in my own way. He is available for the entire time when I need to discuss about the work. I am also thankful to our HOD Prof. S. K. Rath to provide the lab for the entire duration of my work. He is always encouraging and supportive for all his students. I am also acknowledging the resources provided by our institute NIT Rourkela. At last but not least, I am dedicating my work to my parents. Their love, support and encouragement provide me the way to pursue my interest. Apurva Sachan Roll: 212CS2115 Declaration I, Apurva Sachan (Roll No. 212CS2115) understand that plagiarism is defined as any one or the combination of the following : 1. Uncredited verbatim copying of individual sentences, paragraphs or illus- trations (such as graphs, diagrams, etc.) from any source, published or unpublished, including the internet. 2. Uncredited improper paraphrasing of pages or paragraphs (changing a few words or phrases, or rearranging the original sentence order). 3. Credited verbatim copying of a major portion of a paper (or thesis chapter) without clear delineation of who did or wrote what. (Source: IEEE, the Institute, Dec. 2004) I have made sure that all the ideas, expressions, graphs, diagrams, etc., that are not a result of my work, are properly credited. Long phrases or sentences that had to be used verbatim from published literature have been clearly identified using quotation marks. I affirm that no portion of my work can be considered as plagiarism and I take full responsibility if such a complaint occurs. I understand fully well that the guide of the thesis may not be in a position to check for the possibility of such incidences of plagiarism in this body of work. Place: NIT Rourkela Apurva Sachan Date: June 2, 2014 M.Tech., CSE Department NIT Rourkela, Odisha Abstract Fully homomorphic encryption has long been viewed as cryptography’s prized ”holy grail” amazingly helpful yet rather subtle. Starting from the breakthrough invention of FHE in 2009 by Craig Gentry, numerous schemes are presented then by various authors following the Gentry’s blueprint. We discuss the basic homomorphic encryption given by the DGHV over the inte- gers. It is modification of the Gentry’s scheme which is based on the ideal lattices. The main idea of the DGHV scheme is its simplicity for the arithmetic operations. Our plan is to reduce the size of the public key which ultimately reduces the space complexity of the algorithm. We then further introduces the concept of the ap- proximate common divisor problem on the DGHV scheme. We propose the GACD attack over the modulus switching and public key com- pression technique of DGHV scheme. The overall contribution of this work is analysis, design and performance of the scheme. Keywords: Homomorphic encryption; Fully Homomorphic Encryption; DGHV scheme; leveled DGHV scheme; approximate common divisor problem Contents Certificate i Acknowledgement ii Declaration iii Abstract iv List of Tables vii List of Algorithms viii 1 Introduction 2 1.1 Homomorphic Encryption in Cloud computing . . . . . . . . . . . . 3 1.2 Homomorphic Encryption Technique . . . . . . . . . . . . . . . . . 3 1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Outline of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review 7 3 Fully Homomorphic Encryption over integers 12 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Bootstrappble Encryption . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 A Somewhat Homomorphic Encryption Scheme . . . . . . . . . . . 13 3.4 Limitations of DGHV scheme . . . . . . . . . . . . . . . . . . . . . 15 3.5 The new DGHV scheme . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 Fully Homomorphic Scheme using DGHV scheme . . . . . . . . . . 16 4 Attacks on Homomorphic Encryption Technique 19 4.1 New Square Root Algorithm for PACD . . . . . . . . . . . . . . . . 19 4.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 v 4.1.2 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Performance and Optimization 25 5.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6 Conclusion & Future Work 29 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Bibliography 30 List of Tables 5.1 Concrete parameters as calculated for our implementation to pro- tect from various attacks. . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2 Time complexity of the scheme with Sage 6.1.1 [1] . . . . . . . . . . 26 vii List of Algorithms 4.1 Solving PACD by multipoint evaluation of univariate polynomials . 20 4.2 [T,D] ← TreeProduct(A) . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 V ← RecursiveEvaluation(f,t ,D) . . . . . . . . . . . . . . . . . . 22 i 4.4 V ← RecursiveEvaluation(f,t ,D) . . . . . . . . . . . . . . . . . . 23 i viii