In case you missed the previous article ( ), I gave a very brief introduction on Homomorphic Encryption (HE), talked about library, and outlined some of the pain points of learning to use it. Part 1 Microsoft SEAL’s — you really have to spend a lot of time understanding the inner-workings of the library so I built to help you rapidly experiment with Microsoft SEAL using , the JavaScript package I wrote. tl;dr morfix.io node-seal 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. : Paillier for simple applications, SEAL for complex applications Spoiler 📋 Feature Comparison It is important to know is not the only HE library — especially in the JavaScript world. Unfortunately, it happens to be the only homomorphic library available among a sea of homomorphic libraries in the JavaScript domain. node-seal fully partially Many of these alternatives leverage the . 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 and a ciphertext as : Paillier cryptosystem plain 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 Paillier can only multiply a by a — but this is still very useful. For very simple applications Paillier maybe a better choice. ciphers cipher plain Encrypting values So far, we are talking about homomorphic evaluations on — this is where Paillier shines in terms of both algorithmic and spatial complexity. single values You simply encrypt a value and receive a : cipher cipher = encrypt( ) cipher // Pseudocode const 5 typeof // 'bigint' Homomorphic operations are rather fast on single values and each Paillier is just another , albeit a very large one — a . This is the reason why many Paillier implementations are dependent on support. cipher number BigInt BigInt How you would encrypt a value and receive a using SEAL: cipher plain = encode( ) plain cipher = encrypt(plain) cipher // Pseudocode const 5 typeof // ? const typeof // ? In SEAL, there’s an extra abstraction — you need to perform an extra step of your data before encryption. Needless to say, the underlying data is not a primitive type. encoding 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 all the numbers into a single using the . batch plain BatchEncoder What this means is instead of iterating in a loop for 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 ( ). n SIMD 🦾 : In SEAL, the number of elements you are allowed to encode using the 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: elements. Note BatchEncoder 4096 📦 The Setup The process is a bit different because where Paillier can directly encrypt numbers, SEAL requires us to first 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. encode paillier-bigint paillier = ( ) * paillier ( () => { { publicKey, privateKey } = paillier.generateRandomKeys( ) cipher = publicKey.encrypt( n) decypted = privateKey.decrypt(cipher) })() // import paillier in node.js const require 'paillier-bigint.js' // import paillier in native JS import as from 'paillier-bigint' async // Create keys const await 3072 // Encrypt the plainText integer const 5 // Decrypt the cipherText const // decrypted === 5n Not bad! Now, let’s look at node-seal… node-seal { Seal } = ( )
( () => { Morfix = Seal() schemeType = Morfix.SchemeType.BFV polyModulusDegree = bitSizes = [ , , ] bitSize = encParms = Morfix.EncryptionParameters(schemeType) encParms.setPolyModulusDegree(polyModulusDegree) coeffModulus = Morfix.CoeffModulus.Create(
      polyModulusDegree, .from(bitSizes)
    )
    encParms.setCoeffModulus(coeffModulus) plainModulus = Morfix.PlainModulus.Batching(polyModulusDegree, bitSize)
    encParms.setPlainModulus(plainModulus) context = Morfix.Context(encParms, ) (!context.parametersSet) { ( )
    } keyGenerator = Morfix.KeyGenerator(context) secretKey = keyGenerator.getSecretKey() publicKey = keyGenerator.getPublicKey() evaluator = Morfix.Evaluator(context) batchEncoder = Morfix.BatchEncoder(context) encryptor = Morfix.Encryptor(context, publicKey) decryptor = Morfix.Decryptor(context, secretKey) array = .from({ : })
      .map( i) plain = batchEncoder.encode(array) cipher = encryptor.encrypt(plain) decryptedPlainText = decryptor.decrypt(cipher) decodedPlainText = batchEncoder.decode(decryptedPlainText) })() // Pick one for your environment // npm install node-seal // yarn add node-seal // // ES6 or CommonJS // import { Seal } from 'node-seal' const require 'node-seal' async // Wait for the web assembly to fully initialize const await //////////////////////// // Encryption Parameters //////////////////////// // Create a new EncryptionParameters const const 4096 const 36 36 37 const 20 const // Assign Poly Modulus Degree // Create a suitable set of CoeffModulus primes const Int32Array // Assign a PlainModulus (only for BFV scheme type) const //////////////////////// // Context //////////////////////// // Create a new Context const true // Helper to check if the Context was created successfully if throw new Error 'Could not set the parameters in the given context. Please try different encryption parameters.' //////////////////////// // Keys //////////////////////// const const const //////////////////////// // Instances //////////////////////// const // Create a BatchEncoder (only BFV SchemeType) const const const //////////////////////// // Homomorphic Functions //////////////////////// // Create an array of 4096 values const Int32Array length 4096 ( ) => _, i // Encode data to a PlainText const // Encrypt a PlainText const // Decrypt a CipherText const // Decode data from a PlainText const // decodedPlainText === array 😧🔫 Okay wow — there’s more you need to setup when using node-seal. Luckily for you, all your code can be generated using the on and there’s also documentation located at . You can find a little more information on vs in . a lot code generator morfix.io/sandbox docs.morfix.io BFV CKKS Part 1 Scheme Type I’ve selected because I want to just worry about integers and not floats. I’ve also selected to use the to take advantage of . My 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. BFV batchEncoder SIMD polyModulusDegree 4096 CoeffModulus The 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 . coeffModulus morfix.io/sandbox PlainModulus The is the gatekeeper of the upper and lower bounds of each value you encrypt. More precisely, the values are stored the . 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. plainModulus modulo plainModulus 20 💾 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 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 is trivial since there are a few ways to serialize BigInts. ciphers ciphers I’m using synchronous operations for the sake of readability here… fs genKeyPair = keySize => { keys = paillier.generateRandomKeys(keySize)
  privateKey = keys.privateKey
  publicKey = keys.publicKey BigInt.prototype.toJSON = { }
  fs.writeFileSync( , .stringify(privateKey), )
  fs.writeFileSync( , .stringify(publicKey), )
} loadKeys = () => { rawPrivateKey = fs.readFileSync( , ) rawPublicKey = fs.readFileSync( , ) privateKeyObject = .parse(rawPrivateKey) publicKeyObject = .parse(rawPublicKey) publicKey = paillier.PublicKey(
    BigInt(publicKeyObject.n),
    BigInt(publicKeyObject.g)
  ) privateKey = paillier.PrivateKey(
    BigInt(privateKeyObject.lambda),
    BigInt(privateKeyObject.mu),
    publicKey,
    BigInt(privateKeyObject.p),
    BigInt(privateKeyObject.q)
  ) { privateKey, publicKey }
} // Generate and save const async const // 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. ( ) function return ` ` ${ .toString()} this 'paillier_private_key' JSON 'utf8' 'paillier_public_key' JSON 'utf8' // Load and instantiate const async const 'paillier_private_key' 'utf8' const 'paillier_public_key' 'utf8' const JSON const JSON const new const new return 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 and for 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: save load all genKeyPair = context => { keyGenerator = Morfix.keyGenerator(context) privateKey = keys.getSecretKey() publicKey = keys.getPublicKey()
  fs.writeFileSync( , privateKey.save(), )
  fs.writeFileSync( , publicKey.save(), )
} loadKeys = context => { sKey = Morfix.SecretKey() pKey = Morfix.PublicKey()
  sKey.load(context, fs.readFileSync(secretKeyName, ))
  pKey.load(context, fs.readFileSync(publicKeyName, )) { : sKey, : pKey }
} // Generate and save const async const const const 'seal_private_key' 'utf8' 'seal_public_key' 'utf8' // Load and instantiate const async const const 'utf8' 'utf8' return privateKey publicKey The serialized output can be configured to be a base64 string or a binary Uint8Array. These methods are also available on and . Deserializing automatically ensures the object is valid, making it versatile for many languages such as C++ or Python. plains ciphers very But there’s one drawback — the size… saved = encrypted.save() .log(Buffer.byteLength(saved, )) const console 'base64' // 91213 bytes ~ Yikes! That’s 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 . Consequently, this means more bandwidth costs over the wire. 89Kb a lot GaloisKeys 📊 Performance Now on to the good stuff! 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. Disclaimer: I’ve configured Paillier to use a 3072-bit length which represents a 128-bit security context according to the . 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. NIST recommendation paillier-bigint Generating private/public keys: Done [ microseconds]
Running tests .................................................. Done
Average encrypt: microseconds
Average decrypt: microseconds
Average add: microseconds
Average multiply plain: microseconds 2285233 232081 229535 55 1409 node-seal /
| Encryption parameters :
|   scheme: BFV
|   poly_modulus_degree: |   coeff_modulus size: ( + + ) bits
|   plain_modulus: \
Generating secret/public keys: Done [ microseconds]
Running tests .................................................. Done
Average batch: microseconds
Average unbatch: microseconds
Average encrypt: microseconds
Average decrypt: microseconds
Average add: microseconds
Average multiply: microseconds
Average multiply plain: microseconds 4096 109 36 36 37 786433 5428 269 352 6438 1844 118 18647 2535 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 together. This is an important distinction where you cannot perform this operation using Paillier and why it is called homomorphic. ciphers partially 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 — didn’t I mention SEAL supports batching? , this test is performing these operations on . Don’t believe me? Feel free to check out the . With that in mind, you can realize a speedup over Paillier: Wait a minute Yes 4096 elements all at the same time benchmark 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 😎 : 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. Note If you want more in-depth benchmarking of node-seal, you can and simply run or . You will be surprised to find is actually than in addition to the results listed above! clone my repo yarn benchmark:bfv yarn benchmark:ckks CKKS faster BFV 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 in a network or memory-constrained environment are You only need to perform very simple homomorphic evaluations You’re not dealing with large amounts of encrypted data When to use SEAL You in a network or memory-constrained environment are not You need to run advanced homomorphic evaluations When you are computing on large encrypted datasets For environments that do not support WebAssembly, such as , you still have the option of choosing a pure JS implementation: or the deep import inside . Keep in mind the performance is quite a bit worse. React-Native paillier-pure node-seal Stay tuned for where I build a simple application using . No jokes this time. Part 3 node-seal Thank you for reading! Previously published at https://medium.com/@s0l0ist/homomorphic-encryption-for-web-apps-b615fb64d2a2

Stacks

Assembly

Microsoft

Build privacy-preserving apps

Read My Stories

Too Long; Didn't Read

ML Practitioners - Ready to Level Up your Skills?

Homomorphic Encryption — for Web Apps 🧐 (Part 2)

Too Long; Didn't Read

Companies Mentioned

Coin Mentioned

@s0l0ist

RELATED STORIES