Finding the Inverse of some Shift Invariant Transformations

Fukang Liu; Vaibhav Dixit; Santanu Sarkar; Willi Meier; Takanori Isobe

Paper 2025/769

Finding the Inverse of some Shift Invariant Transformations

Fukang Liu, Institute of Science Tokyo

Vaibhav Dixit, IIT Madras

Santanu Sarkar, IIT Madras

Willi Meier, FHNW

Takanori Isobe, The University of Osaka

Abstract

We study the problem of how to find the inverse of shift invariant (SI) transformations proposed in Daemen's thesis. In particular, two of them have been used in practice: and . The first one is the well-known transformation used in \textsf{SHA-3}, \textsf{Subterranean 2.0} and \textsf{Rasta}, while the second one is used in a recently proposed ZK-friendly hash function called Monolith. While the concrete formula of the inverse of of arbitrary size has been given and proved by Liu et al. at JoC 2022, it remains unknown how to deduce such a formula and how to systematically study other SI transformations. In this work, we aim to provide a general method and flow to find the inverse of SI transformations, though it is still limited to some specific types and it may not work for all such transformations. However, such a general method does shed new insight on how to find their inverse, as we can apply this method to several different SI transformations, including the one used in Monolith. We expect that this method can be further generalized and applied to more SI transformations.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in JOC 2025
Keywords: Boolean functions Chi
Contact author(s): liufukangs @ gmail com
vaibhavrdrk @ gmail com
sarkar santanu bir1 @ gmail com
willimeier48 @ gmail com
takanori isobe @ ist osaka-u ac jp
History: 2025-04-30: approved; 2025-04-30: received; See all versions
Short URL: https://ia.cr/2025/769
License: CC BY

BibTeX

@misc{cryptoeprint:2025/769,
      author = {Fukang Liu and Vaibhav Dixit and Santanu Sarkar and Willi Meier and Takanori Isobe},
      title = {Finding the Inverse of some Shift Invariant Transformations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/769},
      year = {2025},
      url = {https://eprint.iacr.org/2025/769}
}