Research On BDD Size Of Password Boolean Function

In the symmetric cryptosystem,the(vector)Boolean function is the only nonlinear component that plays a crucial role in the security of the cryptosystem.To resist various traditional attacks,Boolean functions need to have good cryptographic properties:high algebraic number,high nonlinearity,high algebraic immunity,and so on.In addition,BDD attack,as a new attack method,puts forward new requirements for the cryptographic properties of Boolean functions,that is,Boolean functions need to have a high BDD size.However,as of now,there is very little research on this key indicator.Based on the knowledge of Boolean function theory,this paper studies BDD size and uses BDD to weigh some new mainstream attacks to provide relevant data for designing cryptographic functions.The main work includes:First,Analyzing the BDD size of rotationally symmetric Boolean functions.It mainly analyzes the construction and search space of rotationally symmetric Boolean functions,and gives the function distribution corresponding to BDD size.The search results show that most of the BDD size of the rotationally symmetric Boolean function accounts for 1/3 of the value interval,and it's easy to search for larger BDD size.Second,Analyzing the BDD size of the Hidden weighted bit functions(HWBF).This paper starts with the OBDD model,constructs the balanced partition based on the concept of foaming set and gives the general expression of the function boundary value|AOBDD|,and does not completely discuss the lower boundary of the HWBF node.In the case of half discussion,The lower boundary of the BDD size of the element HWBF is Ω(1.14n).Third,based on genetic algorithm,Mining the password Boolean function against synthetic attack.In this paper,the genetic algorithm is designed and improved by combining the characteristics of Boolean functions.The Boolean functions of anti-SAT and Bypass complementary attacks and BDD attacks in gate-level locking are mined.The maximum BDD size of the 3～10-element Boolean function and the corresponding Hamming weight are given.While the function search space reaches 21024,we can ensure the accuracy of the search results.