The Inverse of \(\chi \) and Its Applications to Rasta-Like Ciphers

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. It can be found from the designers’ analysis that the security of the two ciphers highly relies on the high algebraic degree of the inverse of the n-bit \(\chi \) operation denoted by \(\chi _n^{-1}\), while surprisingly the explicit formula of \(\chi _n^{-1}\) has never been given in the literature. As the first contribution, for the first time, we give a very simple formula of \(\chi _n^{-1}\) that can be written down in only one line and we prove its correctness in a rigorous way. Based on this formula of \(\chi _n^{-1}\), an obvious yet important weakness of the two ciphers can be identified, which shows that their security against the algebraic attack cannot be solely based on the high degree of \(\chi _n^{-1}\). Specifically, this weakness enables us to theoretically break two out of three instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable against our attacks than Rasta because of its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with \((n,\kappa ,r)\in \{(327,80,4),(1877,128,4),(3545,256,5)\}\) are reduced to only 1 round, where n, \(\kappa \) and r denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.