Abstract:
We study the distribution of the linear bias coefficient $L_{\beta,\alpha}^F$ for random functions $F:\mathbb{Z}_q^n \rightarrow \mathbb{Z}_q^m$ defined on finite Abelian groups, where functions are selected uniformly from all possible mappings. The paper is devoted to cryptographic applications, in particular, to the analysis of the resistance of format-preserving encryption algorithms to linear cryptanalysis. The main theoretical contribution is Theorem 1, which establishes the exact probability distribution of the linear bias coefficient. For $\sigma = \gcd(\beta, q)$, the probability that $L_{\beta,\alpha}^F$ equals a given value $\widehat{\gamma}$ is $$\Pr\left[L_{\beta,\alpha}^F = \widehat{\gamma}\right] = q_{\sigma}^{-q_{\sigma}^n} \textstyle\sum\limits_{a \in \mathbf{A}_q^n\colon \atop |f_a| = [f^{\widehat{\gamma}}]} \dfrac{q_{\sigma}^{n}!}{a_0! \cdot \ldots \cdot a_{q_{\sigma}-1}!},$$ where $\mathbf{A}_q^n$ denotes the set of non-negative integer vectors $(a_0, \ldots, a_{q_{\sigma}-1})$ whose components sum to $q^n$; the polynomial ideal $A_q[t]$ is defined as $\{ f(t) \in \mathbb{Z}[t]/(t^q - 1): f(\zeta) = 0 \}$ for a primitive $q$-th root of unity $\zeta$; the equivalence class $[f^{\widehat{\gamma}}]$ in the quotient ring $R_q = \mathbb{Z}[t]/A_q[t]$ satisfies $f^{\widehat{\gamma}}(\zeta) = \widehat{\gamma}$. This result provides a framework for evaluating the linear cryptanalysis resistance of generalized Feistel networks and other symmetric cryptographic constructions.
Keywords:FPE algorithms, generalised Feistel network, linear method of cryptographic analysis, linear prevalence, linear prevalence probability distribution.
Fulltext:
PDF file (707 kB)