Search

Properties of the additive differential probability $\mathrm{adp}^{\mathrm{XR}}$ of the composition of bitwise XOR and a bit rotation are investigated, where the differences are expressed using addition modulo $2^n$. This composition is widely used in ARX constructions consisting of additions modulo $2^n$, bit rotations and bitwise XORs. Differential cryptanalysis of such primitives may involve maximums of $\mathrm{adp}^{\mathrm{XR}}$, where some of its input or output differences are fixed. Although there is an efficient way to calculate this probability (Velichkov et al, 2011), many of its properties are still unknown. In this work, we find maximums of $\mathrm{adp}^{\mathrm{XR}}$, where the rotation is one bit left/right and one of its input differences is fixed. Some symmetries of $\mathrm{adp}^{\mathrm{XR}}$ are obtained as well. We provide all its impossible differentials in terms of regular expression patterns and estimate the number of them. This number turns out to be maximal for the one bit left rotation and noticeably less than the number of impossible differentials of bitwise XOR.

We consider the function $x^{-1}$ that inverses a finite field element $x \in \mathbb{F}_{p^n}$ ($p$ is prime, $0^{-1} = 0$) and affine $\mathbb{F}_{p}$-subspaces of $\mathbb{F}_{p^n}$ such that their images are affine subspaces as well. It is proven that the image of an affine subspace $L$, $|L| > 2$, is an affine subspace if and only if $L = q \mathbb{F}_{p^k}$, where $q \in \mathbb{F}_{p^n}^{*}$ and $k \mid n$. In other words, it is either a subfield of $\mathbb{F}_{p^n}$ or a subspace consisting of all elements of a subfield multiplied by $q$. This generalizes the results that were obtained for linear invariant subspaces in 2006. As a consequence, we propose a sufficient condition providing that a function $A(x^{-1}) + b$ has no invariant affine subspaces $U$ of cardinality $2 < |U| < p^n$ for an invertible linear transformation $A: \mathbb{F}_{p^n} \to \mathbb{F}_{p^n}$ and $b \in \mathbb{F}_{p^n}^{*}$. As an example, it is shown that the condition works for S-box of AES. Also, we demonstrate that some functions of the form $\alpha x^{-1} + b$ have no invariant affine subspaces except for $\mathbb{F}_{p^n}$, where $\alpha, b \in \mathbb{F}_{p^n}^{*}$ and $n$ is arbitrary.

NSUCRYPTO is the unique cryptographic Olympiad containing scientific mathematical problems for professionals, school and university students from any country. Its aim is to involve young researchers in solving curious and tough scientific problems of modern cryptography. From the very beginning, the concept of the Olympiad was not to focus on solving olympic tasks but on including unsolved research problems at the intersection of mathematics and cryptography. The Olympiad history starts in 2014. In 2019, it was held for the sixth time. In this paper, problems and their solutions of the Sixth International Olympiad in cryptography NSUCRYPTO'2019 are presented. We consider problems related to attacks on ciphers and hash functions, protocols, Boolean functions, Dickson polynomials, prime numbers, rotor machines, etc. We discuss several open problems on mathematical countermeasures to side-channel attacks, APN involutions, S-boxes, etc. The problem of finding a collision for the hash function Curl27 was partially solved during the Olympiad.

Problems and their solutions of the Fifth International Students' Olympiad in cryptography NSUCRYPTO'2018 are presented. We consider problems related to attacks on ciphers and hash functions, Boolean functions, quantum circuits, Enigma, etc. We discuss several open problems on orthogonal arrays, Sylvester matrices and disjunct matrices. The problem of existing an invertible Sylvester matrix whose inverse is again a Sylvester matrix was completely solved during the Olympiad.

Mathematical problems and their solutions of the Fourth International Students' Olympiad in cryptography NSUCRYPTO'2017 are presented. We consider problems related to attacks on ciphers and hash functions, cryptographic Boolean functions, the linear branch number, addition chains, error correction codes, etc. We discuss several open problems on algebraic structure of cryptographic functions, useful proof-of-work algorithms, the Boolean hidden shift problem and quantum computings.