BGV全同态加密

方案描述

• KeyGen(\(\lambda\))：根据预设的加密方案的安全性，选择一个安全参数\(\lambda\)，安全参数的选择将影响密文模数\(q\)和密文多项式的最高次数\(N\)。在本文中，选择的参数满足128比特安全性。随机采样\(s \leftarrow \mathcal{R}_2\)，\(a \leftarrow \mathcal{U}_{q_L}\)和\(e \leftarrow \mathcal{X}\)。之后，计算私钥\(sk = s\)和公钥\(pk = (pk_1,pk_2) = ([-a \cdot s+te]_{q_L} , a)\)。

• KeySwitchGen(\(sk\))：模交换能够让同态乘法的次数增加，而模交换需要依赖模交换密钥，首先随机采样多项式\(a \leftarrow \mathcal{U}_{q_L}\)和\(e \leftarrow \mathcal{X}\)。然后输出\(ks = (ks_1, ks_2) \equiv ([-a \cdot s + te + sk \cdot sk]_{q_L} , a)\)作为模交换密钥。

• Enc(\(m,pk\))：给定输入消息\(m \in \mathcal{P}\)，首先选择三个随机多项式：\(u \leftarrow \mathcal{R}_2\)，\(e_1 \leftarrow \mathcal{X}\)和\(e_2 \leftarrow \mathcal{X}\)。然后加密器通过计算生成密文\(c\)：\(c=(c_1,c_2)\equiv([pk_1 \cdot u+te_1+m]_{q_L},[pk_2 \cdot u+te_2]_{q_L}) \in \mathcal{C}\)。

• Dec(\(c,sk\))：解密一个密文\(c\)，需要在对应的模数链层次\(l\)执行以下步骤：\(\mathrm{i)}\) 计算\(m' = [c_1 + c_2 \cdot sk]_{q_l}\)，以及\(\mathrm{ii)}\) 输出解密后的明文\(m = m' \pmod{t}\)。

计算模拟

给出模拟代码

def poly_mod_add(poly1, poly2, mod):
    """多项式模环加法"""
    # 确保 poly1 是较长的那个多项式
    if len(poly2) > len(poly1):
        poly1, poly2 = poly2, poly1
    # 将较短的多项式补零
    poly2 += [0] * (len(poly1) - len(poly2))
    # 对应系数相加并取模
    result = [(a + b) % mod for a, b in zip(poly1, poly2)]
    return result

def poly_mod_mult(poly1, poly2, mod, N):
    """多项式模环乘法"""
    # 初始化结果多项式
    result = [0] * (len(poly1) + len(poly2) - 1)
    # 对每个系数进行乘法和加法
    for i, a in enumerate(poly1):
        for j, b in enumerate(poly2):
            result[i + j] += a * b
            result[i + j] %= mod
    for i in range(N):
        try:
            result[i] = (result[i] - result[i+N]) % mod
        except:
            break
    return result[0:N]

def poly_mult_number(poly, num,mod):
    for i in range(len(poly)):
        poly[i] = (poly[i] * num) %mod
    return poly


def Gen_pk(a,s,t,e,mod,N):
    pk1 = poly_mod_mult(a,s,mod,N)
    pk1 = poly_mult_number(pk1,-1,mod)
    pk1 = poly_mod_add(pk1,poly_mult_number(e,t,mod),mod)
    pk2 = a
    return [pk1,pk2]

def Enc(pk,m,u,mod,N):
    pk1 = pk[0]
    pk2 = pk[1]
    c1 = poly_mod_mult(pk1,u,mod,N)
    c1 = poly_mod_add(c1,m,mod)
    c1 = poly_mod_add(c1,poly_mult_number(e1,t,mod),mod)

    c2 = poly_mod_mult(pk2,u,mod,N)
    c2 = poly_mod_add(c2,poly_mult_number(e2,t,mod),mod)
    return [c1,c2]

def dec(c,sk,mod,N,t):
    temp = poly_mod_mult(c[1],sk,mod,N)
    temp = poly_mod_add(c[0],temp,mod)
    for i in range(len(temp)):
        temp[i] = temp[i] % t
    return temp
# 示例使用
m = [-1,2]  # 表示 2+x
a = [1, 1]     # 表示 1+x
s = [1]
e = [2,3]
t = 5
u = [0,1]
e1 = [3,4]
e2 = [5,6]
mod = 133            # 模数
N = 2

# # 计算多项式模环加法
# add_result = poly_mod_add(poly1, poly2, mod)
# print("多项式加法结果:", add_result)
# 计算多项式模环乘法
print("原始明文:",m)
pk = Gen_pk(a,s,t,e,mod,N)
sk = s
print("公钥pk1:", pk[0])
print("公钥pk2:", pk[1])
c = Enc(pk,m,u,mod,N)
print("密文c1:", c[0])
print("密文c2:", c[1])
result = dec(c,sk,mod,N,t)
print("解密后的多项式",result)

加密模拟