**On Degree-d Zero-Sum Sets of Full Rank**

*Christof Beierle and Alex Biryukov and Aleksei Udovenko*

**Abstract: **A set $S \subseteq \mathbb{F}_2^n$ is called degree-$d$ zero-sum 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 $n-d-1$. We prove some results on the existence of degree-$d$ zero-sum sets of full rank, i.e., those that contain $n$ linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-$d$ zero-sum set of rank $n$.

The motivation for studying those objects comes from the fact that degree-$d$ zero-sum 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.

**Category / Keywords: **foundations / Boolean function, annihilator, orthogonal matrix, nonlinear invari- ant, trapdoor cipher, symmetric cryptography

**Date: **received 10 Dec 2018

**Contact author: **aleksei udovenko at uni lu

**Available format(s): **PDF | BibTeX Citation

**Version: **20181218:193317 (All versions of this report)

**Short URL: **ia.cr/2018/1194

[ Cryptology ePrint archive ]