On designated-weight Boolean functions with highest algebraic immunity

被引：5

作者：

Liu MeiCheng ^{[1
,3
]}

Du YuSong ^{[2
]}

Pei DingYi ^{[2
]}

Lin DongDai ^{[1
]}

机构：

[1] Chinese Acad Sci, Inst Software, State Key Lab Informat Secur, Beijing 100190, Peoples R China

[2] Guangzhou Univ, Coll Math & Informat Sci, Guangzhou 510006, Guangdong, Peoples R China

[3] Chinese Acad Sci, Grad Univ, Beijing 100049, Peoples R China

来源：

SCIENCE CHINA-MATHEMATICS | 2010年 / 53卷 / 11期

基金：

中国国家自然科学基金;

关键词：

cryptography; Boolean function; algebraic immunity; algebraic degree; nonlinearity; STREAM CIPHERS; LINEAR FEEDBACK; ODD NUMBER; ATTACKS; CONSTRUCTION; VARIABLES;

D O I：

10.1007/s11425-010-4059-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study Sigma(d-1)(i=0) ((n)(i))-weight Boolean functions with algebraic immunity achieving the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d not equal n+1/2 their nonlinearities equal the minimum of Sigma(d-1)(i=0) ((n)(i)) and Sigma(n-d)(i=0) ((n)(i)). Lastly, we identify two classes of such functions, one having algebraic degree of n or n - 1.

引用

页码：2847 / 2854

页数：8

共 19 条

[1]

Armknecht F, 2006, LECT NOTES COMPUT SC, V4004, P147

[2]

Canteaut A, 2006, LECT NOTES COMPUT SC, V3969, P120

[3]

Carlet C, 2008, LECT NOTES COMPUT SC, V5350, P425, DOI 10.1007/978-3-540-89255-7_26

[4]

Courtois NT, 2003, LECT NOTES COMPUT SC, V2729, P176

[5]

Courtois NT, 2003, LECT NOTES COMPUT SC, V2656, P345

[6] Basic theory in construction of Boolean functions with maximum possible annihilator immunity [J].

Dalai, Deepak Kumar ;

Maitra, Subhamoy ;

Sarkar, Sumanta .

DESIGNS CODES AND CRYPTOGRAPHY, 2006, 40 (01) :41-58

[7]

Dalai DK, 2004, LECT NOTES COMPUT SC, V3348, P92

[8] Construction of Boolean functions with maximum algebraic immunity and count of their annihilators at lowest degree [J].

Du YuSong ;

Pei DingYi .

SCIENCE CHINA-INFORMATION SCIENCES, 2010, 53 (04) :780-787

[9]

Hammer P., 2010, BOOLEAN METHODS MODE

[10] On the construction of Boolean functions with optimal algebraic immunity [J].

Li, Na ;

Qu, LongJiang ;

Qi, Wen-Feng ;

Feng, GuoZhu ;

Li, Chao ;

Xie, DuanQiang .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (03) :1330-1334

← 1 2 →