實施 BFV 再線性化

我目前正在研究BFV的 Python 實現$$ 12 $$密碼系統。

我達到了密鑰生成、加密、添加和解密按預期工作的地步。然而，我正在努力解決的是乘法和重新線性化。特別是重新線性化“版本 1”。

我確實明白，鑑於密文的乘法，我們最終會得到一個新的密文，該密文在以下情況下無法解密 $ s $ 鑑於乘法結果只能通過以下方式解密 $ s^2 $ . 因此，想法是創建重新線性化鍵 $ rlk_i $ 其中包含鹼基 $ T $ 分解（在我的案例庫中 $ 2 $ ） 的 $ s^2 $ . 然後可以通過基礎上的“內積”使用這些密鑰 $ T $ 對給定密文進行分解，以將此類密文恢復為線性形式，然後可以通過以下方式解密 $ s $ .

在論文之後（尤其是第 10 頁），我將下面附加的程式碼放在一起。

鑑於我們正在處理多項式，我將 $ n $ 係數轉換成它們的二進製表示。這導致 $ n $ 二元分解，每個長度 $ log_2(q) $ （在哪裡 $ q $ 是密文模數）。

我基本上遵循這個答案

不幸的是，我無法恢復正確的結果（ $ 6 $ ) 解密重新線性化的密文時。我得到的是一個具有隨機係數的多項式。

鑑於加密、添加和解密工作沒有任何問題，我不確定我在哪裡犯了錯誤。任何人都可以更深入地了解多項式係數的位分解（最好使用係數 $ > 9 $ ) 以及它們與重新線性化鍵相乘的方式。

這是程式碼的關鍵部分。我還使用程式碼庫創建了一個Repl.it，因此您可以檢查整個實現：

# `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]))
       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

經過一番掙扎，我終於能夠解決這個問題。

在進行更多研究時，我偶然發現了這篇論文，它在第 3 頁提供了分解函式的正確公式（請注意，該論文是由 Frederik Vercauteren 合著的）。

我將公式翻譯成以下 Python 函式：

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)

可以通過以下測試進行驗證：

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)

如果您正在尋找FV12的 Python 實現，可以在 GitHub 上找到我的程式碼。

我希望這可以揭開基本分解算法的神秘面紗，並幫助遇到與我相同問題的其他人。

引用自：https://crypto.stackexchange.com/questions/80962