Algebraic Immunity Of Boolean Functions And Vector Value Functions

Boolean functions and vector value functions play important roles in the designand analysis of modern cryptographic algorithms. Some cryptographic criterias havebeen put forward to measure whether the cryptographic algorithms are immune toknown attacks, such as nonlinearity to measure whether the cryptographic algorithmsare immune to linear attack and correlation immunity to measure whether thecryptographicalgorithmsareimmunetocorrelationattack.Algebraicimmunityisanewcriteriatomeasurewhetherthecryptographicalgorithmsareimmunetoalgebraicattack.This thesis investigates the theory of algebraic immunity of Boolean functions andvector value functions, including the relations between algebraic immunity and othercryptographic criterias, counting problems and algorithms of algebraic immunity. Thefruitsofthisthesisareoutlinedasfollows:(1) The relation between the weight and algebraic immunity of Boolean functionsis studied with probability method, which could be used to give a lower boundof the number of balanced Boolean functions with maximum algebraicimmunity;(2) A new fast algorithm to give a upper bound of algebraic immunityof a kind ofspecific functions is presented, based on which we can estimate their algebraicvulnerability;(3) A relation between algebraic immunity and nonlinearity of vector valuefunctionsisgiven.