混淆电路(garbled circuits)和混淆(obfuscation)是密码研究领域中两个非常重要的工具. 混淆电路是由 Yao 在安全两方计算问题中提出的一种构造方法发展而来, 混淆则是从代码混淆发展而来. 混淆电路和混淆均要求对电路进行``加密''使得电路内容不可读且保留其功能性. 由于直接对电路操作, 混淆电路和混淆相当于对函数本身进行``保护''. 这一特点使得他们在密码学领域以及现实社会均具有广泛的应用. 但是, 如此相似的两个工具在通用构造上以及相互构造中却呈现出完全相反的难度. 混淆电路的实现仅需要 AES 等简单的加密方案, 而目前大多数的通用混淆即不可区分混淆的实现则是依赖于多线性映射的构造. 也就是说, 现有的混淆电路的实现效率远远高于不可区分混淆的实现效率. 这一实现效率上的巨大差异使得混淆电路和混淆的区别和联系成为我们关注的问题. 本文对混淆电路和不可区分混淆进行介绍, 包括语义定义、安全定义、常见的构造方案, 以及应用场景. 并对两者在不同的安全级别间的区别与联系进行分析说明, 探索两者之间互相构造的可能性. 通过这些分析和探索, 我们希望为接下来两个工具的构造和优化提供新的思路.

本文首先对Simon 量子算法作出了进一步研究, 证明了Simon 承诺中存在周期的随机函数具有唯一周期的概率接近1. 随后总结了对常见分组密码结构进行Simon 量子算法攻击的一般性步骤, 指出对Feistel 结构及其扩展结构应用Simon 算法时, 只需要中间的轮函数为置换, 就可以构造出完全满足 Simon 承诺的周期函数. 同时修正了Dong 等人对RC6 算法结构攻击中的错误, 并且对三轮MISTY-L 和MISTY-R 进行了区分攻击. 最后论证了在选择明文攻击下, 三轮Lai-Massey 结构能够抵抗Simon 量子算法攻击.

周期为奇素数幂pⁿ (p 为奇素数, n ⩾ 2) 的二元伪随机序列的线性复杂度及k-错线性复杂度的计算是序列密码中的一个研究热点, 已有文献中提出了算法. 本文从一个新的角度讨论这类序列的线性复杂度及k-错线性复杂度, 即通过将序列表示为p*p^n-1 矩阵形式, 从该矩阵的每一列所含非零元素的个数即可确定序列在2模p²为本原根时的线性复杂度及k-错线性复杂度. 本文中主要针对n = 2 的情况, 即周期为p²的二元序列, 从理论上对主要结果加以证明, 但所用思想方法可以推广至n > 2 的情况.

分析了ESF 算法在截断不可能差分分析下的安全性. 首先给出了ESF 算法的一些新的8 轮截断不可能差分区分器. 其次, 基于得到的8 轮不可能差分区分器, 并利用密钥编排算法部分子密钥间存在的依赖关系, 给出了ESF 算法的13 轮不可能差分分析, 恢复了80 比特主密钥, 其时间复杂度为2^77.39次13 轮ESF 算法加密, 数据复杂度为2^61.99个选择明文. 这是ESF 算法目前最好的不可能差分分析结果.

内积加密体制作为一种特殊的函数加密, 被广泛应用于云计算领域. 针对现有内积加密方案的公开参数随系统属性个数线性增长的缺陷, 本文利用素数阶群上的双线性映射提出了一个公开参数长度固定且具有适应安全性的内积加密方案. 在设计方案时, 我们通过利用素数阶熵扩张引理给出的公开参数形式, 实现了公开参数长度固定; 方案的密钥生成算法, 通过利用属性向量分量与随机向量结合的技巧, 生成每个私钥分量, 在素数阶熵扩张引理和MDDH_k;k+1ⁿ 困难假设成立条件下, 利用Game 序列的证明方法, 证明了方案具有适应安全性. 并且与现有内积加密方案相比, 本文方案的公开参数长度仅有16 个群元素, 公开参数的选取不受属性个数影响, 大大降低了公开参数选取量, 使得方案的实用性和操作性更强.

在智能电网中, 为了满足电力公司能够实时获得用户用电量的需求, 同时保护用户个人隐私, 本文提出了一个基于身份信息验证的可靠数据聚合方案. 在本方案中, 用户使用同态Okamoto-Uchiyama加密算法对用电量进行加密和用基于用户身份信息的密钥对消息签名. 网关收到所有用户发来的用电信
息后, 会对其签名一一验证, 为了降低网关的计算量, 本方案支持批量验证, 能够将所有用户验证所需的双线性对运算次数降低到一个常数. 最后, 控制中心可以在不知道单个用户数据的情况下获得聚合数据. 在本方案的通信过程中, 攻击者无法获得或篡改任何用户的用电量. 同时, 本方案还具备容错功能, 使得当个
别用户的智能电表出现故障也不会影响其他用户用电信息的收集. 通过安全性分析, 我们证明了该方案具有机密性、完整性和不可抵赖性, 并且在计算能力上较以往的方案有显著的提高.

模糊关键词搜索能够在关键词被拼错的情况下, 仍然可以使云服务器返回用户感兴趣的文件. 然而已有的模糊搜索方案大多都假设云服务器是诚实的. 一旦云服务器由于软硬件故障等原因返回给用户错误的结果, 这些模糊关键词搜索方案将无法工作. 另一方面, 云服务器上如果存储大量的冗余数据, 会浪费云服务器的存储资源和用户的网路带宽. 针对以上问题, 提出了一个支持数据去重的可验证的模糊多关键词搜索方案. 为了保护数据隐私性并实现数据去重, 采用收敛加密对文件加密. 为了实现模糊关键词搜索以及对搜索结果排序, 采用局部敏感哈希和TF-IDF 规则建立安全索引. 为了验证搜索结果的正确性, 采用基于MAC 的验证机制. 安全性分析和性能分析表明提出的方案是安全、高效的.

积分分析是针对分组密码十分有效的分析方法之一, 其通常利用密文某些位置的零和性质构造积分区分器, 并据此进行密钥恢复攻击. 在ASIACRYPT 2016 上, 向泽军等人首次运用混合整数线性规划(MILP) 模型对积分分析可分性质进行刻画, 并对六种轻量级分组密码积分区分器进行搜索. 本文针对轻量级分组密码PUFFIN 算法, 运用基于比特可分性质的MILP模型搜索可分路径, 得到PUFFIN 算法最长9轮积分区分器. 但由于该9轮区分器区分优势不够明显且攻击数据复杂度较高, 攻击效果不佳. 为取得更好的攻击效果, 本文选择搜索8轮积分区分器对PUFFIN 算法进行10轮密钥恢复攻击. 该攻击能够恢复PUFFIN 算法100 比特轮密钥, 攻击的数据复杂度为2^54.81个选择明文, 时间复杂度为2^67.49次10 轮算法加密, 存储复杂度为2²⁰个存储单元.

置换多项式在分组密码算法设计中具有广泛的应用. 一般情况下, 分组密码算法中明密文之间的关系就是密钥控制下的置换. 另外, 密码算法的许多重要组成部分也是置换. 例如, 具有良好密码学性质的置换常被用来设计对称密码算法中唯一的非线性部件$S$盒.

完全置换多项式是一类特殊的置换, 其概念是Mann在上个世纪四十年代提出的, 早期的研究结果与正交拉丁方联系紧密. 完全置换多项式具有优良的密码学性质. 例如, 偶特征有限域上的完全置换多项式只有一个不动点. 此外, 非线性完全置换具有良好的位独立性和雪崩特性, 使得基于完全置换的密码算法具备良好的扩散和混淆作用. 因此, 完全置换多项式的研究具有重要的理论和实际意义.

完全置换多项式在密码学中的较早应用是由美国Teledyne电子技术公司的Mittenthal提出的. 他分别在1995年和1997年发表的论文《Block substitutions using orthomorphic mapping》和专利《Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation》中讨论了完全置换的构造和基本性质, 首次公开了如何使用完全置换多项式来设计密码算法以及非线性动力系统装置. 这些成果为完全置换在密码学中的应用奠定了基础, 并使人们对完全置换多项式这一数学对象产生浓厚的兴趣. 在随后的十年里, 国内外学者在这一研究方向上取得了一系列进展. 在密码应用方面比较有代表性成果的是Vaudenay在1999年证明了添加完全置换或几乎完全置换的Lai-Massey结构具有更好的伪随机性. 另外, 国内的标志性成果是2006年公布的基于完全置换的分组密码算法SMS4, 该算法被指定用于无线局域网WAPI且被我国商用密码管理局确定为国家密码行业标准, 在密码行业中有着极为重要的作用.

2007年之后的几年里, 完全置换多项式的研究进展非常缓慢, 主要原因是判断多项式的完全置换性质是一个十分困难的问题, 即使最简单的单项式的完全置换性质也不容易被刻画. 直到2014年, Tu, Zeng 和Hu 提出了用加法特征和极坐标表示的方法来将完全置换单项式的问题转化成有限域上特殊方程解的问题. 受到其启发, 从2015年开始国际学术界重新兴起了研究有限域上完全置换多项式的热潮. 在最近五年, 涌现了一大批有代表性的成果, 例如基于例外多项式、AGW 准则或密码结构的完全置换.

完全置换多项式在流密码、 Hash函数、编码设计、校验位系统设计等领域也有一定的应用. 虽然最近几年完全置换多项式的研究已经取得了一系列进展, 但是已有的完全置换多项式类依然十分稀少, 完全置换多项式的研究尚处于初级阶段, 还存在许多有待进一步研究的重要问题, 其中完全置换多项式的构造以及相关密码学性质分析是该方向的重点研究内容.

在本期``完全置换多项式''专栏中共收录三篇文章, 其中包含一篇综述论文和两篇研究论文, 希望对完全置换多项式的理论和应用研究起到促进作用.

第一篇是综述论文《完全置换多项式的研究进展》. 该论文较全面地总结分析了近二十多年来有限域上完全置换多项式的相关理论研究成果, 从完全置换多项式的构造方法和多项式的形式出发给出了已有完全置换的分类, 阐述了完全置换多项式的存在性、代数次数、圈结构以及广义完全置换多项式的相关研究进展. 此外, 还指出了一些值得进一步研究的问题. 该论文是一篇较好的介绍完全置换多项式的综述, 对想了解完全置换多项式的研究者有很高的参考价值和很好的指导意义.

第二篇论文题目是《有限域上几类置换和完全置换》. 因为判定一个多项式构成完全置换的条件是相当复杂的, 所以研究特殊类型的完全置换多项式具有重大的意义. 该论文运用迹函数、线性置换和Dickson置换构造了有限域$\mathbb{F}_{q^n}$上六类形如$\gamma x + {\rm Tr}_q^{q^n}(h(x))$的置换多项式, 证明了其中三类为完全置换并分析了其余三类不构成完全置换的原因. 另外, 在已知的置换判定法则基础上他们还研究了形如$xh(x^s)$的二项式的完全置换性质, 得到了有限域上几类新的完全置换.

第三篇论文题目是《有限域上完全置换多项式的构造》. 稀疏型完全置换多项式因其具有简洁的代数表达式以及便于硬件实现的特点而备受关注. 该论文构造了特征2有限域$\mathbb{F}_{q^2}$上形如$xh(x^{q-1})^{q+1}$的两类完全置换多项式, 给出了这些多项式是完全置换多项式的充要条件或者充分条件. 通过选取适当的函数, 得到了几类完全置换三项式和完全置换七项式.

两篇研究论文均考虑完全置换多项式的构造问题, 研究成果丰富了已有完全置换多项式的构造, 具有重要的理论意义.

完全置换多项式的定义是Mann 在1942 年构造正交拉丁方时提出的. Niederreiter 和Robinson 在1982 年对有限域上完全置换多项式进行了详细研究. Mittenthal 于1995 年首次将具有良好性能的完全置换多项式用于设计非线性动力替代装置. 此后, 完全置换多项式的理论研究逐渐成为密码学的一个热点研究问题. 近年来, 完全置换多项式在密码学、通信理论以及组合设计中具有广泛的应用. 本文对有限域上完全置换多项式的相关理论进行了总结, 包括完全置换多项式的存在性、完全置换多项式的构造、代数次数、圈结构以及广义完全置换多项式.

置换多项式是有限域及其应用研究的重要理论和工具, 它在数学和通信领域均有广泛的应用. 完全置换是一种特殊的置换多项式, 它的构造和应用是密码学、编码理论、组合设计等领域中的热点问题. 本文介绍了置换和完全置换的研究进展, 研究了有限域上具有特定形式的多项式的置换性质, 给出了有限域上置换和完全置换的一般构造方法. 先后运用迹函数、线性置换和Dickson置换构造了有限域$\mathbb{F}_{q^n}$上六类形如$\gamma x+\mathrm{Tr}^{q^n}_q(h(x))$ 的置换, 通过限制系数$\gamma$的取值得到三类新的完全置换. 基于已知的置换判定法则, 确定了二项式$\gamma x+x^{s+1}$是置换的充分条件, 进而得到有限域$\mathbb{F}_{q^n}$上几类新的$xh(x^{s})$型完全置换. 结果表明: 有限域$\mathbb{F}_{q^n}$上形如$\gamma x+\mathrm{Tr}^{q^n}_q(h(x))$或$\gamma x+x^{s+1}$的置换与它的子域$\mathbb{F}_{q}$上的某些置换具有对应关系, 由此可利用$\mathbb{F}_{q}$上已知的完全置换来构造$\mathbb{F}_{q^n}$上新的完全置换.

Complete permutation polynomials over finite fields have been widely used in cryptography, coding theory, and combinatorial designs. The research of complete permutation polynomials was derived from the construction of orthogonal Latin squares. Later, Niederreiter and Robinson gave a detailed study of complete permutation polynomials over finite fields. Sparse complete permutation polynomials attract more attention due to their simple algebraic expressions. Therefore, the construction of sparse complete permutation polynomials has important significance both in theory and practice. This paper constructs several classes of complete permutation trinomials, complete permutation polynomials with seven terms and other complete permutation polynomials over $\mathbb{F}_{q^2}$ with characteristic $2$. Using the AGW criterion, the problem of proving complete permutation polynomials over $\mathbb{F}_{q^2}$ is converted into that of showing the corresponding equation having no solution in the unit circle of $\mathbb{F}_{q^2}$. Furthermore, by considering the number of solutions in the unite circle to these equations, some necessary and sufficient conditions and some other sufficient conditions for these polynomials to be complete permutation polynomials are given.