up:: Migration Architecture MOC

Re-Encrypting Data at Rest for PQC

Re-encrypting data at rest for PQC is the question of whether stored data has to be unwrapped and re-wrapped under post-quantum protection, and the reassuring answer is that most of it doesn’t, because the bulk encryption of stored data uses symmetric algorithms like AES-256 that survive the quantum era. What’s actually quantum-vulnerable in a data-at-rest system is the public-key layer that protects the keys, not the symmetric layer that protects the data, so the fix is usually rotating and re-wrapping keys rather than decrypting and re-encrypting petabytes of archives. The exception is data that was protected in a way that ties its confidentiality to a quantum-vulnerable algorithm, or data already exposed through harvest-now-decrypt-later, which is where a genuine re-encryption effort becomes necessary.

The short version:

1. Most stored data is bulk-encrypted with symmetric algorithms like AES-256, which survive quantum computers, so the data itself usually doesn’t need re-encrypting.
2. The quantum-vulnerable part of a data-at-rest system is the public-key layer that wraps and delivers the symmetric keys, so the common fix is key rotation and re-wrapping, not touching the data.
3. Full re-encryption is warranted where data was protected directly by a quantum-vulnerable algorithm, or where its confidentiality must outlast the arrival of a quantum computer and it’s already at harvest-now-decrypt-later risk.
4. The decision is per data set, driven by how long each must stay confidential and how it was encrypted, so it starts with discovery, not with a blanket re-encrypt-everything project.
5. Crypto-agility in the storage layer is what keeps this from recurring, because a system designed to rotate keys and algorithms cleanly makes the next transition routine.

Picture a warehouse of locked strongboxes, where each box is sealed with a heavy, quantum-resistant padlock, and the keys to all those padlocks are themselves kept in one master safe whose combination lock is the old, quantum-vulnerable kind. A quantum computer can crack the combination on the master safe, which gets it every key, which opens every box. The strongboxes and their padlocks are fine. Replacing the vulnerable combination lock on the master safe, and issuing new keys, protects everything inside without ever having to open and reseal a single strongbox. That’s key rotation. You only actually re-seal the boxes, which is re-encryption, for the ones whose padlock itself was the weak kind, or the ones someone already photographed the contents of.

Do I have to re-encrypt data I already stored?

For most data, no, because the algorithm protecting the data itself is usually symmetric and survives quantum computers. Data at rest is typically encrypted with a symmetric cipher such as AES-256, and Grover’s algorithm only provides a square-root speedup against symmetric keys, which halves their effective strength rather than breaking them. NIST states in its report on post-quantum cryptography that a sufficiently long symmetric key remains secure, so AES-256 keeps roughly 128 bits of effective strength even against a quantum attacker and needs no replacement.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, NISTIR 8105. AES-256 is standardized in FIPS 197, FIPS 197, and its 256-bit classical security strength is tabulated in NIST SP 800-57 Part 1 Rev. 5, SP 800-57; Grover’s square-root speedup takes that to roughly 128 bits of quantum security, still well above any migration threshold.

So the sweeping fear, re-wrapping 15 years of archives, is usually the wrong picture. The data was encrypted with an algorithm that isn’t the problem. What has to change is the layer above it, where the symmetric keys are protected and delivered, because that layer commonly uses quantum-vulnerable public-key cryptography. The honest scope of a data-at-rest migration is “fix how the keys are protected,” and only “re-encrypt the data” for the specific cases where the data’s own protection is quantum-vulnerable.

Where is a data-at-rest system actually quantum-vulnerable?

The vulnerability lives in the key-protection layer, not the data-encryption layer, because almost every real storage system uses envelope encryption, which splits those two jobs. Understanding the split is what lets you fix the right thing.

1. The data-encryption key (DEK) protects the data. A symmetric key, usually AES-256, encrypts the actual bytes. This layer is quantum-resistant, so the data stays protected.
2. The key-encryption key (KEK) protects the DEK. In envelope encryption the DEK is itself encrypted, often by a key kept in a hardware security module or a cloud key-management service. Where that wrapping or the key delivery relies on a quantum-vulnerable public-key algorithm like RSA, that’s the exposed point.
3. The transport and access path uses public-key crypto. Getting keys to the systems that need them, and authenticating those systems, often runs over TLS and public-key exchange, which is quantum-vulnerable and is being addressed separately through hybrid key exchange for data in motion.

The consequence is that a quantum attacker’s path to your stored data runs through the public-key crypto that protected or delivered the AES key, rather than through the AES that encrypted the data. Close that path by moving the key-protection and key-delivery layers to post-quantum algorithms, and the symmetric data encryption underneath keeps doing its job unchanged.

When is full re-encryption actually necessary?

Full re-encryption is necessary when the data’s own confidentiality is tied to a quantum-vulnerable algorithm, or when the data is long-lived and already exposed to harvesting, so re-wrapping the keys isn’t enough. Those cases are the real re-encryption projects, and they’re worth identifying precisely because they’re the expensive exception rather than the rule.

1. Data encrypted directly with a quantum-vulnerable algorithm. If a data set was encrypted using public-key cryptography directly, or with a scheme whose confidentiality rests on RSA or elliptic-curve math, then the data itself is vulnerable and has to be decrypted and re-encrypted under a quantum-safe scheme. This is uncommon for bulk storage but does occur.
2. Long-lived confidential data at harvest-now-decrypt-later risk. Data whose confidentiality must survive past the plausible arrival of a CRQC, and that has been transmitted or stored in a way an adversary could have copied, is exposed under HNDL. If the copy an adversary might hold was protected by a quantum-vulnerable algorithm, re-encrypting your own copy protects the future, though it can’t un-expose a copy already taken.
3. Weak symmetric protection. Data still under AES-128 or an older cipher, rather than AES-256, has a thinner margin under Grover’s, so re-encrypting it up to AES-256 is the sensible move for anything that must stay confidential for decades.

The discipline is to make this a per-data-set decision. A blanket “re-encrypt everything” project spends enormous effort re-wrapping data that was never at risk, while the targeted version finds the specific data sets that meet one of these conditions and re-encrypts only those. That targeting is a direct output of discovery, which is why the decision starts with knowing what you have and how it was protected.

What’s the difference between key rotation and re-encryption?

Key rotation replaces the keys that protect data, while re-encryption replaces the encryption of the data itself, and the whole cost saving in a data-at-rest migration comes from knowing which one a situation actually requires. They solve different problems, and confusing them leads either to underprotecting real exposure or to a wildly overscoped project.

	Key rotation	Full re-encryption
What changes	The keys that wrap or deliver the data-encryption key	The encryption of the data bytes themselves
What it touches	The key-management and key-delivery layer	Every object in the data set, read and rewritten
Typical cost	Low, a key-management operation	High, proportional to the volume of data
When it’s enough	The data cipher is quantum-safe (AES-256) and only the key-protection layer was vulnerable	The data’s own encryption was quantum-vulnerable or too weak
PQC relevance	Move the key-wrapping and delivery to post-quantum algorithms	Re-encrypt under a quantum-safe symmetric scheme

The practical rule is to reach for key rotation first and re-encryption only where a data set genuinely meets a re-encryption condition. Rotating and re-wrapping keys under post-quantum protection secures the vast majority of stored data at a fraction of the cost of decrypting and re-encrypting it, and it’s the move key management systems are already built to perform cleanly.

How does crypto-agility change the picture for stored data?

Crypto-agility in the storage layer turns re-encryption from a crisis into a routine operation, because a system designed to rotate keys and swap algorithms cleanly can migrate stored data without a bespoke project each time. The reason a re-encryption effort feels daunting is usually that the storage system was never built to change its cryptography, so every rotation is a special event. An agile design makes it a scheduled maintenance task instead.

A crypto-agile storage architecture keeps the algorithm a configurable choice rather than a hardcoded assumption, tracks which key and algorithm protected each object so it knows what still needs migrating, and supports rotating the key-encryption layer without decrypting the data underneath. Building that agility is an up-front cost, and it’s the investment that keeps the next transition, whether it’s a future algorithm deprecation or a key compromise, from being another multi-year re-encryption program. For long-lived data especially, agility is what makes the difference between a storage estate that can follow the standards forward and one that has to be rebuilt each time they move.

Common misconceptions

1. “Quantum computers mean I have to re-encrypt all my archives.” Most archives are bulk-encrypted with AES-256, which survives quantum computers, so the data usually stays put. What needs changing is the public-key layer that protects and delivers the keys, which is key rotation, not re-encryption.
2. “AES is broken by quantum, so my stored data is exposed.” Grover’s algorithm only halves symmetric strength, so AES-256 keeps about 128 bits of effective security. Symmetric encryption of data at rest is one of the parts that carries forward largely intact.
3. “Key rotation and re-encryption are the same thing.” Rotation replaces the keys protecting the data; re-encryption replaces the data’s encryption itself. One is a cheap key-management operation, the other is a data-volume-scaled project, and using the wrong one either overspends or underprotects.
4. “Re-encrypting now protects data that was already harvested.” Re-encrypting your copy protects the future, but a copy an adversary already took under harvest-now-decrypt-later stays exposed to a future quantum computer. Re-encryption can’t reach a copy you don’t hold, which is why the harvest window matters so much.
5. “I should just re-encrypt everything to be safe.” A blanket re-encryption project spends heavily on data that was never at risk. The targeted approach re-encrypts only the data sets whose own protection was quantum-vulnerable or too weak, which is far cheaper and just as safe.

Questions people ask

Do I have to re-encrypt 15 years of stored data for post-quantum? Usually not. If those archives are encrypted with a symmetric cipher like AES-256, the data itself is quantum-safe, and the migration is about moving the key-protection and key-delivery layer to post-quantum algorithms. You re-encrypt only the specific data sets whose own encryption was quantum-vulnerable.

Is my AES-encrypted data safe from quantum computers? Yes, with a sufficient key length. AES-256 keeps roughly 128 bits of effective strength under Grover’s algorithm, which is far beyond any foreseeable machine. AES-128 has a thinner margin, so long-lived data under it is worth moving up to AES-256.

What actually needs to change in my storage system? The public-key layer that wraps the data-encryption keys and the path that delivers them, because that’s the quantum-vulnerable part. In envelope encryption terms, the key-encryption key and its transport move to post-quantum, while the symmetric data-encryption key keeps protecting the data. The database-specific version of this, plus the TLS-to-database channel that a database estate also carries, is in PQC for Databases and Data-at-Rest Key Wrapping.

How do I know which data needs full re-encryption? Through discovery. Re-encrypt data sets that were encrypted directly with a quantum-vulnerable algorithm, or that must stay confidential for decades and are exposed to harvesting. Everything else is a key-rotation problem, not a re-encryption one.

Can I just rotate keys instead of re-encrypting? For most data, yes, and that’s the point. Rotating and re-wrapping keys under post-quantum protection secures data whose symmetric encryption is already quantum-safe, at a fraction of the cost of decrypting and re-encrypting the data itself.

Does re-encrypting protect against harvest-now-decrypt-later? Only for copies you control. It protects your stored copy going forward, but it can’t reach a copy an adversary already harvested, which stays exposed to a future quantum computer. That’s why closing the harvest window on data in motion matters alongside the data-at-rest work.

How do I avoid doing this again in 5 years? Build crypto-agility into the storage layer, so key and algorithm changes are configurable operations rather than bespoke projects. An agile storage system can follow the standards forward without a fresh re-encryption program each time they move.

---

Everything here is the map, given freely. When your team needs its stored data triaged by confidentiality lifetime and encryption method, the key-rotation cases separated from the genuine re-encryption cases, and an agile storage layer that won’t force this again, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-14 · Maintained by Addie LaMarr, LaMarr Labs.