Generalized Lexicographic MultiObjective Combinatorial Optimization. Application to Cryptography
本文形式化了一类优先多准则优化问题，并评估了当前已知的次优解，进而用于寻找对对称密码设计有价值的布尔函数，这些函数对多种攻击具有已知的最大鲁棒性。
This paper formalizes a family of prioritized multicriteria optimization problems and assesses the corresponding up-to-date known suboptimal solutions. The resulting framework is then employed to characterize and search for Boolean functions which are valuable for a robust symmetric (mainly block) cipher design. The proposed optimality definitions generalize the lexicographic method by establishing an ordered sequence of multiobjective combinatorial optimization problems, which, in turn, gathers the relative relevance of the criteria, so that the optimal solutions can be obtained from a sequential application of the Pareto efficiency. The relationship among the different formulable problems is characterized in terms of both their respective solutions sets and computing costs. Since, in practice, only a limited set of functions can be evaluated (i.e., are known), the best known Pareto efficient functions are also defined. Finally, this framework is employed to obtain new functions having known (Pareto) maximal robustness against linear, differential, randomness-based, interpolation, algebraic and correlation attacks.