1,126 reads

Homomorphic Encryption — for Web Apps 🧐 (Part 2)

by Nick AngelouApril 11th, 2020

Too Long; Didn't Read

Microsoft SEAL is the only fully homomorphic library available among a sea of partially homomorphic libraries in the JavaScript domain. SEAL can operate on all batched elements in parallel with no cost as Single Instruction, Multiple DataSIMD (SIMD) or Multiple Instruction, Single Instruction (SIXIX) SEAL can also operate on the number of data you are allowed to encode using the BatchEncoder. For very simple applications Paillier may be a better choice for simple applications, SEAL for complex applications.

Companies Mentioned

Coin Mentioned

featured image - Homomorphic Encryption — for Web Apps 🧐 (Part 2)

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

📋 Feature Comparison

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
```
ciphers
```
together
Multiply a
```
cipher
```
by a
```
plain
```

SEAL

Negate a
```
cipher
```
Add two
```
ciphers
```
together
Add a
```
plain
```
to a
```
cipher
```
Subtract two
```
ciphers
```
together
Subtract a
```
plain
```
from a
```
cipher
```
Multiply two
```
ciphers
```
together
Multiply a
```
cipher
```
by a
```
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.

Encrypting values

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 number, albeit a very large one — a BigInt. This is the reason why many Paillier implementations are dependent on BigInt support.

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.

Parallelism

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 the
BatchEncoder
is 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: 4096 elements.

📦 The Setup

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.

paillier-bigint

// 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…

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

CKKS

in Part 1.

Scheme Type

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 SIMD. My

polyModulusDegree

is set to

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.

CoeffModulus

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.

PlainModulus

The

plainModulus

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

plainModulus

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

and worry about this value when you encounter decryptions that fail after a certain magnitude.

💾 Spatial Complexity

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 all of the objects in their library allowing us to communicate much more easily with different library implementations. Let’s see what this looks like assuming some of the objects we are using are global in this scope:

// 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 very versatile for many languages such as C++ or Python.

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.

📊 Performance

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.

paillier-bigint

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

node-seal

/
| 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 partially homomorphic.

Node-seal vs Paillier-bigint:

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

yarn benchmark:ckks

. You will be surprised to find

CKKS

is actually faster than

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.

Conclusion

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