On the number of rotation symmetric Boolean functions  

作　　者：FU ShaoJing LI Chao QU LongJiang 

机构地区：[1]Science College of National University of Defense Technology, Changsha 410073, China [2]State Key Laboratory of Information Security, Beijing 100039, China [3]National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China

出　　处：《Science China(Information Sciences)》2010年第3期537-545,共9页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant No. 60803156);the Open Research Fund of State Key Laboratory of Information Security (Grant No. 01–07);the Open Research Fund of National Mobile Communications Research Laboratory of Southeast University (Grant No. W200807).

摘　　要：Rotation symmetric Boolean functions （RSBFs） have been used as components of different cryptosystems. This class of functions are invariant under circular translation of indices. In this paper, we investigated balanced RSBFs and 1st order correlation immune RSBFs. Based on constructive techniques, we give an accurate enumeration formula for n-variable balanced RSBFs when n is a power of a prime. Furthermore, an original and efficient method to enumerate all n-variable （n prime） 1st order correlationimmune functions is presented. The exact number of 1st order correlation immune RSBFs with 11 variables is 6925047156550478825225250374129764511077684773805520800 and the number of 13 variables has 189 digits. Then for more variables, we also provide a significant lower bound on the number of 1st order correlation immune RSBFs.Rotation symmetric Boolean functions （RSBFs） have been used as components of different cryptosystems. This class of functions are invariant under circular translation of indices. In this paper, we investigated balanced RSBFs and 1st order correlation immune RSBFs. Based on constructive techniques, we give an accurate enumeration formula for n-variable balanced RSBFs when n is a power of a prime. Furthermore, an original and efficient method to enumerate all n-variable （n prime） 1st order correlationimmune functions is presented. The exact number of 1st order correlation immune RSBFs with 11 variables is 6925047156550478825225250374129764511077684773805520800 and the number of 13 variables has 189 digits. Then for more variables, we also provide a significant lower bound on the number of 1st order correlation immune RSBFs.

关 键 词：CRYPTOGRAPHY rotation symmetry correlation immunity BALANCEDNESS 

分 类 号：O153.2[理学—数学] TN814.01[理学—基础数学]