Encryption schemes have evolved tremendously over the past decades, and homomorphic encryption (HE) is one of the most fascinating areas. While most people are familiar with partially homomorphic encryption (PHE) schemes like RSA or Paillier that support either addition or multiplication, the Boneh-Goh-Nissim (BGN) cryptosystem, introduced in 2005, by Dan Boneh and Eu-Jin Goh from Stanford, and Kobbi Nissim from BGU, offers a unique feature: It supports unlimited additions and exactly one multiplication. This places BGN in the category of somewhat homomorphic encryption (SHE)—more powerful than classic PHE, but not fully homomorphic like Gentry’s FHE (discovered shortly after in 2009). In this post, we’ll break down the BGN cryptosystem, explain its key components, and demonstrate Python snippets for key generation, encryption, decryption, and its homomorphic operations.
Vlog
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curve Roots, RSA-style Security
One of the interesting aspects of the Boneh-Goh-Nissim (BGN) cryptosystem is its use of elliptic curves—but not in the way standard elliptic curve cryptography (ECC) does. BGN relies on groups derived from elliptic curves, but the security comes from a composite-order structure, similar to RSA.
- In standard ECC, order of the elliptic curve should be prime, whereas here it shouldn’t.
- In standard ECC, the security comes from the discrete logarithm problem on a prime-order curve, which allows small key sizes (e.g., 256-bit keys are strong).
- In BGN, the curve’s order is a product of two large primes, n = p x q, just like RSA. This means the scheme requires large keys for security, despite using elliptic curves.
So, while BGN uses the language and algebra of elliptic curves, the key sizes behave more like RSA than typical ECC: you need large numbers to maintain security, not the compact sizes ECC allows. This is a subtle but important distinction for anyone considering BGN in practice.
Homomorphic Encryption And Cloud
Homomorphic encryption enables computations on encrypted data without needing the private key. With the widespread adoption of cloud systems, homomorphic encryption has become increasingly popular. This technology allows us to store data in the cloud and leverage its processing power while keeping the private key secure. As a result, system design becomes both more cost-effective and secure. Watch this video to see how homomorphic encryption operates on both on-premises and cloud platforms.
Boneh-Goh-Nissim in Python
In this post, we will mostly focus on the math behind the cryptosystem and implement it from scratch. If you are interested in how to use the algorithm easy and fast instead of its mathematical foundation, then you may consider to use LightPHE.
LightPHE is a lightweight partially homomorphic encryption library for python. It wraps many partially homomorphic algorithms such as RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, Okamoto–Uchiyama, Benaloh, Naccache–Stern, Goldwasser–Micali, Sander-Young-Yung. With LightPHE, you can build homomorphic crypto systems with a couple of lines of code, encrypt decrypt your data and perform homomorphic operations such as homomorphic addition, homomorphic multiplication, homomorphic xor, regenerate cipher texts, multiplying your cipher text with a known plain constant according to the built algorithm.
# !pip install lightphe>=0.0.22
from lightphe import LightPHE
import pytest
# Initialize BGN with 1024-bit keys
cs = LightPHE(algorithm_name="Boneh-Goh-Nissim")
# Define plaintexts
m1 = 83
m2 = 31
# Encrypt messages
c1 = cs.encrypt(plaintext=m1)
c2 = cs.encrypt(plaintext=m2)
# Decrypt to verify
assert cs.decrypt(c1) == m1
assert cs.decrypt(c2) == m2
# Homomorphic addition
assert cs.decrypt(c1 + c2) == (m1 + m2)
# Homomorphic multiplication (only once!)
c1_times_c2 = c1 * c2
assert cs.decrypt(c1_times_c2) == (m1 * m2)
# Multiplying twice triggers an error
with pytest.raises(
ValueError,
match="Boneh-Goh-Nissim only supports multiplication ciphertexts once!",
):
c1_times_c2_sq = c1_times_c2 * c2
# Scalar multiplication
k = 2
assert cs.decrypt(c1 * k) == (m1 * k)
# Re-randomization
c1_prime = cs.cs.reencrypt(c1.value)
c2_prime = cs.cs.reencrypt(c2.value)
assert c1.value != c1_prime and c2.value != c2_prime
assert cs.cs.decrypt(c1_prime) == m1
assert cs.cs.decrypt(c2_prime) == m2
You may consider to watch the LightPHE demo video.
Key Generation
BGN key generation may look intimidating at first glance, but it can be understood as a sequence of well-structured steps. Let’s break it down.
We start by selecting two large, distinct prime numbers: q1 and q2
q1 = sympy.randprime(2**512, 2**513) q2 = sympy.randprime(2**512, 2**513)
These primes play a role very similar to RSA. We compute:
n = q1 * q2
This value n will define the composite order of the elliptic curve group we are about to construct. Because of its products are 512-bits, then it will have 1024-bit-ish key size.
Next, we search for a prime p such that:
p = n * l - 1
with the constraint: p = 3 (mod 4)
This condition ensures the elliptic curve y2 = x3 + x is supersingular. Supersingular curves are required for bilinear pairings, which enable BGN’s homomorphic multiplication feature.
Instead of randomly guessing l, we iterate over multiples of 4 to satisfy the modular condition efficiently.
Once p is found, we define the curve as
y2 = x3 + x (mod p)
Then we construct the curve and try to find a valid generator point G
from sympy.ntheory.residue_ntheory import sqrt_mod
for _ in range(max_tries):
x = random.randint(0, p - 1)
rhs = (pow(x, 3, p) + x) % p
y_list = sqrt_mod(rhs, p, all_roots=True) # get all square roots
if y_list: # if there is at least one solution
G = (x, y_list[0])
break
We can construct this curve using LightECC to perform elliptic curve arithmetic operations:
from lightecc import LightECC
# y^2 = x^3 + a*x + b (mod p)
ec = LightECC(
form_name="weierstrass",
curve_name="custom",
config={"a": 1, "b": 0, "p": p, "G": G, "n": None},
)
We set the n argument to None because it refers to the order of the elliptic curve — in other words, the number of points on the curve. It is expected to be the product of the primes q1 and q2, but we deliberately avoid setting it at this stage until we verify it.
nG = n * ec.G
if nG == ec.O:
logger.debug("nG is the point at infinity, as expected.")
else:
raise ValueError(f"nG = {n} x {ec.G} must be the infinity point but it is not. Try with different arguments.")
Once we confirm that the product of q1 and q2 is indeed the order of the elliptic curve, we can reconstruct the curve as follows:
ec = LightECC(
form_name="weierstrass",
curve_name="custom",
config={"a": 1, "b": 0, "p": p, "G": G, "n": n},
)
This ensures that the subgroup generated by G has order divisible by n. In other words, we successfully embedded our RSA-like structure into the elliptic curve group. If this condition fails, we retry everything from scratch.
Next, we pick a random value r such that:
while True:
r = random.randint(2, n - 1)
if math.gcd(r, n) == 1:
break
We’ll compute then
u = r * G h = u * q2
Here, u and h are points on our elliptic curve, too.
Once these computations done, q1 and q2 pair will be our private key, whereas base point G, elliptic curve points u and h, and random number l will be our public keys.
Encrypt
Encryption in BGN combines the plaintext with randomness and maps the result onto an elliptic curve point.
At a high level, a message m is encrypted as:
c = m * G + r * h
where G and h are elliptic curve points, and ciphertext will be an elliptic curve point as well.
BGN requires a new random value for every encryption:
def generate_random_key(self) -> int:
return random.randint(1, q2 - 1)
This randomness is critical for semantic security—encrypting the same message twice should produce completely different ciphertexts.
def encrypt(plaintext: int) -> EllipticCurvePoint:
r = generate_random_key()
G = ec.G
c = (G * plaintext) + (h * r)
return c
plaintext * G encodes the message onto a point the curve, whereas r * h adds randomness (noise).
Because h is derived from the secret structure of the group, this noise hides the plaintext but can still be removed during decryption using the private key.
Decrypt
Decryption in BGN works by removing the randomness added during encryption and then recovering the plaintext via a discrete logarithm.
Recall that encryption produces:
c = m * G + r * h
To decrypt, we multiply the ciphertext by the private key q1
def decrypt(self, ciphertext: EllipticCurvePoint) -> int:
G = ec.G
mP = ciphertext * q1
P = G * q1
# need to extract m from given P and mP
Since BGN operates over a small message space, we can recover m by brute force:
for i in range(1, q1 + 1):
iP = P * i
if iP == mP:
return i
raise Exception("Decryption failed")
In general, solving discrete logarithms is hard. But in BGN:
- The message space is intentionally small
- We are not solving DLP over the full group
- Only within a restricted range
This makes brute-force search practical and efficient.
You can think of decryption as:
- Wiping out the noise using q1
- Reducing the ciphertext to a clean multiple of a base point
- Finding how many times that base point was added
This design is what makes BGN elegant. Encryption hides the message in a structured way, and decryption carefully peels that structure back—just enough to recover the plaintext.
Homomorphic Features
What makes BGN truly interesting is its ability to perform computations directly on encrypted data. Without decrypting anything, we can manipulate ciphertexts and still obtain meaningful results after decryption.
Let’s go through the supported operations.
Homomorphic Addition
Addition in BGN is almost surprisingly simple.
def add(ciphertext1: EllipticCurvePoint, ciphertext2: EllipticCurvePoint) -> EllipticCurvePoint:
return ciphertext1 + ciphertext2
Recall that a ciphertext is:
c = m * G + r * h
If we add two ciphertexts:
c1 + c2 = (m1 * G + r1 * h) + (m2 * G + r2 * h)
c1 + c2 = (m1 + m2) * G + (r1 + r2) * h
After decryption, this yields:
m1 + m2
You can repeat this operation as many times as you want—BGN supports unlimited additions.
Scalar Multiplication
We can also multiply a ciphertext by a constant:
def multiply_by_constant(ciphertext: EllipticCurvePoint, constant: int) -> EllipticCurvePoint:
return ciphertext * constant
Mathematically:
k * c = k * (m * G + r * h) = (km)* G + (kr) * h
After decryption:
m’ = k * m
This is especially useful when evaluating linear functions over encrypted data.
Re-randomization
BGN allows refreshing a ciphertext without changing its underlying plaintext:
def reencrypt(ciphertext: EllipticCurvePoint) -> EllipticCurvePoint:
r_prime = self.generate_random_key()
c_prime = ciphertext + (r_prime * h)
return c_prime
This works because:
c’ = c + r’ * h = m*G + (r + r’) * h
The plaintext stays the same, but the randomness changes. This is important for security and unlinkability—the same message can have many different ciphertext representations.
High-Level Overview of Elliptic Curve Pairing
We will use elliptic curve pairing in BGN’s homomorphic multiplication feature. Let me try to explain it in high level. Think of an elliptic curve as a playground where you can add points together, but multiplying them directly doesn’t make sense. That’s where a pairing comes in.
A pairing is like a magic bridge: it takes two points from the curve and moves them into a different space where multiplication suddenly becomes possible. In that new space, multiplying the points corresponds exactly to multiplying the underlying secret numbers (the plaintexts) that those points represent.
In the Boneh-Goh-Nissim system, addition and scaling happen naturally on the curve. Multiplication cannot happen on the curve, so the pairing moves the ciphertexts to a special target group. You can do exactly one multiplication, because after moving through the bridge, the result no longer lives on the curve.
In simple terms, the pairing is a temporary switch: it transforms the points so you can multiply them safely, and then you can decrypt the result back into a regular number. It’s what allows BGN to do something that normal elliptic curve math can’t do on its own.
Homomorphic Multiplication
Unlike addition c1 + c2, multiplication uses the pairing map:
e: G x G -&> G_T
where G is original elliptic curve group, G_T is target group of the pairing.
After one multiplication, the ciphertext leaves the curve and enters G_T. Because of this, the resulting ciphertext is no longer a point on the elliptic curve. So, you cannot multiply it again. This is exactly why BGN supports only one multiplication per ciphertext.
Luckily, LightECC handles pairing easily as
def multiply(ciphertext1: EllipticCurvePoint, ciphertext2: EllipticCurvePoint) -> Tuple[int, int]:
return ec.pairing(ciphertext1, ciphertext2)
Notice that, we haven’t multiplied the ciphertexts directly, instead we used elliptic curve’s pairing function.
How Homomorphic Multiplication Works
Mathematically:
c1 = m1 * G + r1 * h
c2 = m2 * G + r2 * h
The pairing gives:
e(c1, c2) = e(G, G)m1*m2 * noise
The multiplicative structure of G_T encodes m1 * m2. After decryption, we recover the product of the plaintexts.
Practical Notes:
- The pairing requires a supersingular curve with embedding degree 2
- The result lives in Fp2, usually represented as a tuple (a, b) corresponding to a + bi where i² = -1 mod p
You can think of addition as vector addition on the curve, while multiplication is like casting the vectors into a special field where exactly one product can be safely computed.
Decrypting a Multiplication Result
After performing a homomorphic multiplication, the ciphertext is no longer a point on the elliptic curve, but an element in the target group G_T (here, Fp2). Decryption is slightly different from standard curve-based decryption.
Let c = e(c1, c2) be the pairing result of two ciphertexts. Using the private key q1:
cq1 = e(cq, c2)q1 = (e(G, G)q1*m1*m2 x noise ) q1
The noise term vanishes (just like in normal decryption), leaving:
cq1 = e(G, G)q1*m1*m2
We now need to solve a discrete logarithm problem in G_T to recover
m = m1 * m2
So, its implementation will be very straightforward.
from lightecc.commons.pairing import _fp2_pow, _fp2_mul
def _decrypt_gt(ciphertext: tuple, q1: int) -> int:
p = ec.modulo
G = ec.G
# pairing of generator with itself
e_gg = self.ec.pairing(G, G)
# base = e(G, G)^q1, target = ciphertext^q1
base = _fp2_pow(e_gg, q1, p)
target = _fp2_pow(ciphertext, q1, p)
# brute-force DLP in G_T
acc = (1, 0)
for i in range(1, q1 + 1):
acc = _fp2_mul(acc, base, p)
if acc == target:
return i
raise Exception("Decryption of G_T ciphertext failed")
How It Works?
- base = e(G, G)^q1 -&> acts like the “unit step” in the target group
- target = ciphertext^q1 -&> the encrypted product raised by the private key
- Brute-force search in the small message space yields m1 * m2
Even though solving discrete logarithms is generally hard, in BGN:
- We only need to search over a small message space
- This makes brute-force feasible and efficient
Think of it as a two-step process:
- Remove the noise (private key exponentiation)
- Count multiples in the target group until you reach the observed value
In other words, BGN cleverly moves multiplication into a field where decryption remains practical—even after leaving the elliptic curve.
Do You Really Need FHE?
If your use case does not require arbitrary-depth multiplications, BGN can be a very practical alternative to fully homomorphic encryption.
Fully Homomorphic Encryption (FHE) is incredibly powerful—but that power comes at a cost:
- Very large key sizes
- High computational overhead
- Complex implementations
In contrast, BGN offers a much simpler and more efficient model:
- Unlimited additions
- Exactly one multiplication
- More approachable performance characteristics
If a single multiplication is enough for your computation, BGN might be all you need—without the heavy machinery of FHE.
Homomorphic Linear Regression
One of the most practical applications of the Boneh–Goh–Nissim (BGN) cryptosystem is the ability to compute linear models over encrypted data. In particular, BGN naturally supports the core operation behind linear regression: the dot product.
At its core, a linear model computes:
y = Σ xi wi
With BGN, we can evaluate this expression without ever decrypting the inputs.
In the following example, we compute a simple linear combination using encrypted inputs and weights.
cs = LightPHE(
algorithm_name="Boneh-Goh-Nissim",
key_size=50,
max_tries=10000,
)
# Feature values
x1 = 5
x2 = 3
# Model weights
w1 = 7
w2 = 4
# Encrypt values
x1_enc = cs.encrypt(plaintext=x1)
w1_enc = cs.encrypt(plaintext=w1)
x2_enc = cs.encrypt(plaintext=x2)
w2_enc = cs.encrypt(plaintext=w2)
# Homomorphic multiplications (feature × weight)
x1w1_enc = x1_enc * w1_enc
x2w2_enc = x2_enc * w2_enc
# Homomorphic addition (sum of contributions)
sum_enc = x1w1_enc + x2w2_enc
# Decrypt final result
sum_decrypted = cs.decrypt(sum_enc)
assert sum_decrypted == (x1 * w1 + x2 * w2)
This example directly matches the capabilities of BGN. Each ciphertext × ciphertext multiplication is allowed exactly once per ciphertext.
In BGN, the “one-time multiplication” limitation refers to operations in the source elliptic curve group G. Once a multiplication is performed using the pairing operation, the result is mapped into the target group GT. However, this does not mean that multiplication is no longer possible altogether. In fact, elements in GT can still be multiplied with each other using the group operation of GT without restriction. So, while BGN allows only one “level” of cryptographic multiplication before transitioning groups, the target group itself still supports standard algebraic multiplication operations internally.
So the computation effectively becomes:
(x1 w1) + (x2 w2)
All of this happens while the data remains encrypted.
BGN also supports multiplication of a ciphertext by a known constant, which is useful for scaling contributions in linear models:
scaled_value = cs.decrypt(x1w1_enc * 5) assert scaled_value == (5 * x1 * w1)
This enables simple transformations such as feature weighting or coefficient scaling directly in the encrypted domain.
While BGN is not suitable for deep machine learning pipelines, it is extremely effective for shallow encrypted computations, especially:
- Dot product evaluation
- Linear scoring functions
- Simple regression inference
This makes it a strong candidate for privacy-preserving inference, where sensitive data must remain encrypted even during computation.
Dot Product and Cosine Similarity on Encrypted Data
One of the most powerful extensions of BGN is its ability to compute dot products over encrypted vectors. This is particularly important because many machine learning and similarity-based tasks rely on dot products as a core building block.
Recall that the dot product between two L2 normalized vectors is defined as:
v1 v2= Σ xi wi
With BGN, we can compute this directly in the encrypted domain.
In the following example, both vectors are encrypted element-wise:
cs = LightPHE(algorithm_name="Boneh-Goh-Nissim", key_size=30) # v1 = [5, 2, 8] i1, i2, i3 = 5, 2, 8 # v2 = [1, 1, 2] j1, j2, j3 = 1, 1, 2 # Encrypt first vector i1_enc = cs.encrypt(i1) i2_enc = cs.encrypt(i2) i3_enc = cs.encrypt(i3) # Encrypt second vector j1_enc = cs.encrypt(j1) j2_enc = cs.encrypt(j2) j3_enc = cs.encrypt(j3) # Homomorphic dot product cosine_sim_enc = i1_enc * j1_enc + i2_enc * j2_enc + i3_enc * j3_enc assert cs.decrypt(cosine_sim_enc) == i1 * j1 + i2 * j2 + i3 * j3
Each term i_k_enc * j_k_enc uses BGN’s one-time multiplication, and the results are combined via homomorphic addition, which is unlimited.
This is extremely important because cosine similarity is widely used in:
- Face recognition
- Embedding similarity (e.g., NLP, vision models)
- Recommendation systems
With additively homomorphic encryption (PHE) (e.g., Paillier): you can compute dot product only if one vector is plaintext. Because multiplication between ciphertexts is not supported
Euclidean Distance on Encrypted Data
Another important similarity metric is the Euclidean distance, which measures how far apart two vectors are in space.
It is defined as:
d(v1, v2) = √(xi – yi)2
In practice, we often compute the squared Euclidean distance to avoid the costly square root:
d(v1, v2)2 = (xi – yi)2
BGN allows us to compute this entirely over encrypted data. The key idea is:
- Subtraction → convert to addition using negative values
- Squaring → one ciphertext-ciphertext multiplication per dimension
- Summation → homomorphic addition (unlimited)
cs = LightPHE(algorithm_name="Boneh-Goh-Nissim", key_size=30)
# v1 = [5, 2, 8]
i1, i2, i3 = 5, 2, 8
# v2 = [1, 1, 2]
j1, j2, j3 = 1, 1, 2
# Encrypt v1
i1_enc = cs.encrypt(i1)
i2_enc = cs.encrypt(i2)
i3_enc = cs.encrypt(i3)
# Encrypt negative v2 (to simulate subtraction)
j1_enc = cs.encrypt(-j1)
j2_enc = cs.encrypt(-j2)
j3_enc = cs.encrypt(-j3)
# Compute squared Euclidean distance
euclidean_sqrt_enc = (
(i1_enc + j1_enc) * (i1_enc + j1_enc)
+ (i2_enc + j2_enc) * (i2_enc + j2_enc)
+ (i3_enc + j3_enc) * (i3_enc + j3_enc)
)
assert (
cs.decrypt(euclidean_sqrt_enc)
== (i1 - j1) ** 2 + (i2 - j2) ** 2 + (i3 - j3) ** 2
)
This enables fully encrypted versions of:
- Nearest neighbor search
- Face recognition (distance-based matching)
- Clustering (e.g., k-means distance step)
- Similarity scoring in embedding spaces
In Summary
The Boneh-Goh-Nissim cryptosystem occupies a unique and often overlooked position in the landscape of homomorphic encryption. It strikes a careful balance between capability and complexity, offering more expressive power than partially homomorphic schemes while avoiding the heavy computational cost of fully homomorphic encryption.
By combining elliptic curve structures with an RSA-like composite order, BGN demonstrates how subtle algebraic design choices can unlock new functionality—most notably, the ability to perform unlimited additions alongside a single multiplication. This seemingly small extension turns out to be powerful enough for a surprising range of practical use cases.
Although it does not aim to replace fully homomorphic encryption, BGN serves as a compelling alternative when the depth of computation is limited. In such scenarios, it provides a much more approachable and efficient solution, both conceptually and computationally.
Ultimately, BGN is not just a historical stepping stone on the path to FHE, but a reminder that sometimes, carefully constrained capabilities can lead to elegant and highly practical cryptographic designs.
Support this blog financially if you do like!
