Formalizing the Cryptographic Migration Problem

With the advancements in quantum computing, transitioning to post-quantum cryptography is becoming increasingly critical to maintain the security of modern systems. This paper introduces a formal definition of the cryptographic migration problem and explores its complexities using a suitable directed graph model. Characteristics of the resulting migration graphs are analyzed and trade-offs discussed. By using classical mathematical results from combinatorics, probability theory and combinatorial analysis, we assess the challenges of migrating ``random'' large cryptographic IT-infrastructures. We show that any sufficiently large migration project that follows our model has an intrinsic complexity, either due to many dependent (comparatively easy) migration steps or due to at least one complicated migration step. This proves that in a suitable sense cryptographic migration is hard in general.