New Results on the Algebraic Immunity of Boolean Functions

被引：1
作者：
Rizomiliotis, Panagiotis [1 ]
机构：
[1] Univ Aegean, Dept Informat & Commun Syst Engn, GR-83200 Karlovassi, Samos, Greece
来源：
ENHANCING CRYPTOGRAPHIC PRIMITIVES WITH TECHNIQUES FROM ERROR CORRECTING CODES | 2009年 / 23卷
关键词：
Algebraic immunity; annihilator; high order nonlinearity; LINEAR FEEDBACK; STREAM CIPHERS; ATTACKS;
D O I：
10.3233/978-1-60750-002-5-192
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The algebraic immunity AI(f) of a Boolean function f is defined as the minimum degree of all annihilators of f. The high value of algebraic immunity consists a necessary condition for Boolean functions used in stream ciphers to resist algebraic attacks, of the two values. In this paper, we introduce the notion of extended algebraic immunity (AI) over bar (f) defined as the maximum of pAI(f) and pAI(f circle plus 1), where pAI(f) is the minimum degree of all annihilators of f (pAI ( f circle plus 1) of f circle plus 1 respectively). We introduce a lower bound of the r-th order nonlinearity of a Boolean function f with given (AI) over bar (f) and (AI) over bar (f). The bound is tighter than all known lower bounds, where only the algebraic immunity AI ( f) is used. The value of (AI) over bar (f) can be computed as part of the calculation of AI(f), with no extra computational cost.
引用
收藏
页码：192 / 202
页数：11
相关论文
共 14 条
  • [1] [Anonymous], [No title captured]
  • [2] Carlet C, 2006, LECT NOTES COMPUT SC, V4117, P584
  • [3] Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction
    Carlet, Claude
    Dalai, Deepak Kumar
    Gupta, Kishan Chand
    Maitra, Subhamoy
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (07) : 3105 - 3121
  • [4] Courtois NT, 2003, LECT NOTES COMPUT SC, V2729, P176
  • [5] Courtois NT, 2003, LECT NOTES COMPUT SC, V2656, P345
  • [6] DING C, 1991, LECT NOTES COMPUTER
  • [7] Lidl R., 1996, ENCY MATH ITS APPL, V20
  • [8] LOBANOV M, TIGHT BOUND NONLINEA
  • [9] McWilliams F.J., 1977, THEORY ERROR CORRECT
  • [10] Meier W, 2004, LECT NOTES COMPUT SC, V3027, P474
12