Dixon结式在密码学中的应用

摘要：

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

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

所属期刊栏目：18

分类号：TP309(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划2004CB318003

在线出版日期：2007-08-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1738-1745