Shift-invariant transformations and almost liftings

arXiv:2407.11931 · math.CO, cs.CR, cs.IT, math.IT · Submitted 2024-07-16 · Read on arXiv

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

Related papers