Homomorphic encryption is a form of encryption that permits computations on encrypted data without the need to decrypt it. The output, when decrypted, is identical to that produced had the operations been performed on the unencrypted data. While there is a lack of practical schemes that deliver fully homomorphic encryption, there do exist practical schemes that exhibit some homomorphic capabilities. One example is RSA. Another is the discrete log-based systems, typically defined either modulo a prime p, or using elliptic curves. It is the latter that is the focus here.
There are two main types of homomorphic encryption: fully homomorphic encryption (FHE) and partially homomorphic encryption (PHE). FHE allows arbitrary computations to be performed on encrypted data, while PHE allows only certain types of computations to be performed, such as addition or multiplication using elliptic curves, with G being a generator of an elliptic curve group. The (homomorphic) operations that can be performed are:
- Addition: given points bG and cG, an expression of form a = b + c can be evaluated in encrypted form as aG = bG + cG.
- Scalar multiplication: given bG, an expression of the form, a = cb, where c is a constant, can be evaluated in encrypted form as aG = c(bG).