Homomorphic encryption

Description

Homomorphic encryption is a form of encryption with an additional evaluation capability for computing over encrypted data without access to the secret key. The result of such a computation remains encrypted. Homomorphic encryption can be viewed as an extension of public-key cryptography. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought of as homomorphisms between plaintext and ciphertext spaces.

Homomorphic encryption includes multiple types of encryption schemes that can perform different classes of computations over encrypted data. The computations are represented as either Boolean or arithmetic circuits.

Some common types of homomorphic encryption are partially homomorphic, somewhat homomorphic, leveled fully homomorphic, and fully homomorphic encryption:

• Partially homomorphic encryption encompasses schemes that support the evaluation of circuits consisting of only one type of gate, e.g., addition or multiplication.

• Somewhat homomorphic encryption schemes can evaluate two types of gates, but only for a subset of circuits.

• Leveled fully homomorphic encryption supports the evaluation of arbitrary circuits composed of multiple types of gates of bounded (pre-determined) depth.

• Fully homomorphic encryption (FHE) allows the evaluation of arbitrary circuits composed of multiple types of gates of unbounded depth and is the strongest notion of homomorphic encryption.

For the majority of homomorphic encryption schemes, the multiplicative depth of circuits is the main practical limitation in performing computations over encrypted data. Homomorphic encryption schemes are inherently malleable. In terms of malleability, homomorphic encryption schemes have weaker security properties than non-homomorphic schemes.

---

Approach

Homomorphic encryption schemes have been developed using different approaches. Specifically, fully homomorphic encryption schemes are often grouped into generations corresponding to the underlying approach.

Paillier

In the Paillier cryptosystem, if the public key is the modulus 𝑛 and the base 𝑔, then the encryption of a message 𝑚 is 𝐸(𝑚)=𝑔𝑚𝑟𝑛mod𝑛2, for some random 𝑟∈{0,…,𝑛−1}. The homomorphic property is then

𝐸(𝑚1)⋅𝐸(𝑚2)=(𝑔𝑚1𝑟1𝑛)(𝑔𝑚2𝑟2𝑛)mod𝑛2=𝑔𝑚1+𝑚2(𝑟1𝑟2)𝑛mod𝑛2=𝐸(𝑚1+𝑚2).

---

Microsoft SEAL

Algorithms

Microsoft SEAL supports both asymmetric and symmetric encryption algorithms.

Scheme types

Microsoft SEAL comes with two different homomorphic encryption schemes with very different properties:

• BFV: The BFV scheme allows modular arithmetic to be performed on encrypted integers. For applications where exact values are necessary, the BFV scheme is the only choice.

• CKKS: The CKKS scheme allows additions and multiplications on encrypted real or complex numbers, but yields only approximate results. In applications such as summing up encrypted real numbers, evaluating machine learning models on encrypted data, or computing distances of encrypted locations CKKS is going to be by far the best choice.

Compression

Data compression can be achieved by building SEAL with Zlib support. By default, data is compressed using the DEFLATE algorithm which achieves significant memory footprint savings when serializing objects such as encryption parameters, ciphertexts, plaintexts, and all available keys: Public, Secret, Relin (relinearization), and Galois. Compression can always be disabled.