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.
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.
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski & Vaikuntanathan - SIAM J. Comp. 2014 / FOCS 2011
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages
Brakerski & Vaikuntanathan - Crypto 2011
Lattice-based FHE as secure as PKE
Brakerski & Vaikuntanathan - ITCS 2014
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
C++ library implementing the [BGV12] encryption scheme, including optimizations from [SV11] and [GHS12]. The algorithms in the library are described in [HS14] and [HS15].
Algorithms in HElib
Halevi & Shoup - Crypto 2014, video
Bootstrapping for HElib
Halevi & Shoup - Eurocrypt 2015
Faster Homomorphic Linear Transformations in HElib
(Halevi & Shoup - Crypto 2018)
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Brakerski, Gentry & Vaikuntanathan - ToCT 2014 / ITCS 2012
Fully homomorphic SIMD operations
Smart, Vercauteren - DCC 2014
Homomorphic Evaluation of the AES Circuit
Gentry, Halevi & Smart - Crypto 2012 video
General purpose C++ library for lattice cryptography.
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).
FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second
Ducas & Micciancio - Eurocrypt 2015
Faster Bootstrapping with Polynomial Error
(AlperinSheriff & Peikert - Crypto 2014)
TFHE: Fast Fully Homomorphic Encryption over the Torus
(Chillotti, Gama, Georgieva & Izabachene - Invited to J. Cryptology, Prelim. versions in AsiaCrypt 2016/ AsiaCrypt 2017, video)
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.
FHEW with Efficient Multibit Bootstrapping
(Biasse & Ruiz - LatinCrypt 2015)
Large FHE Gates from Tensored Homomorphic Accumulator (Bonnoron, Ducas & Fillinger - AfricaCrypt 2018)
Ring Packing and Amortized FHEW Bootstrapping
(Micciancio & Sorrell - ICALP 2018)
Homomorphic Encryption for Arithmetic of Approximate Numbers
(Cheon, Kim, Kim & Song - AsiaCrypt 2017)
Bootstrapping for Approximate Homomorphic Encryption
(Cheon, Han, Kim, Kim & Song - EuroCrypt 2018)
A Full RNS Variant of Approximate Homomorphic Encryption__ (Cheon, Han, Kim, Kim & Song - SAC 2018)
Improved Bootstrapping for Approximate Homomorphic Encryption
(Chen, Chillotti & Song - Eurocrypt 2019)
General purpose software framework for lattice-based cryptography written in the functional programming language Haskell, offering strong abstraction and safety properties.
HEXL Code on GitHub
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.
A Simple BGN-Type Cryptosystem from LWE
Gentry, Halevi & Vaikuntanathan - EuroCrypt 2010
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
Brakerski - Crypto 2012 video
Field switching in BGV-style homomorphic encryption
Gentry, Halevi, Peikert & Smart - JCS 2013/SCN 2012
Fully Homomorphic Encryption with Polylog Overhead
Gentry, Halevi & Smart - Eurocrypt 2012 video
Practical Bootstrapping in Quasilinear Time
AlperinSheriff & Peikert - Crypto 2013
Packed Ciphertexts in LWE-Based Homomorphic Encryption
Brakerski, Gentry & Halevi - PKC 2013
An Efficient Leveled Identity-Based FHE
Wang, Wang & Li - NSS 2015
LWE-Based FHE with Better Parameters
Wang, Wang & Li - IWSEC 2015
Packing Messages and Optimizing Bootstrapping in GSW-FHE
Hiromasa, Abe & Okamoto - PKC 2015
Sanitization of FHE Ciphertexts
(Ducas & Stehle - EuroCrypt 2016)
Evaluations and Comparisons
Can homomorphic encryption be practical?
(Naehrig, Lauter & Vaikuntanathan - CCSW 2011)
A Comparison of the Homomorphic Encryption Schemes FV and YASHE
(Lepoint & Naehrig - AfricaCrypt 2014)
Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning
(Boura, Gama & Georgieva - 2018)
Specialized implementations
Polynomial multipliers for fully homomorphic encryption on FPGA
(JayetGriffon, Cornelie, Maistri, ElbazVincent & Leveugle - ReConFig 2015)
Accelerating bootstrapping in FHEW using GPUs
(Lee, Lee, Cheon & Paek - ASAP 2015)
Applications
Theses
Other
Quantum Fully Homomorphic Encryption with Verification
(Alagic, Dulek, Schaffner & Speelman - AsiaCrypt 2017)
A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes
(Bajard, Eynard, Hasan & Zucca - SAC 2016)
Efficient Reductions in Cyclotomic Rings - Application to Ring-LWE Based FHE Schemes
(Bajard, Eynard, Hasan, Martins, Sousa & Zucca - SAC 2017)
An Improved RNS Variant of the BFV Homomorphic Encryption Scheme
(Halevi, Polyakov & Shoup - 2018)
Faster Homomorphic Function Evaluation Using Non-integral Base Encoding
(Bonte, Bootland, Bos, Castryck, Iliashenko & Vercauteren - CHES 2017)
High-Precision Arithmetic in Homomorphic Encryption
(Chen, Laine, Player & Xia - CT-RSA 2018)
More recent tutorials typically cover newer FHE schemes.