On the Formalization of Cryptographic Migration

We present a novel approach to gaining insight into the structure of cryptographic migration problems which are classic problems in applied cryptography. We use a formal model to capture the inherent dependencies and complexities of such transitions. Using classical mathematical results from combinatorics, probability theory, and combinatorial analysis, we evaluate the challenges of migrating large cryptographic IT infrastructures and prove that - in a suitable sense - cryptographic migration exhibits a certain expected complexity. We also provide numerical data for selected parameter sets. Furthermore, we analyze the proposed model in terms of real-world patterns and its practical applicability. Additionally, we discuss the challenges of modeling real-world migration projects. As concrete examples we examine the transition to post-quantum cryptography of the CI/CD system GitLab and the multi-level technological transition of distribution power grids. This work paves the way for future advancements in both the theoretical understanding and practical implementation of cryptographic migration strategies.