In this paper, we present a new method to find Sbox circuits with optimal multiplicative complexity (MC), i.e., MC-optimal S-box circuits. We provide new observations for efficiently constructing circuits and computing MC, combined with a popular pathfinding algorithm named A*. In our search, the A* algorithm outputs a path of length MC, corresponding to an MC-optimal circuit. Based on an in-depth analysis of the process of computing MC, we enable the A* algorithm to function within our graph to investigate a wider range of S-boxes than existing methods such as the SAT-solver-based tool [1] and LIGHTER [2]. We provide implementable MC-optimal circuits for all the quadratic 5-bit bijective S-boxes and existing 5-bit almost-perfect nonlinear (APN) S-boxes. Furthermore, we present MC-optimal circuits for 6-bit S-boxes such as Sarkar Gold, Sarkar Quadratic, and some quadratic permutations. Finally, we theoretically demonstrate new lower bounds for the MCs of S-boxes, providing tighter bounds for the MCs of AES and MISTY S-boxes than previously known. This study complements previous results on MC-optimal S-box circuits and is intended to provide further insight into this field.
In this paper, we propose a methodology for finding impossible differential distinguishers for permutations used in sponge-like constructions. Given the difference between typical block ciphers and such permutations in terms of key additions, we initiate the construction of an impossible differential trail starting from the middle round. Based on the proposed methodology, we present several new or improved truncated and impossible distinguishers for ASCON, DRYGASCON, SYCON, and SHAMASH, all of which were submitted to the NIST Lightweight Cryptography project. For ASCON, we significantly reduce the attack complexity compared to existing results, and notably, this marks the first instance of proposing specific truncated and impossible differential trails for SYCON and SHAMASH. Finally, we discuss how truncated differential distinguishers, identified using our methodology, enable key-recovery attacks in weak-key setting. The methodology of this paper is significant not only for the ciphers considered but also for other permutation-based ciphers with similar structures. Given that the target algorithms are suitable for resource-constrained devices, our results provide new insights into security for the Internet of Things.