💻 computer science

Post-Quantum Security of Block Cipher Constructions

This paper establishes the theoretical foundations for post-quantum security in symmetric-key cryptography by providing the first rigorous security proofs for key-length extension schemes, tweakable block ciphers, and various encryption and authentication modes using new techniques applicable to both the plain and quantum ideal cipher models.

Original authors: Gorjan Alagic, Chen Bai, Christian Majenz, Kaiyan Shi

Published 2026-04-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gorjan Alagic, Chen Bai, Christian Majenz, Kaiyan Shi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very secure, high-tech safe (a block cipher) that you use to lock up your most valuable secrets. For decades, we've been confident that these safes are unbreakable, even by super-smart computers.

But now, a new kind of computer is coming: the Quantum Computer. Think of this not just as a faster computer, but as a computer that can look at a safe from every possible angle at the same time. It's like having a ghost that can walk through walls and try every combination of keys simultaneously.

The big question is: Are our current digital safes still safe when a quantum ghost comes knocking?

This paper is a team of security experts (Alagic, Bai, Majenz, and Shi) who decided to build a new set of blueprints to test these safes against quantum ghosts. They didn't just look at one safe; they looked at the entire "safe-making industry," including how we extend keys, how we tweak locks, and how we use these locks to send secret messages.

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Ghost" in the Machine

In the old days, to break a safe, you had to try keys one by one. If the safe had a 128-bit key, it would take a normal computer billions of years to guess it.

The Quantum Threat: A quantum computer can use a trick called Grover's Algorithm. Instead of trying keys one by one, it tries them all at once. It's like having a master key that can instantly shrink the time it takes to break a safe from billions of years to just a few days.
The Gap: We knew how to protect public-key cryptography (like the locks on your bank website) from quantum computers. But we didn't have a rigorous mathematical proof that the symmetric locks (the ones inside the safe itself) were safe. It was a "blind spot" in our security.

2. The New Tool: The "Resampling" Trick

To prove these safes are safe, the authors invented a new mathematical tool called Ideal Cipher Resampling.

The Analogy: Imagine you are a magician trying to prove that a deck of cards is truly random. You secretly swap a few cards in the deck while no one is looking.
The Old Way: In classical security proofs, you could easily track these swaps.
The Quantum Way: A quantum observer is like a ghost looking at the deck. If you swap a card, the ghost might sense the change instantly because it's looking at the whole deck at once.
The Solution: The authors developed a "Resampling Lemma." It's a mathematical guarantee that says: "Even if a quantum ghost is watching, if you only swap a tiny number of cards, the ghost won't notice unless it has already looked at almost every single card in the deck."
Why it matters: This allows them to swap out the "real" lock for a "perfectly random" lock in their proofs without the quantum attacker noticing, proving the real lock is just as good as the perfect one.

3. The Three Big Wins

Using this new tool, they tested three major types of cryptographic constructions:

A. The "Key-Lengthener" (FX Construction)

What it is: Sometimes a lock is too small. So, we wrap it in extra layers of padding (like putting a small safe inside a bigger safe) to make the key longer. This is called FX.
The Verdict: They proved that even with quantum computers, this "double-wrapping" technique works.
Real World: This directly secures lightweight ciphers like PRINCE and PRIDE, which are used in things like smart cards and IoT devices. They showed that simply doubling the key size (a common rule of thumb) is actually the right move here.

B. The "Tweakable" Locks (LRW and XEX2)

What it is: Imagine a master key that can open a specific door, but you want to change the lock slightly every time you open it so that if someone steals the key, they can't use it on the next door. This is called a Tweakable Block Cipher.
The Verdict: They proved these are safe too.
Real World: This is huge because XEX2 is the engine behind XTS-AES, the standard used to encrypt your hard drives (like your laptop or phone storage). The authors confirmed that your hard drive encryption is robust against quantum attacks, provided you use the right key sizes.

C. The "Modes of Operation" (How we use the locks)

What it is: A block cipher is just a single lock. To encrypt a whole movie or a long email, you need a "mode" (a recipe) on how to use that lock over and over. Examples include CBC, GCM, and CMAC.
The Verdict: They found a "Universal Translator." They showed that if the underlying lock is safe, the recipe (the mode) is also safe against quantum computers.
Real World: This means the protocols protecting your internet traffic (HTTPS), your emails, and your cloud storage are likely safe, as long as the underlying lock (like AES) is used correctly.

4. The "Tightness" Check: Are we over-preparing?

A common fear is that to be safe from quantum computers, we need to make our keys massively huge (like doubling or tripling them), which slows everything down.

The Finding: The authors calculated the exact "breaking point." They found that for many of these systems, you don't need to go overboard. You just need to increase the key size slightly (e.g., from 128 bits to 256 bits).
The Analogy: It's like realizing you don't need to build a fortress wall 100 feet high to stop a quantum ghost; a wall 20 feet high is actually enough if built with the right bricks. This saves us from unnecessary slowdowns in our technology.

Summary

This paper is a foundational step. It moves us from "We hope these locks are safe" to "We have a mathematical proof that these locks are safe."

For the average user: It means your current digital security (hard drives, internet, apps) is likely ready for the quantum future, provided we update our keys to be a bit longer.
For the industry: It gives engineers the confidence to design new systems without having to reinvent the wheel. They can take existing, proven designs and just apply the new "quantum-safe" math to them.

In short: The quantum ghost is coming, but thanks to this paper, we now know exactly how to reinforce our locks so the ghost can't get in.

1. Problem Statement

While the impact of quantum computing on public-key cryptography (e.g., via Shor's algorithm) is well-understood, the post-quantum security of symmetric-key cryptography, particularly block ciphers and their associated constructions, remains largely unexplored.

The Gap: Existing security proofs for symmetric schemes often rely on classical assumptions (e.g., transcripts, classical queries) that do not translate to the quantum setting.
The Threat Model: In a post-quantum scenario, an adversary possesses a quantum computer capable of executing the block cipher algorithm in superposition. This leads to the Quantum Ideal Cipher Model (QICM), where the adversary has quantum oracle access to the underlying ideal cipher (both forward and inverse), while the construction itself (using secret keys) is typically queried classically.
The Challenge: Proving security in QICM is difficult because classical techniques (like hybrid arguments based on transcripts) fail when the adversary can query the oracle in superposition. Furthermore, standard "doubling the key length" heuristics are not rigorously justified and may be insufficient or overkill.

2. Methodology

The authors develop a rigorous framework for proving post-quantum security in the QICM. Their methodology relies on two main pillars:

A. Ideal Cipher Resampling Lemma

The core technical innovation is a new Resampling Lemma tailored for the Ideal Cipher Model.

Concept: In security proofs, one often needs to modify the behavior of an ideal cipher (e.g., swapping outputs for specific inputs) to simulate a "random" world. In the quantum setting, an adversary might detect these modifications if they have queried those specific points in superposition.
The Lemma: The authors prove that a quantum distinguisher cannot detect such modifications (resampling) unless it has made a very large number of queries to the ideal cipher prior to the modification.
Generalization: Unlike previous resampling lemmas that applied only to random functions or permutations, this lemma applies to ideal ciphers (keyed permutations) and allows for arbitrary distributions of the key and resampling points.

B. Hybrid Argument with Resampling

They adapt the hybrid argument technique (previously used for Even-Mansour ciphers) to the QICM:

Hybrid Sequence: They construct a sequence of hybrid experiments transitioning from the "real" world (using the block cipher construction) to the "ideal" world (using a random permutation).
Step-by-Step Switching: Instead of switching all queries at once, they switch classical queries one by one.
Resampling: When switching a query to the ideal case, they simultaneously modify the underlying ideal cipher in a few locations to maintain consistency with the transcript.
Bounding Distinguishability: They use the Resampling Lemma to bound the adversary's ability to distinguish between hybrids, showing that the advantage is negligible unless the adversary makes a prohibitive number of quantum queries.

3. Key Contributions

The paper provides the first post-quantum security proofs for several fundamental symmetric-key constructions:

FX Construction (Key-Length Extension):
- Proves the post-quantum security of the FX scheme, which extends the key length of a block cipher ( $E_{k_0}(x \oplus k_1) \oplus k_2$ ).
- Establishes tight security bounds that match known quantum attacks (Grover search, BHT collision finding, and Offline-Simon attacks).
- Applications: Directly establishes post-quantum security for lightweight ciphers PRINCE and PRIDE, which are instantiations of the FX construction.
Tweakable Block Ciphers (LRW and XEX2):
- Proves security for LRW (Liskov-Rivest-Wagner) and XEX2 in both the plain model and QICM.
- XEX2 Significance: XEX2 is the core of the XTS-AES standard used for disk encryption. This is the first rigorous post-quantum security analysis for XTS-AES.
- The bounds account for both classical collision attacks (birthday bound) and quantum speedups in key search.
Block Cipher Modes (General Lifting Theorem):
- Introduces a General Lifting Theorem (Theorem 7 and 8) that allows classical security proofs of block cipher modes (e.g., CBC, CTR, GCM, CMAC) to be "lifted" to the post-quantum setting.
- The theorem states that the post-quantum security of a mode is bounded by the post-quantum security of the underlying block cipher plus the classical information-theoretic security of the mode.
- This implies that most modes used in secure internet traffic (like GCM) remain secure in the post-quantum era, provided the underlying block cipher (e.g., AES) is secure against quantum key search.

4. Key Results and Security Bounds

The authors derive precise security bounds (distinguishing advantages) for various constructions. Let $q_C$ be classical queries, $q_Q$ be quantum queries, $m$ be the key length, and $n$ be the block size.

FX Construction:
- Advantage $\approx O(q_C \sqrt{q_Q} + q_Q \sqrt{q_C}) \cdot 2^{-(m+n)/2}$ .
- This bound is tight, matching the complexity of the best-known quantum attacks (Offline-Simon and Grover+BHT).
LRW Construction:
- Advantage $\approx O(q_C^2 2^{-n}) + O((q_C \sqrt{q_Q} + q_Q \sqrt{q_C}) 2^{-(m+n)/2})$ .
- The $q_C^2 2^{-n}$ term corresponds to the classical birthday collision attack.
- The second term corresponds to quantum key recovery attacks.
Block Cipher Modes (in QICM):
- For modes like CBC, GCM, and CMAC, the advantage is bounded by:
  $\text{Adv} \leq \frac{q_Q^2}{2^m} + \delta(q_C)$
- Here, $\frac{q_Q^2}{2^m}$ represents the quantum advantage in searching the key space (Grover's limit), and $\delta(q_C)$ is the classical information-theoretic bound (e.g., birthday bound $q_C^2/2^n$ ).

5. Significance

Foundational Theory: This work establishes the first rigorous theoretical foundation for post-quantum symmetric-key cryptography, moving beyond heuristic arguments.
Practical Relevance: It validates the security of widely deployed standards (AES, XTS-AES, GCM) against quantum adversaries, provided parameters are chosen correctly.
Parameter Selection: The tight bounds allow cryptographers to determine exact parameter requirements. For instance, it confirms that simply doubling the key length is often sufficient to counter Grover's algorithm, but the interaction between classical and quantum queries ( $q_C$ and $q_Q$ ) must be carefully analyzed for specific constructions like FX.
Methodological Advance: The Ideal Cipher Resampling Lemma is a powerful new tool that can likely be applied to prove the security of other complex symmetric constructions in the quantum setting.

In summary, the paper demonstrates that while quantum computers pose a threat to symmetric cryptography (primarily via key search), many standard constructions remain secure with appropriate parameter adjustments, and their security can now be formally proven using the developed hybrid-resampling techniques.