Crypto-Agile Key Hierarchies for Client-Controlled Encrypted Storage: Incremental Migration Without Global Re-Encryption

Client-controlled encrypted-storage systems commonly organize key material as a hierarchical structure to support scalable access control, sharing, and revocation without global re-encryption. Hierarchical key-management models generally assume a fixed cryptographic suite, leaving suite evolution outside the operations explicitly represented by the hierarchy—a limitation that becomes increasingly relevant as systems transition from classical to post-quantum cryptographic primitives. This paper treats crypto-agility as a first-class structural property of hierarchical key systems. We formalize cryptographic migration as an explicit operator over the key hierarchy, capable of acting on arbitrary subsets of suite-sensitive nodes while allowing different cryptographic suites to coexist consistently within the same hierarchy. We formalize three complementary properties of crypto-agile migration: agility-soundness, coexistence-isolation, and migration-locality. We establish conditional confidentiality guarantees for isolated outgoing-edge and holder-access representations under explicitly restricted adversarial views, together with a structural locality result. We further analyze the security of the resulting structure under multi-suite coexistence and show that the cost of migrating a node is bounded by its immediate incoming and outgoing edges, authorized holders, and fixed per-node work, rather than by the size of the hierarchy or the data subtree it protects. The model is instantiated on an operational client-controlled storage deployment built on primitives aligned with the outgoing Commercial National Security Algorithm Suite (CNSA 1.0), illustrating how the proposed operator applies to migration toward post-quantum primitives.