Shift-invariant transformations and almost liftings
math.CO, cs.CR, cs.IT, math.IT
Submitted: 2024-07-16
Updated: 2025-11-03
Comments: 20 pages, title and terminology have been slightly changed, accepted for publication in Cryptogr. Commun
DOI: 10.1007/s12095-025-00848-w
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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 at most n.
Terminology
Abstract
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 at most 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 χ used in the Keccak hash function.
Sources
- New classes of reversible cellular automata
- Affine and cyclic affine equivalence of rotation-symmetric S-boxes
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality