对称布尔函数的算术相关函数

来源:用户上传      作者: 赵庆兰 郑东 董晓丽

　　摘 要：
　　算术相关函数是最近提出的一种研究布尔函数密码学性质的方法，该方法通过定义多元2-adic数上的加法和乘法运算，构建一种新的环结构，实现对经典相关函数的带进位计算的模拟。首先介绍了算术相关函数的定义，并针对具有良好密码学性质的对称布尔函数讨论了其算术相关函数的性质和取值，最后利用对称布尔函数的实值对称性证明了对称布尔函数的算术自相关函数也是一个与向量的重量有关的实值对称函数，至多是n+1值的。
　　关键词：密码学；布尔函数； 2-adic数；算术相关函数；对称布尔函数
　　中图分类号： TN918.1
　　文献标志码：A
　　Arithmetic correlations of symmetric Boolean function
　　Abstract：
　　The arithmetic correlation function is a new method for studying the cryptographic properties of Boolean functions. Based on the basic definitions of addition and multiplication of multi-2-adic integer， the study constructed a new algebraic ring and realized the arithmetic or “with-carry” analogs of classic correlation functions. In this paper the definition of arithmetic autocorrelation function was introduced. The arithmetic correlation value of symmetric Boolean functions was studied. The results show that the arithmetic autocorrelation function of symmetric Boolean functions is a real symmetric function with at most n+1 values.
　　Key words：
　　cryptology； Boolean function；2-adic number； arithmetic correlation function； symmetric boolean function
　　0 引言
　　布尔函数在密码学包括流密码和分组密码的设计和分析中有着重要的作用[1]，但是这些函数必须满足一定的条件才能应用到具体的密码系统中。非线性、平衡性、相关免疫性和扩散性是衡量密码函数密码学性质优劣的重要指标[2]，函数的自相关性能有效地刻画密码函数的扩散性质，函数的平方自相关值越低， 那么它的扩散性就越好。所以研究布尔函数的相关函数有十分重要的意义，对相关函数的研究已有很多成果[1，3]。Klapper[4-5]提出了一种新的研究布尔函数性质的工具——算术Walsh变换和算术相关函数，通过借鉴2-adic整数环上的运算构建一个新的环结构，是对经典Walsh变换和相关函数的一种带进位运算的模拟。算术相关函数定义在序列的算术自相关的基础之上，而序列的算术自相关在进位反馈寄存器（Feedback with Carry Shift Registers，FCSR）中有着重要的作用。文献[5]证明了布尔函数算术自相关函数的计算定理，并计算了线性函数、仿射函数的算术自相关函数。文献[6]对二次型函数的算术Walsh变换系数进行了分析计算，进一步讨论了对布尔函数的性质进行进位模拟的意义。目前尚无文献对对称布尔函数的相关函数进行研究。本文首先介绍了一些基础知识，引出了布尔函数算术相关函数的定义，并针对称布尔函数这一具有良好密码学性质的布尔函数的子类进行了初步的讨论，在文献[5]给出的定理的基础上证明了n元对称布尔函数的算术自相关函数具有实值对称性，在某个向量上的算术自相关函数与向量的重量有关。
　　1 预备知识
　　3 对称布尔函数的算术相关函数
　　对称布尔函数作为布尔函数的一个子类：一方面，在函数的存储上占用较少的内存空间；另一方面，实际应用中需要的逻辑门个数与变元个数呈线性关系。因此，研究具有良好密码学性质的对称布尔函数有着十分重要的意义[9-12]。
　　4 结语
　　本文初步讨论了对称布尔函数的算术自相关函数，证明了对称布尔函数的算术自相关函数跟向量的重量有关，至多是n+1值的。而对于算术相关函数的其他性质，比如特殊布尔函数中的对称布尔函数、bent函数的算术相关函数值的分布，上界或者下界，以及与布尔函数其他密码学性质之间的关系都是有待研究的问题。
　　全局雪崩准则（Global Avalanche Criterion，GAC）和k阶扩散准则是研究布尔函数在抵抗密码攻击方面的密码学性质的重要指标，布尔函数的相关函数则是这些概念定义的基础。文献[5]在定义算术相关函数的基础上也定义了算术雪崩准则（Arithmetic Avalanche Criterion，AAC）和k阶扩散准则（Arithmetic Propagation Criterion of degree k，APC（k）），对于怎样构造满足AAC或者APC（k）的布尔函数并没有进一步的讨论，这也是以后的一个研究方向。
　　参考文献：
　　[1] CARLET C. Boolean functions for cryptography and error correcting codes[EB/OL].[2013-08-20]. http：//www1.spms.ntu.edu.sg/～kkhoongm/chap-fcts-Bool.pdf. 　　[2] WEN Q， NIU X，YANG Y. Boolean functions of modern cryptography[M]. Beijing： Science Press，2008.（温巧燕，钮心忻，杨义先. 现代密码学中的布尔函数 [M]. 北京： 科学出版社， 2000.）
　　[3] CUSICK T， STANICA P. Cryptographic boolean functions and applications[M]. San Diego： Academic Press， 2009.
　　[4] KLAPPER A， GORESKY M. A with-carry Walsh transform （extended abstract）[C]// Proceedings of the 6th International Conference on Sequences and Their Applications. Berlin： Springer-Verlag， 2010： 217-228.
　　[5] KLAPPER A， GORESKY M. Arithmetic correlations and Walsh transforms[J]. IEEE Transactions on Information Theory， 2012， 58（1）：479-492.
　　[6] KLAPPER A. Arithmetic Walsh transform of quadratic boolean functions[C]// Proceedings of the 8th International Conference on Sequences and Their Applications. Berlin： Springer-Verlag， 2012： 65-76.
　　[7] KOBLITZ N. p-Adic numbers， p-Adic analysis， and Zeta functions[M]. Berlin： Springer，1984.
　　[8] KLAPPER A，GORESKY M. Feedback shift registers， combiners with memory， and 2-Adic span[J]. Journal of Cryptology， 1997， 10（2）： 111-147.
　　[9] CANTEAUT A， VIDEANU M. Symmetric Boolean functions[J]. IEEE Transactions on Information Theory， 2005， 51（8）：2791-2811.
　　[10] BRAEKEN A， PRENEEEL B. On the algebraic immunity of symmetric boolean functions[C]// Proceedings of the 6th International Conference on Cryptology. Heidelberg： Springer， 2005： 35-48.
　　[11] DALAI D K， MAITRA S， SKAKAR S. Basic theory in construction of boolean functions with maximum possible annihilator immunity[J]. Design， Codes and Cryptography， 2006， 40（1）： 41-58.
　　[12] OU Z， ZHAO Y. On one class of symmetric Boolean functions[J]. Journal on Communications，2013，34（1）：89-104.（欧智慧，赵亚群.一类对称布尔函数的研究[J].通信学报，2013，34（1）：89-104.）
转载注明来源:https://www.xzbu.com/8/view-4880918.htm