四元数代数上的NTRUEncrypt失败

Question

这是我前两个问题(1和2)的后续，可能需要先查看它们以获得完整的上下文。我正在尝试重新创建本论文的结果。介绍了这里的基本算法。

我正在尝试实现NTRUEncrypt系统，但工作在四元数代数上。我认为代码是正确的，因为它对一个非常简单的盲值r很好。问题是-它只适用于选定的非常简单的案例。请参阅下面的Sage代码和正确的方案：

1.四元数类实现

多项式环上四元数的简单实现。

密码系统操作所需的基本功能。

最重要的是：Q_1 \times Q_2乘法是递归实现的(即四元数由两个复数等组成)。

def QuotientRingPolynomialInverse(p, ring):
    return ring(p) ^ -1

class Quaternion():
    def __init__(self, arglist):
        self.coordinates = tuple(arglist)

def QuaternionCojnugate(Q):
    templist = list(Q.coordinates)
    templist = [
        templist[i] if i==0 else -templist[i] for i in range(len(templist))
    ]
    return Quaternion(templist)

def QuaternionNormSquared(Q):
    return sum([c*c for c in Q.coordinates])

def Quaternion_mul_const(Q, a):
    return Quaternion([c*a for c in Q.coordinates])

def Quaternion_add_Quaternion(Q1, Q2):
    dim = len(Q1.coordinates)
    return Quaternion([
        Q1.coordinates[i] + Q2.coordinates[i] for i in range(dim)
    ])

def Quaternion_sub_Quaternion(Q1, Q2):
    dim = len(Q1.coordinates)
    return Quaternion([
        Q1.coordinates[i] - Q2.coordinates[i] for i in range(dim)
    ])

def Quaternion_mul_Quaternion(Q1, Q2):
    dim = len(Q1.coordinates)
    # recursion base
    if dim == 1:
        return Quaternion([Q1.coordinates[0] * Q2.coordinates[0]])
    # recursion step
    else:
        # helper objects
        halfd = int(dim / 2)
        Q1a = Quaternion(Q1.coordinates[:halfd])
        Q1b = Quaternion(Q1.coordinates[halfd:])
        Q2a = Quaternion(Q2.coordinates[:halfd])
        Q2b = Quaternion(Q2.coordinates[halfd:])
        # multiply recursively
        Q1a2a = Quaternion_mul_Quaternion(
            Q1a,
            Q2a
        )
        Q2b1b = Quaternion_mul_Quaternion(
            QuaternionCojnugate(Q2b),
            Q1b
        )
        Q2b1a = Quaternion_mul_Quaternion(
            Q2b,
            Q1a
        )
        Q1b2a = Quaternion_mul_Quaternion(
            Q1b,
            QuaternionCojnugate(Q2a)
        )
        # construct the final object
        Qa = Quaternion_sub_Quaternion(Q1a2a, Q2b1b)
        Qb = Quaternion_add_Quaternion(Q2b1a, Q1b2a)
        return Quaternion(Qa.coordinates + Qb.coordinates)

2.密码系统

的参数

设置(N,p,q)参数，构造多项式(商)环。

N = 11
p = 3
q = 127

R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)

P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)

Q.<x> = PolynomialRing(Zmod(q))
QQ = Q.quotient(x^N - 1)

3.公钥生成

定义四元数f = (f_1, f_2, f_3, f_4)和g = (g_1, g_2, g_3, g_4)。将f转换为商环并计算其逆。生成公钥h = pf_q^{-1} \times g

f_1 = RR([1, 0, 0, 1, -1, 1, 0, 0, 0, 0, -1])
f_2 = RR([0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0])
f_3 = RR([-1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0])
f_4 = RR([0, 1, 0, 0, 0, 0, 0, -1, -1, -1, -1])
Q_f = Quaternion([f_1, f_2, f_3, f_4])
Q_fPP = Quaternion([PP(_) for _ in Q_f.coordinates])
Q_fQQ = Quaternion([QQ(_) for _ in Q_f.coordinates])

g_1 = RR([0, -1, 0, 0, 0, 0, 1, 0, 0, 1, 0])
g_2 = RR([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1])
g_3 = RR([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
g_4 = RR([-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1])
Q_g = Quaternion([g_1, g_2, g_3, g_4])

Q_f_ = QuaternionCojnugate(Q_f)
f_norm = QuaternionNormSquared(Q_f)
f_norm_inv_p = PP(f_norm) ^ -1
Q_fp = Quaternion([
    PP(_) * f_norm_inv_p for _ in Q_f_.coordinates
])
f_norm_inv_q = QQ(f_norm) ^ -1
Q_fq = Quaternion([
    QQ(_) * f_norm_inv_q for _ in Q_f_.coordinates
])

Q_pfq = Quaternion_mul_const(Q_fq, p)
Q_pfqg = Quaternion_mul_Quaternion(Q_pfq, Q_g)
Q_h = Quaternion([QQ(_) for _ in Q_pfqg.coordinates])

4.加密

定义四元数m和r (盲值)。加密消息e = r \times h + m。

m = (
    PP([1, 0, 0, 0, 0, -1, 0, 0, 0, 1, 1]),
    PP([1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0]),
    PP([1, -1, 0, -1, 0, 0, 0, 0, 0, 1, 1]),
    PP([0, 0, 0, -1, -1, 0, 0, 0, -1, 0, 0]),
)
Q_m = Quaternion(m)

r = (
    QQ([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
)
Q_r = Quaternion(r)

Q_rh = Quaternion_mul_Quaternion(Q_r, Q_h)
Q_fhRR = Quaternion([RR(_) for _ in Q_rh.coordinates])

Q_rhm = Quaternion_add_Quaternion(Q_fhRR, Q_m)
Q_e = Quaternion([QQ(_) for _ in Q_rhm.coordinates])

5.解密

a = f \times e (记得把系数放在中心位置)

b = PP[a]

c = f_p^{-1} \times b

Q_a = Quaternion_mul_Quaternion(Q_fQQ, Q_e)

Q_a = Quaternion([
    ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[0].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[1].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[2].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[3].lift()]),
])

Q_b = Quaternion([PP(_) for _ in Q_a.coordinates])

Q_c = Quaternion_mul_Quaternion(Q_fp, Q_b)

assert Q_m.coordinates[0] == Q_c.coordinates[0]
assert Q_m.coordinates[1] == Q_c.coordinates[1]
assert Q_m.coordinates[2] == Q_c.coordinates[2]
assert Q_m.coordinates[3] == Q_c.coordinates[3]

在上面的例子中，所有的检查结果，因此我相信我的错误是概念性的，而不是在代码中.在下面的r中，密码系统失败：

r = (
    QQ([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]),
)

我做错了什么？

Answer 1

这有点难解开，但我怀疑问题在于未能解释四元数的非交换性。示例代码中的r是一个纯粹的实元素，因此通勤，但最后提到的r有一个k组件，因此不一定与其他四元数通勤。

忽略模块p的内容，NTRU系统的目标是尝试使接收机恢复特征零多项式。

pg(x)r(x)+f(x)m(x).

然而，接收机在特征q中完成它们的所有恢复，因此，如果任何系数在区间(-q/2,q/2)之外，则恢复在以前的情况下失败。对于四元数，还有一个额外的问题，就是在恢复多项式时，确保我们做正确的右乘和左乘。

在此，接收机形成了特征q多项式h。

h(x)\equiv pf^{-1}(x)g(x)\pmod{\langle q,x^n-1\rangle}.

然后发送方形成特征q多项式。

e(x)\equiv r(x)h(x)+m(x)=pr(x)f^{-1}(x)g(x)+m(x)\pmod{\langle q,x^n-1\rangle}.

接收机然后计算特征q多项式。

f(x)e(x)\equiv pf(x)r(x)f^{-1}(x)g(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}.

如果我们处于一个可交换的环境中，这将是很好的，因为事情会解决到pr(x)g(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}的需要。然而，四元数不通勤，因此我们不能进行这种简化。

然而，如果我们改变e(x)的计算，使我们在右边用r(x)相乘

e(x)\equiv h(x)r(x)+m(x)=pf^{-1}(x)g(x)r(x)+m(x)\pmod{\langle q,x^n-1\rangle}

和

f(x)e(x)\equiv pf(x)f^{-1}(x)g(x)r(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}

这将解析为pg(x)r(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}和解密可以正确进行。我认为这只需要将Q_rh = Quaternion_mul_Quaternion(Q_r, Q_h)更改为Q_rh = Quaternion_mul_Quaternion(Q_h, Q_r)，但还没有进行试验。