# Fully Homomorphic Encryption (FHE)

The first candidate fully homomorphic encryption scheme was proposed by (Gentry, STOC 2009). Current FHE schemes still make use of the bootstrapping methodology originally proposed by Gentry, but applied to quite different cryptosystems. To a large extent, all known FHE schemes are based on lattices, or closely related problems. Here we focus on solutions based on the standard lattice problems LWE and RingLWE. For an historical account and early developments of FHE, see the wikipedia page.

## Foundations

The first FHE schemes based on the hardness of standard lattice problems (with superpolynomial approximation factors) were given by Brakerski and Vaikuntanathan, first in (2) using RingLWE, and then in (1) using LWE in general lattices. The underlying approximation factor was reduced to a polynomial in (3), using techniques from (4) to improve bootstrapping.

1. Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski & Vaikuntanathan - SIAM J. Comp. 2014 / FOCS 2011

2. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages
Brakerski & Vaikuntanathan - Crypto 2011

3. Lattice-based FHE as secure as PKE
Brakerski & Vaikuntanathan - ITCS 2014

The underlying cryptosystem is essentially a standard LWE (or RingLWE) (public key or secret key) encryption scheme, which already provides some linear homomoprhic properties. The same is essentially true for all subsequent FHE schemes, described in this page. The technical novelty and primary differences between the various schemes are

• the (homomorphic) multiplication method, used to compute the product of ciphertexts, and
• the bootstrapping procedure, and its implementation in terms of a possibly different homomorphic encryption scheme.

Other, less substantial, but practically important differences include

• how messages are encoded in the (Ring)LWE native plaintext space. This may involve packing several messages in a single (Ring)LWE ciphertext, and additional homomorphic operations which are specific to the encoding method, and
• implementation details, including specific choices of the integer modulus, polynomial ring, and concrete representation of ring elements that support faster algorithms and/or conversion procedures.

## HElib: Implementing Homomorphic Encryption

C++ library implementing the [BGV12] encryption scheme, including optimizations from [SV11] and [GHS12]. The algorithms in the library are described in [HS14] and [HS15].

1. Algorithms in HElib
Halevi & Shoup - Crypto 2014, video

2. Bootstrapping for HElib
Halevi & Shoup - Eurocrypt 2015

3. Faster Homomorphic Linear Transformations in HElib
(Halevi & Shoup - Crypto 2018)

4. (Leveled) Fully Homomorphic Encryption without Bootstrapping
Brakerski, Gentry & Vaikuntanathan - ToCT 2014 / ITCS 2012

5. Fully homomorphic SIMD operations
Smart, Vercauteren - DCC 2014

6. Homomorphic Evaluation of the AES Circuit
Gentry, Halevi & Smart - Crypto 2012 video

General purpose C++ library for lattice cryptography.

## FHEW/TFHE: Homomorphic Encryption with Fast Bootstrapping

Lattice based cryptography produces noisy ciphertexts, and the amount of noise grows as homomorphic operations are performed on them. So, in order to perform arbitrary computations, ciphertexts need to be periodically refreshed. This refreshing procedure, called bootstrapping, turns an encryption scheme with bounded homomorphic properties into a fully homomorphic one. Bootstrapping is by far the main efficiency bottleneck of current FHE schemes.

The FHEW (11) scheme was the first to show that by refreshing the ciphertexts after every single operation, it is possible to reduce the bootstrapping time to a fraction of a second. FHEW introduces a new method to compute boolean gates on encrypted data that greatly simplifies bootstrapping, and implements a variant of the bootstrapping procedure of (12), based on a Ring variant of the GSW cryptosystem (4). The efficiency of FHEW was further improved by the TFHE scheme (13), which implements a ring variant of the bootstrapping procedure from (14) using a method similar to (11).

1. Faster Bootstrapping with Polynomial Error
(AlperinSheriff & Peikert - Crypto 2014)

2. TFHE: Fast Fully Homomorphic Encryption over the Torus
(Chillotti, Gama, Georgieva & Izabachene - Invited to J. Cryptology, Prelim. versions in AsiaCrypt 2016/ AsiaCrypt 2017, video)

3. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems
(Gama, IzabachÃ¨ne, Nguyen & Xie - Eurocrypt 2016)

The main advantage of these schemes over other implementations is that they provide building blocks for homomorphic computation that are arbitrarily composable. The drawback is that the amount of computation performed in-between bootstrappings is rather limited: in FHEW, this was just a single bit operation. This is improved in (15) (16) to larger gates, and (MS18) with a new bootstrapping procedure which simultaneously refreshes n ciphertexts at essentially the same asymptotic cost of a single FHEW bootstrapping.

1. FHEW with Efficient Multibit Bootstrapping
(Biasse & Ruiz - LatinCrypt 2015)

2. Large FHE Gates from Tensored Homomorphic Accumulator (Bonnoron, Ducas & Fillinger - AfricaCrypt 2018)

3. Ring Packing and Amortized FHEW Bootstrapping
(Micciancio & Sorrell - ICALP 2018)

## HEAAN: FHE on approximate numbers

1. Homomorphic Encryption for Arithmetic of Approximate Numbers
(Cheon, Kim, Kim & Song - AsiaCrypt 2017)

2. Bootstrapping for Approximate Homomorphic Encryption
(Cheon, Han, Kim, Kim & Song - EuroCrypt 2018)

3. A Full RNS Variant of Approximate Homomorphic Encryption__ (Cheon, Han, Kim, Kim & Song - SAC 2018)

4. Improved Bootstrapping for Approximate Homomorphic Encryption
(Chen, Chillotti & Song - Eurocrypt 2019)

## SEAL: Simple Encrypted Arithmetic Library

1. Simple Encrypted Arithmetic Library - SEAL v2.1
(Chen, Laine & Player - Financial Cryptography 2017)

## Lol: A library for ring-based lattice cryptography

General purpose software framework for lattice-based cryptography written in the functional programming language Haskell, offering strong abstraction and safety properties.

1. Lol: Functional Lattice Cryptography
Crockett & Peikert - CCS 2016

## HEXL: Intel Homorphic Encryption Acceleration Library

HEXL Code on GitHub

## Other papers

This is only a very partial list, as new FHE papers (especially implementation and application ones) keep poppoing up continuously. See DBLP for a more comprehensive listing.

1. A Simple BGN-Type Cryptosystem from LWE
Gentry, Halevi & Vaikuntanathan - EuroCrypt 2010

2. Field switching in BGV-style homomorphic encryption
Gentry, Halevi, Peikert & Smart - JCS 2013/SCN 2012

3. Fully Homomorphic Encryption with Polylog Overhead
Gentry, Halevi & Smart - Eurocrypt 2012 video

4. Practical Bootstrapping in Quasilinear Time
AlperinSheriff & Peikert - Crypto 2013

5. Packed Ciphertexts in LWE-Based Homomorphic Encryption
Brakerski, Gentry & Halevi - PKC 2013

6. An Efficient Leveled Identity-Based FHE
Wang, Wang & Li - NSS 2015

7. LWE-Based FHE with Better Parameters
Wang, Wang & Li - IWSEC 2015

8. Packing Messages and Optimizing Bootstrapping in GSW-FHE
Hiromasa, Abe & Okamoto - PKC 2015

9. Sanitization of FHE Ciphertexts
(Ducas & Stehle - EuroCrypt 2016)

Evaluations and Comparisons

1. Can homomorphic encryption be practical?
(Naehrig, Lauter & Vaikuntanathan - CCSW 2011)

2. A Comparison of the Homomorphic Encryption Schemes FV and YASHE
(Lepoint & Naehrig - AfricaCrypt 2014)

3. Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning
(Boura, Gama & Georgieva - 2018)

Specialized implementations

1. Polynomial multipliers for fully homomorphic encryption on FPGA
(JayetGriffon, Cornelie, Maistri, ElbazVincent & Leveugle - ReConFig 2015)

2. Accelerating bootstrapping in FHEW using GPUs
(Lee, Lee, Cheon & Paek - ASAP 2015)

Applications

1. Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption
(Yasuda, Shimoyama, Kogure, Yokoyama & Koshiba - ISP 2015)

Theses

1. Towards practical fully homomorphic encryption
Alperin-Sheriff (Georgia Tech, PhD 2015)

Other

1. Quantum Fully Homomorphic Encryption with Verification
(Alagic, Dulek, Schaffner & Speelman - AsiaCrypt 2017)

2. A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes
(Bajard, Eynard, Hasan & Zucca - SAC 2016)

3. Efficient Reductions in Cyclotomic Rings - Application to Ring-LWE Based FHE Schemes
(Bajard, Eynard, Hasan, Martins, Sousa & Zucca - SAC 2017)

4. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme
(Halevi, Polyakov & Shoup - 2018)

5. Faster Homomorphic Function Evaluation Using Non-integral Base Encoding
(Bonte, Bootland, Bos, Castryck, Iliashenko & Vercauteren - CHES 2017)

6. High-Precision Arithmetic in Homomorphic Encryption
(Chen, Laine, Player & Xia - CT-RSA 2018)

## Tutorials (Video)

More recent tutorials typically cover newer FHE schemes.

• Simons Institute: FHE Part I, FHE Part II (Shai Halevi, May 2015)
• Simons Institute: FHE (Zvika Brakerski, July 2015)
• UC Irvine: Homomorphic Encryption (Shai Halevi, Lattices with Symmetries workshop, 2013)
• Bar Ilan U: FHE (Craig Gentry, Winter School on Lattice Cryptography, 2012)
• Bar Ilan U: FHE (Shai Halevi, Winter School on Secure Computation, 2011)
• IACR: FHE Part I, FHE Part II (Shai Halevi, 2011)