Holy Grail of Cryptography - Homomorphic Encryption


What if it is possible to analyze or manipulate encrypted data without revealing the data to anyone? Make an encrypted search query to a search engine and the results come back in an encrypted form, payment data never decrypted, and still, transactions take place, & your PII even though processed by a third party but in an encrypted form, never to be seen by anyone but you!!


I know you are intrigued and I have caught your attention. So let's explore this in detail.


Before we delve into this exciting space, we must brush up on our basics (not everyone is as smart as you!). Encryption is a process where you convert plain text (readable) into a garbled language (unreadable) to ensure confidentiality. If a person wants to read it, he has to know the magic key ( Symmetric-key / Public-private Key). The idea here is that you ensure that the data is secured when sent across or when stored at rest. All sounds hunky-dory, right? While modern encryption algorithms are virtually unbreakable (because they require so much processing power that it makes the process of breaking it too costly and time-consuming to be feasible), they also make it impossible to process the data without first decrypting it — and decrypting your data becomes the weakest link. 


As such, regardless of whether you’re working with data at rest or data in transit, traditional public-key encryption requires that data must be decrypted before it can be analyzed or manipulated. But what if we told you that there is a type of encryption that completely side-steps the need for decrypting the data before you use it — meaning that data integrity and privacy are protected while you process data in use?


Just like Iron Man, it is Homomorphic Encryption that will save us all from Thanos ( read hackers if you are not an Avengers fan). 


What is HE (Homomorphic Encryption)?


Simply put, HE is a method of encryption that allows any data to remain encrypted while it’s being processed and manipulated. So when a hospital chain wants a third-party processor to work on the HIPAA-regulated data, it can easily share this via using HE without the risk of it being readable to the third party. If we go back to the basics, what HE is doing is that it uses an encryption algorithm to convert the plain text into garbled text, however, if someone wants to work on it, there is no need to provide him the key or decrypt the data, the third party can work on the garbled data itself. Sounds cool, right? 


If you are scratching your head as to how will it be done, don’t worry, you are not alone. It uses an algebraic system to allow you or others to perform a variety of computations (or operations) on the encrypted data. In practice, most homomorphic encryption schemes work best with data represented as integers and while using addition and multiplication as the operational functions. [ The complex mathematics is beyond my understanding, so how should I explain?]


Who is the HE-Man?


The origins of homomorphic encryption date back to 1978 — shortly after Rivest, Shamir and Adleman presented RSA encryption. However, Gentry, a graduate student at Stanford University, created an algebraically homomorphic encryption system as his graduate thesis in 2009. 


Gentry, who is an esteemed MacArthur Foundation fellow and worked as a Research scientist in the Cryptography Research Group at the IBM Thomas J. Watson Research Center, established the first fully homomorphic encryption scheme in 2009. 


There z always many types


There are three main types of homomorphic encryption. The primary difference between them boils down to the types and frequency of mathematical operations that can be performed on their ciphertext. The three types of homomorphic encryption include:

  • Partially Homomorphic Encryption (PHE)
  • Somewhat Homomorphic Encryption (SHE)
  • Fully Homomorphic Encryption (FHE)

PHE as the name suggests is quite partial in nature. It keeps sensitive data secure by only allowing select mathematical functions to be performed on encrypted data. Basically, it allows only one mathematical function ( like addition) to be performed on the data unlimited times. Hence the use cases are quite limited. Partially homomorphic encryption (with regard to multiplicative operations) is the foundation for RSA encryption, which is commonly used in establishing secure connections through SSL/TLS. Some examples of PHE include ElGamal encryption (a multiplication scheme) and Paillier encryption (an addition scheme).


Somewhat Homomorphic Encryption - Where there is a HE, there will always be a SHE ( bad joke, I know!). This supports limited operations that can be performed only a set number of times. So you can perform addition and multiplication, but only a limited number of times. 


Fully Homomorphic Encryption (FHE) 


This is the Holy Grail of cryptography. It allows all mathematical operations to be performed on the encrypted data an unlimited number of times and that’s what makes it the gold standard. Unlike other forms of homomorphic encryption, it can handle arbitrary computations on your ciphertexts.


The goal behind fully homomorphic encryption is to allow anyone to use encrypted data to perform useful operations without access to the encryption key. In particular, this concept has applications for improving cloud computing security. Cheap cloud computing and cloud storage have fundamentally changed how businesses and individuals use and manage their data. Traditional encryption methods, such as AES, are extremely fast, and allow data to be stored conveniently in encrypted form. However, to perform even simple analytics on the encrypted data, either the cloud server needs access to the secret key, which leads to security concerns, or the owner of the data needs to download, decrypt, and operate on the data locally, which can be costly and create a logistic challenge. Homomorphic encryption can be used to simplify this scenario considerably, as the cloud can directly operate on the encrypted data, and return only the encrypted result to the owner of the data. More complex application scenarios can involve multiple parties with private data that a third party can operate on, and return the result to one or more of the participants to be decrypted.


Craig Gentry, an American computer scientist and Research Fellow at Algorand Foundation, describes his version of homomorphic encryption — fully homomorphic encryption — in terms of a glovebox analogy:


“So, basically, anybody can come and they can stick their hands inside the gloves and manipulate what’s inside the locked box. They can’t pull it out, but they can manipulate it; they can process it. They can take raw materials and produce a necklace or something inside the box. And, you know, they finish and [the person with the private key] has to come with the secret key and open it up, and only they can extract the finished product out of there.”


Why not bring it on?


Because it’s super slow. Computation at the expense of speed. Unfortunately, in its current state, homomorphic encryption is impractically slow. In the encryption race, it’s running in the last place. This is, in part, because homomorphic encryption has larger computational overhead than plaintext operations.  However, use cases that are not computationally intensive —like prediction using a pre-trained model— are feasible with fully homomorphic encryption in its current state.


Several open-source implementations of homomorphic encryption schemes exist today. Below is an incomplete list.

  • Microsoft SEAL: A widely used open-source library from Microsoft that supports the BFV and the CKKS schemes.
  • PALISADE: A widely-used open-source library from a consortium of DARPA-funded defense contractors that supports multiple homomorphic encryption schemes such as BGV, BFV, CKKS, TFHE, and FHEW, among others, with multiparty support.
  • HELib: An early and widely used library from IBM that supports the CKKS and BGV scheme and bootstrapping.
  • FHEW / TFHE: Supports the TFHE scheme.  (Please note that the FHEW and TFHE libraries are distinct from the FHEW and TFHE schemes which are also supported by other libraries listed on this page.)
  • HeaAn: This library implements the CKKS scheme with native support for fixed-point approximate arithmetic.
  • Λ ○ λ (pronounced “L O L”): This is a Haskell library for ring-based lattice cryptography that supports FHE.
  • NFLlib: This library is an outgrowth of the European HEAT project to explore high-performance homomorphic encryption using low-level processor primitives.
  • HEAT: This library focuses on an API that bridges FV-NFLib and HeLIB.
  • HEAT: A HW accelerator implementation for FV-NFLlib.
  • cuHE: This library explores the use of GPGPUs to accelerate homomorphic encryption.
  • Lattigo: This is a lattice-based cryptographic library written in Go.
  • Concrete: This library supports a custom variant of the TFHE scheme.
  • EVA: A compiler and optimizer for the CKKS scheme (targeting Microsoft SEAL).

Ongoing research and advances in Quantum computing will make HE a reality very soon. Till that point in time, it is imperatives that the organizations use the best encryption standards out there and implement a defense in depth strategy to ensure that if one of the defenses is broken, the other comes to the rescue.

Comments

You may also like to read...

Access Control Models - DAC, MAC, RBAC , Rule Based & ABAC

Understanding Security Modes - Dedicated , System high, Compartmented , Multilevel

Identification, Authentication, Authorization, and Accountability

How to Pass SSCP Exam in the First Attempt

The Endorsement Process - CISSP, SSCP & other (ISC)2 certifications