文摘
多变量公钥密码术是一组加密方案建造np困难的解二次方程在有限的领域,在这隐藏的场方程(HFE)家庭计划仍是最著名的。然而,最初的HFE方案是不安全的,后续修改显示仍然容易受到攻击。在本文中,我们提出一个新变型的HFE方案考虑到特殊的方程 定义在有限域上当 。我们观察到方程可以用来进一步破坏底层中部的特殊结构的地图HFE方案。结果表明,提出的公钥加密方案是安全的对已知攻击包括MinRank攻击,代数攻击,攻击线性化方程。建议增加一些优势原HFE方案对加密速度和公共密钥大小。
1。介绍
公钥密码术(1)建立解决np困难的多元二次方程在有限的申请(2,3)是作为一个可信的候选人基于传统的分解和离散对数公钥密码体制由于其高性能和抵抗量子攻击(4]。隐藏的场方程(HFE)方案5)可能是最著名的密码体制在多变量公钥加密方案。HFE方案首先定义了一个单变量映射在一个扩展字段: 在一定程度选择不能很大,以便用户可以使用Berlekamp算法(6)有效计算的根源。然后两个可逆的仿射变换应用于隐藏地图中央的特殊结构(2,5]。然而,中央地图可以用一个低秩矩阵表示7),这使得它容易MinRank攻击(7- - - - - -9]。所以需要一些修改来修复基本HFE计划(10- - - - - -14]。然而,所有已知的改性方法只能对部分特殊结构的非线性变换HFE中央地图,因此它们仍然容易受到一些攻击15- - - - - -17]。
我们认为HFE计划在有限的领域特征3。我们强加一些限制明文空间,可以使用限制合并系数的线性部分和广场的部分。通过这样做,我们可以对中央完全非线性变换的地图HFE加密方案。性能分析表明,改性可以保存公钥存储位,减少了加密成本了位运算。结果表明,改性可以保护已知的攻击包括MinRank攻击,线性化方程的攻击,直接代数攻击。
2。建议
2.1。符号
让是一个订单有限域与作为一个主要力量。让是一个不可约多项式与学位在;然后 形成一个学位,扩展字段。建设标准的同构承认之间的扩展字段和向量空间;也就是说,一个元素 ,我们有 。我们表示的逆映射作为。注意,弗罗贝尼乌斯的地图 为 定义在是线性;即,当表达了在基础领域,将维线性函数在。
2.2。描述
加密方案包含三个subalgorithms:密钥生成、加密和解密。
密钥生成。系统参数包含一个不可约多项式与学位在扩展字段 ,同构之间的和。首先,我们定义一个HFE地图在(1)和随机选择两个可逆的仿射变换 和 。然后我们计算它们的倒数和和- variable二次多项式 。为 ,我们设置 所有的系数都在哪里为 。然后我们合并广场的系数和线性的,也就是说, 为 ,得到的公钥HFE修改方案,即二次多项式 在那里, , 密钥由,,。
加密。明文空间 。对于一个明文 ,我们只计算 密文。
解密。给定一个密文 ,我们计算 和 ,我们使用Berlekamp算法(6计算所有原象 这样 ,为每一个,我们计算 。最后,我们计算 。如果 ;然后输出明文。如果我们不能得到一个向量所有的形式像原,我们输出的符号指定一个无效的密文。
为什么解密工作。我们观察到 ,所以 。因此,对 , 所以 。修改后的HFE解密恢复明文通过剥离组成一个接一个从最左边的一面。
讲话。原HFE方案(5适用于任何领域和它的扩展。事实上,二次多项式映射正是原HFE方案的公钥和密钥的原始计划也包括吗,,。加密的原始HFE方案计算 ,明文是在但不一定在 。的解密算法修改HFE计划正是原始HFE解密。
2.3。性能和比较
之间做个比较提出HFE修改和原始HFE计划在一个统一的平台,我们认为HFE方案定义和它的扩展字段。它可以很容易地看到,修改和原始HFE方案共享一个公共密钥和解密算法。所以两个方案相同的密钥大小和解密成本。在修改后的方案中,公钥,因此我们不需要存储公钥的平方项的系数。因此该方案减少了公共密钥大小位。在加密过程中,提出了修改HFE计划不需要做平方计算,所以该加密降低了计算成本位运算。
3所示。安全
我们分析的安全提出HFE修改加密方案。我们首先回顾已知攻击的基本思想,然后解释为什么这个提议对这些攻击是安全的。
3.1。线性化方程的攻击
基本思想。线性化方程攻击(18)被发现在Matsumoto-Imai Patarin计划(19]。Matsumoto-Imai方案,排列 在2特点是这样定义的 ,然后使用两个可逆的仿射变换和伪装中央地图成二次映射在,即 攻击的基本观点如下。请注意, 意味着 。通过设置 我们可以表达 作为双线性方程对输入和输出的函数 : 在哪里 和 。给定一个密文 ,我们想恢复相应的明文 。请注意,(、职责)是一个仿射变换(职责。)的输入(输出,分别地。)功能 。所以和满足以下方程来源于双线性方程,即 在哪里 和所有的系数。这些方程被称为线性化方程,可以有效地从公众多项式计算。结果表明,线性化方程至少有排名 (20.]。所以鉴于密文 ,我们只需要解决线性化方程来获得相应的明文 。
为什么这个提议是安全的对线性化方程攻击。我们首先注意HFE计划(5)提出了Patarin阻止攻击的线性化方程,没有证据报道存在的线性化方程HFE计划。对线性化方程的HFE方案是安全攻击。HFE提出修改方案而言,我们只是注意,任何明文 , 是一个有效的密文原FHE方案和提出修改HFE方案。因此,我们不能指望从修改后的HFE方案获得线性化方程。
3.2。MinRank攻击
基本思想。不失一般性,我们假设这两个可逆的仿射变换和都是线性的(21)和定义的条款 在在(1)。然后我们可以看看作为一个二次型 然后我们联系一个对称维方阵这样 对称矩阵是地位低的,它是对称矩阵的特殊结构使原HFE方案没有安全感。我们回忆起 , 和小于或等于表示最小的整数 作为,我们会发现过去的所有元素 列(行、职责)为零。因此,对称矩阵的秩最多是。松说,当我们应用两个线性变换的输入和输出映射,相应的矩阵的秩。我们定义的二次部分 作为 ,即为 , 请注意,可以表示为均匀二次多项式在基础领域;那么两个线性变换的应用程序的输入和输出也会给均匀二次多项式在基础领域。也就是说 或者说, 上面的方程,我们可以提高二次部分的公钥扩展字段在某些未知的线性变换来获得因此。Kipnis和沙米尔指出[7),通过提高二次部分的公钥HFE计划的扩展字段,他们可以找到一个矩阵的集合。矩阵然后由发现这些矩阵的线性组合有一个最低等级(最多)。因此通过解决MinRank问题我们可以确定矩阵系数的线性变换。虽然MinRank问题被证明是np完备性(22,23),减少MinRank问题并处以严重的安全威胁的安全HFE计划(7,8]。
为什么建议对MinRank攻击是安全的。为了说明为什么提出修改对MinRank攻击(HFE方案是安全的7,8),我们只需要表明,当扩展字段,二次公钥的一部分不是与一个低秩矩阵。我们设置了二次公钥的一部分作为 与 为 。如果我们取消扩展字段和发现相应的矩阵不是地位低的,我们可以要求我们的建议对MinRank攻击是安全的(7,8]。所以我们定义 现在我们显示相应的矩阵不一定是低等级。我们定义 与 为 , 很明显, 。因此我们可以很容易的验证 所以我们得到 。在这个矩阵方程,我们只知道是低等级(最多)。然而,矩阵的秩是未知的,因此矩阵的秩吗不一定是低。因此,敌人不能来源于公开已知的地图一个低秩矩阵。所以MinRank攻击并不适用于cryptanalyzing HFE提出修改方案。
3.3。代数攻击
基本思想。攻击多变量公钥密码体制的一个简单的方法是直接利用多变量二次方程组的求解算法来计算Grobner基的一些理想。考虑到密文 ,我们想解决明文从二次方程: 代数或直接攻击可以使用一些Grobner基算法等(24)和XL (25)算法来解决发电机的理想 生成的 。这是观察到(26场方程) 为 将有用的简化计算,那么我们也可以添加发电机场方程;也就是说,我们解决Grobner理想的基础 为什么建议对代数攻击是安全的。在HFE加密方案提出修改,我们强加一些限制明文空间。明文空间 但不是。因此我们有一些额外的方程,将明文 ;即为 ,我们有 。明文块也满足场方程 。不过,我们可以推导出场方程 从方程 。提出修改加密方案,我们需要找到理想的Grobner基 评估的难度Grobner基算法恢复明文,我们可以利用规律的程度的二次方程27]估计计算成本。至少计算成本位运算,结果显示在219页(2]。建议下参数 和 ,二次方程的规律的程度 。因此,计算开销 位运算。所以代数攻击下,提议修改HFE加密方案可以获得一个安全水平的建议下80位参数。
3.4。显示参数
考虑到上述的讨论,我们建议选择 和 。我们可以看到从安全分析,提出HFE修改加密方案可以获得一个安全水平的建议下80位参数。
4所示。结论
在本文中,我们提出了一个新颖的HFE加密方案修改。拟议的HFE修改具有以下特点:(我)普遍的填充物多变量公钥加密方案:该HFE变体可以合并广场和线性施加一些限制条款明文空间。该方法是一种通用填充方案,因此可用于其他多元密码结构。(2)完全非线性变换在地图中央:该方法可以删除所有条款在公共广场多元二次多项式,因此对所有多项式非线性变换。(3)安全对已知攻击:我们说明拟议的HFE修改加密方案是安全的对已知攻击攻击,包括线性化方程MinRank攻击,代数攻击。(iv)更高效的加密和较小的公共密钥大小:建议修改加密方案不存储公钥的广场上,因此可以减少加密成本位运算和保存公钥存储位。作为一种新的多变量公钥加密的安全建议需要进一步了解。所以我们鼓励读者检查的安全建议。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是由中国国家自然科学基金(授予号。61572390,61572390,61540049),中国国家重点研发项目(没有。2017 yfb0802002),自然科学基金在中国的宁波(没有。201601 hj-b01382),项目河南省高校科技创新人才(没有。18 hastit022)、河南省基础教育委员会授予a520025 16和18号a520047),基础大学河南省(没有的关键老师。2016 ggjs - 141)、开放的基础认知无线电和信息处理重点实验室,教育部(桂林电子科技大学)(没有。CRKL160202)和优秀青年教师工程许昌大学。