Are all homomorphic encryption schemes based on latticed-based schemes?

Question

PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic encryption schemes based on lattice-based cryptography?

Answer 1

It depends what you mean with "homomorphic".

If you mean "compact and fully-homomorphic" (i.e., one can evaluate arbitrary polytime-computable functions on the ciphertexts, and the ciphertext size does not grow with the function being evaluated), then the answer is essentially yes. All known fully-homomorphic encryption schemes with compact ciphertexts use lattice techniques. Note, though, that this requires interpreting "lattice-techniques" in a relatively broad sense. Indeed:

• One can build FHE from indistinguishability obfuscation (here). In essence, this is a construction of a very different nature compared to standard lattice-based constructions. However, all known modern candidate constructions of iO use LWE somewhere (among other, sometimes non-standard, assumptions). See e.g. here, here, and here for the three latest results on this front. Also, any FHE built using this line of work would be completely inefficient in practice.
• One can build FHE from different assumptions related to approximate GCD, see this work. However, while the assumption is formally different, this employs essentially the same approach and ideas, but simply instantiated in a different setting that does not directly involve lattices.

If you do not mean "compact and fully-homomorphic", then no. More precisely:

• If you do not insist on compactness, there are generic methods to make any encryption scheme fully homomorphic - but the ciphertext will grow exponentially with the size of the evaluated circuit in general. See e.g. this work and this work.
• If you want compact ciphertexts, but not necessarily the ability to evaluate arbitrary functions, then there are many homomorphic encryption schemes around. (Textbook) RSA is multiplicatively homomorphic. The additive variant of ElGamal is additively homomorphic when the plaintexts are small enough. Goldwasser-Micali is homomorphic for the XOR operation. Paillier is additively homomorphic over $\mathbb{Z}_n$. BGN allows to evaluate degree-two polynomials, provided that the plaintext remains small. In addition, there are generic techniques to boost these limited homomorphisms (e.g. boosting degree-1 to a subclass of degree-2 polynomials), see e.g. this work.