Freely subscribe to our NEWSLETTER

Homomorphic encryption (HE)

While traditional encryption schemes can be used to privately outsource data storage to the cloud, the data cannot be used for computations without first decrypting it. This results in a huge loss of utility. For example, a secure cloud service may require a user to download their encrypted data, decrypt it locally, and perform necessary computations, instead of simply returning an encrypted result to the user. Homomorphic encryption solves this problem, as it allows the cloud service to perform the computations while protecting the customer’s data with a state-of-the-art cryptographic security guarantee. The cloud only ever sees encrypted data, and only the customer can reveal the result of the computation. One of the advantages of the lattice-based cryptosystems mentioned earlier is that they can build systems that securely and privately handle computation on encrypted data. The term homomorphic encryption may seem esoteric, but it just means encryption which you can compute on. Standard cryptosystems in use today don’t have this property: if you try to add together two ciphertexts (encrypted texts) encrypted using the Advanced Encryption Standard (AES), then the result will be gibberish. Homomorphic encryption differentiates itself by preserving the structure of the data. It encodes data in a mathematical object, and then encrypts it in a way that doesn’t affect the contained information.

HE applications

HE plays a role in a family of privacy-preserving computation techniques (PPCT) that address and eliminate the classic compromise of sharing data while retaining privacy. HE expands the role of encryption by extending its scope from “data at rest” and “data in transit” to “data in use” (data being processed, viewed, updated). HE can better enable enterprises to leverage the services of third-party providers (typically but not restricted to cloud) by reducing or (in some cases) eliminating privacy concerns. HE provides the ability to compute on data while the data is encrypted. This has enabled industry and government to provide capabilities for outsourced computation securely.

Fully homomorphic encryption has numerous applications. For example, it enables private queries to a search engine – the user submits an encrypted query, and the search engine computes a succinct encrypted answer without ever looking at the query in the clear. It also enables searching on encrypted data – a user stores encrypted files on a remote file server and can later have the server retrieve only files that (when decrypted) satisfy some Boolean constraint, even though the server cannot decrypt the files on its own.

Categories of HE technologies

HE is a cryptographic method that enables third parties to process encrypted data and return an encrypted result to the data owner, while providing no knowledge about the data or the results. HE enables algorithm providers to protect proprietary algorithms and data owners to keep data private Partially homomorphic encryption (PHE) allows only one operation on the encrypted data (i.e. either addition or multiplication but not both). Introduced in 1978, RSA was one of the earliest PHE schemes.

Fully homomorphic encryption allows an unlimited number of both addition and multiplication operations. Among the spectrum of HE technologies, FHE has the greatest potential industry impact. However, practical implementations have eluded technologists for decades. In practice today, fully homomorphic encryption is not fast enough for most business implementations. Partially homomorphic encryption is the most practical implementation, and fully homomorphic encryption is suitable for specific use cases.

FHE (Fully Homomorphic Encryption), SHE and PHE

FHE allows you to do an unbounded number of operations. SHE (Somewhat Homomorphic Encryption) is more general than PHE in the sense that it supports homomorphic operations with additions and multiplications. PHE (Partially Homomorphic Encryption) schemes are in general more efficient than SHE and FHE, mainly because they are homomorphic w.r.t to only one type of operation: addition or multiplication. SHE and PHE are not suitable for data sharing scenarios.

SHE scheme is also a PHE. This implies that PHE’s are at least as efficient as SHE’s. (Source: Market Intellica)

HE Performance

While massive improvements have been made in recent years, general Fully HE-based (FHE) processing remains 1,000 to 1,000,000 times slower than equivalent plaintext operations. One example (using 128-bit security) with the NTRU public-key based lattice encryption reported 55 000 operations per second compared to 8 000 for RSA and 4 000 for ECC.

Examples comparing file encryption and decryption of a 50KB file the RSA algorithm and the old homomorphic El-Gamal asymmetric key encryption algorithm and Paillier asymmetric algorithm reported the following process time for decrypting a 123KB file was on RSA (60 seconds), ElGamal (10 seconds) and Paillier (150 seconds). Source: Research Gate, Department of Software Engineering, University of Engineering & Technology, Taxila, Pakistan:

Examples of performance of operations per send on short data (20+ bytes) encryption and multiplication with ASE, RSA, and homomorphic algorithms (NTRU and Gentry):

HE Security

The security of the most practical homomorphic encryption schemes is based on the Ring-Learning With Errors (RLWE) problem, which is a hard mathematical problem related to high-dimensional lattices. The RLWE problem is closely related to famous hard lattice problems which are currently considered to be secure against quantum computers. Similarly, RLWE and subsequently most homomorphic encryption schemes are secure against quantum computers. Making them in fact more secure than factorization and discrete logarithm-based systems such as RSA and many forms of elliptic curve cryptography.
The post-quantum cryptography standardization project organized by NIST had several submissions based on hard lattice problems like what modern homomorphic encryption uses. The NIST selected 26 algorithms to advance to the second round for more analysis. This report describes the evaluation and selection process, based on public feedback and internal review, of the second-round candidates. The report summarizes the 26 second-round candidate algorithms and identifies those selected to move forward to the third round of the competition. The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER.

Lattice-based cryptography is based on cryptographic systems such as learning with errors. Lattice-based cryptography has been published and analyzed increasingly during 2011 to 2020 in more than 180 papers (Source: Cloud Security Alliance).

Factors that may inhibit HE adoption in the short term

While massive improvements have been made in recent years, general FHE-based processing remains several thousand times slower than equivalent plaintext efforts. Consequently, the computational overhead remains too heavy for FHE in most general computing scenarios. Like any early technology, HE efforts remain diverse and fragmented. A lack of standardization inhibits consistency wherein TSP and potential customers can rally around to create an economy of scope and scale. For example, the HE community must continue to work to simplify and standardize APIs and SDKs.

Bibliography
1. C. Gentry. “A Fully Homomorphic Encryption Scheme.” Stanford University. September 2009, https://crypto.stanford.edu/craig/craig-thesis.pdf
2. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, https://csrc.nist.gov/publications/detail/nistir/8309/final
3. ISO/IEC 29101:2013 (Information technology – Security techniques – Privacy architecture framework)
4. ISO/IEC 19592-1:2016 (Information technology – Security techniques – Secret sharing – Part 1: General)
5. Homomorphic Encryption Standardization, Academic Consortium to Advance Secure Computation, https://homomorphicencryption.org/standards-meetings/
6. Homomorphic Encryption Standardization, https://homomorphicencryption.org/
7. NIST Post-Quantum Cryptography PQC, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
8. http://publications.officialstatistics.org/handbooks/privacy-preserving-techniques-handbook/UN%20Handbook%20for%20Privacy-Preserving%20Techniques.pdf