I'm currently working on a Python implementation of the BFV 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, ct_1) * t / q) % q) c_1 = np.poly1d(np.round(add(mul(ct_0, ct_1), mul(ct_0, ct_1)) * t / q) % q) c_2 = np.poly1d(np.round(mul(ct_0, ct_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() for i, bit in enumerate(bit_coeff): coeff = add(coeff, mul(bit, multiplicands[i])) result.append(coeff) 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] for i in range(l)] # The `rlk_0` from above multiplicands_c_1_p = [rlk[i] 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