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, ...]`
def gen_gadget(size):
    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]))
    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)

return result

2 Answers 2


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]),
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?
  • $\begingroup$ Thank you very much for the hints! I was able to fix the multiplication which was indeed incorrect. $\endgroup$
    – pmuens
    Jun 4, 2020 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.