Fully Homomorphic Encryption (FHE)

FHE Standardization Webpage
Vinod Vaikuntanathan FHE links

The first candidate fully homomorphic encryption scheme was proposed by Gentry in

  1. Fully homomorphic encryption using ideal lattices
    Gentry - STOC 2009

To a large extent, all known FHE schemes are based on lattices, or closely related problems. Here we focus on solutions based on standard lattice problems, like LWE and RingLWE. For an historical account and early developments of FHE, see the wikipedia page. All known FHE schemes still make use of the bootstrapping methodology origially proposed in (1), but applied to quite different cryptosystems.

Foundations

The first FHE schems based on LWE and RingLWE lattice problems (for superpolynomial approximation factors) were given by Brakerski and Vaikuntanathan in

  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

Reducing the LWE approximation to a (more standard) polynomial factor was first accomplished in

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

building on techniques from

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

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. (Leveled) Fully Homomorphic Encryption without Bootstrapping
    Brakerski, Gentry & Vaikuntanathan - ToCT 2014 / ITCS 2012

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

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

PALISADE Lattice Cryptography Library

General purpose C++ library for lattice cryptography.

FHEW: Fully Homomorphic Encryption using FFTW

FHEW is a small C/C++ fully homomorphic encryption library, cabable of evaluating an arbitrarily composable boolean gate in less than a second. It introduces a new method to compute boolean gates on encrypted data that greatly simplifies bootstrapping, and implements a variant of the AP14 bootstrapping procedure based on a Ring version of the GSW cryptosystem.

  1. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second
    Ducas & Micciancio - Eurocrypt 2015

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

TFHE: Torus FHE

TFHE improves FHEW with several additional optimizations.

  1. Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds
    Chillotti, Gama, Georgieva & Izabachene - AsiaCrypt 2016 video

  2. Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping
    Chillotti, Gama, Georgieva & Izabachene - AsiaCrypt 2017

SEAL: Simple Encrypted Arithmetic Library

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

Other papers

  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. FHEW with Efficient Multibit Bootstrapping
    Biasse & Ruiz - LatinCrypt 2015

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

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

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

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

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

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

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

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

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

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

Tutorials (Video)

More recent tutorials typically cover newer FHE schemes.