In recent years,automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation in symmetric-key cryptanalyses.Among these methods,the automatic...In recent years,automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation in symmetric-key cryptanalyses.Among these methods,the automatic search with the Boolean satisfiability problem(SAT,in short)gradually becomes a powerful cryptanalysis tool.A key problem in the SAT-based automatic search method is how to fully characterize a set S■{0,1}^(n) with as few Conjunctive normal form(CNF,in short)clauses as possible,which is called a full CNF characterization(FCC,in short)problem.In this work,the authors establish a complete theory to solve a best solution of an FCC problem.Specifically,the authors start from plain sets,which can be characterized by exactly one clause.By exploring mergeable sets,the authors give a sufficient and necessary condition for characterizing a plain set.Based on the properties of plain sets,the authors further provide an algorithm of solving an FCC problem for a given set S,which can generate all the minimal plain closures of S and produce a best FCC theoretically.As application,the authors apply the proposed algorithm to many common S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables and get their FCCs,all of which are the best-known results at present.展开更多
The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC...The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC) presented by Si W and Ding C(2012),etc.In order to evaluate the security of those ciphers in resistance to(fast) algebraic attacks,the authors need to characterize algebraic properties of Tr(λx^(-1)).However,currently only some bounds on algebraic immunity of Tr(λx^(-1)) are given in the public literature,for example,the NGG upper bound and the Bayev lower bound,etc.This paper gives the exact value of the algebraic immunity of Tr(λx^(-1)) over F_(2~n),that is,AI(Tr(λx^(-1))) =[2n^(1/2)]- 2,where n ≥ 2,A ∈ F_(2~n) and λ≠ 0,which shows that Dalai's conjecture on the algebraic immunity of Tr(λx^(-1)) is correct.What is more,the authors demonstrate some weak properties of Tr(λx^(-1)) against fast algebraic attacks.展开更多
With the development of artificial intelligence,the genetic algorithm has been widely used in many fields.In cryptography,the authors find it is natural to code an individual and design its fitness in a genetic algori...With the development of artificial intelligence,the genetic algorithm has been widely used in many fields.In cryptography,the authors find it is natural to code an individual and design its fitness in a genetic algorithm for a straightforward guess and determine analysis(SGDA,in short).Based on this observation,the authors propose an SGDA based on genetic algorithm.Comparing it with the other three SGDAs based on exhaustive search,MILP method and CPP method respectively,the authors illustrate its effectiveness by three stream ciphers:Small scale SNOW 2.0,medium scale Enocoro-128v2 and large scale Trivium.The results show our method is significantly superior to them,especially for Trivium,the method can find a solution of 165 variables in less than one hour,while the other three methods are not applicable due to its enormous search space of size 2^(619.37).As far as we know,it is a best solution in an SGDA for Trivium so far.展开更多
In the light of multi-continued fraction theories, we make a classification and counting for multi-strict continued fractions, which are corresponding to multi-sequences of multiplicity m and length n. Based on the ab...In the light of multi-continued fraction theories, we make a classification and counting for multi-strict continued fractions, which are corresponding to multi-sequences of multiplicity m and length n. Based on the above counting, we develop an iterative formula for computing fast the linear complexity distribution of multi-sequences. As an application, we obtain the linear complexity distributions and expectations of multi-sequences of any given length n and multiplicity m less than 12 by a personal computer. But only results of m=3 and 4 are given in this paper.展开更多
基金supported by the National Key Research and Development Project under Grant No.2018YFA0704705CAS Project for Young Scientists in Basic Research under Grant No.YSBR-035。
文摘In recent years,automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation in symmetric-key cryptanalyses.Among these methods,the automatic search with the Boolean satisfiability problem(SAT,in short)gradually becomes a powerful cryptanalysis tool.A key problem in the SAT-based automatic search method is how to fully characterize a set S■{0,1}^(n) with as few Conjunctive normal form(CNF,in short)clauses as possible,which is called a full CNF characterization(FCC,in short)problem.In this work,the authors establish a complete theory to solve a best solution of an FCC problem.Specifically,the authors start from plain sets,which can be characterized by exactly one clause.By exploring mergeable sets,the authors give a sufficient and necessary condition for characterizing a plain set.Based on the properties of plain sets,the authors further provide an algorithm of solving an FCC problem for a given set S,which can generate all the minimal plain closures of S and produce a best FCC theoretically.As application,the authors apply the proposed algorithm to many common S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables and get their FCCs,all of which are the best-known results at present.
基金supported by the National Natural Science Foundation of China under Grant No.61572491the 973 Program under Grant No.2011CB302401the open project of the SKLOIS in Institute of Information Engineering,Chinese Academy of Sciences under Grant No.2015-MS-03
文摘The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC) presented by Si W and Ding C(2012),etc.In order to evaluate the security of those ciphers in resistance to(fast) algebraic attacks,the authors need to characterize algebraic properties of Tr(λx^(-1)).However,currently only some bounds on algebraic immunity of Tr(λx^(-1)) are given in the public literature,for example,the NGG upper bound and the Bayev lower bound,etc.This paper gives the exact value of the algebraic immunity of Tr(λx^(-1)) over F_(2~n),that is,AI(Tr(λx^(-1))) =[2n^(1/2)]- 2,where n ≥ 2,A ∈ F_(2~n) and λ≠ 0,which shows that Dalai's conjecture on the algebraic immunity of Tr(λx^(-1)) is correct.What is more,the authors demonstrate some weak properties of Tr(λx^(-1)) against fast algebraic attacks.
基金supported by the National Key Research and Development Project under Grant No.2018YFA0704705,2016YFB0800401the National Natural Science Foundation under Grant No.61972297。
文摘With the development of artificial intelligence,the genetic algorithm has been widely used in many fields.In cryptography,the authors find it is natural to code an individual and design its fitness in a genetic algorithm for a straightforward guess and determine analysis(SGDA,in short).Based on this observation,the authors propose an SGDA based on genetic algorithm.Comparing it with the other three SGDAs based on exhaustive search,MILP method and CPP method respectively,the authors illustrate its effectiveness by three stream ciphers:Small scale SNOW 2.0,medium scale Enocoro-128v2 and large scale Trivium.The results show our method is significantly superior to them,especially for Trivium,the method can find a solution of 165 variables in less than one hour,while the other three methods are not applicable due to its enormous search space of size 2^(619.37).As far as we know,it is a best solution in an SGDA for Trivium so far.
基金the National Natural Science Foundation of China (Grants Nos. 60173016 and 90604011)
文摘In the light of multi-continued fraction theories, we make a classification and counting for multi-strict continued fractions, which are corresponding to multi-sequences of multiplicity m and length n. Based on the above counting, we develop an iterative formula for computing fast the linear complexity distribution of multi-sequences. As an application, we obtain the linear complexity distributions and expectations of multi-sequences of any given length n and multiplicity m less than 12 by a personal computer. But only results of m=3 and 4 are given in this paper.
