A previous post introduced homomorphic encryption (HE) and the challenges of applying it to deep learning. This post will dig into the three main types of HE schemes. We will first introduce the notion of a circuit, so that we can describe the properties of each type and differentiate between them. If you are wondering what each type allows you to do, then this post is for you.
Circuits
Say we have a function F that takes two input values x and y and computes x + x.y, a mathematical representation of this function is written as F(x, y) = x + x.y, but we can also represent F as a directed acyclic graph as shown in the figure below.
A circuit is a directed acyclic graph, which has a set of inputs, gates (e.g. addition or multiplication), edges that connect inputs and edges together, and a final output. Circuits have two properties of interest, namely, size and depth. The size is the number of gates a circuit has. The depth is the biggest distance between every possible input and the output. In the figure above, the circuit has a size of two as it has two gates, and a depth of two as the longest path is between y and the final output, and it has two gates along the way.
Types of Homomorphic Encryption Schemes
HE schemes are classified depending on the possible circuits they can evaluate on encrypted data, differences lies in the available gates to use, and the depth of those circuits. Next we discuss the three types of HE schemes, namely, partially, somewhat and fully homomorphic encryption.
Partially Homomorphic Encryption (PHE)
This type of scheme can evaluate any circuit composed of a single type of gate, addition or multiplication, but never both. It doesn’t restrict neither the size nor the depth of the circuit. This type is well suited for applications that only need to perform either addition or multiplication on encrypted data. The RSA cryptosystem is an example of a PHE that allow an unbounded number of modular multiplications.
Somewhat Homomorphic Encryption (SHE)
This type of scheme can evaluate circuit composed of both addition and multiplication gates, but with a restriction on the depth (e.g. circuits with a depth of at most 5). What we call Leveled Homomorphic Encryption is a subset of SHE, it can evaluate circuits with variable depth, but the depth must be set prior to encryption, so you must set your scheme’s parameters depending on the circuits you are aiming to evaluate. SHE is useful for evaluating low degree polynomials up to some level, however, we sometimes need to evaluate circuits of arbitrary depth.
Fully Homomorphic Encryption (FHE)
FHE schemes can evaluate circuits composed of both addition and multiplication gate, but in contrast to SHE, FHE has an unlimited circuit depth, which makes it suitable for deep learning applications. Although many FHE schemes have been proposed during the last decade, it has been difficult to use them in practice. Actually, FHE are now built on top of SHE. Thanks to Craig Gentry, who showed in his paper how we can build FHE out of SHE by using what he called bootstrapping.
Conclusion
Here we compared schemes based on the possible circuits they can evaluate, and FHE is the most powerful type based on this, however, to put such scheme into practice, someone need to consider other factors as well, we can mention the cost of evaluation, the size of ciphertexts, the domain of plaintexts (integers or real numbers), and the cost of bootstrapping for FHE schemes.
comments powered by Disqus