密码函数安全性指标的研究进展

密码学报 ISSN 2095-7025 CN 10-1195/TN E-mail: jcr@

Journal of Cryptologic Research,2014,1(6):578–588

©《密码学报》编辑部版权所有. Tel/Fax: +86-10-81033101 密码函数安全性指标的研究进展

屈龙江1, 付绍静2,3, 李 超1,2

1. 国防科技大学 理学院, 长沙410073

2. 国防科技大学 计算机学院, 长沙410073

3. 北京邮电大学网络与交换技术国家重点实验室, 北京100088

通讯作者: 付绍静, E-mail: shaojing1984@

摘 要: 密码函数包含布尔函数与向量函数(S-盒)两大类, 是构成序列密码、分组密码和Hash函数这三

类密码算法的重要组件, 其密码学性质的好坏直接关系到密码算法的安全性. 密码算法对于各种已知攻击

的抵抗性可以由它所使用的密码函数的相应密码学指标来衡量, 密码函数的差分均匀度反映了其抵抗差

分攻击的能力, 密码函数的非线性度反映了其抵抗线性攻击或快速相关攻击的能力, 密码函数的代数免疫

度反映了其抵抗代数攻击的能力, 密码函数的相关免疫度反映了其抵抗相关攻击的能力, 密码函数的代数

次数反映其抵抗Berlekamp Massey攻击或高阶差分攻击的能力, 其中非线性度、代数免疫度、差分均匀度

是三个重要的密码学指标. 本文总结了近年来在高度非线性函数、高代数免疫度函数和低差分函数研究方

面的进展, 重点归纳了Bent函数和向量Bent函数这两类高度非线性函数的性质与构造、具有最优代数免

疫度且同时满足高非线性度等其它密码指标较优的布尔函数与向量函数构造、三类低差分函数(PN函数、

APN函数和4-差分函数)的性质与构造三个方面的研究现状与进展情况, 并对这三方面的下一步研究作了

展望.

关键词: 密码函数; 非线性度; 代数免疫度; 差分均匀度

中图法分类号: TP309.7 文献标识码: A DOI: 10.13868/ki.jcr.000053

中文引用格式: 屈龙江, 付绍静, 李超. 密码函数安全性指标的研究进展[J]. 密码学报, 2014, 1(6): 578–588.

英文引用格式: Qu L J, Fu S J, Li C. Recent progress in properties of cryptographic functions[J]. Journal of

Cryptologic Research, 2014, 1(6): 578–588.

Recent Progress in Properties of Cryptographic Functions

QU Long-Jiang1, FU Shao-Jing2,3, LI Chao1,2

1. College of Science, National University of Defense Technology, Changsha 410073, China

2. College of Computer Science, National University of Defense Technology, Changsha 410073, China

3. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications,

Beijing 100876, China

Corresponding author: FU Shao-Jing, E-mail: shaojing1984@

基金项目: 国家自然科学基金项目(61272484); 网络与交换技术国家重点实验室开放基金(SKLNST-2013-1-05)

收稿日期: 2014-10-19 定稿日期: 2014-12-14

屈龙江 等: 密码函数安全性指标的研究进展 579

Abstract: Boolean functions and vectorial functions are two large classes of cryptographic functions, and they

are the most important components of stream ciphers, block ciphers and Hash functions. Their cryptographic

properties are crucial to the security of the underlying ciphers. The resistance against different attacks of

cryptographic algorithms are largely measured by the cryptographic properties of their underlying cryptographic

functions. The differential uniformity measures the resistance against differential attack, the nonlinearity

measures the resistance against linear attack or fast correlation attack, and the algebraic immunity measures the

resistance against algebraic attack, and correlation immunity measures the resistance against correlation attack,

the algebraic degree measures the resistance against Berlekamp Massey attack or higher order differential attack,

where noninearity, algebraic immunity and differential uniformity are three important security criteria of

cryptographic functions. In this paper, we present a survey on the recent progress about cryptographic functions

with low differential uniformity, those with high nonlinearity and those with high algebraic immunity respectively,

with emphasis being on the constructions and the distribution of the functions with high nonlinearity such as Bent

functions and vectorial Bent functions; construction of Boolean functions and vectorial functions with optimum

algebraic immunity and good cryptographic properties; properties and constructions of the functions with low

uniformity such as perfect nonlinear functions, almost perfect nonlinear functions, 4-uniform functions. We also

propose some research problems on these criteria.

Key words: cryptographic functions; nonlinearity; differential uniformity; algebraic immunity

1 引言

密码函数包含布尔函数与向量函数(S-盒)两大类, 是构成序列密码、分组密码和Hash函数这三类密

码算法的重要组件, 其密码学性质的好坏直接关系到基于该组件设计的密码算法的安全性[1–3], 相应的密

码算法对于各种已知攻击的抵抗性可以由它所使用的密码函数的相应密码学指标来衡量, 比如密码函数

的差分均匀度反映了其抵抗差分攻击的能力, 密码函数的非线性度反映了其抵抗线性攻击或快速相关攻

击的能力, 密码函数的代数免疫度反映了其抵抗代数攻击的能力, 密码函数的相关免疫度反映了其抵抗相

关攻击的能力, 密码函数的代数次数反映其抵抗Berlekamp Massey攻击或高阶差分攻击的能力等. 设计密

码算法中采用的函数必须综合考虑这些不同的安全性指标, 比如对于SPN型分组密码, 其使用的密码函数

要求满足低差分均匀度、高非线性度、高代数次数等性质; 对于组合序列密码, 其使用的密码函数需要满

足高非线性度、高代数次数、高代数免疫度、高阶弹性等性质. 但由于这些安全性指标之间存在着制约关

系, 因此研究这些制约关系以及构造同时使这些安全性指标折衷最优的密码函数就是一件很重要很有意

义的工作. 另外, 密码函数在编码和通信领域中也有广泛应用, 比如满足特定性质的密码函数可以用来构

造性能优良的纠错码和跳频码[4,5], 并且所构造的码参数与原有密码函数的非线性度等安全性指标密切

相关.

本文总结了密码函数研究方面近年来的主要研究进展. 全文结构如下: 第1节介绍密码函数安全性指

标的研究意义, 第2、3、4节分别讨论了低差分函数、高度非线性函数和高代数免疫度函数研究方面的进

展, 第5节是本文的总结与展望. 另外需要指出的是, 篇幅所限, 本文没有涉及弹性函数(相关免疫函数)、

满足全局雪崩准则的密码函数、一般有限域上逻辑函数等方面的研究内容, 对于这几个方面研究感兴趣的,

可以参阅文献[6–11]及其中的参考文献.

本节最后介绍密码函数的一些基本概念.

布尔函数: 一个n元布尔函数f为一个从F2n到F2的映射(F2为二元有限域), 通常用如下形式表示:

580 Journal of Cryptologic Research 密码学报 Vol.1, No.6, Dec. 2014

f x1,x2, ,xn a0 aixi

i 1n1 i1 id n ai1, ,idxi xi a1, ,nx1x2 xn (1)1d

其中系数a0,ai,ai,j, ,a1, ,n F2.

代数正规型(ANF): 上述式(1)的表示形式称之为f的代数正规型.

代数次数: 记为deg f ,是代数正规型中系数非零项所含有变元个数的最大值.

仿射函数: 代数次数小于等于1的布尔函数.

Hamming重量: 使得f x 取值为1的向量x F2n的个数, 记为wt f .

Walsh谱: 定义在F2n上的一个实值函数, 用如下形式表示:

Wf

x x1,x2, ,xn F2 1 nfx 1 i n x , , , , 12n ii

2 高度非线性函数

线性攻击是攻击迭代分组密码最有效的方法之一. 线性攻击的基本思想是通过寻找密码算法有效的线性近似表达式来破译密码系统. 一个密码算法抵抗线性攻击的能力与其采用的密码函数抵抗线性攻击的能力密切相关, 而衡量该能力的密码学指标被称为非线性度, 布尔函数的非线性度NL f 定义为其与仿射函数的最小Hamming距离, 其与Walsh谱有如下联系:

1NL f 2n 1 max Fnf 22

非线性度越大, 表明这个函数与仿射函数的距离就越远, 抵抗线性攻击的能力也就越强. 对一个n元布尔函数, 有NL f 2n 1 2n2 1.若f的非线性度达到该最大值, 则称其为Bent函数, n元Bent函数存在当且仅当n为偶数. 对 n,m -向量函数F,同样有NL f 2n 1 2n2 1.若F的非线性度达到该最大值, 则称其为向量Bent函数. n,m 向量Bent函数存在当且仅当n为偶数且m n2.当m n时, 对 n,n -函数F,有NL f 2n 1 2 n 1 ,达到该最大值的函数称为几乎Bent函数(almost Bent function, AB函数). 显然n元AB函数仅在n为奇数时存在. 目前仍不清楚当n为偶数时, 一个 n,n -函数所能达到的最大非线性度是多少? 人们猜想该值为2n 1 2n,达到该界的 n,n -函数也被称为具有已知最优非线性度.

Bent(布尔)函数、向量Bent函数、几乎Bent函数分别是特定条件下达到最高非线性度的函数, 在密码

编码学、组合学等理论, 人们给出了Bent函数的各种推广、学研究中受到最多关注. 事实上, 基于密码学、

变种以及子类. 篇幅所限, 这里只论述Bent函数和向量Bent函数的研究进展, 并且限定在特征为2的域上, 对Bent函数的其它推广和变种感兴趣的请参考文献[12].

编码以及组合学研究中都受到了较多关 注, Bent函数的概念由Rothaus于1976年提出[13], 它在密码、

这是因为: 从密码学看, 它是非线性度最优的布尔函数, 还具有完全非线性, 因此是抗击线性、差分密码攻击的最优布尔函数; 从编码角度看, 它达到了一阶Reed-Muller码的覆盖半径(所谓的“Deep hole”[13]); 从组合学角度看, 它还与Hadamard矩阵、差集等组合对象有着十分密切的联系. 目前人们仍不清楚Bent函数的一般结构, 而Bent函数的等价分类更是一个十分困难的问题. 近十余年人们致力于构造新的Bent函数, 尤其是基于迹函数表示理论(多项式表示理论)的构造. 事实上, 2004年以前, 人们主要关注基于代数正规型的Bent函数构造, Maiorana-McFarland构造和PS构造(Partial Spread构造, 也称为Dillon构造)是最主要

屈龙江 等: 密码函数安全性指标的研究进展 581

的两种构造方法, 构造的Bent函数最多[1]. 2004年Dillon和Dobbertin给出了Kasami函数为Bent函数的充要条件[14], 2006年Canteaut等在该类函数中找到了第一个非正规(non-normal)Bent函数[15], 而后者的存在性是一个多年的公开问题. 这些工作激起了人们使用多项式表示方法研究Bent函数的兴趣, Leander函数[16,17]、Canteaut-Charpin-Kyureghyan函数[18]随后分别在2006年、2008年被发现. 除了单项式Bent函数外, 二次多项式Bent函数、基于Niho指数的多项式Bent函数、基于Dillon指数的多项式Bent函数也相继被构造出来, 详见文献[19]及其中的参考文献. Niho指数和Dillon指数得到较多研究的原因是, 前者限制在指标为2(注意: 这里是index 2, 是指域扩张次数为2, 而不是特征为2. )的子域上是个仿射函数, 而后者限制在该子域上得到的特殊函数可以由Kloosterman和Dickson多项式等理论计算. 在多项式表示的Bent函数构造研究中, 用到的主要理论和技术包括指数和理论——尤其是Kloosterman和理论, Dickson多项式理论, Dobbertin的多变元方法, 偶扩张的表示方法等. 人们利用类似的技术研究了Bent函数的子类regular-Bent函数和Hyper-Bent函数、推广semi-Bent函数等, 提出了许多新的构造, 详见文献[20–22]及其中的参考文献. 另外, 2011年Langevin和Leander计算出8元Bent函数的个数[23], 他们的结果表明, 所有仿射等价于Maiorana-McFarland型或Dillon型的Bent函数在全体Bent函数中只占微不足道的一部分. 这表明人们对于Bent函数的认识还不深, 给出Bent函数新的一般构造或者新的有效刻画是一个很有价值的问题.

在向量Bent函数研究方面, 1991年Nyberg首先研究向量Bent函数的构造, 提出了Maiorana-McFarland构造和PS构造两种主要构造方法[24]. 1999年Satoh等人改进了文献[24]中的第一种构造, 使得构造函数可以达到最优代数次数[25]. 2010年Carlet和Mesnager在文献[26]中系统总结了向量Bent函数的已有构造, 并给出了一些新的构造. 从文献[26]可以看出, 向量Bent函数的研究结果不如Bent函数丰富, 比如Bent函数构造中有许多从低维函数构造高维函数的二次构造, 但是向量Bent函数的二次构造要少得多, 尤其是不能构造出输出维数最大的向量Bent函数. 2013年董德帅等构造了两类单项式型的向量Bent函数和一类基于PS类Bent函数的构造, 构造函数均可以达到最大代数次数[27]. 2014年Muratovic-Ribic等给出了多项式型向量Bent函数的一些新构造, 构造函数的输出维数可以达到最大[28].

在人们关注密码函数的高非线性度方面研究的同时, 关于密码函数非线性度的一些扩展概念相继被提出, 如高阶非线性度(定义为密码函数与一个低代数次数函数的最小距离)、无限制非线性度(定义为密码函数与一个非常值布尔函数复合后函数的非线性度)、以及广义非线性度(能抵抗广义相关攻击的函数)等, 篇幅所限, 本文不作详细论述, 感兴趣的读者请参考文献[29–31].

3 代数免疫度

代数攻击的提出和发展被认为是近年来密码分析技术最重要的突破之一. 代数攻击通过求解超定的多变元方程组来获得密钥. 给定密码算法中使用的一个布尔函数f,代数攻击的关键是找到f或者1 f的次数最低的非零零化子. 代数攻击深刻地改变了密码算法中使用的密码函数的设计要求, 增加了一个新的设计准则叫做“代数免疫度”(algebraic immunity, AI). n元布尔函数f的代数免疫度AI f 是使得gf 0或g f 1 0成立的非零n元布尔函数g的最小代数次数. 这个概念由Meier于2004年首先提出[32], 提出后即受到密码学界的深刻关注. Dalai紧跟着研究了代数免疫度和原有密码学性质的关联和制约[33]. 之后, Carlet进一步给出了代数免疫度与非线性度的关系式[34].

文献[32]中证明了对任意n元布尔函数, 其代数免疫度的最大值为 n .构造具有最大代数免疫度(maximum algebraic immunity, MAI)的布尔函数受到越来越多学者的关注. 2005年Dalai首先从零化子的概

582 Journal of Cryptologic Research 密码学报 Vol.1, No.6, Dec. 2014

念出发, 提出了基于支撑包含关系的MAI函数构造方法, 然后研究了所构造函数的非线性度、代数次数等性质[35]. 2007年Carlet提出了一种“平面理论”方法来构造具有特定代数免疫度的布尔函数[36]. 基于该方法, Carlet与曾祥勇等人构造了几类具有较高非线性度的MAI函数[37]. 屈龙江和李娜等提出基于“交换基”技术来构造MAI函数的方法, 并给出了MAI函数计数的首个理论下界[38]. 李娜和戚文峰把奇数元MAI布尔函数的构造与寻求一个列满秩矩阵关联起来, 从而得到了一类具有较优非线性度的奇数元MAI函数[39], 刘美成与裴定一等进一步用矩阵理论给出了偶数元布尔函数为MAI函数的充要条件[40]. 2008年Carlet和冯克勤构造了著名的Carlet-Feng函数, 利用BCH界证明了其为MAI函数, Carlet-Feng函数还具有最优代数次数和远高于以往构造的非线性度, 而且数值实验表明, 它们还具有较好的抵抗快速代数攻击能力[41]. Carlet-Feng函数简单的结构和优良的性质激发了人们使用迹表示理论研究MAI函数构造的兴趣, 得到了一系列结果. 首先王启春等用本原多项式为工具重新考察了Carlet-Feng函数, 给出了其非线性度更好的下界[42]. Rizomiliotis进一步分析了Carlet-Feng函数, 构造了几类新的平衡MAI函数, 并且提出了一个较有效的矩阵方法来分析这些函数的抵抗快速代数攻击能力[43]. 曾祥勇等利用Rizomiliotis的矩阵方法, 通过修改Carlet-Feng函数构造了三类MAI函数, 构造函数具有与Carlet-Feng函数类似的良好性质[44]. J. Li等进一步推广了Rizomiliotis的矩阵方法, 给出了抗代数攻击的MAI函数的两种新构造, 构造函数同样具有良好的非线性度和较强的抵抗快速代数攻击的能力[45].

涂自然等结合Carlet-Feng函数和一类PS型Bent函数构造了一类具有高非线性度的函数, 其代数免疫度的最优性依赖于一个组合猜想——Tu-Deng猜想的正确性, 他们构造了一类具有很高非线性度的偶数元平衡MAI函数[46], 利用该猜想, 他们还构造了一类1阶弹性的代数免疫度次优的布尔函数[47]. 但是与Carlet-Feng函数不同, Tu-Deng函数不具有较好的抵抗快速代数攻击能力. 2010年唐小虎等人结合PS型Bent函数与Dobbertin构造的思想, 给出了平衡的偶数元MAI函数的构造, 并且这类函数的非线性度优于以往所有结果[48]. 受Tu-Deng函数启发, 唐灯等提出了一个新的组合猜想(该猜想很快由Cohen等证实), 并基于其构造了两类具有很高非线性度的MAI函数, 这些函数(称为Tang-Carlet-Tang函数)还具有较好的抵抗快速代数攻击能力[49]. 2012年, Pasalic和韦永壮通过在射影几何空间中选取合适的平面来构造高非线性MAI函数[50].

与代数攻击使用两边乘以非零低次函数的方程组不同, 快速代数攻击使用经过线性组合的方程组. 为了抵抗快速代数攻击, 希望布尔函数f满足: 对于任意满足e d n和e n2的正整数对 e,d ,不存在次数不超过e的非零函数g使得fg的次数不超过d.满足该条件的函数称为完全代数免疫函数(perfect algebraic immune function, PAI函数). 构造PAI函数成为近十年一个很重要的研究问题. 开始人们只能得到一些负面结果: 2009年刘美成等证明对称布尔函数具有较差的快速代数免疫性, 不可能为PAI函数[51]. Y. Zhang等进一步证明大部分偶数元旋转对称布尔函数不可能为PAI函数[52]. 2012年刘美成等人给出了PAI函数存在性的完整回答: n元PAI函数存在当且仅当n 2m或2m 1,并且证明了Carlet-Feng函数为PAI函数或几乎PAI函数[53]. 随后他们进一步考察了MAI函数的已有构造, 证明了Tang-Carlet-Tang函数也为PAI函数或几乎PAI函数[54].

Courtious、Nawaz等人讨论了从基于幂函数的向量函数可以建立的方程的数目和类型, 特别是线性独立方程、二次方程等较容易求解的方程, 以此来刻画向量函数对代数攻击的抵抗能力即向量函数的代数免疫度[55,56]. 2006年, Armknecht首先把布尔函数的代数免疫度概念推广到集合的代数免疫度上, 并进一步利用函数映射集给出向量函数的基本代数免疫度和图形代数免疫度的定义, 他还运用组合数学中的拟阵理论对基本代数免疫度较高的向量函数的构造做了初步探讨[57]. 之后, 文献[58]给出了向量函数的组件代数

屈龙江 等: 密码函数安全性指标的研究进展 583

免疫度的定义. 2009年, Carlet和冯克勤给出了一类具有最优基本代数免疫度、最优代数次数的向量函数的构造, 该构造的向量函数同时具有较高的非线性度[59]. 2011年冯克勤和杨晶将Tu-Deng函数的构造思想推广到向量函数, 构造了一类具有高基本代数免疫度的向量Bent函数和一类同时具有高基本代数免疫度和高非线性度的平衡向量函数[60]. 董德帅等利用文献[43]中的构造思想, 将文献[60]的构造推广, 得到的新构造具有更高的非线性度[61]. Y. Lou等利用群分解的方法, 构造了一类具有最优(几乎最优)基本代数免疫度且其他密码学性质良好的向量函数[62].

4 低差分函数

差分攻击是攻击迭代分组密码最有效的方法之一. 差分攻击的基本思想是通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特. 一个密码算法抵抗差分攻击的能力与其采用的密码函数抵抗差分攻击的能力密切相关, 而后者可以用差分均匀度来衡量. 设F为有限域Fq到其自身的映射, 则其差

分均匀度定义为:

F max#x FqF x a F x b *a Fq,b Fq

若 F t,则称F为t-差分(一致性)函数. 特别地, 若 F 1,则称其为完全非线性函数(perfect nonlinear

function, PN函数); 若 F 2,则称其为几乎完全非线性函数(almost perfect nonlinear function, APN函数).

一个密码函数的差分均匀度越小, 其抵抗差分攻击的能力就越强. 有限域Fq上的低差分函数主要包

括完全非线性函数, 几乎完全非线性函数和差分均匀度为4的函数(4-uniform function, 4-差分函数)等. 当有限域的特征为奇数时, PN函数、APN函数分别达到最优、次优的差分均匀度; 而在偶特征的有限域上, 差分均匀度必然为偶数, 此时APN函数、4-差分函数分别达到最优、次优的差分均匀度. 由于绝大多数密码算法用的密码函数是定义在偶特征有限域上的, 所以在密码研究中, APN函数、4-差分函数受到了更多关注. 但是需要注意的是, PN函数、APN函数和4-差分函数等低差分函数之间有着十分紧密的联系, 很多构造是相互启发的.

新的低差分函数的构造是密码函数研究中的重要问题, 它涉及到这些函数之间的等价性问题. 最主要的等价性有两个: CCZ等价和EA等价. 设F,G为两个Fq到自身的函数, 若存在仿射置换函数l1,l2和仿射函数l3,使得F l1 G l2 l3,则称F和G扩展仿射等价(extended affine equivalent, EA等价). 函数F的图

定义为 x,F x :x F ,若两个函数的图仿射同构, 则称这两个函数qCCZ等价(Carlet-Charpin-Zinoviev

equivalent, CCZ等价).

容易验证EA等价意味着CCZ等价; 但是反之不然. CCZ等价保持函数的差分均匀度和非线性度(更准确地说, 是保持函数的扩展Walsh谱), 而EA等价还保持代数次数(如果函数的代数次数 2). 一般而言, 在理论上证明两个无限函数类是否CCZ等价是一个非常困难的问题, 而判断EA等价则要简单许多. 近年来, 关于CCZ等价和EA等价的关系得到了较多研究, 主要的突破是人们证明了在很多情况下, CCZ等价和EA等价是一致的, 这些成果包括: (1) 2008年Kyureghyan和Pott对于平面函数(完全非线性 n,n -函数)的结果[63]; (2) 2009年Budaghyan和Carlet对于布尔函数的结果[64]; (3) 2011年Budaghyan和Carlet关于向量Bent函数的结果[65]; (4) 2012年Yoshiara证明了Edel的猜想: 两个代数次数为2(以下简称二次)的APN函数CCZ等价当且仅当它们EA等价[66]. 由于在理论上分析不同函数之间的CCZ等价性非常困难, 实践上人们一般通过计算机计算一些CCZ等价不变量, 比如差分均匀度、扩展Walsh谱、 -秩、 -秩和各种

584 Journal of Cryptologic Research 密码学报 Vol.1, No.6, Dec. 2014

形式的自同构群等. 如果两个函数有不同的CCZ等价不变量, 则它们一定不等价; 反之则不能判断. 另外, 一个无限函数类的差分均匀度、扩展Walsh谱等CCZ等价不变量的有效计算研究在理论上和应用上都是很有意义的, 特别是扩展Walsh谱的计算. 这是因为: 由APN函数可以构造性能优良的线性码[1], 并且APN函数的扩展Walsh谱对应于该线性码的重量分布, 而线性码的重量分布是线性码的一个重要参数, 利用其可以有效计算译码算法的错误概率.

2005年以前, 低差分函数的研究主要集中于有限域上的幂函数(单项式), 主要构造包括2类(不等价的)PN幂函数(Demobowski-Ostrom幂函数, Coulter-Mattews函数), 6类(不等价的)APN幂函数(Gold函数, Kasami函数, Welch函数, Niho函数, 逆函数和Dobbertin函数). Dobbertin猜测“APN幂函数只有这6类”. 2011年Hernando和McGuire在该猜想上取得了重要进展, 他们运用代数几何的理论证明了exceptional指数(即使得xd在无穷多个域上为APN函数的指数d)只有Gold指数和Welch指数[67], 但整个Dobbertin猜测仍未解决. 2006年以后, 人们陆续发现了一些多项式形式的二次PN函数和二次APN函数. 二次PN函数又称为Demobowski-Ostrom型(DO型)PN函数, 其在代数上等价于一个有限交换(预)半域. 周悦和Pott在文献[68]中列出了2011年之前所有已知的交换半域(即二次PN函数), 并且构造了一个含两个参数的交换半域族, 进一步类似构造了一族二次APN函数. 具体到二次APN函数的构造, 2006年人们首先发现F26上的一个CCZ不等价于所有幂函数的APN二项式[69], 随后该二项式被推广为一个无限类, 接着人们发现了更多二次APN函数无限类, 其中文献[70]列出了2011年前的所有构造, 并且构造了一个含两个参数的APN函数族. 2011年Carlet研究了向量函数三种非线性度度量之间的关系, 并进一步利用向量Bent函数构造二次APN函数[71], 论文中得到的一大类构造涵盖了以往的许多构造. 另外, 目前所有二次APN函数族的Walsh谱都得到了计算, 结果表明, 这些函数都具有与Gold函数相同的Walsh谱, 即当n为奇数时为三谱值, 而当n为偶数时为五谱值[72,73].

为了避免熵泄露, 一般要求分组密码中使用的向量函数是个置换; 而(同时)为了软硬件实现时具有较高的效率, 又希望其定义在二元域的偶数维扩域(偶数维扩张, 以下简称偶扩张)上. 于是寻找偶扩张上的APN置换就成为了密码研究中的一个重要问题, 该问题被称为“大APN问题”. 很长一段时间里, 人们只能得到关于该问题的一些负面结果, 比如Seberry等人指出, 要构造出这样的APN置换, 不能从二次函数中寻找[74]; 而Carlet等指出, 幂函数中也不可能有这样的APN置换[75]; E. Pasalic、P. Charpin和李永强、王明生分别指出某些形如一个幂函数和一个线性函数的和函数不可能为APN置换[76–78]. 2009年Dillon和Wolfe通过分解一个APN函数所对应的线性码, 找到了F26上的一个APN置换[79]. 但是, 他们的方法并没

有发现偶扩张上的其它APN置换, 整个“大APN问题”仍然是公开的. 由于缺乏偶扩张上的APN置换, 密码算法S-盒设计的一个自然选择就是使用4-差分置换, 比如著名的AES算法的S-盒使用了F28上的逆函

数, 它就是一个4-差分置换. 近年来4-差分置换的研究受到较多关注, 人们给出了一系列新的构造. 2011年Carlet回顾了低差分函数研究进展, 并且提出了一种利用奇扩张上APN置换来构造偶扩张上 4-差分置换的方法[80]. C. Bracken等在文献[81]中利用APN函数构造了一类新的4-差分置换, 使得已知的F22k上的4-差分置换达到了5类, 并且它们全都达到了已知最优非线性度. 李永强等对该方法进行

了进一步研究, 从Gold函数出发, 成功地构造了一类偶扩张上的具有已知最优非线性度的4-差分置 换[82]. 2013年我们和合作者使用交换构造法(switching construction)研究了逆函数, 先后提出了优先函数、优先布尔函数等概念, 并且以它们为工具构造了偶扩张上大量的CCZ不等价的具有最优代数次数的4-差分置换族[83,84], 进一步在理论上证明了F22k上4-差分置换的个数是随着变元个数增长而呈指数

增长的, 这极大地扩展了该类函数. 受上述工作的启发, 查正邦、唐灯等学者进一步研究了逆函数的交

屈龙江 等: 密码函数安全性指标的研究进展 585

换构造法或者提出不同的修改方法, 构造了一些新的4-差分置换, 这些新置换大多具有最优代数次数, 其中一些子类还具有已知最优非线性度[85–87].

5 总结与展望

综上所述, 近年来国内外学者在密码函数的安全性指标研究方面已经取得了许多重要的结果, 但仍有许多问题亟需进一步的研究. 例如尽管人们已经构造了一些单项式PN函数、APN函数, 二次PN函数、APN函数, 但是一些基本的问题仍不清楚: 比如“Dobbertin猜想”是否成立, 即APN幂函数是否只有6类? 如何构造一个(CCZ等价意义下)非二次的多项式PN函数和APN函数? 又如, “大APN问题”, 即一般偶扩张上是否存在APN置换的问题, 还远没有解决等等. 另外, 人们虽然已经给出了Bent函数和向量Bent函

结构与分布仍有许多基本的问题并不清楚, 需要进一步研究. 还有, 在代数的很多构造, 但是关于其性质、

数免疫度研究方面, 虽然2012年抵抗快速代数攻击的完全代数免疫布尔函数的存在性问题得到了解决, 但是其构造还很少; 向量函数的代数免疫度研究方面的结果也比较少. 最后, 多种密码学指标折衷最优的布尔函数或向量布尔函数的构造还很匮乏, 亟需丰富. 所有这些问题都值得我们继续深入研究.

References

[1] Carlet C, Boolean Functions for Cryptography and Error Correcting Codes, Chapter of the Monography Boolean Models and

Methods in Mathematics, Computer Science, and Engineering[M]. Cambridge University Press, 2010.

[2] Carlet C. Vectorial Boolean functions for cryptography[J]. Boolean Models and Methods in Mathematics, Computer Science, and

Engineering, 2010, 134: 398–469. [3] Cusick T W, Stanica P. Cryptographic Boolean Functions and Applications[M]. Academic Press, 2009.

[4] 李超, 屈龙江, 周悦. 密码函数的安全性指标分析[M]. 北京: 科学出版社, 2011.

[5] Carlet C, Charpin P, Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems[J]. Designs, Codes

and Cryptography, 1998, 15(2): 125–156.

[6] Zhang W G, Pasalic E. Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and

good algebraic properties[J]. IEEE Transactions on Information Theory, 2014, 60(10):6681–6695.

[7] Zhang W, Pasalic E. Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes[J],

IEEE Transactions on Information Theory, 2014, 60(3): 1638–1651.

[8] Zhou Y. On Cryptographic Properties of Boolean Functions[D]. Doctor 's Degree, Xidian University, 2009.

周宇. 布尔函数的密码学性质研究[D]. 博士学位论文, 西安电子科技大学, 2009

[9] 温巧燕, 钮心忻, 杨义先. 现代密码学中的布尔函数[M]. 北京: 科学出版社, 2000.

[10] 冯登国. 频谱理论及其在密码学中的应用[M]. 北京: 科学出版社. 2000.

[11] 李世取, 曾本胜, 廉玉忠, 等. 密码学中的逻辑函数[M]. 北京: 北京中软电子出版社, 2003.

[12] Tokareva N N. Nonlinear Boolean Functions: Bent Functions and Their Generalizations[M]. Saarbrucken: LAP Lambert

Academic Publishing, 2011.

[13] Rothaus O S. On “Bent” functions[J]. Journal of Combinatorial Theory, Series A, 1976, 20(3): 300–305.

[14] Macwilliams F J, Sloane N J A. The Theory of Error-Correcting Codes[M]. Amsterdam: AMC, 1977.

[15] Dillon J F, Dobbertin H. New cyclic difference sets with Singer parameters[J]. Finite Fields and Their Applications, 2004, 10(3):

342–389.

[16] Canteaut A, Daum M, Dobbertin H, et al. Finding non-normal Bent functions[J]. Discrete Applied Mathematics, 2006, 154(2):

202–218.

[17] Leander N G. Monomial bent functions[J]. IEEE Transactions on Information Theory, 2006, 52(2): 738–743.

[18] Canteaut A, Charpin P, Kyureghyan G M. A new class of monomial bent functions[J]. Finite Fields and Their Applications, 2008,

14(1): 221–241.

[19] Mesnager S. Several new infinite families of Bent functions and their duals[J]. IEEE Transactions on Information Theory, 2014,

60(7): 4397–4407.

[20] Li N, Helleseth T, Tang X. New constructions of quadratic Bent functions in polynomial form[J]. IEEE Transactions on

Information Theory. DOI: 10.1109/TIT.2014.2339861.

586 Journal of Cryptologic Research 密码学报 Vol.1, No.6, Dec. 2014

[21] Charpin P, Gong G. Hyperbent functions, Kloosterman sums, and Dickson polynomials[J]. IEEE Transactions on Information

Theory, 2008, 54(9): 4230–4238.

[22] Mesnager S, Flori J P. Hyperbent functions via Dillon-like exponents[J]. IEEE Transactions on Information Theory, 2013, 59(5):

3215–3232.

[23] Langevin P, Leander G. Counting all bent functions in dimension eight 9927058926593437030578586124288[J]. Designs, Codes

and Cryptography, 2011, 59(1-3): 193–205.

[24] Nyberg K. Perfect nonlinear S-boxes[C]. In: Advances in Cryptology—EUROCRYPT '91. Springer Berlin Heidelberg, 1991:

378–386.

[25] Satoh T, Iwata T, Kurosawa K. On cryptographically secure vectorial Boolean functions[C]. In: Advances in Cryptology—

ASIACRYPT '99. Springer Berlin Heidelberg, 1999: 20–28.

[26] Carlet C, Mesnager S. On the construction of bent vectorial functions[J]. International Journal of Information and Coding Theory,

2010, 1(2): 133–148.

[27] Dong D, Zhang X, Qu L, et al. A note on vectorial bent functions[J]. Information Processing Letters, 2013, 113(22): 866–870.

[28] Muratovic-Ribi´c A, Pasalic E, Bajri´S S. Vectorial Bent functions from multiple terms trace functions[J]. IEEE Transactions on

Information Theory, 2014, 60(2): 1337–1347.

[29] Carlet C. On the higher order nonlinearities of Boolean functions and S-boxes, and their generalizations[C]. In: Sequences and

Their Applications—SETA 2008. Springer Berlin Heidelberg, 2008: 345–367.

[30] Carlet C, Prouff E. On a new notion of nonlinearity relevant to multi-output pseudo-random generators[C]. In: Selected Areas in

Cryptography—SAC 2003. Springer Berlin Heidelberg, 2004: 291–305.

[31] Carlet C, Khoo K, Lim C W, et al. Generalized correlation analysis of vectorial Boolean functions[C]. In: Fast Software

Encryption—FSE 2007. Springer Berlin Heidelberg, 2007: 382–398.

[32] Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions[C]. In: Advances in

Cryptology—EUROCRYPT 2004. Springer Berlin Heidelberg, 2004: 474–491.

[33] Dalai D K, Gupta K C, Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions[C]. In:

Progress in Cryptology—INDOCRYPT 2004. Springer Berlin Heidelberg, 2005: 92–106.

[34] Carlet C. On the higher order nonlinearities of algebraic immune functions[C]. In: Advances in Cryptology-CRYPTO 2006.

Springer Berlin Heidelberg, 2006: 584–601.

[35] Dalai D K, Maitra S, Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity[J].

Designs, Codes and Cryptography, 2006, 40(1): 41–58.

[36] Carlet C. A method of construction of balanced functions with optimum algebraic immunity[J]. IACR Cryptology ePrint Archive,

2006, 2006: 149.

[37] Carlet C, Zeng X, Li C, et al. Further properties of several classes of Boolean functions with optimum algebraic immunity[J].

Designs, Codes and Cryptography, 2009, 52(3): 303–338.

[38] Li N, Qu L J, Qi W F, et al. On the construction of Boolean functions with optimal algebraic immunity[J]. IEEE Transactions on

Information Theory, 2008, 54(3): 1330–1334.

[39] Li N, Qi W F. Construction and analysis of Boolean functions of 2t+1 variables with maximum algebraic immunity[C]. In:

Advances in Cryptology—ASIACRYPT 2006. Springer Berlin Heidelberg, 2006: 84–98.

[40] Liu M C, Pei D Y, Du Y S. Identification and construction of Boolean functions with maximum algebraic immunity[J]. Science

China Information Sciences, 2010, 53(7): 1379–1396.

[41] Carlet C, Feng K. An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks

and good nonlinearity[C]. In: Advances in Cryptology—ASIACRYPT 2008. Springer Berlin Heidelberg, 2008: 425–440.

[42] Wang Q, Peng J, Kan H, et al. Constructions of cryptographically significant Boolean functions using primitive polynomials[J].

IEEE Transactions on Information Theory, 2010, 56(6): 3048–3053.

[43] Rizomiliotis P. On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation[J].

IEEE Transactions on Information Theory, 2010, 56(8): 4014–4024.

[44] Zeng X, Carlet C, Shan J, et al. More balanced Boolean functions with optimal algebraic immunity and good nonlinearity and

resistance to fast algebraic attacks[J]. IEEE Transactions on Information Theory, 2011, 57(9): 6310–6320.

[45] Li J, Carlet C, Zeng X, et al. Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity

and good behavior against fast algebraic attacks[J]. Designs, Codes and Cryptography, 2014: 1–27.

[46] Tu Z, Deng Y. A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic

immunity[J]. Designs, Codes and Cryptography, 2011, 60(1): 1–14.

[47] Tu Z, Deng Y. Boolean functions optimizing most of the cryptographic criteria[J]. Discrete Applied Mathematics, 2012, 160(4):

427–435.

屈龙江 等: 密码函数安全性指标的研究进展 587

[48] Tang X, Tang D, Zeng X, et al. Balanced Boolean functions with (almost) optimal algebraic immunity and very high

nonlinearity[J]. IACR Cryptology ePrint Archive, 2010, 2010: 443.

[49] Tang D, Carlet C, Tang X. Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast

algebraic attacks[J]. IEEE Transactions on Information Theory, 2013, 59(1): 653–664.

[50] Pasalic E, Wei Y. On the construction of cryptographically significant Boolean functions using objects in projective geometry

spaces[J]. IEEE Transactions on Information Theory, 2012, 58(10): 6681–6693.

[51] Liu M, Lin D, Pei D. Fast algebraic attacks and decomposition of symmetric Boolean functions[J]. IEEE Transactions on

Information Theory, 2011, 57(7): 4817–4821.

[52] Zhang Y, Liu M, Lin D. On the immunity of RSBFs against fast algebraic attacks[J]. Discrete App, 2014, 162(3): 17–27.

[53] Liu M, Zhang Y, Lin D. Perfect algebraic immune functions[C]. In: Advances in Cryptology—ASIACRYPT 2012. Springer

Berlin Heidelberg, 2012: 172–189.

[54] Liu M, Lin D. Almost Perfect Algebraic Immune Functions with Good Nonlinearity[R]. Cryptology ePrint Archive, report

2012/498, 2012.

[55] Courtois N T, Debraize B, Garrido E. On exact algebraic [non-] immunity of S-boxes based on power functions[C]. In:

Information Security and Privacy—ACISP 2006. Springer Berlin Heidelberg, 2006: 76–86.

[56] Nawaz Y, Gupta K C, Gong G. Algebraic immunity of S-boxes based on power mappings: analysis and construction[J]. IEEE

Transactions on Information Theory, 2009, 55(9): 4263–4273.

[57] Armknecht F, Krause M. Constructing single-and multi-output Boolean functions with maximal algebraic immunity[C]. In:

Automata, Languages and Programming. Springer Berlin Heidelberg, 2006: 180–191.

[58] Ars G and Faugere J. Algebraic immunities of functions over finite fields[J]. Boolean Functions Cryptography and Applications,

2005: 21–38.

[59] Carlet C, Feng K. An infinite class of balanced vectorial Boolean functions with optimum algebraic immunity and good

nonlinearity[C]. In: Coding and Cryptology. Springer Berlin Heidelberg, 2009: 1–11.

[60] Feng K, Yang J. Vectorial Boolean functions with good cryptographic properties[J]. International Journal of Foundations of

Computer Science, 2011, 22(06): 1271–1282.

[61] Dong D, Qu L, Fu S, et al. New constructions of vectorial Boolean functions with good cryptographic properties[J]. International

Journal of Foundations of Computer Science, 2012, 23(03): 749–760.

[62] Lou Y, Han H, Tang C, et al. Constructing vectorial Boolean functions with high algebraic immunity based on group

decomposition[J]. International Journal of Computer Mathematics, 2014 (just-accepted): 1–13.

[63] Kyureghyan G M, Pott A. Some theorems on planar mappings[C]. In: Arithmetic of Finite Fields. Springer Berlin Heidelberg,

2008: 117–122.

[64] Budaghyan L, Carlet C. CCZ-equivalence and Boolean functions[J]. IACR Cryptology ePrint Archive, 2009, 2009: 63.

[65] Budaghyan L, Carlet C. CCZ-equivalence of bent vectorial functions and related constructions[J]. Designs, Codes and

Cryptography, 2011, 59(1-3): 69–87.

[66] Yoshiara S. Equivalences of quadratic APN functions[J]. Journal of Algebraic Combinatorics, 2012, 35(3): 461–475.

[67] Hernando F, McGuire G. Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN

functions[J]. Journal of Algebra, 2011, 343(1): 78–92.

[68] Zhou Y, Pott A. A new family of semifields with 2 parameters[J]. Advances in Mathematics, 2013, 234: 43–60.

[69] Edel Y, Kyureghyan G, Pott A. A new APN function which is not equivalent to a power mapping[J]. IEEE Transactions on

Information Theory, 2006, 52(2): 744–747.

[70] Bracken C, Byrne E, Markin N, et al. A few more quadratic APN functions[J]. Cryptography and Communications, 2011, 3(1):

43–53.

[71] Carlet C. Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions[J]. Designs,

Codes and Cryptography, 2011, 59(1-3): 89–109.

[72] Bracken C, Zha Z. On the Fourier spectra of the infinite families of quadratic APN functions[J]. Advances in Mathematics of

Communications, 3(3): 219–226.

[73] Tan Y, Qu L, Ling S, et al. On the Fourier spectra of new APN functions[J]. SIAM Journal on Discrete Mathematics, 2013, 27(2):

791–801.

[74] Seberry J, Zhang X M, Zheng Y. Relationships among nonlinearity criteria[C]. In: Advances in Cryptology—EUROCRYPT '94.

Springer Berlin Heidelberg, 1995: 376–388.

[75] Carlet C, Charpin P, Zinoviev V. Codes, Bent functions and permutations suitable for DES-like cryptosystems[J]. Designs, Codes

and Cryptography, 1998, 15(2): 125–156.

588 Journal of Cryptologic Research 密码学报 Vol.1, No.6, Dec. 2014

[76] Li Y, Wang M. On EA-equivalence of certain permutations to power mappings[J]. Designs, Codes and Cryptography, 2011, 58(3):

259–269.

[77]

Li Y, Wang M. Permutation polynomials EA-equivalent to the inverse function over GF(2n)[J]. Cryptography and

Communications, 2011, 3(3): 175–186.

[78] Pasalic E, Charpin P. Some results concerning cryptographically significant mappings over GF(2n)[J]. Designs, Codes and

Cryptography, 2010, 57(3): 257–269.

[79]

Dillon J F. Almost perfect nonlinear polynomials: an update[C]. In: 9th International Conference on Finite Fields and Applications

of Fq9, 2009.

[80] Carlet C. On known and new differentially uniform functions[C]. In: Information Security and Privacy. Springer Berlin Heidelberg,

2011: 1–15.

[81] Bracken C, Tan C H, Tan Y. Binomial differentially 4 uniform permutations with high nonlinearity[J]. Finite Fields and Their

Applications, 2012, 18(3): 537–546.

[82] Li Y, Wang M. Constructing differentially 4-uniform permutations over

Designs, Codes and Cryptography, 2014, 72(2): 249–264.

[83] Qu L, Tan Y, Tan C H, et al. Constructing differentially 4-uniform permutations over

Transactions on Information Theory, 2013, 59(7): 4675–4686.

[84] Qu L, Tan Y, C. Li and Gong G. More constructions of differentially 4-uniform permutations on F22kF22m from quadratic APN permutations over F22m+1[J]. F22kvia the switching method[J]. IEEE [J]. Designs, Codes and

Cryptography, available at /abs/1309.7423.

[85] Zha Z, Hu L, Sun S. Constructing new differential 4-uniform permutations from the inverse function[J]. Finite Fields and Their

Applications, 2014, 25: 64–78.

[86] Tang D, Carlet C, Tang X. Differentially 4-uniform bijections by permuting the inverse function[J]. IACR Cryptology ePrint

Archive, 2013, 2013: 639.

[87] Li Y, Wang M, Yu Y. Constructing differentially 4-uniform permutations over GF(2^2k) from the Inverse Function Revisited[J].

IACR Cryptology ePrint Archive, 2013, 2013: 731.

作者信息

屈龙江(1980–), 博士, 副教授.

主要研究领域为密码学.

E-mail: ljqu_happy@ 付绍静(1984–), 博士, 讲师. 主要研究领域为密码学. E-mail: shaojing1984@

李超(1966–), 博士, 教授, 中国

密码学会理事. 主要研究领域为

密码学.

E-mail: lichao_nudt@

本文来源：https://www.bwwdw.com/article/a0be.html