Shift-invariant functions and almost liftings
<|reference_start|>Shift-invariant functions and almost liftings: We investigate shift-invariant vectorial Boolean functions on $n$~bits that are lifted from Boolean functions on $k$~bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. 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 lifted functions 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 lifted functions 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.<|reference_end|>
@article{haugland2024shift-invariant,
    title={Shift-invariant functions and almost liftings},
    author={Jan Kristian Haugland, Tron Omland},
    journal={arXiv preprint arXiv:2407.11931},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.11931},
    primaryClass={math.CO cs.CR cs.IT math.IT}
}