On Homomorphic Encryptions and the RLWE problem : Part 1

Published in

metrics-and-matroids

8 min readJul 4, 2021

As more and more companies shift to the cloud, and are forced to work remotely on potentially unsafe networks because of COVID-19, how do we guarantee the security of stakeholders while still providing them with cutting-edge AI software applications? Homomorphic encryptions are the ‘key’ (sorry for that lame pun :P).

On a more serious note, let’s first set a bit of context. Let’s understand why we need homomorphic encryption schemes, and why we need even greater security than what is guaranteed by traditional cryptographic algorithms such as RSA.

Quantum computing

“Quantum computing is the exploitation of collective properties of quantum states, such as superposition and entanglement, to perform computation.” The devices which perform quantum computation are called quantum computers. Algorithms designed for quantum computers have much lower time-complexities than their classical counterparts.

(Superposition dictates that quantum states can be added together to create another valid quantum state. Conversely, any quantum state can be represented as the sum of two or more distinct quantum states.)

Quantum computers are based on the concept of qubits as opposed to regular bits. Qubits can take a spectrum of values between 0 and 1, whereas regular bits are either 0 or 1.

In a classical computer, 2 bits correspond to 4 possible configuration — 00, 01, 10, 11

To determine which one of the 4 configurations we actually have, we need 2 values (value of first bit and value of second bit).
In Quantum computing, we can represent a quantum mechanical state by using a linear combination of the 4 configurations.

We have 4 coefficients for this superposition. So we need 4 values. Hence 2 qubits contain 4 bits of information.

If we keep scaling this up, we arrive at the conclusion that n qubits corresponding to 2^n classical bits. Just scaling up to 300 qubits will need the equivalent of ²³⁰⁰ classical bits (which is approximately the number of particles in the universe!).

This is the basis of the exponential speedup guaranteed by quantum computers in solving certain problems.

The number of operations required to arrive at the result is exponentially small. Improvement is in the total number of operations.

Shor’s Algorithm

It is a quantum algorithm for factoring exponentially faster than the best currently-known algorithms running on a classical computer. It is the crucial element in the process for cracking trapdoor-based codes (such as RSA). “If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor’s algorithm could be used to break public-key cryptography schemes, such as the widely used RSA scheme.”

It is easy to imagine that at this rate of progress, quantum computers should be able to outperform the best classical ones pretty soon.

However, the reality is not that simple. It turns out that quantum factoring is much harder in practice than expected. The reason is that noise becomes a significant problem for large quantum computers. Currently, the best way to tackle this noise is by using certain error-correcting codes, which themselves require significant number of extra qubits.

“Taking this into account dramatically increases the resources required to factor 2048-bit numbers. In 2015, researchers estimated that a quantum computer would need a billion qubits to do the job reliably. That’s significantly more than the 70 qubits in today’s state-of-the-art quantum computers.”

Craig Gidney at Google in Santa Barbara and Martin Ekerå at the KTH Royal Institute of Technology in Stockholm, Sweden have recently published some groundbreaking research where they have significantly optimised Shor’s algorithm and have shown how 2048 bit RSA Integers could be factored in just 8 hours using 20 million qubits. Getting to 1 billion qubits might take some time, however the question we should be asking is if we can get to 20 million qubits in 25 years.

From the above facts, pretty obvious to conclude that quantum computing can give cryptographic systems a run for their money, since the basis of public and private key cryptography is the hardness of factoring large numbers into primes. This pretty much makes it clear that we will need encryption schemes which are hard to crack even on quantum computers in the near future.

One such algorithm is the RLWE problem, which we will go over in detail in Part 2 of this blog post series. For now, let’s focus on the first term in the title, the idea of homomorphic encryption.

Security guarantees of RSA encryption

RSA encryption algorithm is based on the hardness of factoring the product of two large prime numbers. “It is much easier to multiply primes together than to factor them back out. With big enough primes (say, a thousand digits) the multiplication can be done in a fraction of a second while the factoring could take millions of years.” These kinds of algorithms are called ‘trapdoor’ functions. Miller-Rabin test is used to find these huge primes upto extremely high degrees of certainty.

RSA encryption schemes with large key sizes (2048 bits) are considered safe, for now. However, this sense of false security can be dangerous and misleading.

“Symmetric algorithms used for encryption, like AES, are still thought to be safe (with sufficient key length — e.g. AES-256 or larger); however, current asymmetric algorithms like RSA and ECDSA will be rendered essentially useless once quantum computers reach a certain scale.”

Homomorphic Encryption

With the latest advances in AI and ML, and the vast amounts of data required to train these models, customer and stakeholder data security is an absolute necessity. Common sense dictates that to build any ML model to do any task, the model needs to be exposed to the raw data. However, this can lead to security vulnerabilities. Software supply chain attacks are an excellent example for this. How do we protect against such attacks? Is there any way we ensure that we can build models without actually seeing the data?
The answer is yes! This is where homomorphic encryptions (H.E) come in.

H.E allows us to perform computations on encrypted data without first decrypting it. This enables the data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted. The encryption and decryption functions can be thought of as homomorphisms between plaintext and ciphertext spaces. A homomorphism is a structure-preserving map/function between two algebraic structures of the same type.

Data owners can encrypt their data with the public key, send it to a data processor that has no access to the secret key, and receive the answer to their query in encrypted form, which only the data owner can unlock with the secret key.

Let us get into a bit of math, and understand what exactly is a homomorphism more concretely.

What is a homomorphism?

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two rings {foreshadowing..} or two vector spaces).

By preservation of structures, we mean that homomorphisms preserve the operations on these structures.

A map f : A -> B between two sets A and B equipped with the same structure, such that if ‘.’ is an operation of the structure, then

f( x . y ) = f(x) . f(y), for every pair of elements x and y in A.

Homomorphic cryptosystems

“An encryption function E and its decryption function D are homomorphic with respect to a class of functions ℱ if for any function f ∈ ℱ, we can construct a function g such that f(x) = D(g(E(x))) for some set of x that we’re interested in.”

In simpler terms, for a specific subset of cryptosystems and target functions, it is possible to map a desired computation (the function f) on plaintext to a specific computation on the ciphertext (the function g) whose result, when decrypted, matches the desired plaintext result.

The illustration above demonstrates how we can use this property to run inference on private data using a remote untrusted computer. The remote machine receives a ciphertext (encryption of her data) from the user (with no decryption key), executes a function g (this can be her model, which she wants to train or run inference on) on the ciphertext, then returns the result to her. She then decrypts the result to reveal the plaintext for f(x). This ensures that the remote computer does not gain access to her unencrypted data.

One important property of RLWE-based HE schemes is semantic security, which is the inability of a computationally limited attacker to distinguish between the ciphertexts of known plaintexts. That is, E(x) != E(y), even when x = y. This is due to random noise which is introduced during the encryption process.

Partial and Fully Homomorphic Encryption

We have different types of HE schemes, some support a single algebraic operation (such as addition or multiplication) and some can support two (both addition and multiplication). The former class of HE schemes are called “partially homomorphic” (PHE) and latter are called “fully homomorphic” (FHE).

There’s an interesting observation to be made here. Composing addition and multiplication suffices to construct polynomial functions, and hence polynomial approximations to non-polynomial functions such as sigmoid or ReLU.

Another class of HE schemes, “Levelled homomorphic” schemes support addition and multiplication, but up to a fixed computational depth.

FHE allows us to do arbitrary computation. Bit addition and bit multiplication takes care of that. In general, we would not want crypto-systems to have these homomorphic properties. It adds structure, and structure is dangerous. Structure exposes vulnerabilities which can be exploited. However, it can be extremely useful too, if coupled with a very robust and hard encryption algorithm.

The quest for a ‘harder’ problem

We’ve already discussed that the RSA problem (and others) might not be ‘hard’ enough in a few years from now. However, we still have a few years, right? And for ordinary people like you and me, the risk is much less. Transaction details of today won’t create much of an issue if broken in 25 years.

The problem is not as trivial for governments, military and security organisations, banks and anyone who needs to store data for 25 years (now even less) or longer.

Retrospective decryption of data from the past is one thing these organisations should be worried about — especially if the employed key lengths used at the time were sufficiently short.

This brings us to the RLWE problem, which is presumed to be difficult even for a quantum computer. And this problem can be used to create fully homomorphic encryption schemes.