🔢 mathematics

Explainable PQC: A Layered Interpretive Framework for Post-Quantum Cryptographic Security Assumptions

This paper proposes "Explainable PQC," an interdisciplinary, three-layer framework combining complexity theory, combinatorial Hodge theory, and empirical Julia-based experimentation to enhance the transparency and communication of security assumptions in post-quantum cryptography, specifically for lattice-based schemes like ML-KEM and ML-DSA, without claiming new hardness results or attacks.

Original authors: Daisuke Ishii, Rizwan Jahangir

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daisuke Ishii, Rizwan Jahangir

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 are trying to explain why a specific type of digital lock (Post-Quantum Cryptography, or PQC) is safe from future "super-hackers" (quantum computers). The problem is that the math behind these locks is so complex that it looks like alien code to most people, including business leaders and policymakers.

This paper, "Explainable PQC," doesn't try to invent a new lock or break an existing one. Instead, the authors (Daisuke Ishii and Rizwan Jahangir) propose a new way to translate the complex math into a story that humans can understand. They call this a "Layered Interpretive Framework."

Think of it like explaining how a high-security bank vault works to a tourist. You don't need to show them the blueprints of the steel alloy or the quantum physics of the sensors. You just need to explain the layers of protection in a way that makes sense.

Here is the paper's framework, broken down into three simple layers using everyday analogies:

Layer 1: The "Who Can Break It?" Checklist (Complexity)

The Analogy: Imagine a list of three types of burglars:

The Old-School Thief: Uses a crowbar and a flashlight (Classical Computers).
The Super-Thief: Uses a time machine or a magic wand (Quantum Computers).
The Blueprint Proof: A guarantee from the architect that the lock is built on a foundation that cannot be easily dismantled (Reduction-Based Security).

What the paper does:
It creates a simple "Report Card" for different encryption methods:

RSA (The old lock): The Old-School Thief can't break it easily, but the Super-Thief (Quantum) can smash it open instantly. The architect's guarantee is also weak because we don't fully understand why it's hard.
ML-KEM (The new PQC lock): The Old-School Thief can't break it. The Super-Thief also can't break it (at least, not with any known magic wand). And the architect has a strong guarantee: "We built this on a mathematical foundation that is proven to be incredibly difficult to crack."

The takeaway: This layer helps people quickly see why the new locks are safer than the old ones without needing a PhD in math.

Layer 2: The "Geological Map" (Mathematical Structure)

The Analogy: Imagine the math behind the lock is a massive, jagged mountain range.

Old Math: We know the mountain is high, but we don't know its shape.
New Math (Combinatorial Hodge Theory): The authors are trying to draw a detailed map of this mountain. They are looking at the "fans" (the way the rock faces fan out) and the "stars" (local clusters of rocks).

What the paper does:
They are exploring a fancy new way to look at the shape of these mathematical mountains. They hypothesize that the reason these locks are so hard to break isn't just because the mountain is tall, but because the shape of the mountain is weird.

The Theory: Maybe the mountain is made of small, local clusters of rocks that are easy to climb, but the connections between these clusters are so twisted that you can't climb the whole thing at once.
The Goal: They aren't proving the mountain is unclimbable yet. They are just saying, "If we understand the shape of the mountain better, we might understand why the thieves keep failing."

Layer 3: The "Toy Test Track" (Empirical Experimentation)

The Analogy: You can't test a Formula 1 car on a track that is only 10 feet long, but you can test a toy car to see how it behaves.

The Reality: Real PQC locks use massive, high-dimensional math (like a 500-story building).
The Experiment: The authors built a "Toy Lattice" (a small, low-dimensional version) using a programming language called Julia. They ran the "thieves" (algorithms like LLL and BKZ) against these toy locks.

What they found:

At 10 feet (10 dimensions), the toy thief could easily break the lock.
At 40 feet (40 dimensions), the toy thief got tired and gave up (the computer timed out).
The Lesson: Even though 40 feet is tiny compared to the real 500-story building, the difficulty of breaking the lock explodes as you get bigger. This proves that the "toy" behavior matches the "real world" theory: the bigger the lock, the harder it is to break, and the cost to break it grows incredibly fast.

Why Does This Matter?

The authors are very honest about what they aren't doing:

They are not inventing new math proofs.
They are not saying "This specific lock is 100% unbreakable."
They are not testing the real, massive locks used by banks today.

The Real Value:
They are building a bridge. Right now, there is a huge gap between the cryptographers (who speak in complex math) and the people who need to buy and use these locks (businesses, governments, the public).

This paper says: "Let's stop trying to force everyone to learn the complex math. Instead, let's use this three-layer framework to explain the security story clearly. We can show the 'Report Card' (Layer 1), the 'Mountain Map' (Layer 2), and the 'Toy Test Results' (Layer 3) to help everyone understand why these new digital locks are the best we have against the quantum future."

In short: It's a user manual for understanding the concept of quantum-safe security, making the scary math feel a little less like magic and a little more like a structured, understandable system.

1. Problem Statement

The security of Post-Quantum Cryptography (PQC) relies on complex computational assumptions (e.g., Learning With Errors - LWE, Shortest Vector Problem - SVP) that are well-founded in complexity theory but opaque to non-specialist stakeholders, including industry practitioners and policymakers. While NIST has standardized lattice-based schemes (ML-KEM/FIPS 203 and ML-DSA/FIPS 204), a significant gap exists between the formal cryptographic proofs underlying these schemes and the practical understanding required for rational decision-making.

The authors identify a need for a framework that can communicate PQC security assumptions by aligning complexity-theoretic reasoning, mathematical structure, and implementation-level evidence without claiming to provide new hardness proofs or attack vectors. The goal is to bridge the "trust gap" caused by the sophisticated mathematics of lattice cryptography.

2. Methodology: The Layered Interpretive Framework

The paper proposes "Explainable PQC," an interdisciplinary framework consisting of three distinct layers. This framework is explicitly scoped as a communication and interpretive tool, not a formal proof system.

Layer 1: Complexity-Based Interpretive Model

This layer establishes a vocabulary to classify cryptographic schemes based on three dimensions:

Classical Security ( $S_c$ ): Resistance to known polynomial-time classical algorithms.
Quantum Security ( $S_q$ ): Resistance to known polynomial-time quantum algorithms (e.g., Shor's algorithm).
Reduction-Backed Security ( $S_r$ ): Whether the scheme's hardness is supported by formal worst-case-to-average-case reductions from established hard problems (e.g., LWE).

The authors define a mapping $\Phi: C \to (S_c, S_q, S_r)$ to generate an "interpretive security profile." For example, RSA-2048 is classified as $(Yes, No, No)$, whereas ML-KEM-768 is $(Yes, Yes, Yes)$. This layer clarifies that PQC relies on approximate lattice problems rather than NP-hard exact variants, acknowledging the open relationship between complexity classes BQP and NP.

Layer 2: Exploratory Mathematical Investigation

This layer applies Combinatorial Hodge Theory and Polyhedral Geometry to study the structural aspects of lattice hardness.

Focus: The authors investigate the intersection cohomology of fans associated with toric varieties and the Local Generation Theorem.
Hypothesis: They propose that lattice fan relations can be decomposed into local "star" structures. The hypothesis suggests that if lattice relations are locally bounded, global algorithmic attacks (like block-wise BKZ reduction) may fail to capture global topological connectivity, which could explain the hardness of high-dimensional lattice problems.
Status: This is presented as an exploratory mathematical program. The authors explicitly state that no direct link to computational complexity or new attacks has been proven yet; it is a structural investigation intended to potentially inform future complexity analysis.

Layer 3: Empirical Experimentation Platform

To provide tangible evidence of scaling behavior, the authors developed an open-source toolkit in Julia called the "Open Problem Toolkit."

Function: It constructs lattice instances, performs basis reduction (using LLL and KZ algorithms), and benchmarks exact solvers (EKZ).
Scope: Experiments were conducted in low-dimensional settings (10D to 40D), far below the dimensions used in deployed standards (400–500+).
Goal: To illustrate the "computational explosion" of exact solvers as dimension increases, serving as an educational and illustrative tool rather than a security evaluation of real-world systems.

3. Key Contributions

Conceptual Framework: The definition of a three-layer interpretive framework that separates complexity reasoning, mathematical structure, and empirical evidence, providing a structured way to discuss PQC security without replacing formal proofs.
Vocabulary for Security: A new classification system distinguishing between classical vulnerability, quantum vulnerability, and reduction-backed assumptions, clarifying the nuance between NP-hardness and the approximate lattice problems used in PQC.
Mathematical Program: The identification of a specific research direction using Combinatorial Hodge Theory and fan decompositions to understand the geometric origins of lattice hardness, clearly distinguishing established results from interpretive claims.
Empirical Tool: The release of a Julia-based platform demonstrating the rapid growth of computation time for exact lattice solvers in low dimensions, validating the theoretical "intractability" through controlled experimentation.

4. Results

Interpretive Profiles: The framework successfully differentiates RSA (vulnerable to quantum, not reduction-backed) from ML-KEM (resistant to known quantum attacks, reduction-backed).
Mathematical Insights: The Local Generation Theorem provides a decomposition of lattice fan relations, suggesting that global connectivity may be a key factor in hardness, distinct from local complexity. However, no new complexity-theoretic proofs were derived.
Empirical Findings:
- At 10 dimensions, both approximate (LLL) and exact (EKZ) solvers completed successfully.
- At 40 dimensions, the approximate solver (LLL) succeeded, but the exact solver (EKZ) hit a timeout (3600s), demonstrating an exponential growth in computational cost even at these low dimensions.
- This confirms the "wall" where exact solutions become computationally intractable, even on modern hardware, reinforcing the intuition behind lattice security.

5. Significance and Limitations

Significance:
The paper addresses a critical communication gap in the transition to PQC. By integrating complexity theory, advanced geometry, and empirical data, it offers a holistic model for explaining why PQC is secure to non-experts. It moves beyond abstract mathematical proofs to provide a "structured narrative" for security assumptions. The empirical layer serves as a pedagogical tool ("Educational TOY LATTICE") to help students and practitioners visualize the scaling behavior of lattice problems.

Limitations & Scope:

Not a Proof System: The framework does not provide formal security guarantees, concrete security parameter estimates, or side-channel analysis.
Exploratory Math: The connection between Combinatorial Hodge Theory and computational complexity remains an open problem; no cryptographic shortcuts or attacks were discovered.
Low-Dimensional Experiments: The empirical results are limited to dimensions (10–40) far below production standards (400+). They illustrate scaling trends but do not evaluate the security of deployed NIST standards directly.
Audience: The framework is designed for interpretability and communication, not for formal certification or compliance.

Conclusion

"Explainable PQC" does not claim to solve the PQC security problem but rather to explain it. It proposes a unified model that connects the theoretical hardness of lattice problems, the geometric structures underlying them, and the empirical evidence of their computational difficulty. This layered approach aims to foster greater transparency and trust in Post-Quantum Cryptographic standards among researchers, industry practitioners, and the broader public.