Provable Lower Bounds for Iterative Differentials of Nibble-Based SPNs via Markov Chains

Differential cryptanalysis of nibble-based SPNs is usually assessed either by a single trail, which is provable but can be exponentially loose, or by a heuristic cluster of trails, which carries no formal guarantee. We give a fixed-parameter tractable method that returns a rigorous, entrywise-justified lower bound on the probability DPr(∆) = (Mr )[∆, ∆] of an iterative differential ∆ → ∆: restricting the exact Markov transition operator to differences with at most K active nibbles yields a substochastic truncation MK ≤ M whose retained mass Pcomp = (MK r )[∆, ∆] is a strict lower bound, certified by the exactly computed discarded mass P¯drop (Pcomp ≤ DPr(∆) ≤ Pcomp + P¯drop). The state count |WK| = P j≤K