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.展开更多
We study the Boolean satisfiability problem （SAT） restricted on input formulas for which there are linear arithmetic constraints imposed on the indices of variables occurring in the same clause. This can be seen as ...We study the Boolean satisfiability problem （SAT） restricted on input formulas for which there are linear arithmetic constraints imposed on the indices of variables occurring in the same clause. This can be seen as a structural counterpart of Schaefer＇s dichotomy theorem which studies the SAT problem with additional constraints on the assigned values of variables in the same clause. More precisely, let k-SAT（m, A） denote the SAT problem restricted on instances of k-CNF formulas, in every clause of which the indices of the last k - m variables are totally decided by the first m ones through some linear equations chosen from A. For example, if A contains i3 = il ＋ 2i2 and i4 = i2 - i1 ＋ 1, then a clause of the input to 4-SAT（2, A） has the form Yi1 V Yi2 V Yi1＋2i2 V yi2-i1＋1, with yi being xi or xi^-. We obtain the following results： 1） If m ≥ 2, then for any set .4 of linear constraints, the restricted problem k-SAT（m, A） is either in P or NP-complete assuming P ≠ NP. Moreover, the corresponding #SAT problem is always #P-complete, and the MAx-SAT problem does not allow a polynomial time approximation scheme assuming P ≠ NP. 2） m = 1, that is, in every clause only one index can be chosen freely. In this case, we develop a general framework together with some techniques for designing polynomial-time algorithms for the restricted SAT problems. Using these, we prove that for any .A, #2-SAT（1, .A） and MAX-2-SAT（1, A） are both polynomial-time solvable, which is in sharp contrast with the hardness results of general #2-SAT and MAX-2-SAT. For fixed k ≥ 3, we obtain a large class of non-trivial constraints .4, under which the problems k-SAT（1, A）, #k-SAT（1, .A） and MAx-k-SAT（1, A） can all be solved in polynomial time or quasi-polynomial time.展开更多
基金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 in part by the National Basic Research 973 Program of China under Grant Nos. 2011CBA00300,2011CBA00301the National Natural Science Foundation of China under Grant Nos. 61033001, 61061130540, 61073174
文摘We study the Boolean satisfiability problem （SAT） restricted on input formulas for which there are linear arithmetic constraints imposed on the indices of variables occurring in the same clause. This can be seen as a structural counterpart of Schaefer＇s dichotomy theorem which studies the SAT problem with additional constraints on the assigned values of variables in the same clause. More precisely, let k-SAT（m, A） denote the SAT problem restricted on instances of k-CNF formulas, in every clause of which the indices of the last k - m variables are totally decided by the first m ones through some linear equations chosen from A. For example, if A contains i3 = il ＋ 2i2 and i4 = i2 - i1 ＋ 1, then a clause of the input to 4-SAT（2, A） has the form Yi1 V Yi2 V Yi1＋2i2 V yi2-i1＋1, with yi being xi or xi^-. We obtain the following results： 1） If m ≥ 2, then for any set .4 of linear constraints, the restricted problem k-SAT（m, A） is either in P or NP-complete assuming P ≠ NP. Moreover, the corresponding #SAT problem is always #P-complete, and the MAx-SAT problem does not allow a polynomial time approximation scheme assuming P ≠ NP. 2） m = 1, that is, in every clause only one index can be chosen freely. In this case, we develop a general framework together with some techniques for designing polynomial-time algorithms for the restricted SAT problems. Using these, we prove that for any .A, #2-SAT（1, .A） and MAX-2-SAT（1, A） are both polynomial-time solvable, which is in sharp contrast with the hardness results of general #2-SAT and MAX-2-SAT. For fixed k ≥ 3, we obtain a large class of non-trivial constraints .4, under which the problems k-SAT（1, A）, #k-SAT（1, .A） and MAx-k-SAT（1, A） can all be solved in polynomial time or quasi-polynomial time.
