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?

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
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-Nissim | Freeman-Boneh-Goh-Nissim | Brakerski-Vaikuntanathan | Gentry-Halevi-Vaikuntanathan | |
| Hard problem | Subgroup decision, i.e. factoring | Decision linear | Ring learning with errors | Learning with errors |
| Quantum resistant | ❌ | ❌ | ✅ | ✅ in theory |
| Ciphertext | A curve point | A vector of 3 curve points | A pair of polynomials | A square matrix |
| Multiplication | 1 pairing | 9 pairings | Polynomial tensor product | Matrix product |
| Default key size | 1024-bit n | 1024-bit field | Ring degree 4096 | Lattice dimension 4 |
| Security level | About 80 bits | About 112 bits | About 128 bits, post-quantum | None, for learning only |
| Plaintext space | Small, as decryption tries values one by one | [-2^20, 2^20] | Modulo 2^24 | Modulo 101 |
| Out of range results | Decryption gets linearly slower | Decryption raises an error | Wrap around silently | Wrap around silently |
| Adding a fresh ciphertext to a product | ❌ Needs a trick, see below | ✅ | ✅ | ✅ |
| Fresh / multiplied ciphertext size | 0.7 KB / 0.7 KB | 2.1 KB / 5.9 KB | 257 KB / 386 KB | 477 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, seconds | Boneh-Goh-Nissim | Freeman-Boneh-Goh-Nissim | Brakerski-Vaikuntanathan | Gentry-Halevi-Vaikuntanathan |
| Key generation | Minutes, and highly variable | 1.5 | 0.2 | 1.8 |
| Encryption | 0.69 | 0.79 | 0.37 | 0.23 |
| Addition | < 0.001 | 0.001 | 0.002 | 0.008 |
| Multiplication | 1.96 | 4.56 | 0.38 | 0.73 |
| Decryption of a product, 17 x 21 | 2.27 | 1.09 | 0.14 | 0.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.
from lightphe import LightPHE
algorithms = [
"Boneh-Goh-Nissim",
"Freeman-Boneh-Goh-Nissim",
"Brakerski-Vaikuntanathan",
"Gentry-Halevi-Vaikuntanathan",
]
for algorithm in algorithms:
cs = LightPHE(algorithm_name = algorithm)
x, y, z = cs.encrypt(3), cs.encrypt(4), cs.encrypt(5)
# boneh-goh-nissim cannot add a fresh ciphertext to a product,
# so z is multiplied with an encrypted 1 first. this works for all four.
one = cs.encrypt(1)
# one multiplication, then additions and multiplications with constants
assert cs.decrypt(x * y * 2 + z * one) == 29
# but not a second multiplication
try:
x * y * z
raise AssertionError("a second multiplication must be refused")
except ValueError as err:
print(f"{algorithm}: {err}")
package main
import (
"fmt"
"log"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
algorithms := []lightphe.Algorithm{
lightphe.BonehGohNissim,
lightphe.FreemanBonehGohNissim,
lightphe.BrakerskiVaikuntanathan,
lightphe.GentryHaleviVaikuntanathan,
}
for _, algorithm := range algorithms {
cs, err := lightphe.New(algorithm)
check(err)
x, err := cs.EncryptInt(3)
check(err)
y, err := cs.EncryptInt(4)
check(err)
z, err := cs.EncryptInt(5)
check(err)
// boneh-goh-nissim cannot add a fresh ciphertext to a product,
// so z is multiplied with an encrypted 1 first. this works for all four.
one, err := cs.EncryptInt(1)
check(err)
// one multiplication, then additions and multiplications with constants
xy, err := x.Multiply(y)
check(err)
doubled, err := xy.MultiplyByInt(2)
check(err)
zLifted, err := z.Multiply(one)
check(err)
result, err := doubled.Add(zLifted)
check(err)
m, err := cs.Decrypt(result)
check(err)
fmt.Println(algorithm, m) // 29
// but not a second multiplication
if _, err := xy.Multiply(z); err != nil {
fmt.Println(algorithm, err)
} else {
log.Fatal("a second multiplication must be refused")
}
}
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import java.math.BigInteger;
import java.util.List;
List<String> algorithms = List.of(
"Boneh-Goh-Nissim",
"Freeman-Boneh-Goh-Nissim",
"Brakerski-Vaikuntanathan",
"Gentry-Halevi-Vaikuntanathan");
for (String algorithm : algorithms) {
LightPHE cs = LightPHE.builder().algorithmName(algorithm).build();
Ciphertext x = cs.encrypt(3), y = cs.encrypt(4), z = cs.encrypt(5);
// boneh-goh-nissim cannot add a fresh ciphertext to a product,
// so z is multiplied with an encrypted 1 first. this works for all four.
Ciphertext one = cs.encrypt(1);
// one multiplication, then additions and multiplications with constants
assert cs.decrypt(x.multiply(y).multiply(2).add(z.multiply(one))).equals(BigInteger.valueOf(29));
// but not a second multiplication
try {
x.multiply(y).multiply(z);
throw new AssertionError("a second multiplication must be refused");
} catch (IllegalArgumentException | UnsupportedOperationException e) {
System.out.println(algorithm + ": " + e.getMessage());
}
}
import { LightPHE } from 'lightphe-ts';
const algorithms = [
'Boneh-Goh-Nissim',
'Freeman-Boneh-Goh-Nissim',
'Brakerski-Vaikuntanathan',
'Gentry-Halevi-Vaikuntanathan',
];
for (const algorithm of algorithms) {
const cs = new LightPHE({ algorithmName: algorithm });
const [x, y, z] = [3, 4, 5].map((m) => cs.encrypt(m));
// boneh-goh-nissim cannot add a fresh ciphertext to a product,
// so z is multiplied with an encrypted 1 first. this works for all four.
const one = cs.encrypt(1);
// one multiplication, then additions and multiplications with constants
console.assert(cs.decrypt(x.multiply(y).multiply(2).add(z.multiply(one))) === 29n);
// but not a second multiplication
try {
x.multiply(y).multiply(z);
throw new Error('a second multiplication must be refused');
} catch (err) {
console.log(`${algorithm}: ${(err as Error).message}`);
}
}
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.
from lightphe import LightPHE
# retailer's stock quantities and unit costs - both confidential
quantities = [12, 75, 40, 26, 18]
unit_costs = [12, 30, 45, 8, 95]
for algorithm in [
"Boneh-Goh-Nissim",
"Freeman-Boneh-Goh-Nissim",
"Brakerski-Vaikuntanathan",
"Gentry-Halevi-Vaikuntanathan",
]:
# retailer builds the cryptosystem, encrypts both columns and uploads them to the cloud
cs = LightPHE(algorithm_name = algorithm)
encrypted_quantities = [cs.encrypt(q) for q in quantities]
encrypted_costs = [cs.encrypt(c) for c in unit_costs]
# cloud computes the inventory value, a dot product of two encrypted vectors
encrypted_value = encrypted_quantities[0] * encrypted_costs[0]
for q, c in zip(encrypted_quantities[1:], encrypted_costs[1:]):
encrypted_value = encrypted_value + q * c
# retailer decrypts it
print(f"{algorithm}: {cs.decrypt(encrypted_value)}")
# expected: 6112 for the first three, 6112 mod 101 = 52 for gentry-halevi-vaikuntanathan
package main
import (
"fmt"
"log"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// retailer's stock quantities and unit costs - both confidential
quantities := []int64{12, 75, 40, 26, 18}
unitCosts := []int64{12, 30, 45, 8, 95}
for _, algorithm := range []lightphe.Algorithm{
lightphe.BonehGohNissim,
lightphe.FreemanBonehGohNissim,
lightphe.BrakerskiVaikuntanathan,
lightphe.GentryHaleviVaikuntanathan,
} {
// retailer builds the cryptosystem, encrypts both columns and uploads them to the cloud
cs, err := lightphe.New(algorithm)
check(err)
encrypt := func(values []int64) []*lightphe.Ciphertext {
var out []*lightphe.Ciphertext
for _, value := range values {
c, err := cs.EncryptInt(value)
check(err)
out = append(out, c)
}
return out
}
encryptedQuantities, encryptedCosts := encrypt(quantities), encrypt(unitCosts)
// cloud computes the inventory value, a dot product of two encrypted vectors
var encryptedValue *lightphe.Ciphertext
for i := range encryptedQuantities {
product, err := encryptedQuantities[i].Multiply(encryptedCosts[i])
check(err)
if encryptedValue == nil {
encryptedValue = product
} else {
encryptedValue, err = encryptedValue.Add(product)
check(err)
}
}
// retailer decrypts it
value, err := cs.Decrypt(encryptedValue)
check(err)
fmt.Printf("%s: %s\n", algorithm, value)
}
// expected: 6112 for the first three, 6112 mod 101 = 52 for gentry-halevi-vaikuntanathan
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import java.util.List;
// retailer's stock quantities and unit costs - both confidential
List<Long> quantities = List.of(12L, 75L, 40L, 26L, 18L);
List<Long> unitCosts = List.of(12L, 30L, 45L, 8L, 95L);
for (String algorithm : List.of(
"Boneh-Goh-Nissim",
"Freeman-Boneh-Goh-Nissim",
"Brakerski-Vaikuntanathan",
"Gentry-Halevi-Vaikuntanathan")) {
// retailer builds the cryptosystem, encrypts both columns and uploads them to the cloud
LightPHE cs = LightPHE.builder().algorithmName(algorithm).build();
List<Ciphertext> encryptedQuantities = quantities.stream().map(cs::encrypt).toList();
List<Ciphertext> encryptedCosts = unitCosts.stream().map(cs::encrypt).toList();
// cloud computes the inventory value, a dot product of two encrypted vectors
Ciphertext encryptedValue = encryptedQuantities.get(0).multiply(encryptedCosts.get(0));
for (int i = 1; i < quantities.size(); i++) {
encryptedValue = encryptedValue.add(encryptedQuantities.get(i).multiply(encryptedCosts.get(i)));
}
// retailer decrypts it
System.out.println(algorithm + ": " + cs.decrypt(encryptedValue));
}
// expected: 6112 for the first three, 6112 mod 101 = 52 for gentry-halevi-vaikuntanathan
import { LightPHE } from 'lightphe-ts';
// retailer's stock quantities and unit costs - both confidential
const quantities = [12, 75, 40, 26, 18];
const unitCosts = [12, 30, 45, 8, 95];
for (const algorithm of [
'Boneh-Goh-Nissim',
'Freeman-Boneh-Goh-Nissim',
'Brakerski-Vaikuntanathan',
'Gentry-Halevi-Vaikuntanathan',
]) {
// retailer builds the cryptosystem, encrypts both columns and uploads them to the cloud
const cs = new LightPHE({ algorithmName: algorithm });
const encryptedQuantities = quantities.map((q) => cs.encrypt(q));
const encryptedCosts = unitCosts.map((c) => cs.encrypt(c));
// cloud computes the inventory value, a dot product of two encrypted vectors
const encryptedValue = encryptedQuantities
.map((q, i) => q.multiply(encryptedCosts[i]))
.reduce((sum, product) => sum.add(product));
// retailer decrypts it
console.log(`${algorithm}: ${cs.decrypt(encryptedValue)}`);
}
// expected: 6112 for the first three, 6112 mod 101 = 52 for gentry-halevi-vaikuntanathan
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!
