A Simpler Model for Recovering Superpoly on Trivium
Trivium中恢复超多项式的一个更简单的模型
虽然题目中提到了Trivium，但该论文中提出的方法也可以用于其他的流密码中
Stéphanie Delaune, Patrick Derbez等人发在SAC2021：原文
研究意义
cube攻击是一种有效的密码分析方法，恢复超多项式是该攻击中的一个关键步骤。
对于一个密码问题，确定最佳的MILP建模方法是困难的
motivation
- 大部分情况下实验表明，模型越小求解速度越快
- 作者在恢复超多项式的建模方面，关注于可以减少约束数量的建模方法。
- 基于Trivium的自身特点，找到了有向图的结构来建模
贡献
涉及多项式建模为一个有向图，使用更少的约束和变量。
提出了两个策略来加速模型求解
- 通过寻找“加倍路径”来去除部分偶数单项式路径，
- 设置Gurobi的求解选项和使用次数估计来剪枝。
可以去除50%～80%的偶数单项式路径
- 总体求解效率相比单项式预测模型有30～60倍提升。
下图中为Trivium的结构，有288个内部状态s，分布在3个寄存器ABC上 。每一轮产生3个新比特，替换掉每个寄存器的最后面的比特，然后288个状态变量的值全部循环右移1位。最终产生的3个新比特，放在寄存器的第一个位置， 其他位都是循环右移。
下图是完整描述的Trivium生成过程，包含了所有的转换关系
根据刚才的转换的表示，这里给出一条路径的例子，顶部节点是606轮的点C，由该点可以追溯到523轮和524轮的点B，最终可以发现，这个图其实是一条单项式路径，表示的是K16这个单项式
Trivium-672：$ 𝒛←𝑠_{66}+𝑠_{93}+𝑠_{162}+𝑠_{177}+𝒔_{𝟐𝟒𝟑}+𝑠_{288}$
子结点可以为C606的S177
模型高效的原因
相比单项式预测模型，图模型采用了一种类似于压缩表示的形式，变量是边（状态的传播关系），所需约束个数较少且可以快速得到多个解。
评价
这篇论文提出的建模方法相比前人的方法有较大改进，用了新的数据结构和更少的约束和变量，并且去除偶数单项式路径更容易，对于加速模型求解具有较大的参考价值。
总结
cube攻击是一种有效的密码分析方法，恢复超多项式是该攻击中的一个关键步骤。现有恢复超多项式的模型，在求解效率方面还有改进的空间。大部分情况下实验表明，模型越小求解速度就越快。因此作者在恢复超多项式的建模方面，关注于可以减少约束数量的建模方法。基于Trivium的自身结构，作者将涉及的多项式建模为一个有向图，使用了更少的约束和变量。同时作者提出了两个策略来加速本文模型求解，一是通过寻找“加倍路径”来去除部分偶数单项式路径，二是设置Gurobi的求解选项和使用次数估计来剪枝。最终作者提出的模型可以去除50%～80%的偶数单项式路径，相比单项式预测模型，总体求解效率有30～60倍提升。本文提出的建模方法相比前人的方法有较大改进，构造的模型更简单，去除偶数单项式路径更容易，对于加速模型求解具有较大的参考价值。
上述内容仅用于非领域人员快速了解，具体实现逻辑及细节不做展示
Welcome to MinZhang’s space! If you have any questions about the following issues, you can contact me on GitHub or email- zhangmin2022@iie.ac.cn.