On the construction of cryptographically strong Boolean functions with desirable trade-off  

作　　者：REN Kui PARK Jaemin KIM Kwangjo 

机构地区：[1]ECE Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA,International Research Center for Information Security, Information and Communication University, Daejeon 305-714, Republic of Korea,International Research Center for Information Security, Information and Communication University, Daejeon 305-714, Republic of Korea

出　　处：《Journal of Zhejiang University-Science A(Applied Physics & Engineering)》2005年第5期358-364,共7页浙江大学学报（英文版）A辑（应用物理与工程）

摘　　要：This paper proposes a practical algorithm for systematically generating strong Boolean functions (f:GF(2) n →GF(2)) with cryptographic meaning. This algorithm takes bent function as input and directly outputs the resulted Boolean function in terms of truth table sequence. This algorithm was used to develop two classes of balanced Boolean functions, one of which has very good cryptographic properties:nl(f)=2 2k?1?2k+2k?2 (n=2k), with the sum-of-squares avalanche characteristic off satisfying σf=24k+23k+2+23k-2 and the absolute avalanche characteristic off satisfying σf=24k+23k+2+23k-2. This is the best result up to now compared to existing ones. Instead of bent sequences, starting from random Boolean functions was also tested in the algorithm. Experimental results showed that starting from bent sequences is highly superior to starting from random Boolean functions. Key words Boolean functions - Bent sequences - Nonlinearity - GAC - PC - Balancedness Document code A CLC number TP301.6This paper proposes a practical algorithm for systematically generating strong Boolean functions (f:GF(2)n→GF(2)) with cryptographic meaning. This algorithm takes bent function as input and directly outputs the resulted Boolean function in terms of truth table sequence. This algorithm was used to develop two classes of balanced Boolean functions, one of which has very good cryptographic properties: nl(f)=22k?1?2k+2k?2 (n=2k), with the sum-of-squares avalanche characteristic of f satisfying σf=24k+23k+2+23k+23k?2 and the absolute avalanche characteristic of ?f satisfying ?f=2k+1. This is the best result up to now compared to existing ones. Instead of bent sequences, starting from random Boolean functions was also tested in the algorithm. Experimental results showed that starting from bent sequences is highly superior to starting from random Boolean functions.

关 键 词：Boolean functions Bent sequences NONLINEARITY GAC PC BALANCEDNESS 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]