Back to search

Clemson University

Homomorphic Encryption and the Approximate GCD Problem

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Black, Nathanael
Contributors dc:contributor
  • Dr. Shuhong Gao
  • Dr. Elena Dimitrova
  • Dr. Matthew Macauley
  • Dr. Gretchen Matthews

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/1280

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Black, Nathanael. Homomorphic Encryption and the Approximate GCD Problem. Dissertation thesis, https://open.clemson.edu/all_dissertations/1280