This paper presents a systematic exploration of the evolution of algorithms for S-Box modeling, tracing their progression from foundational techniques, such as the greedy algorithm by Sun et al., to state-of-the-art methods like the SuperBall approach by Li and Sun. Through a detailed comparative analysis, we examine these methodologies, highlight their key differences, and provide insightful observations. Early approaches, such as the greedy algorithm, relied on mathematical tools like SageMath, while more recent advancements leverage Mixed Integer Linear Programming (MILP) to model S-Box inequalities more effectively. Building on these developments, we introduce novel algorithms that utilize MILP techniques to enhance both the efficiency and accuracy of S-Box inequality generation. Our first algorithm, direct inequality generation, constructs the final set of inequalities directly using MILP models. The second, greedy generation and reduction, generates an expanded inequality set, which is then refined using the Sasaki and Todo reduction algorithm to obtain the final result. Both approaches employ the method of undetermined coefficients, similar to the SuperBall approach. Our comparative analysis demonstrates that the proposed algorithms not only meet cryptographic standards but also deliver comparable results to existing models. We further enhance the greedy algorithm proposed by Sun et al. through key modifications, while a novel iterative inequality augmentation technique based on convex hull methods improves the results introduced by Boura and Coggia. Additionally, we identify a lower bound in the SuperBall approach, enabling faster convergence to optimal results. We also suggest methods for deriving a minimal set of inequalities associated with the LAT, BCT, and DPT, as well as the DDT for any given S-box. These methods are useful for enhancing cryptanalysis techniques such as linear cryptanalysis, boomerang attacks, and division property-based attacks on ciphers.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient and Optimized Modeling of S-Boxes

  • Anirudh Aitipamula,
  • Debranjan Pal,
  • Dipanwita Roy Chowdhury

摘要

This paper presents a systematic exploration of the evolution of algorithms for S-Box modeling, tracing their progression from foundational techniques, such as the greedy algorithm by Sun et al., to state-of-the-art methods like the SuperBall approach by Li and Sun. Through a detailed comparative analysis, we examine these methodologies, highlight their key differences, and provide insightful observations. Early approaches, such as the greedy algorithm, relied on mathematical tools like SageMath, while more recent advancements leverage Mixed Integer Linear Programming (MILP) to model S-Box inequalities more effectively. Building on these developments, we introduce novel algorithms that utilize MILP techniques to enhance both the efficiency and accuracy of S-Box inequality generation. Our first algorithm, direct inequality generation, constructs the final set of inequalities directly using MILP models. The second, greedy generation and reduction, generates an expanded inequality set, which is then refined using the Sasaki and Todo reduction algorithm to obtain the final result. Both approaches employ the method of undetermined coefficients, similar to the SuperBall approach. Our comparative analysis demonstrates that the proposed algorithms not only meet cryptographic standards but also deliver comparable results to existing models. We further enhance the greedy algorithm proposed by Sun et al. through key modifications, while a novel iterative inequality augmentation technique based on convex hull methods improves the results introduced by Boura and Coggia. Additionally, we identify a lower bound in the SuperBall approach, enabling faster convergence to optimal results. We also suggest methods for deriving a minimal set of inequalities associated with the LAT, BCT, and DPT, as well as the DDT for any given S-box. These methods are useful for enhancing cryptanalysis techniques such as linear cryptanalysis, boomerang attacks, and division property-based attacks on ciphers.