Improved Graph-Based Model for Recovering Superpoly on Trivium
Cheng junjie,Qiao kexin等人发表在CT-RSA 2023：原文
总结
在cube攻击中，恢复超多项式是一个关键步骤，通常通过建立MILP模型并枚举所有可行解，来得到超多项式中包含的所有单项式。在建模过程中，为了提高求解效率，可以考虑减小模型规模或减少模型的可行解数量。作者观察到，一些子图如果具有相同的输入和输出点，但具有不同的边的指向，则可以考虑在模型中加约束来去掉该剪枝模式。因此本文提出了一种自动搜索2层剪枝模式的算法，通过穷举3个输入点的情况，发现了12种新的剪枝模式，部分剪枝模式可以添加较少的约束来去除大量的可行解。最终作者基于图模型，结合胡凯等人提出的分解策略，可以准确恢复Trivium 843轮的超多项式并减少了模型可行解的数量。然而我认为使用新剪枝模式时，计算结果是否正确需要进一步研究。对于模型规模减小而声称带来的求解效率的提高，文中没有明确的对比说明。
上述内容仅用于非领域人员快速了解，具体实现逻辑及细节不做展示
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.