Paper 2024/1157
Shift-invariant transformations and almost liftings
, National Security Authority, National Security Authority, University of OsloAbstract
We investigate shift-invariant transformations, also known as rotation-symmetric vectorial Boolean functions, on $n$ bits that are induced from Boolean functions on $k$ bits, for $k\leq n$. We consider such transformations that are not necessarily permutations, but are, in some sense, almost bijective, and study their cryptographic properties. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its induced transformation that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its induced transformation is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.
Note: 20 pages, title and terminology have been slightly changed, accepted for publication in Cryptogr. Commun.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Cryptography and Communications
- Keywords
- boolean functionscellular automatashift-invariant transformationss-boxesalmost liftings
- Contact author(s)
-
admin @ neutreeko net
tron omland @ gmail com - History
- 2025-11-04: revised
- 2024-07-16: received
- See all versions
- Short URL
- https://ia.cr/2024/1157
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1157,
author = {Jan Kristian Haugland and Tron Omland},
title = {Shift-invariant transformations and almost liftings},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1157},
year = {2024},
url = {https://eprint.iacr.org/2024/1157}
}
