多变量公钥密码的安全性分析

姓    名：曹巍巍    学科专业：信息安全

 研究方向：密码学    指导教师：胡磊 教授

摘   要

 本文研究了三个多变量公钥方案的安全性。我们利用差分攻击和线性化方程攻击从理论上破解了一种带有双重扰动的多变量加密体制PTH+；推广了线性化方程的攻击方法，提出了非线性化方程攻击，并利用它破解了两个MFE改进方案Quartic-1和Quartic-2；细致分析了针对油醋签名方案的Kipnis-Shamir攻击方法，对存在的问题给出了方法改进和理论补充。具体工作如下：

 1.PTH+方案是对TH方案通过内部扰动和加方法（外部扰动）改进得到的公钥加密方案。TH方案不能抵抗线性化方程攻击。我们的唯密文攻击分为两步：第一步是预计算。利用公钥差分的秩特征将整个明文空间划分为一组陪集。在每个陪集上，PTH+方案中的内部扰动退变为常数。第二步给定一个密文，分别尝试在每个陪集上进行线性化方程攻击直到找到明文。

 2.Quartic-1和Quartic-2是对MFE方案进行改进之后得到的公钥加密方案。原始MFE已被高阶线性化方程攻击破解，改进之后的公钥为四次多项式。对Quartic-1和Quartic-2我们提出了非线性化方程攻击。我们首先找到它们满足的一阶二次化非线性方程，借助Grobner基算法F_4给出了它们的实际破解。

 3.油醋签名方案是一类主要的多变量签名方案。它分为平衡油醋方案和非平衡油醋方案。我们改进了针对奇特征域上的非平衡油醋方案的Kipnis-Shamir攻击，修正了针对偶特征域上的非平衡油醋方案的Kipnis-Shamir攻击，最后理论地证明了在偶特征域上平衡油醋方案的一个重要实验观察。