Paper 2018/1194

On Degree-d Zero-Sum Sets of Full Rank

Christof Beierle, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. Cryptography and Communications
DOI
10.1007/s12095-019-00415-0
Keywords
Boolean functionannihilatororthogonal matrixnonlinear invari- anttrapdoor ciphersymmetric cryptography
Contact author(s)
beierle christof @ gmail com
aleksei @ affine group
History
2019-11-25: revised
2018-12-18: received
See all versions
Short URL
https://ia.cr/2018/1194
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1194,
      author = {Christof Beierle and Alex Biryukov and Aleksei Udovenko},
      title = {On Degree-d Zero-Sum Sets of Full Rank},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1194},
      year = {2018},
      doi = {10.1007/s12095-019-00415-0},
      note = {\url{https://eprint.iacr.org/2018/1194}},
      url = {https://eprint.iacr.org/2018/1194}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.