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