7. Key Management and Crypto-shredding
Module 06 showed how data flows through zones and pipelines — raw records enter the platform, get pseudonymized in streaming, and eventually reach the anonymized zone via batch structural anonymization. But every pseudonymization transform in that pipeline depends on a cryptographic key: HMAC (keyed hashing) needs a shared secret, FPE (format-preserving encryption) needs an encryption key, deterministic encryption needs an AES-SIV key. If the key leaks, every pseudonym derived from it is compromised. If the key is lost, pseudonymized data becomes permanently unlinkable — which may be the goal (right to erasure) or a disaster (operational continuity).
This module follows the chain of decisions that the key dependency creates. It starts with the transform choice (which determines the entire key architecture), then follows the consequences: how the pipeline accesses the key at scale, how the key is protected, what happens when it rotates, and what happens when you need to destroy it for a single individual.
Choosing the transform — and what follows from that choice
The first decision in any anonymization pipeline is which pseudonymization transform to use for each field. Module 03 covered the techniques; Module 05 covered the tooling. This section covers the architectural consequence: each transform implies a different key management burden, and the right choice depends on whether anyone will ever need to reverse the pseudonym.
If re-identification is not a requirement, HMAC with a shared key in KMS gives you consistent, joinable pseudonyms with no decryption keys to store, no DEK tables to manage, and no key material in the data layer. The rest of this module — token vaults, per-subject DEKs, crypto-shredding — only applies when reversibility is an actual need.
When re-identification is needed for some fields but not others, apply different transforms per field. A common pattern in the telco reference architecture (Module 06): HMAC for IMEI (device-level aggregation only, no re-identification needed), deterministic encryption for MSISDN (phone number) and IMSI (SIM identifier) where re-identification is needed for customer support and regulatory requests. This is configured in a single Sensitive Data Protection (SDP) de-identification template — each InfoType maps to its own transform.
Accessing the key — vault design
Once you've chosen a reversible transform (FPE or deterministic encryption), the pipeline needs the key for every record it processes. At CDR scale — millions to billions of records per day — this key access must not become a bottleneck. The design choice is between computing the pseudonym from a key (stateless) or looking it up in a mapping table (stateful).
| Architecture | How it works | Throughput | Re-identification |
|---|---|---|---|
| Stateless (crypto-derived) | Pseudonym computed from input + key. No lookup table. | Very high — computation only, no I/O | Decrypt with the key (FPE, det. enc.) or impossible (HMAC) |
| Stateful (lookup table) | Random token stored in a mapping table (input → token). | Limited by database throughput | Lookup in the mapping table |
Stateless is the default. The pseudonym is a function of the input and the key — no external state, no database to scale, no cache invalidation. FPE and deterministic encryption via Sensitive Data Protection are stateless by design.
Stateful vaults are necessary only when the pseudonym must be a random, non-derivable token (e.g., PCI DSS tokenization of payment card numbers, where the token must have no mathematical relationship to the original PAN), when multiple independent systems must share tokenization without sharing a key (cross-organizational sharing), or when the mapping must be enumerable for audit.
For stateful vaults at CDR scale, the critical design decisions are: cache recently used mappings in memory (in telco, the top 20% of subscribers generate 80% of CDRs), batch unmapped identifiers across a window for bulk lookups, and choose the vault database by throughput requirements — Bigtable for millions of point lookups per second, Cloud SQL for simpler operations, Spanner for global consistency.
Key protection — KMS and HSM
With the transform chosen and the vault architecture set, the next question is how to protect the keys themselves. A leaked pseudonymization key compromises every pseudonym derived from it — for a shared key, that means the entire dataset. The standard approach uses envelope encryption: a KEK (key encryption key) in Cloud KMS wraps the DEKs (data encryption keys) that the pipeline uses directly. The plaintext DEK exists only in pipeline memory during processing; at rest, only the wrapped (encrypted) form is stored. This two-layer design also means KEK rotation is transparent — re-wrapping DEKs with a new KEK version does not change the DEKs themselves, so pseudonyms remain stable.
Cloud KMS
├── Key ring: anonymization-keys (regional)
│ ├── KEK: pseudonymization-master (HSM protection level)
│ │ ├── Version 2 (active for new pseudonymization)
│ │ └── Version 1 (retained for decryption of historical data)
│ └── KEK: partner-export-key (HSM protection level)
│ └── Separate key for partner-facing pseudonymization
│
└── Wrapped DEKs (stored in pipeline config / Secret Manager)
├── DEK for MSISDN FPE transform
└── DEK for IMSI deterministic encryption
(IMEI uses shared HMAC key — no per-field DEK needed)
Choosing the protection level
The KEK is the ultimate trust anchor — its protection level determines the security ceiling of the entire pseudonymization system. Cloud KMS offers several options:
| Protection level | Where key material lives | Who can access it | When to use |
|---|---|---|---|
| SOFTWARE | Google's software infrastructure | Google cannot access customer keys, but the key material exists in software memory | Development, non-regulated workloads |
| HSM | FIPS 140-2 Level 3 certified hardware security modules | Key never leaves the HSM; non-extractable even by Google | Production default for anonymization — protects against software infrastructure breaches |
| EXTERNAL / EXTERNAL_VPC | On-premises or third-party HSM via Cloud EKM | Key material never enters Google's infrastructure | Regulations requiring provider inaccessibility (see FINMA/SBA below) |
For anonymization architectures, HSM is the minimum recommended protection level. The cost premium over SOFTWARE is modest (per-operation and per-active-key-version pricing), and KEK operations (wrap/unwrap DEKs) are infrequent relative to data throughput. Cloud EKM goes further — key material never enters Google's infrastructure — but adds operational complexity (availability depends on the external HSM).
| Regulation / Standard | Expectation |
|---|---|
| Swiss FADP + FINMA | FINMA Circular 2023/1 is risk-based and does not prescribe specific mechanisms. However, the SBA Cloud Guidelines (3rd edition, November 2025) require that the cloud provider cannot unilaterally access encryption keys. Cloud EKM (EXTERNAL) satisfies this most directly. Cloud HSM is typically accepted with contractual controls. For Swiss banking clients, external key management is the preferred posture; HSM is the pragmatic alternative when external key operations add prohibitive complexity. |
| PCI DSS 4.0 | Cryptographic keys must be managed in a device meeting industry standards — in practice, HSM certified to PCI PTS v4.0 or FIPS 140-2 Level 3+. Relevant when anonymization pipelines handle payment identifiers. |
| eIDAS 2.0 | Common Criteria EAL4+ with EN 419 221-5 is mandatory for qualified trust service providers. |
| GDPR | Does not explicitly mandate HSMs, but Article 32 requires "appropriate technical measures." HSM-backed key management is a strong demonstrable measure. |
For most Aliz engagements, specifying HSM is a one-line Terraform change (version_template { protection_level = "HSM" } on the google_kms_crypto_key resource).
Key rotation
Keys don't last forever. Compliance policies require periodic rotation, and key compromise demands immediate rotation. Envelope encryption separates these concerns into two distinct operations with very different impacts.
KEK rotation is routine and non-disruptive. When the KEK in Cloud KMS is rotated to a new version, the new version becomes the primary (used for new wrap operations). Existing wrapped DEKs remain wrapped with the old version — Cloud KMS can still unwrap them as long as the old version is enabled. The DEKs themselves don't change, so pseudonyms remain stable, joins continue to work, and no data needs re-processing. The critical rule: never disable or destroy old KEK versions that still wrap active DEKs. If you want to decommission an old version, first run an explicit re-wrap migration (unwrap each DEK with the old version, re-wrap with the current version, update the stored wrapped blob).
Design the KEK rotation on a standard schedule (annually or per compliance policy).
DEK rotation is disruptive and changes pseudonyms. Replacing the DEK that a transform uses means every pseudonym derived from it changes — records produced before and after the rotation cannot be joined by pseudonym. This is not a routine operation; it is a data lifecycle event with different consequences depending on the transform:
| Transform | What DEK rotation does | How to handle it |
|---|---|---|
| FPE / deterministic encryption | New DEK produces different ciphertexts. Pre- and post-rotation records cannot be joined. | Pin to a specific DEK for a defined period (quarterly, annually). When rotation is needed, re-encrypt the entire pseudonymized zone (Module 06) in a batch migration to restore join continuity. |
| HMAC keyed hashing | New key produces different hashes. Irreversible — existing hashes cannot be re-keyed because the original values are unknown. | Rotation is effectively a "pseudonym reset" — a permanent break in pseudonym continuity. Use only as a deliberate lifecycle event (annual reset, legal hold release), not as routine maintenance. |
| BigQuery DDM (hash masking) | BigQuery manages its own hashing internally. | No action needed — but note the hash is not keyed, so it provides less protection than HMAC. |
Design the DEK rotation around the data lifecycle — it should be a conscious decision triggered by a specific event, not an automated policy. Examples of when DEK rotation is warranted:
- Key compromise or suspected compromise — the most urgent case. Rotate immediately and re-pseudonymize all affected data.
- Personnel change in the key custodian role — when someone with DEK access leaves the organization or changes roles, rotating the DEK ensures they can no longer derive pseudonyms.
- End of a data sharing agreement — when a partner relationship ends and pseudonymized data was shared under a specific key, rotating the DEK ensures future data cannot be correlated with the historical export.
- Regulatory or legal hold release — when data previously under legal hold is released, rotating the DEK breaks continuity between the held period and ongoing operations.
- Major architectural migration — when moving to a new pipeline, new data platform, or new pseudonymization scheme, DEK rotation provides a clean cryptographic boundary between the old and new systems.
Individual erasure — crypto-shredding
The previous sections covered a shared-key architecture: one key (or a small set of keys) for all subjects, protected in KMS, rotated on a lifecycle schedule. This is simple, fast, and sufficient when GDPR right-to-erasure is handled by deleting individual records. Module 10 covers the operational workflow for processing erasure requests, including erasure windows and audit documentation. But record-level deletion across a distributed data platform is hard — the same subject's data may exist in the pseudonymized zone, in downstream materialized views, in backup snapshots, in ML feature stores.
Crypto-shredding offers an alternative: instead of finding and deleting every record, destroy the key that produced the subject's pseudonyms. The pseudonymized values become undecryptable — they can no longer be reversed to the original identifiers — and unattributable — they can no longer be linked to a real-world identity.
This requires per-subject keying — a single shared key for all subjects means destroying it erases everyone, not just the requested individual. Per-subject keying comes with a trade-off: each subject's pseudonyms are produced by a different key, so cross-subject joins on pseudonymized identifiers are not possible. This strengthens crypto-shredding (no cross-subject correlation possible after key destruction) but is a constraint for analytics that need cross-subject pseudonym consistency. If both per-subject erasure and cross-subject joins are needed, consider a hybrid: a shared key for joinable pseudonyms plus a per-subject key for the fields targeted by erasure.
Two approaches to per-subject keying
Per-subject crypto-shredding is an established pattern — endorsed by the EDPB (Guidelines 02/2025), implemented in production systems across healthcare, financial services, and streaming platforms, and supported by GCP's native BigQuery AEAD encryption functions (based on Google Tink). Two architectural approaches exist:
Approach A: Same-table keysets (BigQuery AEAD). Store a KMS-wrapped keyset as a column in the same table as the encrypted data. BigQuery's AEAD.ENCRYPT / AEAD.DECRYPT_STRING functions handle encryption and decryption at query time. Simpler architecture — no separate DEK table, no side inputs, no coordinator. Crypto-shredding requires NULLing or deleting the keyset column across all the subject's rows (a multi-row UPDATE or DELETE), which is heavier but straightforward for moderate record counts.
Approach B: Separate DEK table. Store per-subject wrapped DEKs in a dedicated key management table, separate from the pseudonymized data. Crypto-shredding is a single-row DELETE on the DEK table. Cleaner erasure semantics, but adds the coordination complexity described below (side inputs, atomic coordinators).
| Dimension | Same-table keysets (A) | Separate DEK table (B) |
|---|---|---|
| Crypto-shredding | Multi-row update (NULL the keyset column for the subject's records) | Single-row delete |
| Architecture complexity | Simpler — no separate store, no side inputs | More complex — DEK table, coordinator, side-input refresh |
| Re-identification | Query-time decryption via AEAD.DECRYPT_* — pure SQL | Compute-then-filter flow (lookup DEK → compute pseudonym → filter → decrypt) |
| Residual groupability after shredding | Encrypted values differ per record (AEAD is randomized) — no grouping possible | Deterministic pseudonyms remain groupable (see the erasure properties section below) |
Approach A is simpler and has a privacy advantage: AEAD encryption is randomized (same input + same key → different ciphertext each time), so after keyset deletion, records can't even be grouped. Approach B is better when the erasure operation must be a single atomic action, or when the pseudonymized identifiers must be deterministic for join compatibility across tables.
The rest of this section details Approach B (separate DEK table), as it aligns with the deterministic pseudonymization patterns from Module 06's reference architectures. For Approach A, refer to BigQuery's AEAD encryption documentation and the Google Cloud community articles on end-to-end crypto-shredding with BigQuery AEAD.
Approach B architecture:
- One KEK in Cloud KMS (the same one from the key hierarchy) wraps all per-subject DEKs.
- One DEK per subject — a random AES-256 key generated when the subject first enters the system, wrapped by the KEK, and stored as a row in a BigQuery table.
When a new record arrives, the pipeline computes a lookup hash of the identifier and checks the DEK table (loaded as a Beam side input). If the subject exists, it unwraps their DEK via KMS (cached in-memory) and pseudonymizes the identifier. If the subject is new, it generates a random DEK, wraps it via KMS, inserts into the DEK table, and pseudonymizes. The plaintext DEK is discarded from memory after use.
Implementation note: Per-subject DEKs cannot use SDP's standard de-identification templates. SDP's CryptoReplaceFfxFpeConfig and CryptoDeterministicConfig each take a single fixed crypto_key — there is no mechanism to pass a different key per record. Per-subject pseudonymization therefore requires in-pipeline cryptographic operations: a Beam DoFn that performs FPE or AES-SIV encryption directly using a crypto library (e.g., Google Tink), with the per-subject DEK retrieved from the side input. This is a different implementation pattern from the SDP-based pipeline described in Module 06, with different throughput characteristics and key-exposure properties. SDP remains the right choice for shared-key pseudonymization; per-subject keying is a custom pipeline concern.
The lookup hash (subject_id_hash) is computed using a dedicated lookup key — an HMAC key stored in KMS or Secret Manager, separate from both the KEK and the pseudonymization DEKs. This key must be protected with the same rigor as the KEK: if it leaks, an attacker who knows a subject's original identifier can compute their lookup hash and determine which DEK table row belongs to them, even without the DEK itself.
Cloud KMS
├── KEK: subject-encryption-master (1 key, HSM protection)
│ └── Wraps all per-subject DEKs
└── Lookup key: subject-hash-key (HSM protection)
└── Used to compute subject_id_hash for DEK table lookups
BigQuery dataset: key_management (restricted IAM)
└── Table: subject_deks
├── subject_id_hash | wrapped_dek | created_at
├── a8f3b2... | [encrypted] | 2025-01-15
├── c4d9e1... | [encrypted] | 2025-01-15
└── ... (one row per subject)
Coordinating DEK creation for new subjects
This process sounds clean enough, but the side-input pattern above has an inherent race condition that needs proper handling: Two workers processing records for the same new subject simultaneously can both miss the subject in the stale snapshot, generate different DEKs, and insert both. The same subject ends up with two different DEKs, and records pseudonymized with one cannot be decrypted with the other. For HMAC-based transforms this is unrecoverable as the hashes are irreversible.
BigQuery does not support atomic conditional inserts, so the DEK table alone cannot prevent this. The solution is having an atomic coordinator in front of BigQuery. Multiple options exist, each with different trade-offs:
| Approach | Mechanism | Best for |
|---|---|---|
| Coordinator service (Cloud Run + Firestore) | Workers call a "get-or-create" API. Firestore transactions ensure only one DEK per subject. Fully durable. | Stable populations with low new-subject rates (telco). ~20–50ms latency per new-subject lookup — invisible when new subjects are rare. |
| Redis coordinator (Memorystore) | Redis SETNX is atomic — first worker wins. DEKs synced to BigQuery via write-through. | Higher new-subject rates (e-commerce campaigns). Sub-millisecond coordination. Requires durability strategy for the Redis→BigQuery sync window. |
| Batch pre-generation | Scan the raw zone for new subjects before the pipeline runs, pre-generate DEKs. Pipeline only looks up — never creates. | Batch-only ingestion, or streaming with batch-discoverable new subjects (daily onboarding files). |
For most engagements, the coordinator service (Cloud Run + Firestore) is simplest and fully durable. BigQuery is the analytical store for DEKs (side-input reads, re-identification); a transactional system sits in front of it for DEK creation.
How re-identification and erasure work
The DEK table and pseudonymized records share no join key — deliberately. Storing a subject identifier on every record would enable a simple SQL join for re-identification, but it would also preserve linkability after crypto-shredding: even with the DEK deleted, all records for the subject would remain groupable by that identifier.
Re-identification is a compute-then-filter operation:
- Start with the original identifier (e.g., MSISDN
+36201234567) - Compute the lookup hash:
subject_id_hash = HMAC(MSISDN, lookup_key) - Retrieve the wrapped DEK:
SELECT wrapped_dek FROM subject_deks WHERE subject_id_hash = 'a8f3b2...' - Unwrap the DEK via KMS
- Compute the expected pseudonym:
pseudonym = FPE(MSISDN, DEK) - Filter records:
SELECT * FROM pseudo_cdrs WHERE msisdn_pseudo = 'pseudonym' - Verify and decrypt: for deterministic encryption (AES-SIV), the authentication built into SIV mode rejects records encrypted with a different DEK, automatically filtering collision false positives. For FPE, which is not authenticated, decrypting a collision record with the wrong key produces a valid-looking but incorrect value — verify by checking that the decrypted identifier matches the target from step 1 and discard mismatches.
This requires knowing the original identifier to start. Without it, there is no path from the pseudonymized records to the DEK table — which is exactly the property that makes crypto-shredding effective.
Crypto-shredding is a DELETE on the DEK table. Once the subject's row is deleted, nobody can compute the pseudonym (requires the DEK) or map the pseudonym back to the original identifier (requires the DEK to decrypt). The records become unattributable (cannot be linked to a real-world identity) and undecryptable (the pseudonymized fields cannot be reversed). However, because the pseudonym is deterministic, records sharing the same pseudonym value remain groupable — an observer can see that N records belong to the same unknown person, even without knowing who. This is an inherent property of deterministic pseudonymization; true unlinkability would require randomized tokens (which sacrifice joinability), deleting the pseudonym values themselves, or using Approach A (AEAD) where ciphertexts are randomized.
Erasure windows. In practice, crypto-shredding is not instantaneous: pipeline workers may hold plaintext DEKs in memory caches (short TTL, typically minutes), side-input snapshots retain wrapped DEKs until the next refresh, and BigQuery time travel retains deleted rows for up to 14 days. These windows are bounded and well within GDPR's "without undue delay" standard (one-month outer limit per Article 12). The EDPB, UK ICO, and French CNIL all recognize crypto-shredding as valid erasure provided the encryption is strong and key destruction is irreversible and auditable — none require simultaneous invalidation of every cache and snapshot. Document the windows in the engagement's erasure policy: in-memory caches expire within minutes, side inputs refresh on schedule, and BigQuery time travel is mitigated by the wrapped DEK being useless without KEK access (separately controlled via KMS IAM).
- EDPB Guidelines 02/2025 — "where personal data has been encrypted using state of the art encryption technology and the encryption key has been securely destroyed, the encrypted data may be considered to have been erased"
- NIST SP 800-88 Rev.1 — recognizes cryptographic erasure as a valid sanitization technique (Appendices B and C)
- ISO/IEC 27001 Annex A.8.3.2 — secure disposal procedures, including key destruction traceability
- BigQuery Encryption Functions — Data Deletion/Retention with Crypto Shredding (Part I) — Parviz Deyhim (Google Cloud), BigQuery AEAD per-user keyset pattern
- End-to-End Crypto Shredding (Part II) — Parviz Deyhim (Google Cloud), Tink integration for pipeline-to-BigQuery crypto-shredding
- BigQuery AEAD encryption concepts — GCP documentation for the Approach A (same-table keyset) pattern
- Google Cloud data deletion overview — how Google handles deletion across active and backup storage, including cryptographic erasure
Choosing a DEK store
The DEK table needs to support three operations: high-throughput reads during pipeline execution (via side input or direct lookup), rare re-identification queries, and atomic deletes for crypto-shredding. No single storage system is ideal for all three — the choice depends on the engagement's subject velocity, security model, and operational constraints.
Some practical options that should cover most engagements:
| Store | Strengths | Limitations | Best for |
|---|---|---|---|
| BigQuery | Same IAM, VPC-SC, and audit infrastructure as the pseudonymized data (Module 06). Policy tags restrict DEK access. Re-identification query is a natural fit (point query + filtered scan). Crypto-shredding is a simple row delete. | Not a key-value store — pipeline reads must go through a Beam side input, not direct lookups. Deleted rows recoverable for up to 14 days (time travel + fail-safe). | Most engagements — stable subject populations (telco, established e-commerce) where the side-input pattern covers >99% of lookups and the coordinator handles new subjects. |
| Firestore | Transactional reads and writes — can serve as both the coordinator and the DEK store, eliminating the sync gap. Database-level IAM controls access; application-level authorization logic in the Cloud Run coordinator enforces per-subject policies. | Not designed for analytical queries — re-identification requires application-level orchestration rather than SQL. PITR (point-in-time recovery) means deleted data may be recoverable within the PITR window — configure retention accordingly and document in the erasure policy. Separate project from BigQuery data adds operational surface. | Engagements requiring strict physical separation of keys and data, or where BigQuery's time-travel window is unacceptable. |
| Bigtable | Millions of point reads/writes per second. Lowest latency for pipeline-hot-path lookups. Atomic single-row operations via CheckAndMutateRow — sufficient for conditional insert-if-absent with subject_id_hash as the row key, so Bigtable can serve as its own coordinator without an external service. | No cross-row transactions. No built-in column-level access control. | Very high new-subject rates (ad-tech, IoT with per-device keys) where BigQuery side-input refresh and Firestore latency are both insufficient. |
| Redis (Memorystore) | Sub-millisecond reads via SETNX for atomic coordination. Excellent as a cache/coordinator layer in front of a durable store. | Not a primary data store — requires write-through to BigQuery or Firestore for durability. Adds infrastructure dependency. | Hybrid pattern: Redis for pipeline-time coordination and caching, BigQuery or Firestore as the durable backing store. |
For most Aliz engagements, BigQuery is the default — it keeps the DEK table in the same governance perimeter as the data it protects, and the side-input pattern handles stable subscriber populations well. Mitigate the time-travel caveat by setting the window to the minimum (2 days) and documenting that the wrapped DEK is useless without KEK access (separately controlled via KMS IAM). When the engagement requires stricter erasure guarantees, physical key-data separation, or high-velocity subject creation, move to Firestore or Bigtable and sync to BigQuery for analytical re-identification queries.
Start simple: shared key, stateless crypto, HMAC where re-identification isn't needed. This covers most fields with no key management complexity. Add per-subject DEKs and crypto-shredding only for fields where individual erasure is a real requirement — and design it from the start, because retrofitting per-subject keying onto a shared-key architecture requires re-pseudonymizing all historical data.
Next: Module 08 covers AI and LLM workload patterns — how anonymization interacts with machine learning training, LLM prompting, RAG retrieval, and enterprise AI products on GCP.
Created by Claude Opus with ❤️ for the Aliz Data Engineering team.