这个问题是基于离散多项式模$(x^3-1)$强吗？
我们开始和环R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)合作，
素数，即系数模p模x^{3}-1的二次多项式。作为x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right)，我们选择了R、S\subset R和公共值z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0的一个子集，
。
我们可以将S元素的转置运算定义为将x系数与对应的多项式之一的x^{2}交换，因此\left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c。
现在，我们将函数f:S\times S\mapsto S定义为f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx。它的空元素是-zx，而f是S的封闭映射，所以是A,B\in S,\ f\left(A,B\right)\in S。
接下来，我们定义一个系列如下：
对于本系列中给定的元素，s_{n}，值r_{n}=f\left(s_{n},A\right)
问题是
考虑到函数f不是关联函数，知道B和r_{n}恢复秘密A的值有多困难。作为尺寸的一个例子，比方说n=256,\ p\sim2^{128}。
这个问题可能导致在这两个文档中描述的密码系统：
https://drive.google.com/open?id=1OGnFfooWASVCD1Iw_hVwvHYgqMGGE5nH
https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv
回答 1
Cryptography用户
发布于 2019-11-19 16:03:13
以下是同构：
ax^2 + bx + c (与z)映射到ax^2 + (b + z - z')x + c (与z')
这种转换唯一不明显的地方是它保留了f，也就是说，f(A, B) (使用z)是映射到f'(A', B')的元素(使用z'，f', A', B'是f, A, B的映射版本)。
然而，这并不难显示；我们注意到，约束ax^2 + bx + c = -z \pmod {x-1}等同于a + b + c = -z。
考虑到这一点，如果A = ax^2 - (a+b+z)x + b (将线性项设置为与约束一致的值)，如果B = cx^2 - (c+d+z)x + d，则f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)
如果我们考虑这两个元素A' = ax^2 - (a+b+z')x + b和B' = cx^2 - (c+d+z')x + d的映射版本，那么映射的f'版本将有f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)。
我们可以看到元素f(A, B)映射到元素f'(A', B')，因此保持了同构。
https://crypto.stackexchange.com/questions/75842
复制相似问题
腾讯云开发者
