择多逻辑函数的若干性质

陈涛+童玉珂+卓泽朋

摘要：择多逻辑函数（SML函数）在密码学和计算机通信领域应用广泛.利用Wlash 循环谱和代数理论，系统的对SML函数的Wlash谱特性、平衡性、代数次数、非线性 度和相关免疫性等性质进行研究讨论，得出一些重要结论。

关键词：择多逻辑函数；Wlash谱；平衡性；非线性度；相关免疫性

中图分类号：TN918.1 文献标识码：A 文章编号：1009-3044（2018）01-0067-03

Abstract： Majority logic functions （SML Functions） are widely used in cryptography and computer communications. This paper systematic discuss the Wlash spectrum、balance、algebraic numbers、nonlinearity and correlation immunity of SML functions by Wlash spectrum and algebra， and get some important conclusions.

Key words： majority logic functions；Wlash spectrum；balance；nonlinearity；correlation immunity

1 概述

Courtois等人于2003年提出基于LSFR代数攻击以来，Toyocrypt、LILI-128等流密码陆续被攻破，对密码体制造成巨大威胁.而择多逻辑函数（以下简称SML函数）由于具有最高代数免疫度，可有效抵抗代数攻击，因此备受关注.

目前对SML函数的研究已取得较丰富成果.Bruer在文献[4]中提出SML函数的概念，发现其密码学性能较好而引入流密码中产生SML密钥流生成器.文献[5]中讨论了当时，SML函数的代数正规形中阶数的变化情况以及SML函数的非线性度性质.Dalai在文献[6]中发现SML函数代數免疫度最大，为，并利用SML函数递归构造一类最优密码函数.文献[8]讨论了偶数元SML函数的稳定性和代数结构性，得出SML函数变元较大时，函数非线性度较高的结论.文献[9]证明了SML函数代数免疫阶最大时，稳定性和相关攻击抵抗性能良好.文献[10]对SML函数的一些性质进行讨论，并根据其性质构造了最优代数免疫阶的一类布尔函数.本文在文献[4-10]基础上，利用代数知识和Wlash 循环谱，对SML函数的密码学性质进行系统研究讨论.

2 预备知识

设是元素0和1的有限域，元布尔函数是的映射，记是元布尔函数所组成的集合.数集Z，R和C，这些数域加法记为+，上加法记作，.向量的汉明重量记作：，若满足，则称是平衡布尔函数.对于任意的代数正规型（ANF）可表示为

3.2 代数次数

定理3 若是元SML函数，则的代数次数为：.

证明：根据文献[5]中证明代数免疫度的方法，我们可利用定义3，的小项表示可以表示如下：

上式中，令，可得，因为，所以小项表示中任意一个项代数次数都大于或等于，因此.证毕.

3.3 平衡性和对称性

平衡性和对称性是判断密码函数安全性能的重要指标.根据SML函数的定义，SML函数的自变量是的输入值，输出值为0或1.当变元为奇数时，的个数和的个数相等，则SML函数具有平衡性，也具有对称性.若变元为偶数时，的个数和的个数相等，使得SML函数的值为0或1的概率相等，因此具有平衡性，显然此时不具有对称性.

3.4 非线性度

首先给出非线性度和Walsh循环谱的一个重要关系式：

参考文献：

[1] Courtois N， Meier W. Algebraic attacks on stream ciphers with linear feedback[C]//Lec- ture Notes in Computer Science： Advances in Cryptology eurocrypt. Berlin： Springer Heidelberg， 2003： 345-359.

[2] Meier W， Pasalic E， Carlet C. Algebraic attacks and decomposition of Boolean functions[C]//Lecture Notes in Computer Science： Advances in Cryptology eurocrypt. Berlin： Springer Heidelberg， 2004： 474-491.

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

[4] Bruer J O. On Pseudo Random Sequences as Crypto Generators[A]. Proc of 1984 International Zurich Seminar on Digital Communications. 1984：157-161.

[5] Dalai D K， Maitra S， Sarkar S. Basic theory in construction of Boolean functions with maxim-um possible annihilator immunity[J]. Designs，Codes and Cryptography， 2006， 40（1）：41-58.

[6] 冯登国. 严格择多逻辑函数的非线性度[J].电子科技杂志， 1994， 27（1）：25- 27.

[7] 何良生. 一类具有最高代数免疫阶的布尔函数[J].计算机学报， 2009， 29（9）：1579-1583.

[8] 梁增，李世取. 偶数元择多逻辑函数的稳定性和代数结构[J].信息工程大学学报， 2005， 6（3）：40-44.

[9] 王永娟，韩文报，李世取. 偶数元择多逻辑函数的密码学性质[J].计算机工程与应用， 2009， 45（12）：38-41.

[10] Sihong Su， Xiaohu Tang.Constructing of rotation symmetric Boolean functions with optimal- algebraic immunity and high nonlinearty[J]. De-signs， Codes and Cryptography， 2014， 71（2）： 183-199.

[11] Ding C. A construction of binary linear codes from Boolean functions[J]. Discrete Mathematics， 2016， 339（9）：2288-2303.endprint