Shift-invariant transformations and almost liftings

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\le 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.