Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Committee Chair/Advisor

Dr. Shuhong Gao

Committee Member

Dr. Elena Dimitrova

Committee Member

Dr. Matthew Macauley

Committee Member

Dr. Gretchen Matthews


With the advent of cloud computing, everyone from Fortune 500 businesses to personal consumers to the US government is storing massive amounts of sensitive data 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 Approximate 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 linked to more standard cryptographic primitives. After presenting several algorithms in the literature that attempt to solve the problem, we introduce some new algorithms to attack the problem.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.