擇多邏輯函數的若干性質

陳濤+童玉珂+卓澤朋

摘要：擇多邏輯函數（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