级联函数的扩展代数免疫性  

On Extended Algebraic Immunity of Concatenated Boolean Functions

作　　者：刘志高[1,2] 张福泰[2] 

机构地区：[1]马鞍山职业技术学院,马鞍山243031 [2]南京师范大学计算机科学与技术学院,南京210023

出　　处：《密码学报》2015年第3期226-234,共9页Journal of Cryptologic Research

基　　金：国家自然科学基金项目(61170298);2014年安徽省高校优秀青年人才支持计划

摘　　要：级联构造法是构造具有良好密码学性质的布尔函数的重要方法之一.通过级联,可利用已有的具有良好密码学性质的布尔函数构造出新的密码学性质也较好的布尔函数.布尔函数的扩展代数免疫性是衡量其抵抗代数攻击的重要指标,比布尔函数的代数免疫性指标更有效.本文详细讨论了级联函数f0∥f1∥…∥f2k-1的代数免疫性和扩展代数免疫性.利用布尔函数和其分解函数零化子之间的关系,得到了其代数免疫度的上下界,即其代数免疫度介于参与级联的所有布尔函数代数免疫度的最小值与这个最小值加k之间.同时,还给出了达到其代数免疫度上界的一个充分条件.该条件容易满足且易于判别.此外,基于代数补函数思想,得到了其扩展代数免疫度的上下界,即其扩展代数免疫度不低于参与级联的所有布尔函数扩展代数免疫度的最小值,不高于所有代数免疫度的最小值与k的和.Concatenation is an important method to construct Boolean functions with good cryptographic properties. By concatenation, new Boolean functions with good cryptographic properties can be constructed from known ones. The extended algebraic immunity is an important measurement for Boolean functions against algebraic attacks. It is more effective than the algebraic immunity of Boolean functions. This paper aims to investigate the algebraic immunity and extended algebraic immunity of Boolean functions in the formf0∥f1∥…∥f2k-1. Using the relationship between the annihilators of Boolean functions and the annihilators oftheir decomposition functions, an upper bound and an lower bound of its algebraic immunity are given, i.e., its algebraic immune degree is no less than the minimum value of algebraic immunity degrees of all Boolean functions involved in the concatenation and is no more than the minimum value plus k. Moreover, we present a sufficient condition when the upper bound of its algebraic immunity can be reached. This sufficient condition can easily be satisfied and can be effectively verified. Furthermore, based on algebraic complement, an upper bound and an lower bound of its extended algebraic immunity are also derived, i.e., its extended algebraic immunity is no less than the minimum value of extended algebraic immunity of all Boolean functions involved in the concatenation and is no more than the minimum value of all algebraic immunities plus k.

关 键 词：代数免疫 扩展代数免疫 级联函数 代数攻击 

分 类 号：TN918.1[电子电信—通信与信息系统]