Fully Homomorphic Encryption Part One: A Gentle Intro

Preface

Recently I have taken CS355 (Topics in Cryptography) at Stanford. This was a comprehensive course on advanced crypto topics.

Photo by Markus Spiske on Unsplash

What is FHE?

I shall begin the post with a brief introduction of FHE, or Fully Homomorphic Encryption.

An Overview of Encryption Schemes

If you are familiar with crypto/security materials, you might know a few common encryption schemes such as AES and RSA. Although there’s a difference between symmetric and asymmetric encryption schemes, every scheme could be generalized in the following form.

Encryption Scheme Overview
  1. There is a KeyGen algorithm that generates the key used for both encrypting and decrypting. Notice that in a symmetric scheme both keys are the same, and in an asymmetric scheme the keys are different. (One is called Public Key and the other is called Private Key)
  2. The Encryption algorithm applies encryption to a given plaintext using the encryption key. Then it produces the ciphertext, which is the encrypted plaintext.
  3. The Decryption algorithm inverts the encryption done on a ciphertext using the decryption key. It restores the ciphertext back to the original plaintext.
Photo by Alex Machado on Unsplash

Homomorphic Encryption — an unexpected property

If encrypted ciphertexts look just like random garbage to any viewers, does this mean that ciphertexts are totally useless unless the corresponding decryption key is present?

Example: Anonymous Polling

We all know how polling works — for example, when a group of people want to vote on something (say whether they want to order Japanese for lunch), they could start a poll.

Photo by Holger Link on Unsplash

Levels of Homomorphic Encryption

We should be pretty comfortable with what HE is, and what kind of application it enables us to do. Now, I want to briefly go over different levels (or stages) of HE that will eventually lead us to Fully Homomorphic Encryption.

Partially Homomorphic Encryption

This is the very first stage of HE. If there exists an encryption scheme that is partially homomorphic, this means that this scheme is either additively homomorphic or multiplicatively homomorphic.

Somewhat Homomorphic Encryption

This next category brings us closer to our ideal world. If we say that an HE scheme is somewhat homomorphic, this means that the HE scheme is capable of doing both addition and multiplication to the original plaintexts but its capability is heavily limited.

Leveled Fully Homomorphic Encryption

Now we are getting even closer. If there exists an HE scheme in this category, then we are able to obtain both additions and multiplications to the plaintexts freely. There wouldn’t be any limits on how we combine ciphertexts together.

Fully Homomorphic Encryption

Finally, we arrived at our ultimate goal and the last category — FHE. In an FHE scheme, we can do arbitrary computation to the plaintexts by manipulating the ciphertexts. There are no complexity requirements on the functionality F. Also, an FHE scheme will always gate the ciphertext noise at a manageable threshold so it doesn’t blow up and destroy its observable state.

  1. KeyGen(1^λ)→sk: This is the key generation algorithm that produces the secret key. (This might vary depending on if it’s symmetric/asymmetric.)
  2. Enc(sk,μ∈{0,1})→ct: This is the bit-wise encryption algorithm that encrypts a single bit into some ciphertext.
  3. Dec(sk,ct)→μ: This is the decryption algorithm that recovers the bit μμ from the ciphertext.
  4. Eval(F,ct1,…,ctl)→ct^: This is the evaluation algorithm that combines ll ciphertexts together to obtain an encrypted representation of the evaluation of functionality F under the original l plaintexts. Here the functionality F is represented by a boolean circuit on ll inputs.
  1. The KeyGen, Enc algorithms work the same as before.
  2. When we want to evaluate a set of ciphertexts on functionality F, the Eval algorithm will simply output ciphertext ct^=(F,ct1, …, cti). Notice that we don’t restrict the output size here, so this size can just be as large as the input plus the description of the functionality F.
  3. Finally, when we want to decrypt the resulting ciphertext ct^, the decryption algorithm Dec simply reads the description of the functionality F, decrypts all the following ciphertexts one-by-one, and then apply F on the decrypted plaintexts.
Photo by Giammarco Boscaro on Unsplash

History of FHE

Before we proceed further into the theoretical land, I’d say let’s review the brief history of FHE together :)

Photo by Christian Wiediger on Unsplash

Worth-Mentioning Attempts at FHE

Before we continue explaining how Gentry’s FHE schemes work, I think it’ll be fun to go over some worth-mentioning attempts at build a FHE scheme.

RSA: Multiplicative HE

The very first candidate that exhibits some HE properties is RSA.

  1. First, fix a large number N=p⋅q where p,q are large primes.
  2. Then, find a pair of numbers e,d such that e⋅d=1 mod Φ(N). Here, Φ(⋅) is the Euler totient function and Φ(N)=(p−1)(q−1).
  3. Set (N,e) to be the public key, and (N,d) to be the private key.
  4. When encrypting a message m, simply compute Enc(pk,m) → m^e mod N.
  5. When decrypting a ciphertext c, simply compute Dec(pk,c) → c^d mod N.

Cyclic Group ElGamal: Additive HE

The second candidate that people tried was the ElGamal Encryption scheme over cyclic groups.

  1. First, sample a random element integer α that is less than the size of 𝔾, and set it to be the private key. We set g^α to be the public key.
  2. When we want to encrypt a message m, we will first sample a random integer β, and then we will output ciphertext ct=(v=g^β, e=pk^β⋅g^m).
  3. Later, when we want to decrypt this ciphertext (v,e), we will first compute w ← v^α = g^(αβ) = pk^β. Finally, we can obtain the message m←log_g(e/w).

Pairing-based Crypto: Somewhat HE

After people discovered how crypto based on groups (especially Elliptic Curve Crypto) work, cryptographers went through extensive research for plausible schemes in this realm. Around 20 years ago, Pairings became a fairly hot topic.

MPC-based HE

The last worthy attempt that I wanted to mention is MPC-based HE.

Photo by Andras Vas on Unsplash

Up Next: The GSW FHE Scheme

I think we should all have a pretty solid understanding of what FHE is at this moment.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Steven Yue

Steven Yue

Software Engineer & Part-time student. I code and do photography. Instagram: stevenyue. https://higashi.tech