On the Structural Properties of Toffoli Gate Composition in ARADI: Implications for Algebraic Distinguishers
摘要
This paper identifies and explores a unique structural property in the design of ARADI, a recently proposed low-latency block cipher by NSA researchers – Patricia Greene, Mark Motley, and Bryan Weeks. The property arises from the specific composition of Toffoli gates in the nonlinear layer of ARADI ’s round function and it allows the extension of a given algebraic distinguisher to one extra round without any change in the data complexity. We introduce a theoretical framework to describe this property and present algebraic distinguishers that reach 8 out of 16 rounds of ARADI. We show that these distinguishers have better data complexities than the division property-based distinguishers up to 7 rounds. We also investigate whether modifying the linear layer or the order of composition of Toffoli gates could avoid this property, but ultimately give a negative answer. As a side result, we provide a key-recovery attack on 10 rounds ARADI. Our work highlights the significance of security analysis during the cipher design phase, and shows that these structural properties could have been avoided during this phase.