Fully Homomorphic Encryption (FHE)

FHE Standardization Webpage
Vinod Vaikuntanathan FHE links

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

  4. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
    Gentry, Sahai & Waters - Crypto 2013 video

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

Other, less substantial, but practically important differences include

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

PALISADE Lattice Cryptography Library

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. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second
    Ducas & Micciancio - Eurocrypt 2015

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

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

  4. 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)

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

NFLlib: NTT Fast Lattice library

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. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
    Brakerski - Crypto 2012 video

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

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

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

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

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

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

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

  10. 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.