Paper 2018/1194
On Degreed ZeroSum Sets of Full Rank
Christof Beierle, Alex Biryukov, and Aleksei Udovenko
Abstract
A set $S \subseteq \mathbb{F}_2^n$ is called degree$d$ zerosum if the sum $\sum_{s \in S} f(s)$ vanishes for all $n$bit Boolean functions of algebraic degree at most $d$. Those sets correspond to the supports of the $n$bit Boolean functions of degree at most $nd1$. We prove some results on the existence of degree$d$ zerosum sets of full rank, i.e., those that contain $n$ linearly independent elements, and show relations to degree1 annihilator spaces of Boolean functions and semiorthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree$d$ zerosum set of rank $n$. The motivation for studying those objects comes from the fact that degree$d$ zerosum sets of full rank can be used to build linear mappings that preserve special kinds of \emph{nonlinear invariants}, similar to those obtained from orthogonal matrices and exploited by Todo, Leander and Sasaki for breaking the block ciphers Midori, Scream and iScream.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MINOR revision.Cryptography and Communications
 DOI
 10.1007/s12095019004150
 Keywords
 Boolean functionannihilatororthogonal matrixnonlinear invari anttrapdoor ciphersymmetric cryptography
 Contact author(s)

beierle christof @ gmail com
aleksei @ affine group  History
 20191125: revised
 20181218: received
 See all versions
 Short URL
 https://ia.cr/2018/1194
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1194, author = {Christof Beierle and Alex Biryukov and Aleksei Udovenko}, title = {On Degreed ZeroSum Sets of Full Rank}, howpublished = {Cryptology ePrint Archive, Paper 2018/1194}, year = {2018}, doi = {10.1007/s12095019004150}, note = {\url{https://eprint.iacr.org/2018/1194}}, url = {https://eprint.iacr.org/2018/1194} }