This paper presents a fully homomorphic encryption (FHE) scheme over the integers, which is both conceptually simple and secure. The scheme is based on elementary modular arithmetic and leverages Gentry's technique to transform a "bootstrappable" somewhat homomorphic scheme into a fully homomorphic one. Unlike previous schemes that use ideal lattices over polynomial rings, this scheme uses only addition and multiplication over the integers. The security of the scheme is reduced to the hardness of finding an approximate integer gcd, which is shown to be difficult based on prior work by Howgrave-Graham. The scheme is constructed using a symmetric encryption scheme where the secret key is an odd integer, and the public key consists of integers that are near-multiples of the secret key. Encryption involves adding a bit to a random subset sum of the public key elements. The scheme is then converted into a public key scheme by using multiple "encryptions of zero" as part of the public key. The security of the scheme is reduced to the approximate integer gcd problem, which is shown to be hard under the chosen parameters. The scheme is also shown to be resistant to various known attacks, including brute-force, continued fractions, and lattice-based methods. The paper also discusses optimizations to reduce ciphertext size and improve efficiency, including modular reductions during evaluation and ciphertext compression techniques. The scheme is proven to be secure under the approximate gcd assumption, and the paper provides a reduction from the security of the scheme to the hardness of the approximate gcd problem. The paper also discusses the use of bootstrapping to transform the somewhat homomorphic scheme into a fully homomorphic one, and presents a detailed analysis of the security of the scheme under various attacks. The paper concludes with a discussion of the implications of the results for the broader field of homomorphic encryption.This paper presents a fully homomorphic encryption (FHE) scheme over the integers, which is both conceptually simple and secure. The scheme is based on elementary modular arithmetic and leverages Gentry's technique to transform a "bootstrappable" somewhat homomorphic scheme into a fully homomorphic one. Unlike previous schemes that use ideal lattices over polynomial rings, this scheme uses only addition and multiplication over the integers. The security of the scheme is reduced to the hardness of finding an approximate integer gcd, which is shown to be difficult based on prior work by Howgrave-Graham. The scheme is constructed using a symmetric encryption scheme where the secret key is an odd integer, and the public key consists of integers that are near-multiples of the secret key. Encryption involves adding a bit to a random subset sum of the public key elements. The scheme is then converted into a public key scheme by using multiple "encryptions of zero" as part of the public key. The security of the scheme is reduced to the approximate integer gcd problem, which is shown to be hard under the chosen parameters. The scheme is also shown to be resistant to various known attacks, including brute-force, continued fractions, and lattice-based methods. The paper also discusses optimizations to reduce ciphertext size and improve efficiency, including modular reductions during evaluation and ciphertext compression techniques. The scheme is proven to be secure under the approximate gcd assumption, and the paper provides a reduction from the security of the scheme to the hardness of the approximate gcd problem. The paper also discusses the use of bootstrapping to transform the somewhat homomorphic scheme into a fully homomorphic one, and presents a detailed analysis of the security of the scheme under various attacks. The paper concludes with a discussion of the implications of the results for the broader field of homomorphic encryption.