On the Formalization of Cryptographic Migration

With the advancement of quantum computing, the transition to post-quantum cryptography (PQC) is becoming increasingly critical to maintain the security of modern dependable infrastructural systems. This paper presents a novel approach to gain insight into the structure of cryptographic migration problems, using a semi-formal model to capture the inherent dependencies and complexities of such transitions. Using classical mathematical results from combinatorics, probability theory, and combinatorial analysis, we assess the challenges of migrating large cryptographic IT-infrastructures and prove that -- in a suitable sense -- cryptographic migration has a certain expected complexity. Furthermore, we analyze the proposed model in terms of real-world patterns as well as its practical applicability, and discuss difficulties that arise when trying to model real-world migration projects. This work sets the stage for future advances in both the theoretical understanding and practical implementation of cryptographic migration strategies in the post-quantum era.