Parameterized Complexity Analysis for Cryptanalysis of Composite CipherSystems: FPT Characterization and Optimized Algorithms

Abstract

We present a comprehensive parameterized complexity framework for the cryptanalysis of classical ciphersystems composed of multiple cryptographic transformation layers. Our main theoretical contributionsare threefold. First, we prove that Cipher-Decode is fixed-parameter tractable (FPT) when parameterizedby the structural complexity vector (k, ℓmax, |Σ|), yielding an algorithm with running time O∗(|Σ|k·ℓmax ).Second, we establish that the problem is para-NP-hard when parameterized solely by the number of layersk, and W[1]-hard via a complete formal reduction from k-Clique, providing a tight complexity dichotomy.Third, we design a branch-and-bound algorithm with statistical pruning based on Kullback-Leibler divergenceand the Index of Coincidence, reducing the effective search space by two to six orders of magnituderelative to exhaustive search. Experimental evaluation on 47 benchmark instances spanning Vigenère,substitution, ADFGVX, and multi-layer composite ciphers confirms the theoretical scaling predictions(R2 = 0.9998) and demonstrates speedups of 115× to over 2000× against naive baselines, with directcomparisons against simulated annealing and beam search. To the best of our knowledge, this is the firstrigorous FPT analysis of multi-layer classical cipher cryptanalysis.