Homomorphic Encryption — for Web Apps 🧐 (Part 2) by@s0l0ist

April 11th 2020 739 reads

Startup Advisor, Entrepreneur, Full-Stack Developer, Cybersecurity Professional, Privacy Advocate

In case you missed the previous article (Part 1), I gave a very brief introduction on Homomorphic Encryption (HE), talked about Microsoft SEAL’s library, and outlined some of the pain points of learning to use it.

**tl;dr **— you really have to spend a lot of time understanding the inner-workings of the library so I built morfix.io to help you rapidly experiment with Microsoft SEAL using node-seal, the JavaScript package I wrote.

It turns out you can use this library to build your own privacy-preserving applications, but there are alternatives available. This time around, I’ll compare my implementation to see how SEAL stacks up against another famous cryptosystem to give you some insight.

Spoiler: Paillier for simple applications, SEAL for complex applications

It is important to know node-seal is not the only HE library — especially in the JavaScript world. Unfortunately, it happens to be the only *fully* homomorphic library available among a sea of *partially* homomorphic libraries in the JavaScript domain.

Many of these alternatives leverage the Paillier cryptosystem. Therefore, I’ll make a brief comparison of Paillier vs SEAL even though it is not a truly fair comparison (PHE vs FHE). I’ll briefly go over the capabilities of each, abbreviating a plaintext as

`plain`

and a ciphertext as `cipher`

:Paillier

- Add

together`ciphers`

- Multiply a

by a`cipher`

`plain`

SEAL

- Negate a
`cipher`

- Add two

together`ciphers`

- Add a

to a`plain`

`cipher`

- Subtract two

together`ciphers`

- Subtract a

from a`plain`

`cipher`

- Multiply two

together`ciphers`

- Multiply a

by a`cipher`

`plain`

- Square a
`cipher`

- …

We can easily see that SEAL is the clear winner in terms of features and I haven’t even listed all the different evaluation methods it supports. An important distinction is that while SEAL can homomorphically multiply two

`ciphers`

Paillier can only multiply a `cipher`

by a `plain`

— but this is still very useful. For very simple applications Paillier maybe a better choice.So far, we are talking about homomorphic evaluations on **single values** — this is where Paillier shines in terms of both algorithmic and spatial complexity.

You simply encrypt a value and receive a

`cipher`

:```
// Pseudocode
const cipher = encrypt(5)
typeof cipher // 'bigint'
```

Homomorphic operations are rather fast on single values and each Paillier

`cipher`

is just another How you would encrypt a value and receive a

`cipher`

using SEAL:```
// Pseudocode
const plain = encode(5)
typeof plain // ?
const cipher = encrypt(plain)
typeof cipher // ?
```

In SEAL, there’s an extra abstraction — you need to perform an extra step of *encoding* your data** **before encryption. Needless to say, the underlying data is not a primitive type.

What if you had a few items to encrypt? For example, say you want to encrypt a set of 10 numbers in an array. Using Paillier, you would need to iterate in a loop and encrypt each item, send this over to a server which would perform a homomorphic add or multiply, and return the result.

No problem, Paillier computation is quick enough and the spatial requirements are still quite low. This works more or less efficiently. SEAL on the other hand actually works in almost the same way — at least when you’re using the

`IntegerEncoder`

.Now, let’s say you want to encrypt 1,000+ elements? We start to see Paillier break down in terms of performance. This is where SEAL shines in its amazing ability to **batch** all the numbers into a single

`plain`

using the `BatchEncoder`

. What this means is instead of iterating in a loop for **n** number of elements O(n) to encrypt or perform some HE operation you can do this in constant time O(1). SEAL can operate on all batched elements in parallel with no extra computational cost — also known as Single Instruction, Multiple Data (**SIMD**).

🦾

Note: In SEAL, the number of elements you are allowed to encode using theis defined by the encryption parameters used to set up the encryption context. In a typical context, you would have a power of 2 for the number of elements. Ex:

BatchEncoder4096elements.

The process is a bit different because where Paillier can directly encrypt numbers, SEAL requires us to first *encode* the data into a format it understands before you can encrypt it as mentioned above. It also takes a bit more understanding of how to set it up correctly. I’ll take one of the many Paillier implementations and show a full encrypt/decrypt example for both, skipping homomorphic evaluations.

```
// import paillier in node.js
const paillier = require('paillier-bigint.js')
// import paillier in native JS
import * as paillier from 'paillier-bigint'
(async () => {
// Create keys
const { publicKey, privateKey } = await paillier.generateRandomKeys(3072)
// Encrypt the plainText integer
const cipher = publicKey.encrypt(5n)
// Decrypt the cipherText
const decypted = privateKey.decrypt(cipher)
// decrypted === 5n
})()
```

Not bad! Now, let’s look at node-seal…

```
// Pick one for your environment
// npm install node-seal
// yarn add node-seal
//
// ES6 or CommonJS
// import { Seal } from 'node-seal'
const { Seal } = require('node-seal')
(async () => {
// Wait for the web assembly to fully initialize
const Morfix = await Seal()
////////////////////////
// Encryption Parameters
////////////////////////
// Create a new EncryptionParameters
const schemeType = Morfix.SchemeType.BFV
const polyModulusDegree = 4096
const bitSizes = [36,36,37]
const bitSize = 20
const encParms = Morfix.EncryptionParameters(schemeType)
// Assign Poly Modulus Degree
encParms.setPolyModulusDegree(polyModulusDegree)
// Create a suitable set of CoeffModulus primes
const coeffModulus = Morfix.CoeffModulus.Create(
polyModulusDegree,
Int32Array.from(bitSizes)
)
encParms.setCoeffModulus(coeffModulus)
// Assign a PlainModulus (only for BFV scheme type)
const plainModulus = Morfix.PlainModulus.Batching(polyModulusDegree, bitSize)
encParms.setPlainModulus(plainModulus)
////////////////////////
// Context
////////////////////////
// Create a new Context
const context = Morfix.Context(encParms, true)
// Helper to check if the Context was created successfully
if (!context.parametersSet) {
throw new Error('Could not set the parameters in the given context. Please try different encryption parameters.')
}
////////////////////////
// Keys
////////////////////////
const keyGenerator = Morfix.KeyGenerator(context)
const secretKey = keyGenerator.getSecretKey()
const publicKey = keyGenerator.getPublicKey()
////////////////////////
// Instances
////////////////////////
const evaluator = Morfix.Evaluator(context)
// Create a BatchEncoder (only BFV SchemeType)
const batchEncoder = Morfix.BatchEncoder(context)
const encryptor = Morfix.Encryptor(context, publicKey)
const decryptor = Morfix.Decryptor(context, secretKey)
////////////////////////
// Homomorphic Functions
////////////////////////
// Create an array of 4096 values
const array = Int32Array
.from({length: 4096})
.map((_, i) => i)
// Encode data to a PlainText
const plain = batchEncoder.encode(array)
// Encrypt a PlainText
const cipher = encryptor.encrypt(plain)
// Decrypt a CipherText
const decryptedPlainText = decryptor.decrypt(cipher)
// Decode data from a PlainText
const decodedPlainText = batchEncoder.decode(decryptedPlainText)
// decodedPlainText === array
})()
```

😧🔫

Okay wow — there’s **a lot** more you need to setup when using node-seal. Luckily for you, all your code can be generated using the **code generator** on morfix.io/sandbox and there’s also documentation located at docs.morfix.io. You can find a little more information on

`BFV`

vs `CKKS`

in Part 1.I’ve selected

`BFV`

because I want to just worry about integers and not floats. I’ve also selected to use the `batchEncoder`

to take advantage of `polyModulusDegree`

is set to `4096`

which provides me with a good initial setup that can use the library to its full extent. Any less and I won’t be able to use some of the more advanced functions. Choosing this number also means I can encode/encrypt up to 4096 elements.The

`coeffModulus`

is tricky to explain. You will need to select a few numbers, but their sum cannot exceed a certain maximum (depending on your other encryption parameters). There are lots of ways to configure these values, the best advice I can give is to experiment with the defaults first and worry about optimizing later. I’ve selected the default values provided by the library helper function and hardcoded them. You can see some other configurations in morfix.io/sandbox.The

`plainModulus`

is the gatekeeper of the upper and lower bounds of each value you encrypt. More precisely, the values are stored `plainModulus`

. Without diving into the technical details, start with a value of `20`

and worry about this value when you encounter decryptions that fail after a certain magnitude.Continuing on some of the tradeoffs for using SEAL over Paillier, there comes a time when you may want to save your application state including your encryption keys and

`ciphers`

to load at a later date. A simple serialize function can be made with Paillier by saving the key parameters and then re-creating the keys. Similarly, saving `ciphers`

is trivial since there are a few ways to serialize BigInts.I’m using synchronous

`fs`

operations for the sake of readability here…```
// Generate and save
const genKeyPair = async keySize => {
const keys = paillier.generateRandomKeys(keySize)
privateKey = keys.privateKey
publicKey = keys.publicKey
// BigInt's do not serialize natively.
// We're going to implement out own naïve serializer method
// which just saves to a string of numbers.
BigInt.prototype.toJSON = function () {
return `${this.toString()}`
}
fs.writeFileSync(
'paillier_private_key',
JSON.stringify(privateKey),
'utf8'
)
fs.writeFileSync(
'paillier_public_key',
JSON.stringify(publicKey),
'utf8'
)
}
// Load and instantiate
const loadKeys = async () => {
const rawPrivateKey = fs.readFileSync(
'paillier_private_key',
'utf8'
)
const rawPublicKey = fs.readFileSync(
'paillier_public_key',
'utf8'
)
const privateKeyObject = JSON.parse(rawPrivateKey)
const publicKeyObject = JSON.parse(rawPublicKey)
const publicKey = new paillier.PublicKey(
BigInt(publicKeyObject.n),
BigInt(publicKeyObject.g)
)
const privateKey = new paillier.PrivateKey(
BigInt(privateKeyObject.lambda),
BigInt(privateKeyObject.mu),
publicKey,
BigInt(privateKeyObject.p),
BigInt(privateKeyObject.q)
)
return { privateKey, publicKey }
}
```

The problem with this approach is that there’s no standard serialization methods for most Paillier implementations leaving you to create your own custom wrappers — although for this case it is certainly feasible.

Thankfully, SEAL includes serialization methods

`save`

and `load`

for ```
// Generate and save
const genKeyPair = async context => {
const keyGenerator = Morfix.keyGenerator(context)
const privateKey = keys.getSecretKey()
const publicKey = keys.getPublicKey()
fs.writeFileSync('seal_private_key', privateKey.save(), 'utf8')
fs.writeFileSync('seal_public_key', publicKey.save(), 'utf8')
}
// Load and instantiate
const loadKeys = async context => {
const sKey = Morfix.SecretKey()
const pKey = Morfix.PublicKey()
sKey.load(context, fs.readFileSync(secretKeyName, 'utf8'))
pKey.load(context, fs.readFileSync(publicKeyName, 'utf8'))
return { privateKey: sKey, publicKey: pKey }
}
```

The serialized output can be configured to be a base64 string or a binary Uint8Array. These methods are also available on

`plains`

and `ciphers`

. Deserializing automatically ensures the object is valid, making it But there’s one drawback — the size…

```
const saved = encrypted.save()
console.log(Buffer.byteLength(saved, 'base64'))
// 91213 bytes
```

~**89Kb **Yikes! That’s *a lot* more than the size of a decently large BigInt for Paillier. The encryption keys are also considerably larger as well — especially when you’re using the more advanced functions that need **GaloisKeys**. Consequently, this means more bandwidth costs over the wire.

Now on to the good stuff!

Disclaimer:I have to say this is not a true comparison of Paillier vs SEAL, it’s rather a comparison of a particular library against another with arguably similar contexts. Unfortunately, there’s just not that much to compare it with so this is what we have for JavaScript. I’ve written a simple benchmark comparing the relative performance of each library.

I’ve configured Paillier to use a 3072-bit length which represents a 128-bit security context according to the NIST recommendation. For SEAL 128-bit security is already set up by default (unless overridden) and I’ve selected parameters that reflect a common real-world use case. This is the roughly the minimal setup in SEAL required to perform all homomorphic evaluations (including the advanced functions such as rotations, dot product, etc.) Sure, you could optimize if your application doesn’t use any multiplications to squeeze out every last drop, but this represents a good starting point.

```
Generating private/public keys: Done [2285233 microseconds]
Running tests .................................................. Done
Average encrypt: 232081 microseconds
Average decrypt: 229535 microseconds
Average add: 55 microseconds
Average multiply plain: 1409 microseconds
```

```
/
| Encryption parameters :
| scheme: BFV
| poly_modulus_degree: 4096
| coeff_modulus size: 109 (36 + 36 + 37) bits
| plain_modulus: 786433
\
Generating secret/public keys: Done [5428 microseconds]
Running tests .................................................. Done
Average batch: 269 microseconds
Average unbatch: 352 microseconds
Average encrypt: 6438 microseconds
Average decrypt: 1844 microseconds
Average add: 118 microseconds
Average multiply: 18647 microseconds
Average multiply plain: 2535 microseconds
```

You can find the benchmark script here.

Immediately you can see there’s a performance difference during encryption / decryption favoring SEAL, but another one favoring Paillier evaluations. Keep in mind I’ve only included a few of SEAL’s evaluation functions to keep this comparison more in line with what Paillier offers except multiplying

`ciphers`

together. This is an important distinction where you cannot perform this operation using Paillier and why it is called - Key Generation (5428) vs (2285233)
**~421x faster** - Encrypt (269 + 6438) vs (232081)
**~232x faster** - Decrypt (352 + 1844) vs (229535)
**~105x faster** - Add (55) vs (118)
**~2x slower** - Multiply Plain (1409) vs (2535)
**~2x slower**

*Wait a minute* — didn’t I mention SEAL supports batching? **Yes**, this test is performing these operations on **4096 elements all at the same time**. Don’t believe me? Feel free to check out the benchmark. With that in mind, you can realize a speedup over Paillier:

- Encrypt (269 + 6438) vs (232081 * 4096)
**~141,733x faster** - Decrypt (352 + 1844) vs (229535 * 4096)
**~4,281,301x faster** - Add (118) vs (55 * 4096)
**~1,909x faster** - Multiply Plain (2535) vs (1409 * 4096)
**~2,277x faster**

😎

Note: If you’re going to use more advanced functions with SEAL, you will need to generate relinearization keys which take about the same amount of space and time to generate as the public key. To perform rotations, you need Galois keys which take substantially longer to generate and are exceptionally large.

If you want more in-depth benchmarking of node-seal, you can clone my repo and simply run

`yarn benchmark:bfv`

or `yarn benchmark:ckks`

. You will be surprised to find `CKKS`

is actually `BFV`

in addition to the results listed above!You can see the tradeoff of using SEAL — you get much better computational performance and functionality, but pay for it in spatial complexity.

There’s a lot to digest, but to summarize:

**When to use Paillier**

- You
**are**in a network or memory-constrained environment - You only need to perform very simple homomorphic evaluations
- You’re not dealing with large amounts of encrypted data

**When to use SEAL**

- You
**are not**in a network or memory-constrained environment - You need to run advanced homomorphic evaluations
- When you are computing on large encrypted datasets

For environments that do not support WebAssembly, such as React-Native, you still have the option of choosing a pure JS implementation: paillier-pure or the deep import inside node-seal. Keep in mind the performance is quite a bit worse.

Stay tuned for **Part 3** where I build a simple application using **node-seal**. No jokes this time.

Thank you for reading!

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