Discrete Functions

Theoretical and probabilistic characteristics of the value of linear correlation of round functions of some FPE algorithms

A. V. Kargin


Abstract: We investigate probabilistic properties of the linear correlation (bias) in round functions of certain Format-Preserving Encryption (FPE) algorithms. We consider distributions arising from reducing uniformly distributed binary strings modulo a target alphabet of arbitrary size $ q \in \mathbb{N} $. This non-uniform distribution, denoted by $ G(\mathbb{Z}_{q^L}) $, plays a crucial role in FPE schemes such as FF3-1. We provide its explicit probability mass function and show that it depends on the relation between $ q^L $ and $ l = 2^{\lceil L \log_2 q \rceil} $. For the linear correlation coefficient
$$ L_\beta^{F} = \frac{1}{|X|} \textstyle\sum\limits_{x \in X} \chi_\beta(F(x)), $$
where $ F : \mathbb{Z}_{q^R} \to \mathbb{Z}_{q^L} $ is a random function with values distributed according to $ G(\mathbb{Z}_{q^L}) $, we derive two equivalent formulas for the expected value:
$$ \mathbb{E}[L_\beta^{F}] = \frac{1}{l} {\textstyle\sum\limits_{i=0}^{l - q^L - 1}} \chi_\beta(i), \text{and} \mathbb{E}[L_\beta^{F}] = -\frac{1}{l} {\textstyle\sum\limits_{i=l - q^L}^{q^L - 1}} \chi_\beta(i). $$
We also establish that the equality $ \mathbb{E}[L_\beta^{F}] = 0 $ holds if and only if the canonical prime factorization of $ q^L $ contains the prime $ 2 $ and $ q^L / \beta $ is a power of 2. The variance of $ L_\beta^{F} $ is given by
$$ \mathbb{D}[L_\beta^{F}] = \frac{1}{|X|} \left(1 - (\mathbb{E}[\chi_\beta(F(x))])^2 \right). $$
Finally, we describe the full probability distribution of $ L_\beta^{F} $. For the finite Abelian groups $ X = \mathbb{Z}_q^n $, $ Y = \mathbb{Z}_q^m $ and a random function $ F $ distributed according to $ G $, the probability that $ L_\beta^{F} = \hat{\gamma} $ is determined by the combinatorial structure of how often each value from $ \mathbb{Z}_{q^L} $ appears in the outputs of $ F $. Specifically, this probability corresponds to a weighted sum over multinomial distributions, where each term accounts for a particular frequency distribution of the character values $ \chi_\beta(F(x)) $.

Keywords: FPE algorithms, linear method of cryptographic analysis, linear correlation.

UDC: 004.056

DOI: 10.17223/2226308X/18/14