Best Practices for Key Management in Cloud

Key Rotation in Searchable Encryption: Lifecycle, Re-encryption, and Audit

Part 4 of 6 in the series Searchable Field-Level Encryption on Supabase. Return to the series index to see how all six parts fit together.

In August 2026, a production team rotating a single key version on a searchable encrypted table discovered that the database still held rows encrypted under the previous key version. The cloud key management service had created a new version, but nothing had re-encrypted the existing ciphertext or its derived search terms. That gap, which the Google Cloud KMS documentation states plainly, is the difference between claiming rotation and actually achieving it. Rotation of a key version never re-encrypts data and never disables the prior version. In searchable encryption, the stakes are higher than in ordinary field-level encryption, because every row carries both ciphertext and derived index terms that make it queryable. Rotate the key but leave the terms stale, and the database either cannot match new tokens or, worse, keeps matching old ones under a key you thought you had retired.

This fourth part of the series moves from the leakage trade-offs covered in Part 3 into the operational discipline that keeps a searchable encryption deployment secure over years: key lifecycle management, re-encryption strategies, index maintenance, and audit evidence. The central question is not whether to rotate but how to rotate without breaking search, without outage, and without leaving a trail of deactivated key versions that an auditor flags.

Key Takeaways

• Rotating a key version never re-encrypts existing data and never disables the prior version; in searchable encryption you must re-encrypt both ciphertext and derived index terms.
• Three re-encryption paths exist: full client-side rewrite, proxy re-encryption that transforms ciphertext without exposing keys, and updatable encryption where a single update token lets the server convert old-key data to a new key.
• Rotation can be lightweight (key material change) or heavy (re-encrypting data), and cloud providers impose quotas on version counts, scheduling, and API rate limits that shape your strategy.
• Indexing encrypted columns speeds up queries but reveals metadata, so rotation that changes index terms must rebuild term indexes or search silently degrades.
• NIST SP 800-57 recommends 1 to 2 year crypto-periods for symmetric data encryption keys, and key states (pre-activation, active, deactivated, compromised, destroyed) map directly onto SOC 2 and GDPR evidence requirements.

Why key rotation matters in searchable encryption

Key management is the control that keeps searchable encryption secure over time, and it is one most often deferred until after deployment is in production. The reason is structural. Searchable encryption stores, for every sensitive value, randomized ciphertext plus one or more derived index terms: a keyed hash for equality, an order-preserving term for ranges, and a bloom-filtered set of n-grams for free-text matching. All of these are computed under a key. When that key is compromised, an attacker with the derived terms and the key can reverse the keyed hash, reconstruct the ordering, and test n-gram membership against a plaintext dictionary. Rotation bounds that exposure to the window during which the key was active, which is exactly the argument the Thales key rotation guidance makes: a key active for one year protects one year of data, while a key active for a decade exposes a decade.

The cost of getting this wrong is not theoretical. IBM’s 2025 Cost of Data Breach report found that U.S. organizations paid an average of $10.22 million per breach, up 9 percent from the prior year, while the global average fell to $4.44 million. The report attributes the U.S. increase in part to higher regulatory fines and detection and escalation costs. For a regulated team, a breach that exposes plaintext because a rotated key left stale index terms is the kind of finding that converts a security incident into a compliance failure with a documented penalty attached.

There is a second, subtler reason rotation matters specifically for searchable encryption. Because index terms are keyed, a rotation that changes the key changes every derived term in the database. Leave old terms in place and the database keeps matching them under the retired key; remove them without rebuilding and equality, range, and free-text queries silently stop returning rows. This coupling between key and search index is what makes key rotation in a searchable system a data migration rather than a configuration change, and it is the reason the rest of this article treats re-encryption and index maintenance as one process, not two.

The key lifecycle: states and crypto-periods

Every key in a well-run deployment passes through a defined set of states, and those states are the vocabulary an auditor expects to see. NIST Special Publication 800-57, the standard that PCI DSS, HIPAA, and FedRAMP all point to, defines the lifecycle as pre-activation, active, deactivated, compromised, and destroyed, as the NIST SP 800-57 key management reference explains. A key is generated but not yet authorized in pre-activation, in use in the active state, no longer used for new operations but still needed to decrypt existing data in the deactivated state, known or suspected compromised in the compromised state, and irreversibly deleted in the destroyed state.

The critical distinction, and one most deployments get wrong, is between the originator usage period and the recipient usage period. SP 800-57 separates how long you encrypt with a key from how long you must retain it to decrypt data already written. A common failure is to rotate the key and immediately destroy the old version, only to discover that existing rows are now permanently unreadable. The rule is simple: retain the key in the deactivated state until every value encrypted under it has been re-encrypted or is no longer needed, then destroy it. The SOC 2 key management guidance makes the evidence side explicit: auditors want to see rotation policies, a rotation calendar with proof of execution, logs of key rotation events, and records showing that data encrypted under decommissioned keys has been re-encrypted or destroyed.

For frequency, SP 800-57 recommends a crypto-period of 1 to 2 years for symmetric data encryption keys and up to 2 years for symmetric authentication keys such as HMAC used in equality terms. Cloud providers offer different defaults: Tencent Cloud recommends rotating symmetric keys every 90 days, while Azure Key Vault advises at least every two years and supports automatic rotation policies. The important point is not which number you pick but that you document the choice and justify it. An auditor who asks what your crypto-period is and hears “we have not thought about it” has found a finding, regardless of the underlying strength of your encryption.

Re-encryption strategies: full rewrite, proxy re-encryption, updatable encryption

Once a new key version is active, you must move existing data onto it. The Google Cloud KMS re-encryption workflow is the baseline: decrypt data using the prior key version, re-encrypt it using the new primary version, then disable or schedule destruction of the prior version. Applied to searchable encryption, each step carries extra work. Decrypting a value also means re-deriving every index term under the new key, and re-encrypting means writing both new ciphertext and new terms back into the same row. This is a full client-side rewrite, and it is the most straightforward but most expensive option, because the application must pull each row, decrypt it, recompute terms, and write it back. On a large table this is a background migration, not a switch you flip, and it is exactly the path the key management rotation reference marks as the heavy case: rotation can be lightweight when it is only a key material change, or heavy when it re-encrypts data.

The first alternative is proxy re-encryption. In proxy re-encryption, a semi-trusted proxy transforms ciphertext encrypted under one key into ciphertext decryptable under another key, without ever seeing secret keys or plaintext. The proxy re-encryption reference describes the mechanism: the data owner derives a re-encryption key from the master key and gives it to the proxy, which applies it to convert the ciphertext. The proxy never sees the original decryption key or the target key, and in a unidirectional scheme the re-encryption key is useless for decryption on its own. The appeal for rotation is that transformation happens server-side without exposing plaintext to the cloud. The trade-off is computational: proxy re-encryption schemes typically rely on bilinear pairings over elliptic curves, which are slower than ordinary symmetric operations, and the proxy is assumed honest-but-curious, so a malicious proxy is a real threat model to design against.

The second alternative is updatable encryption, introduced by Boneh and colleagues at CRYPTO 2013. Updatable encryption lets a client rotate the symmetric encryption key for outsourced data without downloading, decrypting, and re-encrypting it. The data owner sends a short update token to the server, and the server uses that token to rotate ciphertext from the old key to the new key without learning anything about the plaintext. This is the mechanism behind updatable searchable symmetric encryption (USSE), where the client issues a single update token that permits the server to convert existing encrypted data from the old key to the new key. For a searchable system, the appeal is that the update token can also re-derive search index terms, so rotation and index refresh happen together in one server-side operation rather than as a client-side data migration. The cost is that updatable encryption is a more specialized primitive, with fewer mature implementations, and security definitions have evolved considerably since 2013, so the choice of scheme matters.

Which strategy fits depends on data size, acceptable downtime, and trust in the cloud provider. For a small table or low write volume, full client-side rewrite is the simplest and requires no exotic primitives. For large datasets where pulling every row is impractical, updatable encryption with a server-side update token is the strongest fit, because it moves re-encryption and term re-derivation into the provider without exposing plaintext. Proxy re-encryption sits in between, useful when you need to delegate transformation to a proxy you partially trust. The honest framing is that none of these is free: full rewrite costs bandwidth and time, updatable encryption adds scheme complexity, and proxy re-encryption adds pairing overhead and a trust assumption.

How rotation and re-encryption affect search performance

Rotation and re-encryption do not just move data; they change the search index, and that has a measurable performance cost. The rotation reference distinguishes the lightweight case (key material change that leaves data untouched) from the heavy case (re-encrypting data). Searchable encryption almost always lands in the heavy case, because derived terms are keyed and must change with the key. Every re-encrypted row must be written back, and every term index over re-derived values must be rebuilt or updated. On a table with millions of rows and several index terms per value, the index rebuild can dominate the migration window.

There is also an operational constraint that shapes the schedule. Cloud key management services impose quotas and limits on version counts, rotation scheduling, and API rate limits. If you rotate every key in a multi-tenant deployment simultaneously, you can hit rate limits that stall the re-encryption job mid-flight, leaving half the rows on the old key and half on the new one. The Cloud Security Alliance key management guidance frames rotation as a lifecycle discipline involving generation, activation, rotation, archival, recovery, and destruction, and it stresses that cloud environments add shared infrastructure and multi-tenancy to the trust model. That means rotation schedules should be staggered by key set and by tenant, with a monitoring window between batches to confirm that search still returns expected rows before moving to the next set.

Because indexing encrypted columns speeds up queries but reveals metadata, index rebuild is not merely a performance concern; it is a security decision. Rebuilding a term index exposes which values share a term and how frequently each appears, which is frequency information Part 3 showed can be exploited. A rotation that touches low-cardinality fields should be scheduled and monitored with that leakage in mind, and the team should document why the index was rebuilt and what metadata it exposed, the same way it would document any other capability choice.

Index maintenance and term re-derivation

The most common production failure in searchable key rotation is treating ciphertext and index terms as if they rotated together automatically. They do not. Rotating the key version changes the key, but the derived terms already stored in the database are still computed under the old key. Until those terms are re-derived under the new key and indexes rebuilt, the database either matches stale terms under the retired key or fails to match new tokens the application now produces. The correct order, as the workflow diagram above shows, is to rotate the key, re-encrypt each row (both ciphertext and terms), rebuild term indexes, and only then disable and eventually destroy the old key version.

Term re-derivation must be atomic with the ciphertext rewrite. If a job re-encrypts ciphertext but leaves the old equality term in place, the row is stored under the new key but still searchable only under the old one, which defeats the entire rotation and leaves a security hole. The safest implementation writes new ciphertext and new terms in a single transaction per row, so a failure rolls back both. For large tables, batch the work, run it during a low-traffic window, and verify after each batch that equality, range, and free-text queries return expected rows before proceeding.

Index build times matter for scheduling. Part 3 of this series reported measured index build times from the CipherStash benchmark suite: an order-preserving B-tree builds in about one second at one million rows, while an order-revealing index takes roughly 44 seconds for the same dataset. A rotation that re-derives an order-revealing term and rebuilds that index inherits that slower build time, so the maintenance window must account for the slowest index type present, not the average. Raising maintenance work memory before the rebuild and preferring B-tree over hash builds for equality on large tables keeps the window short, consistent with the guidance established in Part 2.

Integrating with security frameworks and audit

Key rotation is where searchable encryption meets the compliance frameworks that motivated the deployment in the first place. Under SOC 2, the confidentiality criterion expects encryption and key management procedures, and auditors verify that keys are generated securely, stored in controlled environments, rotated regularly, revoked when compromised, and destroyed at the end of their useful life. The SOC 2 key management guidance lists four evidence artifacts the auditor wants: policies and procedures covering generation, storage, rotation, and destruction; access reviews showing only authorized roles can reach key material; system and event logs recording key usage, rotation, and deletion; and change-management records showing approval for rotation and revocation. For a Type II report, these controls must operate over a three to twelve month observation period, and a single control failure during that window can jeopardize the whole report.

GDPR adds a different lens. Encryption is listed as an example measure under Article 32, which requires appropriate technical and organizational measures for the security of processing. The practical compliance benefit of searchable encryption, as established in Part 1, is that it changes what a breach exposes: a stolen snapshot becomes cryptographically inert without the application tier. Key rotation strengthens that claim by bounding how much data any single compromised key can expose. For the data protection officer, documentation that justifies your rotation schedule, your crypto-periods, and your residual leakage per column is itself a compliance artifact, and it should be written with that purpose in mind.

NIST SP 800-57 is the connective tissue across all of these. PCI DSS, HIPAA, and FedRAMP all point to it when they say to follow standard key management practices, and aligning your rotation policy with its crypto-periods and key states satisfies multiple frameworks at once. The Cloud Security Alliance guidance adds a cloud-specific layer: four dominant architecture patterns (cloud-native, external key origination, external KMS, and multi-cloud), and the full lifecycle from generation through activation, rotation, archival, recovery, and destruction. It also flags a forward-looking requirement for crypto-agility, the ability to migrate to new algorithms as post-quantum standards mature, which happens through the same rotation mechanism you build for ordinary key changes.

Monitoring and auditing are the glue that turns a rotation policy into defensible compliance evidence. Every rotation event must leave a log entry that records which key, which version, who authorized it, and when it happened. The logs feed the security information and event management pipeline, and the rotation calendar shows upcoming rotations and their responsible owners. The Cloud Security Alliance guidance stresses that governance and policy are unique to cloud encryption, because shared infrastructure and multi-tenancy change who can reach key material and the metadata around it. A rotation without a corresponding audit trail is a rotation an auditor cannot verify, which makes it effectively a non-event for compliance purposes.

Common pitfalls and how to avoid them

The failure modes in searchable key rotation are predictable, and each maps to a specific control. The first is rotating the key but not re-encrypting data, which leaves the old key version active forever because data encrypted under it still exists. The fix is to schedule a re-encryption job after every rotation and to destroy the old version only after confirming no rows remain on it. The second is destroying a deactivated key too early, which makes existing data permanently unreadable. The fix is to retain the key in the deactivated state until every value under it is re-encrypted or no longer needed, honoring the distinction between originator and recipient usage periods.

The third pitfall is application caching of key material. If the application caches the old key in memory after rotation, it keeps encrypting new data under the retired key, which means new values are written with terms the database no longer expects. The fix is either to avoid caching key material and call the key management service for each operation, or to build a cache invalidation mechanism triggered by rotation events. The fourth is rotating asymmetric keys without coordinating with the systems that verify or decrypt using them. For asymmetric keys used for encryption, the public portion of the new version must be distributed before new encryptions begin, and access to the private portion granted for decryption, as the Google Cloud KMS guidance notes.

The fifth pitfall is specific to searchable encryption: rotating ciphertext but not index terms, or rebuilding the index without re-deriving terms. This silently breaks search, and it is easy to miss because the database returns no error, just empty result sets. The fix is to make term re-derivation atomic with the ciphertext rewrite and to verify search behavior after each batch. Finally, beware the assumption that rotation is a lightweight operation. On a large searchable table it is a heavy data migration with index rebuilds, rate-limit exposure, and a monitoring window, and it should be planned and resourced accordingly rather than treated as a configuration toggle.

What comes next

This part has covered the operational core of a production searchable encryption deployment: key lifecycle and crypto-periods, three re-encryption paths, the impact of rotation on search performance and index maintenance, and the compliance evidence that ties it all together. The next part of this series looks ahead at the future of searchable encryption on Supabase, the trends shaping the technology, and how to stay current as schemas and key management primitives evolve. You can return to the series index to see how all six parts fit together.

Related Reading

More in-depth coverage from this blog on closely related topics:

• Security vs Performance in Encrypted Cloud
• Searchable Field Encryption on Supabase
• How to Secure Encrypted Data in Supabase
• Difference Between Field Level Encryption

Sources and References

Sources cited while researching and writing this article:

• Key rotation | Cloud Key Management Service – Google Cloud
• Encryption Key Rotation for Data Security
• 2025 Cost of Data Breach report
• NIST SP 800-57 , Key Management Recommendations and Crypto Periods
• SOC 2 Key Management Best Practices: Key Requirements & Templates (2026)
• Re-encrypting data | Cloud Key Management Service – Google Cloud
• What is KMS Rotation? Meaning, Architecture, Examples, Use Cases, and …
• Proxy Re-Encryption , Cloud Key Rotation | ADHDecode
• Key Management in Cloud Services | CSA