偶变元严格几乎最优弹性布尔函数的High-Meets-Low构造

High-Meets-Low Construction of Even-Variable Strictly Almost Optimal Resilient Boolean Functions

在用于流密码中的布尔函数设计中,需要考虑两种重要的设计准则:弹性和非线性度,以抵抗相关攻击和最佳仿射逼近攻击.弹性和非线性度之间存在着制约关系,弹性布尔函数的非线性度的紧上界是尚未解决的公开难题.本文利用High-Meets-Low密码函数构造技术,构造出具有偶数个变元的非线性度严格几乎最优的弹性布尔函数.基于已知的具有高非线性度的m元1阶弹性布尔函数,得到非线性度为2^(n−1)−2^(n/2−1)−2^(n/2−m/4)或2^(n−1)−2^(n/2−1)−2^(n/2−(m/2−1)/2)的n元高阶弹性布尔函数.采用所提方法,可以得到一些具有目前已知最高非线性度的高阶弹性布尔函数,这可由两个参数分别为(22,4,2^(21)−2^(10)−29)和(30,4,2^(29)−2^(14)−2^(12))的弹性布尔函数例子得到证实.

In the design of cryptographic Boolean functions used in stream ciphers,it needs to consider two desirable criteria,resiliency and high nonlinearity,in order to resist the correlation attacks and best affine approximation attacks.It is known that,there exists certain tradeoff between resiliency and nonlinearity,and how tight the nonlinearity bound of a resilient Boolean function is remains to be an open problem.This paper addresses the problem of how to construct resilient Boolean functions with as high nonlinearity as possible.By using the High-Meets-Low(HML)construction technique,a large class of even-variable strictly almost optimal resilient Boolean functions are obtained.Based on a known m-variable 1-resilient Boolean function(m is even),an n-variable higher-order resilient Boolean function with nonlinearity 2^(n−1)−2^(n/2−1)−2^(n/2−m/4)or 2^(n−1)−2^(n/2−1)−2^(n/2−(m/2−1)/2)can be constructed.Furthermore,two resilient functions with the best known nonlinearity are found,whose parameters are(22,4,2^(21)−2^(10)−29)and(30,4,2^(29)−2^(14)−2^(12)),respectively.