**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

**Original Publication**** (with minor differences): **Cryptography and Communications
**DOI: **10.1007/s12095-019-00415-0

**Date: **received 10 Dec 2018, last revised 25 Nov 2019

**Contact author: **beierle christof at gmail com,aleksei@affine group

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

**Version: **20191125:173455 (All versions of this report)

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

[ Cryptology ePrint archive ]