An Overview of Type Theory

An Optimization for RWLE-based FHE

6 minute read

Published: June 26, 2024

For my first foray into the world of academic research, I decided to delve into the topic of cryptography, and in particular homomorphic encryption. I worked with Professor Dongfang Zhao of the HPDIC Lab at the University of Washington, studying optimizations (both at the system level and abstract level) for homomorphic encryption schemes. At the end of it all, I managed to ideate and implement a very simple optimization for a certain family of homomorphic encryption schemes that reduces encryption time by half, and could be even more depending on future work! While not published, the paper is available here for those interested.

To give a very short overview of what homomorphic encryption is, it’s a good idea to understand the motivation behind it first. There are plenty of places online that we store information today. Cloud services range from storing financial or health data to training machine learning models. These are all sensitive, relating to privacy laws and simple human decency, but how can you trust the cloud services if you are not the administrator of the system from start to finish? Simple answer is, you can’t really, and eventually you’ll have to rely on some level of faith that there are no malicious actors on the other end of your data (related: Reflections on Trusting Trust).

So, one solution could be to introduce a layer of encryption before sending off that data. Now you have a second problem: what if I want to compute something on that data? For example, taking an average of the salaries that are at my company. Your average cryptographic scheme doesn’t permit these sort of arithmetic operations. Classically, a public-key scheme consists of a tuple of algorithms \((\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) with the restriction that for any pair \(pk, sk\) produced by \(\mathsf{Gen}\), we have \(\mathsf{Dec}(sk, \mathsf{Enc}(pk, m)) = m\).

This is where homomorphic encryption (HE) takes center stage. An HE scheme will tack on an extra algorithm(s) that allow you to perform certain functions given ciphertexts as input. To keep it simple, I’ll imagine that homomorphic addition is specified by \(\oplus\), with the condition that

\[ \mathsf{Dec}(sk, \mathsf{Enc}(pk, m_1) \oplus \mathsf{Enc}(pk, m_2)) = m_1 + m_2 \]

You can imagine how this might look for other operations as well. The mathematics of this is based in group theory, but won’t be necessary for this exposition.

CKKS and the Optimization

At the cutting-edge of homomorphic encryption schemes in CKKS. There are a handful of schemes that are in the same family as it, but the important part is that CKKS supports both homomorphic addition and multiplication over real numbers with some error due to the nature of HE schemes. At its core, a ciphertext in CKKS is a pair of polynomials \( c = (c_1, c_2) \), \(sk\) is a special polynomial, and \(pk = (pk_1, pk_2)\) is also a pair of polynomials. The ciphertext is structured like so: \[ \begin{cases} c_1 = [pk_1 \cdot u + e_1 + m] \cr c_2 = [pk_2 \cdot u + e_2] \end{cases} \] for a message \(m\). Here, \(e_1\) and \(e_2\) are special “error” polynomials and are sampled randomly for every encryption. Crucially, notice that the polynomial multiplication is by far the most expensive operation being done, but does not carry any part of the message itself. As an quick experiment, look at what happens when we encrypt a ciphertext of the message \(m = 0\): \[ \mathsf{Enc}(pk, 0)= \begin{cases} c^{(0)}_1 = [pk_1 \cdot u + e_1] \cr c^{(0)}_2 = [pk_2 \cdot u + e_2] \end{cases} \] Now if we add any message \(m\) to the first polynomial in encryption of 0, we would be able to produce a ciphertext that encrypts 0. Then we could simply store a single encryption of 0, and any time we want a new ciphertext, we simply add \(m\) to the first polynomial. I’ll write this new encryption method as \(\mathsf{Enc}_z\). Mathematically, this is expressed: \[ \mathsf{Enc}_z(pk, m) = (c^{(0)}_1 + m, c^{(0)}_2) \] But of course, there is still one last issue. If we encrypt the same value twice, they will look exactly the same since all of the randomized parts of \(c^{(0)}_1\) and \(c^{(0)}_2\) were only done once at the time of caching. This is obviously not secure, so one final modification is required: \[ \mathsf{Enc}_z(pk, m) = (c^{(0)}_1 + e_1’ + m, c^{(0)}_2 + e_2’) \] Once again reintroducing the randomness without the need for any polynomial multiplication. The proof of correctness and security is given in the paper, and an implementation in C++ can be found here.

Empirical Results

This scheme (called “Zinc” in the paper) was tested against a previously described optimization called Rache as well as vanilla CKKS. Basic results are described in the table below:

At much smaller number of pivots, Rache does win out, but the range of values encryptable becomes prohibitively small. As we can see, on each of these datasets Zinc outperforms by at least a factor-of-two. To put that into perspective, saving 12 hours on what would otherwise be a 24 hour job is a big deal!

Future Directions

If possible, I would like to extend this optimization to multi-party versions of CKKS and other RWLE-family schemes. Additionally, I can see at least one more optimization that can be applied to the generation of the ciphertext. In the Microsoft SEAL library (and many popular implementations of CKKS), each of the polynomials that are generated are transformed by a variant of the discrete Fourier transform (DFT). This costs \(O(n \log n)\) time, but allows polynomial multiplication can be done in \(O(n \log n)\) time as well, which is a great improvement over the usual \(O(n^2)\) polynomial multiplication. Unfortunately, this does mean that in our modified scheme, the error polynomials \(e_1’\) and \(e_2’\) also need to be transformed. If we can instead generate the polynomial directly in the Fourier space instead of the original space, this would reduce the need to perform the DFT, saving us a little bit more time.

Complexity Analysis and a Lesson in Hidden Assumptions

6 minute read

Published: January 12, 2024

I’ve recently begun taking a course in complexity theory. Even though I’ve studied the topic a little bit in the past, sitting through a formal treatment of the subject has already given me a lot of clarity on little informal notions I had before, such as the general model of Turing machines, and the idea of a universal interpreter. This article intends to recount one of the experiences I had with an exercise from a book, which was slightly modified by my professor and assigned as homework.

The Deduction Theorem

13 minute read

Published: March 27, 2023

Or, an introduction to metalogic. Note: this article is aimed at those who already have some exposure to logic and mathematics, as it explores ideas that require some prior knowledge of proof systems and proofs.