Comparing Somewhat Homomorphic Encryption Algorithms: BGN, Freeman, BV and GHV

A while ago, I wrote a step by step post about Boneh-Goh-Nissim, the classic somewhat homomorphic encryption scheme. It lets you add ciphertexts as many times as you like, and multiply two ciphertexts exactly once. Since then, LightPHE has gained three more schemes with the very same promise: Freeman-Boneh-Goh-Nissim, Brakerski-Vaikuntanathan and Gentry-Halevi-Vaikuntanathan. Four algorithms, one capability. So which one should you use?

Artistic calendar display with highlighted red typography and marked dates by pexels

It turns out they couldn’t be more different under the hood. Two of them live on elliptic curves and multiply with bilinear pairings, the other two live on lattices and multiply polynomials or matrices. Their security assumptions, plaintext spaces, ciphertext sizes and speeds vary by orders of magnitude. In this post, we’ll see how each one pulls off its single multiplication, compare them side by side, and then run the same code on all four with LightPHE in Python, Go, Java and TypeScript.


🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

Public Key Cryptography From Scratch

What Makes Encryption Somewhat Homomorphic

Partially homomorphic schemes such as Paillier support a single kind of operation on ciphertexts, usually addition. Fully homomorphic schemes support any number of additions and multiplications. Somewhat homomorphic schemes sit in between: both operations, but a bounded number of multiplications. The four schemes in this post allow exactly one, so they evaluate degree-2 polynomials on encrypted data:

degree 1:   x + y,   3x + 5y,   x_1 + x_2 + ... + x_n                  partially homomorphic
degree 2:   x y,   x^2 + y^2,   x_1 y_1 + x_2 y_2 + ... + x_n y_n      these four schemes
degree 3+:  x y z,   x^3                                               out of reach

Degree 2 is a sweet spot. It covers dot products and cosine similarity if vectors are normalized already, squared distances and euclidean distance, variances, covariances and correlations, which is a large share of everyday statistics and machine learning inference.

Why only one multiplication? Each scheme has its own reason, and those reasons explain most of the differences between them. Let’s look at them one by one.

Boneh-Goh-Nissim: Pairings on a Composite-Order Curve

Boneh-Goh-Nissim, from Evaluating 2-DNF Formulas on Ciphertexts (TCC 2005), works on an elliptic curve whose group has a composite order n = q1 q2. The public key holds a generator G, and a point h of order q1. Factoring n is the secret.

encrypt:    C = m G + r h                                for a random r
decrypt:    q1 C = m (q1 G) + r (q1 h) = m (q1 G)        as q1 h vanishes, then discrete logarithm base q1 G
multiply:   e(C1, C2) = e(G, G)^(m1 m2) * (terms that vanish when raised to q1)

Multiplying with q1 wipes out the random part, but the message remains hidden in a discrete logarithm. Decryption has to solve it, so messages must be small. The multiplication uses a bilinear pairing e, which maps two curve points to an element of a finite field, the target group. And that’s why there is only one: the result is no longer a curve point, and there is no pairing defined on the target group to apply again.

The catch is the composite order. The security relies on factoring n, so n must be large, and generating a curve of a given composite order is slow.

Freeman-Boneh-Goh-Nissim: The Same Idea in Prime Order

In Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups (EUROCRYPT 2010), David Freeman showed how to get rid of the composite order. Instead of a subgroup of order q1 hiding the noise, a ciphertext is a vector of three points, and the noise lives in a secret two-dimensional subspace H. The private key is a vector v orthogonal to that subspace.

public key: g, h1, h2      vectors of 3 points, where h1 and h2 span H, and v . H = 0
encrypt:    C = m g + a1 h1 + a2 h2                     for random a1, a2
decrypt:    pi(C) = v1 C1 + v2 C2 + v3 C3 = m pi(g)     as pi(h1) = pi(h2) = 0, then discrete logarithm
multiply:   e(C_i, C'_j) for all i, j                   9 pairings

The projection pi plays the role of multiplying with q1: it annihilates the noise. The group order is now a 256-bit prime, and security relies on the decision linear assumption rather than factoring, so keys are generated in a second instead of minutes. Each pairing is cheaper too, but a multiplication needs nine of them, and a multiplied ciphertext is a 3 x 3 grid of field elements. Decryption still solves a discrete logarithm, with baby-step giant-step, so results must stay within [-2^20, 2^20] by default.

Brakerski-Vaikuntanathan: Polynomials and Noise

Brakerski-Vaikuntanathan, from Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages (CRYPTO 2011), leaves elliptic curves behind. It works with polynomials of degree less than d, with coefficients modulo a large q. The private key s is a polynomial with small coefficients, and a ciphertext is a pair of polynomials.

decrypt:    c0 + c1 s = m + t * noise  (mod q)              m is its constant term mod t
multiply:   (c0, c1) x (c0', c1') = (c0 c0',  c0 c1' + c1 c0',  c1 c1')
decrypt:    c0 c0' + (c0 c1' + c1 c0') s + c1 c1' s^2 = (c0 + c1 s)(c0' + c1' s) = m m' + t * (noise ...)

There is no discrete logarithm here: the message sits in the clear modulo t, hidden by a small noise and a uniformly random looking mask. That’s why decryption is fast, and why the plaintext space can be large, 2^24 by default. The limit comes from the noise instead. Additions add noises, multiplications multiply them, and decryption silently returns garbage once the noise exceeds q / 2. A product also turns a pair into a triple, which needs s^2 to decrypt. Fully homomorphic schemes shrink it back with relinearization and tame the noise with modulus switching or bootstrapping; without them, one multiplication is where the road ends.

Its security relies on the ring learning with errors problem, which is believed to be hard for quantum computers too. With d = 4096 and q around 2^100, it offers about 128-bit security against quantum attacks according to the Homomorphic Encryption Standard. The price is size: a ciphertext is two polynomials of 4096 coefficients of 100 bits.

Gentry-Halevi-Vaikuntanathan: Boneh-Goh-Nissim From Lattices

The title of A Simple BGN-Type Cryptosystem from LWE (EUROCRYPT 2010) says it all. Craig Gentry, Shai Halevi and Vinod Vaikuntanathan rebuilt Boneh-Goh-Nissim on plain learning with errors, using matrices. The public key is a matrix A, and the private key is a short trapdoor matrix T with T A = 0 mod q.

encrypt:    C = A S + p X + m I  (mod q)                for random S and small X
decrypt:    T C T^T = T (p X + m I) T^T  (mod q)        as T A = 0, small enough to hold over the integers
            reduce mod p, then multiply with T^-1 and T^-T mod p to recover m I
multiply:   C1 C2^T                                     decrypted in exactly the same way

Look at the decryption: the trapdoor sandwiches the ciphertext from both sides, T C T^T. A product C1 C2^T fits into that sandwich perfectly, as A is cancelled on the left by T and on the right by T^T. A product of three matrices has a middle factor that no trapdoor can reach, which is exactly why there’s only one multiplication. It’s a beautiful construction, and probably the clearest way to see why lattices can multiply at all.





But it’s not practical. Ciphertexts are square matrices whose size grows with n log q, so secure parameters would need ciphertexts of terabytes. LightPHE supports it with tiny lattice dimensions from 2 to 8, for learning purposes only, and warns you every time you build it. Its default plaintext modulus is the prime 101.

Side by Side

Here is how the four compare with LightPHE’s default settings:

Boneh-Goh-NissimFreeman-Boneh-Goh-NissimBrakerski-VaikuntanathanGentry-Halevi-Vaikuntanathan
Hard problemSubgroup decision, i.e. factoringDecision linearRing learning with errorsLearning with errors
Quantum resistant❌❌✅✅ in theory
CiphertextA curve pointA vector of 3 curve pointsA pair of polynomialsA square matrix
Multiplication1 pairing9 pairingsPolynomial tensor productMatrix product
Default key size1024-bit n1024-bit fieldRing degree 4096Lattice dimension 4
Security levelAbout 80 bitsAbout 112 bitsAbout 128 bits, post-quantumNone, for learning only
Plaintext spaceSmall, as decryption tries values one by one[-2^20, 2^20]Modulo 2^24Modulo 101
Out of range resultsDecryption gets linearly slowerDecryption raises an errorWrap around silentlyWrap around silently
Adding a fresh ciphertext to a product❌ Needs a trick, see below✅✅✅
Fresh / multiplied ciphertext size0.7 KB / 0.7 KB2.1 KB / 5.9 KB257 KB / 386 KB477 KB / 477 KB

Ciphertext sizes are their serialized JSON sizes. And here is how long each step took in Python on my laptop, again with default settings:

Python, secondsBoneh-Goh-NissimFreeman-Boneh-Goh-NissimBrakerski-VaikuntanathanGentry-Halevi-Vaikuntanathan
Key generationMinutes, and highly variable1.50.21.8
Encryption0.690.790.370.23
Addition< 0.0010.0010.0020.008
Multiplication1.964.560.380.73
Decryption of a product, 17 x 212.271.090.140.78

Boneh-Goh-Nissim key generation searches for a curve of the right composite order, which took over six minutes in one of my runs. The Go port is a lot faster across the board: it ran Example 1 below, including Boneh-Goh-Nissim key generation for all four schemes, in about 6 seconds.

Example 1: Same Code, Four Schemes

All four share one interface in LightPHE, so let’s evaluate the same degree-2 polynomial, 2 x y + z, with each of them, and then try a second multiplication, which all four must refuse.

There is one wrinkle. In Boneh-Goh-Nissim, a product lives in the target group of the pairing, while a fresh ciphertext is a curve point, so they can’t be added directly. The fix is to multiply the fresh ciphertext with an encryption of 1: Enc(z) * Enc(1) is an encryption of z in the target group. Freeman-Boneh-Goh-Nissim does the same thing automatically, by pairing a fresh ciphertext with g, and the lattice schemes don’t need it at all. The trick works for all four, so the code stays the same.

Java snippets use assert for brevity, so run them with -ea to enable assertions. All four schemes return 29, and all four refuse the second multiplication with an error such as Brakerski-Vaikuntanathan supports only one multiplication. Multiplied ciphertexts cannot be multiplied with ciphertexts again.

Example 2: Where They Differ, Encrypted Inventory Valuation

A retailer keeps its stock quantities and its unit costs encrypted in the cloud, as both are commercially sensitive. To value the inventory, the cloud needs the sum of quantity times unit cost over all products: a dot product of two encrypted vectors, which is a degree-2 function. Let’s run it on all four schemes.

Three schemes report an inventory value of 6112. Gentry-Halevi-Vaikuntanathan reports 52, with no error at all. Every input fits in its plaintext space modulo 101, but the result doesn’t, so it wraps around: 6112 mod 101 is 52. Brakerski-Vaikuntanathan would behave the same way past 2^24. Freeman-Boneh-Goh-Nissim, in contrast, raises an error when a result falls outside [-2^20, 2^20], and Boneh-Goh-Nissim just gets slower, as its decryption tries candidate values one by one.

So size the plaintext space for your results, not for your inputs. All schemes but Boneh-Goh-Nissim accept a plaintext limit: plaintext_limit in Python, WithPlaintextLimit in Go and plaintextLimit in Java and TypeScript. With a limit of 10000, Gentry-Halevi-Vaikuntanathan picks the prime 10007 as its plaintext modulus and returns 6112, but its ciphertext modulus grows to make room, and a ciphertext grows to about 1 MB. For the lattice schemes, a larger plaintext space always leaves less room for noise.

Which One Should You Use

  • Brakerski-Vaikuntanathan for most real use cases. It’s the fastest, it has the largest plaintext space, and it’s quantum resistant at 128-bit security. Its weak spot is size: hundreds of kilobytes per ciphertext.
  • Freeman-Boneh-Goh-Nissim when bandwidth matters more than speed. Its ciphertexts are a few kilobytes, a hundred times smaller than Brakerski-Vaikuntanathan’s, and it fails loudly rather than silently. But results must be small, multiplications are slow, and it’s not quantum resistant.
  • Boneh-Goh-Nissim when you want the tiniest ciphertexts, or to learn the original idea. Freeman’s variant is better at everything else: faster key generation, stronger security at the same key size, and a larger plaintext space.
  • Gentry-Halevi-Vaikuntanathan for learning only. It shows beautifully how lattices multiply, but it’s insecure with the parameters it can afford.

And if all you need is one multiplication on top of an additive scheme you already use, with large plaintexts, LightPHE’s Catalano-Fiore transform adds it to Paillier and friends. If you need more than one multiplication on bits, Gentry-Sahai-Waters in LightPHE evaluates boolean circuits deeper than degree 2.

Caveats

  • Integers only: None of the four supports floats or tensors, because scaling floats by powers of 10 quickly exceeds their small plaintext spaces. Scale values to integers yourself, and remember that a product of two values scaled by 100 is scaled by 10,000.
  • Silent failures: The lattice schemes return wrong results without any error when a result exceeds the plaintext space or the noise exceeds its budget. Check your worst case before deploying.
  • Exactly one multiplication: Degree 3 and above are out of reach for all four. That’s the territory of fully homomorphic encryption.
  • Quantum computers: Both pairing-based schemes fall to Shor’s algorithm. Only the lattice schemes are believed to resist quantum attacks, and only Brakerski-Vaikuntanathan with secure parameters.

Conclusion

Four schemes, one promise: unlimited additions and a single multiplication. Boneh-Goh-Nissim and Freeman’s prime-order version get there with bilinear pairings, and stop because the product lands in a group with no pairing of its own. Brakerski-Vaikuntanathan and Gentry-Halevi-Vaikuntanathan get there with lattices, and stop because the noise and the shape of the ciphertext leave no room for a second round. In practice, Brakerski-Vaikuntanathan is the one to reach for, Freeman-Boneh-Goh-Nissim when ciphertexts must be small, and the other two are wonderful for understanding how it all works.

Thanks to LightPHE’s common interface, switching between them is a one-word change—in Python, Go, Java or TypeScript.


Support this blog financially if you do like!

Buy me a coffee      Buy me a coffee


Leave a Reply