Where Do I Start?

I first learned about Homomorphic Encryption (HE) about 5 years ago. Since then, I have hell-bent on learning how to leverage it within my applications. Most of the libraries I found use many different flavors, or “scheme types”, and are written in low-level languages such as C++. This is mainly because of performance, but has the side-effect of being very hard to adopt.

So how do we use a C++ library in a web app? Spoiler — WebAssembly.

Hopefully by the end of this article, you will have a better understanding of how to use HE in Web Applications. I will briefly go over the some of the technical jargon and illustrate the pain points behind using HE followed by some alternatives.

A Brief Background

HE is a game changer for privacy. It allows for data to be manipulated without decrypting it. The concept dates back to RSA encryption — yes, even RSA has the capability of limited HE functionality. However, it took quite some time before the industry saw a change.

In 2009, Craig Gentry’s dissertation was published and sparked the proliferation of libraries with different capabilities and varying performance. The rest is history.

Looking for Libraries

Today, many libraries can be found floating in the wild. I’ve listed a few prevalent ones and their respective supported scheme types, but there are notable others.

• Microsoft SEAL: BFV, CKKS (C++)
• HElib: BGV (with GHS), CKKS (C++)
• PALISADE: BFV, BGV, CKKS, FHEW (C++)
• TFHE: Ring-variant of GSW (C++)
• HEAAN: CKKS (with bootstrapping) (C++)

Finding the right library and scheme type for your application involves a fair amount of research. What differences do these implementations have? What dependencies do they require — how can I use this in my app? How does a scheme type affect performance — or even more confusing, what limitations does a scheme impose on encrypted data? What the heck is bootstrapping and do I need it?

Some of these questions need answers before you even start designing a privacy-preserving application.

To get started I will talk about Microsoft SEAL as it provided the best documentation when I was learning and is what I’m most familiar with. Full disclosure - I'm not sponsored nor affiliated with Microsoft. I will simplify and make very generalized assumptions so we can get on with it and not dwell on the details.

Working with Microsoft SEAL 😎

Let’s briefly cover how to encrypt data. First, you take an array (or a vector in C++), encode it to a special format to a plaintext, and then encrypt the plaintext to a ciphertext. Homomorphic evaluations occur on ciphertexts. To get a value back, you need to decrypt and decode.

Pseudo code

const arr = [1,2,3...]
const plain = encode(arr)
const cipher = encrypt(plain)
// Add the cipher to itself - element wise
evaluate.add(cipher, cipher)
const decrypted = decrypt(cipher)
const decoded = decode(decrypted)
// `decoded` contains [2,4,6, ...]

Whoa! Hold your horses — I skipped ahead and made this look easy. There are a few steps before you can even get to this point. Here’s an overview of the library:

Dependencies

• None! Optional dependences are zlib for compression and Microsoft GSL

Available schemes

• BFV — Allows you to operate on signed and unsigned integers
• CKKS — Allows you to operate on floating point numbers

Basic differences and limitations

• BFV — The amount of data (array length) a cipher can hold is defined by the encryption parameters. Each element in the array has upper and lower bound set forth by the parameters as well.
• CKKS — Allows for larger bounds on each element in the array, but has half of the capacity (half the array size) to an equivalent cipher encrypted using the BFV scheme. It also only computes approximate values.

Don’t worry if this is all foreign to you…bear with me…

*Note on bootstrapping

Bootstrapping allows for infinite homomorphic evaluations on encrypted data. Without it, there is a limit on how many evaluations (multiplications, etc.) you may perform on a cipher before it becomes impossible to decrypt correctly due to a noise factor.

For now, it is hasn’t been implemented in SEAL; however it’s on their roadmap for CKKS. That being said, implementing bootstrapping can cause a significant penalty to performance, often an order of magnitude. In many cases, homomorphic algorithms for a given application don’t even need bootstrapping.

A homomorphic algorithm without bootstrapping is called a leveled algorithm. The number of levels of the algorithm (aka how many evaluations) is strictly defined by the encryption parameters you choose.

Choosing a scheme type

The first step is to choose a scheme that is appropriate to your application. Do you require integers or can it afford a margin of error? BFV should be used when you absolutely need accuracy. CKKS has its own advantages, but introduces a bit of error in the decryption. With sufficient parameters the error can be reduced to well within acceptable limits — it’s just harder to learn at first.

How do I chose appropriate parameters?

Once you’ve decided on a scheme, now it’s time to define the parameters. This question is perhaps the most difficult to answer because it depends on many factors. Then there are more questions: how do we test which ones work? Is there room for optimization? Do I have to build a new test application each time?

Yes, you might, but let’s go over a methodology. For now, ignore what these definitions mean.

1. Choose a SchemeType — In my opinion,BFV is easier to learn overCKKS. At least, it is easier to see when your decryption comes out completely wrong.
2. Start with a 128-bit SecurityLevel — Higher options are available, but come at the cost of reduced homomorphic operations.
3. Just get it working — Start with a mid-level PolyModulusDegree (4096) and increase when you cannot successfully decrypt. Inversely, decrease it until you cannot successfully decrypt to optimize.
4. Test upper and lower bounds — It’s upsetting when you’ve optimized for performance only to find out your decryption fails on certain values of your application.
5. Fine tuning — Modify the bit-sizes for the CoeffModulus. Also use modulus switching (and/or rescaling for CKKS).
6. (BFV only): Set the PlainModulus to a reasonable value of 20 and tweak when you encounter correct decryption up until a ceiling (or floor). This represents the upper and lower bound of each element in the array, but again this is affected by homomorphic evaluations.

Wow — that’s a lot of things! Whats more disheartening is that these are rather terrible generalizations. There’s still a lot to learn about optimizing and we haven’t even started coding a simple example… 😑

Alternatives

This is the problem which plagued me for days on end. Rather than having an immediate discussion on how to pick parameters, I will tell you a way where you can rapidly experiment on your own.

I built an open-source library, node-seal, in JavaScript leveraging Microsoft SEAL. I figured it would be quicker to write a test suite in JavaScript instead of C++.

It uses WebAssembly at its core with light bindings to work in Node.js or modern browsers 😎. The npm package already has zlib and intrinsics baked-in to make the performance close to the native library. Installing is as simple as npm install node-seal or yarn add node-seal— no need to compile anything and no dependencies.

This is a great first step building web applications leveraging HE, but it still doesn’t solve the problem of quickly iterating on parameters to find what works and what doesn’t.

Using HE in web applications

With no solution, I did what any other developer would do — I built an app for that 🎉

I built Morfix.io to quickly test encryption parameters to see how they influence algorithm design and the decrypted results. Each step of the way is executed the same way as the native C++ library, this means most of the exceptions you will see reflect the run-time exceptions of the native library. You can create keys, variables, and even functions. When you’ve laid out an algorithm, simply execute them and watch the computations percolate down the page — all in real-time 🙂. I’ve included a simple code-generator as well to help get started in JavaScript.

I’ve established HE is possible in client-side applications, but the next step is to process encrypted data.

Now I have to build the server-side logic, right?

Yes, you could — but you don’t have to. By becoming a beta user on my platform, you can create an API which operates under a set of parameters and public keys. No secret keys are needed unless you want to simulate decryption.

How to start

• 👉🏻 Select encryption parameters
• ⬆️ Upload and assign public keys
• ➕ Create variables in the form of PlainTexts and CipherTexts
• ➕ Create a sequence of functions and assign variables accordingly
• 🚀 Execute and decrypt (with a non-persistent SecretKey)

A helpful test bench simulates sending and receiving an encrypted request from the browser so you can focus more on building content rather than debugging. Oh and there’s also another basic code generator for Node.js so you can sending requests from your machine to the cloud and back 💪🏻.

Conclusion

Ultimately, learning HE is tough — there’s really no easy way around it. I’ve built a few tools to help you get started with with either client or server-side applications.

~All without ever decrypting your data~

A big shout out to the 🧠s at Microsoft SEAL!!!

Stay tuned for Part 2 where I build a simple application leveraging homomorphic APIs with JavaScript.

Thanks for reading!

Previously published at https://medium.com/@s0l0ist/homomorphic-encryption-for-web-apps-a3fa52e9f03d