一种密码函数存在性证明的新方法-尤启迪，张习勇，周旋，吴兆阳，袁野.pdf

上善若水

266

8页

1次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(2):717 [doi: 10.13328/j.cnki.jos.006158] http://www.jos.org.cn

一种密码函数存在性证明的新方法



尤启迪

1,2

张习勇

周

旋

吴兆阳

袁

野

(清华大学计算机科学与技术系, 北京 100084)

(天地一体化信息技术国家重点实验室, 北京 100086)

通信作者: 张习勇, E-mail: xiyong.zhang@hotmail.com

摘要: 密码函数在密码学中具有重要的研究价值. 从组合的角度, 给出了一种密码函数不存在性证明的新方法,

并且得到了一些新结果, 部分结果优于已有结论, 这些结果可以部分证明不存在次数大于 2 的齐次旋转对称 bent

函数这一公开猜想. 同时, 利用多项式的最大公因子算法刻画了 2 次齐次旋转对称 bent 函数. 该方法也可以用于

刻画其他形式的 bent 函数的存在性.

关键词: 旋转对称布尔函数; bent 函数; 傅里叶变换

中图法分类号: TP309

中文引用格式: 尤启迪, 张习勇, 周旋, 吴兆阳, 袁野. 一种密码函数存在性证明的新方法. 软件学报, 2022, 33(2):

717–724. http://www.jos.org.cn/1000-9825/6158.htm

英文引用格式: You QD, Zhang XY, Zhou X, Wu ZY, Yuan Y. New Method for Existence Proof of Some Cryptographic Functions.

Ruan Jian Xue Bao/Journal of Software, 2022, 33(2): 717 (in Chinese). http://www.jos.org.cn/1000-9825/6158.htm

New Met hod for Existence Proof of So me Cryptographic Func tions

YOU Qi-Di

1,2

, ZHANG Xi-Yong

, ZHOU Xuan

, WU Zhao-Yang

, YUAN Ye

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

(State Key Laboratory of Space-Ground Integrated Information Technology, Beijing 100086, China)

Abstra ct : Cryptographic functions have important applications in the research of cryptography. This paper describes a more suitable

approach to prove the nonexistence of some cryptographic functions, and obtain some new results, which support the conjecture that there

are no homogeneous rotation symmetric bent functions of algebraic degree>2. Also, homogeneous degree 2 rotation symmetric bent

functions are characterizedby using GCD of polynomials. The method presented in this paper can also be used to characterize the

existence of other forms of bent functions.

Key words: rotation-symmetric Boolean functions; bent functions; Fourier transform

现代密码学的研究离不开密码函数, 密码函数一般用于构造密码算法的中心部件. 自从 Rothus

[1]

在 20 世

纪 70 年代提出了 bent 函数后, bent 函数在过去的 40 多年有了深入的研究, 并且因其良好的密码学和组合学属

性, 在加密算法和纠错编码中有了广泛的应用. 例如在对称密码中, bent 函数由于具有最大非线性度和差分平

衡一致性, 可抵抗线性攻击和差分攻击, 用来构造密码算法的非线性部件.

近些年来, 齐次旋转对称(简记为 RotS)布尔函数因其理想的性质引起了人们的广泛关注

[24]

. 如: 这种函

数可利用前面循环迭代来快速求值, 所以当密码算法对函数求值的效率要求较高时, 这类旋转对称形式的函

数可以作为密码函数使用, 如 MD4 和 MD5 等消息摘要算法.

由于 bent 函数和旋转对称布尔函数都具有优良的密码学性质, 人们自然会问哪种类型的齐次旋转对称

bent 函数存在. 事实上, 文献[510]对齐次 bent 函数都有研究. 特别重要的是, 最近几年, 文献[1113]给出了

 基金项目: 国家自然科学基金(61572027)

收稿时间: 2020-02-17; 修改时间: 2020-04-29; 采用时间: 2020-09-07; jos 在线出版时间: 2021-08-03

718

软件学报 2022 年第 33 卷第 2 期

旋转对称布尔 bent 函数的几种新构造. Stǎnicǎ 和 Maitra

[6,7]

对变元个数在 10 以内的旋转对称 bent 函数进行了

研究, 他们列举了变元个数为 8 时所有的旋转对称 bent 函数, 发现了 43776 个次数为 2 的函数. 但当变元个

数为 10 时, 并没有发现次数为 3、4 和 5 的齐次旋转对称 bent 函数, 于是他们提出了如下猜想.

猜想 1.1. 不存在次数大于 2 的齐次旋转对称 bent 函数.

我们简要综述与该猜想证明相关的一些已有结果和证明方法. 注意到布尔 bent 函数本质上是 Hadamard

差集, Xia 等人

[8]

证明了对任意的 n>3, 不存在变元个数为 2n 的次数为 n 的齐次 bent 函数. 通过利用一个布尔

函数部分点的傅里叶谱值与其子函数的傅里叶谱值之间的关系, Meng 等人

[9]

得到了关于齐次 bent 函数次数的

一个较低的上界. 在文献[14]中, Carsto 和 Medina 等人利用函数的傅里叶变换的线性递归关系, 给出了特殊的

一类旋转对称布尔函数不是 bent 函数的证明.

定理 1.2. 假设 n 元旋转对称布尔函数 f 的简代数正规型为 x

…x

d1

, d≥5, 则对于充分大的 n, f 不

是 bent 函数.

在文献[10]中, Stǎnicǎ 等人从具有缺项的函数的非线性度出发, 得到了如下的不存在性结论(见第 1 节布

尔函数的简代数正规型表示).

定理 1.3. 假设 n 元齐次旋转对称布尔函数 f 的次数大于 3, 则以下结论成立.

1. 如果 f 的简代数正规型为 x

…x

, 则 f 不是 bent 函数;

2. 如果 f 的简代数正规型为 x

…x

d1

d+1

, 且此时 n、d 满足: 当 n1(mod d)时,

;











当

n=1 (mod d)时,









则 f 不是 bent 函数;

3. 如果 f 的简代数正规型为 ... ,

xx x 则当

/2 1













时, f 不是 bent 函数, 其中,

() () () ()

21 1 2

Max { , 1 | 1, 0,1 ,1 }.

iii i

f i diii j

d iin iuuu u ijin im    满足 ≤ ≤ ≤ ≤

利用更精细的计算取定变元后的子函数的谱值, Meng 等人

[15]

得到了更优的不存在性证明结果.

定理 1.4. 假设 n 元齐次旋转对称布尔函数 f 的次数大于 3, 则以下结论成立.

如果 f 的简代数正规型为单项式 x

, 则 f 不是 bent 函数;

如果 f 的简代数正规型为 ... ,

xx x 则当

d ≤

时, f 不是 bent 函数, 其中,

() () () ()

21 1 2

Max { , 1 | 1, 0,1 ,1 }.

iii i

f i diii j

d iin iuuu u ijin im    ≤≤≤≤

由此可见, 目前不存在性的证明结果离上述猜想的完全证明还有较大的差距. 其实, 利用较深刻的数论

结果, 可以将 bent 函数的问题转化为组合的问题. 本文将从组合的角度出发, 给出一种不同的较适用于研究

齐次旋转对称 bent 函数存在性的方法. 通过利用旋转对称布尔函数的旋转对称形式, 本文的方法可以证明更

多无法通过定理 1.2

定理 1.4 得到的不存在性结果. 例如, 我们的结果表明: 其简代数正规型包含 x

…x

的大

多次数大于等于 3 的齐次旋转对称 bent 函数是不存在的; 当简代正规型满足一定条件时, 其次数具有上界

d ≤

最后, 利用多项式的 GCD 算法, 本文给出了次数为 2 的齐次旋转对称 bent 函数的一个等价刻画. 本

文的方法也可用于其他形式的 bent 函数的存在性证明.

1 预备知识

本节给出一些有关齐次旋转对称布尔函数和 bent 函数的预备知识和符号.

假设



为二元域



上的 n 维向量空间, n 元布尔函数 f(x

,…,x

)是



到



的映射. 对 x=(x

,…,x

), u=

,…,u

)



, 记

... ,

xx

x 则任意的布尔函数 f 都有唯一的形式:

() ,







其中,

U 



软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(2):717 [doi: 10.13328/j.cnki.jos.006158] http://www.jos.org.cn

一种密码函数存在性证明的新方法



尤启迪

1,2

张习勇

周

旋

吴兆阳

袁

野

(清华大学计算机科学与技术系, 北京 100084)

(天地一体化信息技术国家重点实验室, 北京 100086)

通信作者: 张习勇, E-mail: xiyong.zhang@hotmail.com

摘要: 密码函数在密码学中具有重要的研究价值. 从组合的角度, 给出了一种密码函数不存在性证明的新方法,

并且得到了一些新结果, 部分结果优于已有结论, 这些结果可以部分证明不存在次数大于 2 的齐次旋转对称 bent

函数这一公开猜想. 同时, 利用多项式的最大公因子算法刻画了 2 次齐次旋转对称 bent 函数. 该方法也可以用于

刻画其他形式的 bent 函数的存在性.

关键词: 旋转对称布尔函数; bent 函数; 傅里叶变换

中图法分类号: TP309

中文引用格式: 尤启迪, 张习勇, 周旋, 吴兆阳, 袁野. 一种密码函数存在性证明的新方法. 软件学报, 2022, 33(2):

717–724. http://www.jos.org.cn/1000-9825/6158.htm

英文引用格式: You QD, Zhang XY, Zhou X, Wu ZY, Yuan Y. New Method for Existence Proof of Some Cryptographic Functions.

Ruan Jian Xue Bao/Journal of Software, 2022, 33(2): 717 (in Chinese). http://www.jos.org.cn/1000-9825/6158.htm

New Met hod for Existence Proof of So me Cryptographic Func tions

YOU Qi-Di

1,2

, ZHANG Xi-Yong

, ZHOU Xuan

, WU Zhao-Yang

, YUAN Ye

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

(State Key Laboratory of Space-Ground Integrated Information Technology, Beijing 100086, China)

Abstra ct : Cryptographic functions have important applications in the research of cryptography. This paper describes a more suitable

approach to prove the nonexistence of some cryptographic functions, and obtain some new results, which support the conjecture that there

are no homogeneous rotation symmetric bent functions of algebraic degree>2. Also, homogeneous degree 2 rotation symmetric bent

functions are characterizedby using GCD of polynomials. The method presented in this paper can also be used to characterize the

existence of other forms of bent functions.

Key words: rotation-symmetric Boolean functions; bent functions; Fourier transform

现代密码学的研究离不开密码函数, 密码函数一般用于构造密码算法的中心部件. 自从 Rothus

[1]

在 20 世

纪 70 年代提出了 bent 函数后, bent 函数在过去的 40 多年有了深入的研究, 并且因其良好的密码学和组合学属

性, 在加密算法和纠错编码中有了广泛的应用. 例如在对称密码中, bent 函数由于具有最大非线性度和差分平

衡一致性, 可抵抗线性攻击和差分攻击, 用来构造密码算法的非线性部件.

近些年来, 齐次旋转对称(简记为 RotS)布尔函数因其理想的性质引起了人们的广泛关注

[24]

. 如: 这种函

数可利用前面循环迭代来快速求值, 所以当密码算法对函数求值的效率要求较高时, 这类旋转对称形式的函

数可以作为密码函数使用, 如 MD4 和 MD5 等消息摘要算法.

由于 bent 函数和旋转对称布尔函数都具有优良的密码学性质, 人们自然会问哪种类型的齐次旋转对称

bent 函数存在. 事实上, 文献[510]对齐次 bent 函数都有研究. 特别重要的是, 最近几年, 文献[1113]给出了

 基金项目: 国家自然科学基金(61572027)

收稿时间: 2020-02-17; 修改时间: 2020-04-29; 采用时间: 2020-09-07; jos 在线出版时间: 2021-08-03

718

软件学报 2022 年第 33 卷第 2 期

旋转对称布尔 bent 函数的几种新构造. Stǎnicǎ 和 Maitra

[6,7]

对变元个数在 10 以内的旋转对称 bent 函数进行了

研究, 他们列举了变元个数为 8 时所有的旋转对称 bent 函数, 发现了 43776 个次数为 2 的函数. 但当变元个

数为 10 时, 并没有发现次数为 3、4 和 5 的齐次旋转对称 bent 函数, 于是他们提出了如下猜想.

猜想 1.1. 不存在次数大于 2 的齐次旋转对称 bent 函数.

我们简要综述与该猜想证明相关的一些已有结果和证明方法. 注意到布尔 bent 函数本质上是 Hadamard

差集, Xia 等人

[8]

证明了对任意的 n>3, 不存在变元个数为 2n 的次数为 n 的齐次 bent 函数. 通过利用一个布尔

函数部分点的傅里叶谱值与其子函数的傅里叶谱值之间的关系, Meng 等人

[9]

得到了关于齐次 bent 函数次数的

一个较低的上界. 在文献[14]中, Carsto 和 Medina 等人利用函数的傅里叶变换的线性递归关系, 给出了特殊的

一类旋转对称布尔函数不是 bent 函数的证明.

定理 1.2. 假设 n 元旋转对称布尔函数 f 的简代数正规型为 x

…x

d1

, d≥5, 则对于充分大的 n, f 不

是 bent 函数.

在文献[10]中, Stǎnicǎ 等人从具有缺项的函数的非线性度出发, 得到了如下的不存在性结论(见第 1 节布

尔函数的简代数正规型表示).

定理 1.3. 假设 n 元齐次旋转对称布尔函数 f 的次数大于 3, 则以下结论成立.

1. 如果 f 的简代数正规型为 x

…x

, 则 f 不是 bent 函数;

2. 如果 f 的简代数正规型为 x

…x

d1

d+1

, 且此时 n、d 满足: 当 n1(mod d)时,

;











当

n=1 (mod d)时,









则 f 不是 bent 函数;

3. 如果 f 的简代数正规型为 ... ,

xx x 则当

/2 1













时, f 不是 bent 函数, 其中,

() () () ()

21 1 2

Max { , 1 | 1, 0,1 ,1 }.

iii i

f i diii j

d iin iuuu u ijin im    满足 ≤ ≤ ≤ ≤

利用更精细的计算取定变元后的子函数的谱值, Meng 等人

[15]

得到了更优的不存在性证明结果.

定理 1.4. 假设 n 元齐次旋转对称布尔函数 f 的次数大于 3, 则以下结论成立.

如果 f 的简代数正规型为单项式 x

, 则 f 不是 bent 函数;

如果 f 的简代数正规型为 ... ,

xx x 则当

d ≤

时, f 不是 bent 函数, 其中,

() () () ()

21 1 2

Max { , 1 | 1, 0,1 ,1 }.

iii i

f i diii j

d iin iuuu u ijin im    ≤≤≤≤

由此可见, 目前不存在性的证明结果离上述猜想的完全证明还有较大的差距. 其实, 利用较深刻的数论

结果, 可以将 bent 函数的问题转化为组合的问题. 本文将从组合的角度出发, 给出一种不同的较适用于研究

齐次旋转对称 bent 函数存在性的方法. 通过利用旋转对称布尔函数的旋转对称形式, 本文的方法可以证明更

多无法通过定理 1.2

定理 1.4 得到的不存在性结果. 例如, 我们的结果表明: 其简代数正规型包含 x

…x

的大

多次数大于等于 3 的齐次旋转对称 bent 函数是不存在的; 当简代正规型满足一定条件时, 其次数具有上界

d ≤

最后, 利用多项式的 GCD 算法, 本文给出了次数为 2 的齐次旋转对称 bent 函数的一个等价刻画. 本

文的方法也可用于其他形式的 bent 函数的存在性证明.

1 预备知识

本节给出一些有关齐次旋转对称布尔函数和 bent 函数的预备知识和符号.

假设



为二元域



上的 n 维向量空间, n 元布尔函数 f(x

,…,x

)是



到



的映射. 对 x=(x

,…,x

), u=

,…,u

)



, 记

... ,

xx

x 则任意的布尔函数 f 都有唯一的形式:

() ,







其中,

U 



of 8

免费下载

软件学报计算机技术

关注

评论