实序列和复序列的线性复杂度

Question

在密码学中，流密码的输出序列是二进制值(或者更一般地说是有限域值)。然而，利用反馈移位寄存器，流密码器也可以生成实变量和复杂变量上的数学序列。我们还可以通过定义序列w(k)将流密码的二进制输出序列z(k)=(-1)^{w(k)}转换为真正的间隔D2。在我的搜索中，我没有找到关于实序列和复序列线性复杂性理论的文献。为什么这样的理论没有用或有趣呢？

Answer 1

一般说来，有限场论是建立在精确算法的基础上的，是比较简洁的。由于我们在密码学中需要精确的算术(否则，像均匀分布这样的东西要么是不可能的，要么是很难证明的，我们需要有限的过程才能真正实现密码)，有限域上的理论就足够了。

几个注意事项：

1. 我们可以定义任意无限域上的线性复杂性理论，例如\mathbb{C}或\mathbb{R}.，例如，在数学和工程本科课程中教授/使用线性递归。从密码的角度来看，这种线性复杂性将非常不稳定。
2. 对于复杂字段上的代码，有一个相关的问题和答案，其中berlekamp massey的问题在链接这里。中得到了解决。
3. 有一个序列复杂性的理论在p-的进场，它代表反馈移位寄存器与进位，率先由克拉珀和戈雷斯基。这里见维基百科。
4. 最后，如果对二进制序列执行映射s_t=(-1)^{u_t}，则直接获得与u_t (如u_{t+3}=u_{t+1}\oplus u_{t} \Longleftrightarrow s_{t+3}=s_{t+1}s_{t} )的线性递归对应的s_t的乘法递归。

Answer 2

这种转换在线性密码分析中很常见，在Hadamard变换下，该过程将比特的加性组合转换为字符的乘法组合。然后，利用特征2中的傅里叶分析，对变换的计算可以提供关于输入位的信息。变换的期望值有时被称为凸值。

使用此转换的一个示例是其期望值形式的堆积引理。关于更现代的用法，例如，参见Coppersmith等人对线性掩蔽流密码的密码分析定理6的证明。