[Resource Topic] 2018/1194: On Degree-d Zero-Sum Sets of Full Rank

Welcome to the resource topic for 2018/1194

On Degree-d Zero-Sum Sets of Full Rank

Authors: Christof Beierle, Alex Biryukov, Aleksei Udovenko


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.

ePrint: https://eprint.iacr.org/2018/1194

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .