The Microsoft SEAL (Simple Encrypted Arithmetic Library) library can support a range of homomorphic encryption methods, and which use Learning With Errors (LWE). In this case we will implement with the BFV (Brakerski/Fan-Vercauteren) method. Overall, BFV is a ring LWE method, and where we have a public modulus of \(Q\). We then have a secret key of \(s\) (and which is between 0 and \(Q\)-1), and a random polynomial value of A. We also have an error polynomial of \(e\).
Homomorphic Encryption with BFV using Node.js |
Theory
The Microsoft SEAL library can support a range of homomorphic encryption methods, and which use Learning With Errors (LWE). In this case we will implement with the BFV (Brakerski/Fan-Vercauteren) method. Overall, BFV is a ring LWE method, and where we have a public modulus of \(Q\). We then have a secret key of \(s\) (and which is between 0 and \(Q\)-1), and a random polynomial value of A. We also have an error polynomial of \(e\). For the public key, we create a polynomial of:
\(B=A.s+e \pmod Q\)
The polynomial values of \(A\) and \(B\) are then the public key, and \(s\) is the private key. To encrypt, we basically take samples from A and B and compute values of \(a_i\) and \(b_i\):
\(a_i = A_i \pmod Q\)
\(b_i= B_i + \frac{q}{2}.M_i \pmod Q\)
and where \(M_i\) is the message bits (0 or 1). To decrypt (a,b), we need the private key (\(s\)) and perform:
\(m = b- s.a \pmod Q\)
Thus:
\(m = B+\frac{q}{2}.M - s.A = (A.s+e+ \frac{q}{2}.M)- s.A = e+\frac{q}{2}.M \pmod Q\)
We then round each coefficient of m to either q/2 or zero. A value of q/2 is 1, and a value of zero is 0. This will work is e is much smaller than q/2. A demonstration of this is here:
Coding
// Derived from https://github.com/morfix-io/node-seal/blob/main/FULL-EXAMPLE.md ;(async () => { const SEAL = require('node-seal') const seal = await SEAL() const schemeType = seal.SchemeType.bfv const securityLevel = seal.SecurityLevel.tc128 const polyModulusDegree = 4096 const bitSizes = [36, 36, 37] const bitSize = 20 const parms = seal.EncryptionParameters(schemeType) // Set the PolyModulusDegree parms.setPolyModulusDegree(polyModulusDegree) // Create a suitable set of CoeffModulus primes parms.setCoeffModulus( seal.CoeffModulus.Create(polyModulusDegree, Int32Array.from(bitSizes)) ) // Set the PlainModulus to a prime of bitSize 20. parms.setPlainModulus( seal.PlainModulus.Batching(polyModulusDegree, bitSize) ) const context = seal.Context( parms, // Encryption Parameters true, // ExpandModChain securityLevel // Enforce a security level ) if (!context.parametersSet()) { throw new Error( 'Could not set the parameters in the given context. Please try different encryption parameters.' ) } const encoder = seal.BatchEncoder(context) const keyGenerator = seal.KeyGenerator(context) const publicKey = keyGenerator.createPublicKey() const secretKey = keyGenerator.secretKey() const encryptor = seal.Encryptor(context, publicKey) const decryptor = seal.Decryptor(context, secretKey) const evaluator = seal.Evaluator(context) var in1 = "2,5,3,4,5" var in2 = "3,5,9,11,2" const myArgs = process.argv.slice(2); in1=myArgs[0] in2=myArgs[1] const array1 = Int32Array.from(in1.split(',')) const array2 = Int32Array.from(in2.split(',')) const plainText1 = encoder.encode(array1) const plainText2 = encoder.encode(array2) var cipherText1 = encryptor.encrypt(plainText1) var cipherText2 = encryptor.encrypt(plainText2) console.log('Plaintext 1:', array1) console.log('Plaintext 2:', array2) evaluator.add(cipherText1, cipherText2, cipherText1) var decryptedPlainText = decryptor.decrypt(cipherText1) var decodedArray = encoder.decode(decryptedPlainText) console.log('Decrypted (Homomorphic Add): ', decodedArray) cipherText1 = encryptor.encrypt(plainText1) cipherText2 = encryptor.encrypt(plainText2) evaluator.sub(cipherText1, cipherText2, cipherText1) decryptedPlainText = decryptor.decrypt(cipherText1) decodedArray = encoder.decode(decryptedPlainText) console.log('Decrypted (Homomorphic Subtract): ', decodedArray) cipherText1 = encryptor.encrypt(plainText1) cipherText2 = encryptor.encrypt(plainText2) evaluator.multiply(cipherText1, cipherText2, cipherText1) decryptedPlainText = decryptor.decrypt(cipherText1) decodedArray = encoder.decode(decryptedPlainText) console.log('Decrypted (Homomorphic Multiplication): ', decodedArray) })()
A sample run is:
Plaintext 1: Int32Array [ 2, 5, 3, 4, 5 ] Plaintext 2: Int32Array [ 3, 5, 9, 11, 2 ] Decrypted (Homomorphic Add): Int32Array [ 5, 10, 12, 15, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 3996 more items ] Decrypted (Homomorphic Subtract): Int32Array [ -1, 0, -6, -7, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 3996 more items ] Decrypted (Homomorphic Multiplication): Int32Array [ 6, 25, 27, 44, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 3996 more items ]