# Implementing BFV Relinearization

I'm currently working on a Python implementation of the BFV[12] cryptosystem.

I got to a point where key generation, encryption, addition and decryption works as expected. Where I'm struggling with however is multiplication and relinearization. In particular relinearization "Version 1".

I do understand that given the multiplication of Ciphertexts we eventually end up with a new ciphertext which isn't decrypt-able under $$s$$ given that the multiplication results in something which is only decrypt-able via $$s^2$$. Therefore the idea is to create relinearization keys $$rlk_i$$ which contain base $$T$$ decompositions (in my case base $$2$$) of $$s^2$$. These keys can then be used via the "dot product" on a base $$T$$ decomposition of the given ciphertext to bring such ciphertext back into a linear form which is then decrypt-able via $$s$$.

Following the paper (especially page 10) I put together the code attached below.

Given that we're dealing with polynomials I decompose the $$n$$ coefficients into their binary representation. This results in $$n$$ binary decompositions, each of length $$log_2(q)$$ (where $$q$$ is the ciphertext modulus).

I'm basically following this answer

Unfortunately I'm not able to recover the correct result ($$6$$) when decrypting the relinearized ciphertext. What I get back is a polynomial with randomly looking coefficients.

I'm not sure where I made a mistake given that encryption, addition and decryption works without any issues. Can anyone maybe shed more light into the bit decompositions of polynomial coefficients (preferably with coefficients $$> 9$$) and the way they're then multiplied with the relinearization keys.

Here are the critical parts of the code. I've also created a Repl.it with the codebase so you can examine the whole implementation:

# add and mul are wrappers for polynomial addition and multiplication which auto-apply the coefficient and polynomial modulus

# ... snip ...

# Relinearization key generation (part of the key generation procedure)

rlk = []
for i in range(l):
a_i = draw_from_modulus(d, q)
e_i = draw_from_normal(d, q)
rlk_0 = add(add(-mul(a_i, sk), e_i), mul(T ** i, mul(sk, sk)))
rlk_1 = a_i
rlk.append((rlk_0, rlk_1))

# ... snip ...

# Relinearization Version 1
t = ctx.t
q = ctx.q

# Encrypting the values 3 and 2
ct_0 = encrypt(ctx, pk, 3)
ct_1 = encrypt(ctx, pk, 2)

# T is the base we're using for decomposition. In our case it's base 2 (binary)
T = 2
l = floor(log(q, T))

# The individual parts of the multiplication
c_0 = np.poly1d(np.round(mul(ct_0[0], ct_1[0]) * t / q) % q)
c_1 = np.poly1d(np.round(add(mul(ct_0[0], ct_1[1]), mul(ct_0[1], ct_1[0])) * t / q) % q)
c_2 = np.poly1d(np.round(mul(ct_0[1], ct_1[1]) * t / q) % q)

# Returns a vector of powers of 2 with length size
# NOTE: We're using it solely in the test at the end of this function to show that we can reconstruct our polynomial
# [1, 2, 4, 8, 16, 32, ...]
return [2 ** i for i in range(size)]

# Decomposes the coefficients of a polynomial into binary representation
# Outputs an array containing arrays of the binary representation for each polynomial
def bit_decompose(poly, width):
return np.array([[(int(coeff) >> i & 1) for i in range(width)] for coeff in poly])

# Reconstructs the polynomial based on the given bit decomposition of its coefficients
# multiplicands is an array of values we want to multiply each coefficients bit representation with
def bit_decompose_inv(bit_coeffs, multiplicands):
result = []
for bit_coeff in bit_coeffs:
coeff = np.poly1d([0])
for i, bit in enumerate(bit_coeff):
coeff = add(coeff, mul(bit, multiplicands[i]))
result.append(coeff[0])
return np.poly1d(result)

# Here we're decomposing the coefficients of c_2 into its bits (each bit array has length l)
u = bit_decompose(c_2, l)

# Generating a list of relinearization keys we'll be using as multiplicands when "reconstructing"
# The polynomial for our new, linearized ciphertext
multiplicands_c_0_p = [rlk[i][0] for i in range(l)] # The rlk_0 from above
multiplicands_c_1_p = [rlk[i][1] for i in range(l)] # The rlk_1 from above

# c_0 prime and c_1 prime
c_0_p = add(c_0, bit_decompose_inv(u, multiplicands_c_0_p))
c_1_p = add(c_1, bit_decompose_inv(u, multiplicands_c_1_p))

# Consolidating the result of our relinearization into a new tuple which represents bot parts of our
# "new" ciphertext
res = (c_0_p, c_1_p)

# --- Test ---
# This test validates that we can decompose and reconstruct polynomials
# via our "gadget" which is just a vector of powers of 2
assert_array_equal(c_2, bit_decompose_inv(bit_decompose(c_2, l), gen_gadget(l)))

result = decrypt(ctx, sk, res)
print(result)
print()

return result


After quite some struggle I was finally able to solve this problem.

While doing some more research I stumbled upon this paper which gives a glimpse at the correct formula for the decomposition function on page 3 (Note that the paper was co-authored by Frederik Vercauteren).

I translated the formula into the following Python function:

def base_decomp(polynomial, T, coeff_modulus):
l = floor(log(coeff_modulus, T))
result = []
for i in range(l + 1):
result.append(np.poly1d(np.floor(polynomial / T ** i).astype(int) % T))
return np.array(result)


which can be validated via the following tests:

c_q = 2 ** 4  # Coefficient modulus
T = 2  # Decomposition base
l = floor(log(c_q, T))
x = np.poly1d([1, 2, 3, 4])
x_decomposed = base_decomp(x, T, c_q)
x_reconstructed = np.poly1d(sum(x_decomposed[i] * (T ** i) for i in range(l + 1)))
assert x_decomposed.shape == (l + 1,)
assert_array_equal(x_decomposed, np.array([
np.poly1d([1, 0, 1, 0]),
np.poly1d([1, 1, 0]),
np.poly1d([1]),
np.poly1d([0]),
np.poly1d([0]),
]))
assert_array_equal(x_reconstructed, x)


You can find my code on GitHub if you're looking for a Python implementation of FV12.

I hope that this demystified the base decomposition algorithm and helps others who run into the same questions I had.

I am also working on the same system (and having a similar problem). From my experience, I advise you to check followings:

1. Does your parameter set allow you to recover result of a homomorphic multiplication? As you know, if noise growth in multiplication operation is not low enough, your decryption operation may fail (so you got a polynomial with randomly looking coefficients as in your case).

2. Did you try decrypting the result of homomorphic multiplication without applying relinearization? You can do it as follow:

$$D(c_2,c_1,c_0) = [round((t/q).[s^2 . c_2 + s . c_1 + c_0]_q)]_t$$

If you can recover your plaintext using this operation, you can now be sure that the problem is really with relinearization step. Otherwise, the following question arises:

1. Does your homomorphic multiplication function really work? I believe that the problem might be here. How did you implement your homomorphic multiplication function?
• Thank you very much for the hints! I was able to fix the multiplication which was indeed incorrect. – pmuens Jun 4 at 12:53