The paper presents a fully homomorphic encryption (FHE) scheme over the integers, which is both conceptually simple and secure. The scheme is based on a "bootstrappable" somewhat homomorphic encryption (SHE) scheme, which can be transformed into a fully homomorphic scheme using Gentry's techniques. The key innovation is the use of elementary modular arithmetic and integer operations, avoiding the need for ideal lattices over polynomial rings. The security of the scheme is reduced to the hardness of finding an approximate integer greatest common divisor (gcd), which is shown to be difficult under the chosen parameters. The scheme is constructed using a symmetric encryption approach, where the secret key is an odd integer, and the public key consists of a set of integers that are close to multiples of the secret key. Encryption involves adding a bit to a random subset sum of the public key elements, while decryption involves computing the parity of the ciphertext modulo the secret key. This scheme is then extended to 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 gcd problem, where the goal is to recover the secret key from the public key elements. The paper analyzes the hardness of this problem, building on previous work by Howgrave-Graham. The parameters of the scheme are chosen to ensure that the approximate gcd problem remains difficult, even with the addition of noise and large public key elements. The paper also discusses various optimizations, including modular reduction during evaluation to keep ciphertext sizes manageable and ciphertext compression to reduce communication complexity. These optimizations are shown to be secure under additional hardness assumptions, such as the $\phi$-hiding assumption. The scheme is shown to be secure against known attacks on the approximate gcd problem, including brute-force, continued fractions, and lattice-based methods. The paper concludes that the proposed FHE scheme is both conceptually simple and secure, with parameters chosen to ensure resistance to all known attacks. The scheme is further extended to a fully homomorphic encryption scheme by "squashing" the decryption circuit, which involves adding extra information to the public key to enable efficient decryption of post-processed ciphertexts. This allows the scheme to be bootstrappable, enabling it to evaluate arbitrary circuits.The paper presents a fully homomorphic encryption (FHE) scheme over the integers, which is both conceptually simple and secure. The scheme is based on a "bootstrappable" somewhat homomorphic encryption (SHE) scheme, which can be transformed into a fully homomorphic scheme using Gentry's techniques. The key innovation is the use of elementary modular arithmetic and integer operations, avoiding the need for ideal lattices over polynomial rings. The security of the scheme is reduced to the hardness of finding an approximate integer greatest common divisor (gcd), which is shown to be difficult under the chosen parameters. The scheme is constructed using a symmetric encryption approach, where the secret key is an odd integer, and the public key consists of a set of integers that are close to multiples of the secret key. Encryption involves adding a bit to a random subset sum of the public key elements, while decryption involves computing the parity of the ciphertext modulo the secret key. This scheme is then extended to 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 gcd problem, where the goal is to recover the secret key from the public key elements. The paper analyzes the hardness of this problem, building on previous work by Howgrave-Graham. The parameters of the scheme are chosen to ensure that the approximate gcd problem remains difficult, even with the addition of noise and large public key elements. The paper also discusses various optimizations, including modular reduction during evaluation to keep ciphertext sizes manageable and ciphertext compression to reduce communication complexity. These optimizations are shown to be secure under additional hardness assumptions, such as the $\phi$-hiding assumption. The scheme is shown to be secure against known attacks on the approximate gcd problem, including brute-force, continued fractions, and lattice-based methods. The paper concludes that the proposed FHE scheme is both conceptually simple and secure, with parameters chosen to ensure resistance to all known attacks. The scheme is further extended to a fully homomorphic encryption scheme by "squashing" the decryption circuit, which involves adding extra information to the public key to enable efficient decryption of post-processed ciphertexts. This allows the scheme to be bootstrappable, enabling it to evaluate arbitrary circuits.