Cryptology ePrint Archive: Report 2018/1194

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 ]