Skip to content

Homomorphic Encryption

HE

HE (Homomorphic Encryption) is a special encryption method that allows computations to be performed on ciphertexts, producing results that are still encrypted. That is, processing ciphertext directly yields the same result as processing the plaintext first and then encrypting the result.

If we define an operator △, for encryption algorithm E and decryption algorithm D, satisfying:

\[ E(X△Y)=E(X)△E(Y) \]

then the operation satisfies the homomorphic property.

Homomorphic encryption systems are broadly classified into four categories: Partially Homomorphic, Somewhat Homomorphic, Leveled Fully Homomorphic, and Fully Homomorphic.

Partially Homomorphic Encryption

Partially Homomorphic Encryption (PHE) allows specific algebraic operations (such as addition or multiplication) to be performed on ciphertexts, where the decrypted result matches the result of performing the same operation on the plaintexts.

  • Additive homomorphism: Satisfies \(E(x)E(y) = E(x + y)\). For example, in elliptic curve encryption, \(E(x) = gx\) has additive homomorphic properties. Pedersen Commitments also have additive homomorphism.
  • Multiplicative homomorphism: Satisfies \(E(X)E(Y) = E(X*Y)\). A typical example is the RSA encryption algorithm, where \(E(x) = x^e\) (where e is the public key), so \(E(x)E(y) = x^e y^e = (xy)^e = E(xy)\), exhibiting multiplicative homomorphism.

In encrypted computation, additive homomorphism can complete any addition operation, and multiplicative homomorphism can do the same for multiplication.

Somewhat Homomorphic Encryption

If we want both multiplication of private inputs and linear combinations, simple partially homomorphic encryption algorithms (RSA, ElGamal) cannot accomplish this. In such cases, somewhat homomorphic encryption may be needed.

Somewhat homomorphic encryption can perform both addition and multiplication on ciphertexts. However, it is important to note that somewhat homomorphic encryption is limited in the number of additions and multiplications it can perform, and the functions it can compute are within a finite range. This is because we cannot compute functions of arbitrary logic and depth.

Leveled Fully Homomorphic Encryption

Leveled fully homomorphic encryption can perform arbitrary combinations of addition and multiplication on ciphertexts without limitations on the number of operations.

However, leveled fully homomorphic encryption introduces a new complexity upper bound \(L\), which constrains the complexity of the function \(F\).

Fully Homomorphic Encryption

A fully homomorphic encryption system has no limitations on computation methods. It allows a third party to perform computations on encrypted data and obtain encrypted results, which can be returned to anyone possessing the decryption key for the original data. The third party cannot decrypt either the data or the results on its own.