Dixon结式在密码学中的应用

被引：9

作者：

唐樨瑾

冯勇

机构：

[1] 中国科学院成都计算机应用研究所自动推理实验室

来源：

软件学报 | 2007年 / 07期

关键词：

多变元密码学; 有限域上的多项式方程; 代数攻击; Dixon结式; DR(Dixon resultants);

D O I：

暂无

中图分类号：

TN918.2 [密码、密码机];

学科分类号：

摘要：

针对密码学中的多变元多项式二次方程系统求解问题,基于扩展Dixon结式提出了一种求解算法DR(Dixon resultants).基本思想为对于MQ(multivariate quadratic)问题,把x1,x2,…,xn?1当作变元,而把xn当作参数,然后利用和改进扩展Dixon结式方法求解该类系统.分析了该算法对于一般情况的复杂度,并且基于实验证据猜测:对于某些稀疏问题,新算法的复杂度很有可能也是多项式的.实验结果表明,对于m=n的一般和稀疏的问题,DR效率优于已有的两种算法.除了高效性,新算法还具有复杂度容易度量、计算时间可以预测的优点.

引用

页码：1738 / 1745

页数：8