💻 computer science

Structural Dependency Analysis for Masked NTT Hardware: Scalable Pre-Silicon Verification of Post-Quantum Cryptographic Accelerators

This paper introduces a scalable four-stage verification hierarchy that extends sound first-order masking analysis to production-scale post-quantum cryptographic accelerators, successfully narrowing manual review requirements for a 1.17-million-cell ML-KEM/ML-DSA chip from hundreds of structural flags to 165 mathematically certified candidates.

Original authors: Ray Iskander, Khaled Kirah

Published 2026-04-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ray Iskander, Khaled Kirah

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 building a super-secure vault to protect the world's most valuable secrets from future "quantum" hackers. To make this vault unbreakable, you don't just use one lock; you split the secret into two pieces (like two halves of a key) and hide them in different parts of the machine. This is called masking.

The golden rule of this system is simple: The two halves of the key must never meet. If they accidentally touch or combine inside the machine, the secret is exposed, and the vault is broken.

The Problem: The "Needle in a Haystack" Dilemma

The machine we are talking about (called Adams Bridge) is massive. It has over 1 million tiny electronic switches (gates).

Checking if the two key-halves ever meet is like trying to find a specific needle in a haystack the size of a city.

Old tools were like magnifying glasses. They could check a small pile of hay (a few thousand switches) perfectly, but they would melt if you tried to use them on the whole city.
Manual checking by human experts is impossible; it would take a lifetime.
Testing the real machine (after it's built) is too late. If it's broken, you have to scrap the whole thing and start over.

The Solution: QANARY (The Canary in the Coal Mine)

The authors built a new tool called QANARY. They named it after the canary birds miners used to carry underground. If the canary stopped singing, the miners knew there was toxic gas before it killed them.

QANARY is a "pre-silicon" detector. It looks at the blueprints (the code) of the machine before it is built to find dangerous spots where the two key-halves might accidentally meet.

How QANARY Works: The Four-Stage Filter

Instead of trying to check every single wire perfectly (which is too slow), QANARY uses a smart, four-step funnel to sort the wires:

The Wide Net (Structural Analysis):
Imagine throwing a giant net over the whole city. It catches everything that might be a problem. It's very fast but catches a lot of "false alarms" (things that look dangerous but are actually safe).
- Result: It flags thousands of wires as "suspicious."
The Fresh Mask Check:
Some wires look suspicious because they mix the keys, but they also have a "fresh randomizer" (like a new, random noise) that scrambles the mix immediately. QANARY checks if this noise is strong enough to hide the secret. If yes, it clears the wire.
The Boolean Detective (Simple Math):
For the remaining suspicious wires, QANARY asks a simple math question: "If I change the secret, does the wire's output change?" If the answer is "No," the wire is safe. This clears up many more false alarms.
The Arithmetic Detective (Complex Math):
This is the magic step. The machine deals with complex numbers (modular arithmetic), not just simple on/off switches. QANARY uses advanced math to re-arrange the problem. It asks: "Even though these two key-halves are touching, does the result still look random?"
- The Result: On a critical part of the machine (the Barrett Reduction module), this step proved that 54% of the wires flagged as dangerous were actually safe.

The Big Win

Before this tool, engineers had to manually inspect 363 suspicious wires on a critical module. It was a nightmare.
After using QANARY:

198 wires were proven safe by math (they got a "Secure Certificate").
165 wires were flagged as "Maybe Dangerous" (the engineers only need to check these).
0 wires were left in the "I don't know" pile.

The whole process took about 3 minutes on a single computer core.

Why This Matters

Speed: It turns a months-long manual review into a 3-minute automated check.
Scale: It works on machines with 1 million+ switches, something no other tool could do.
Safety: It catches "multi-cycle" leaks. Imagine the two key-halves are in different rooms. A simple check says they are safe. But QANARY realizes that in the next second, they might travel through a hallway and meet. It catches these "time-traveling" leaks that other tools miss.

The Bottom Line

This paper introduces a "smart filter" for security. It doesn't just say "This is broken" or "This is safe." It says, "Here are the 165 wires you actually need to worry about, and here is mathematical proof that the other 198 are fine."

It allows engineers to build massive, complex quantum-proof security chips with confidence, knowing they have a "canary" that has already checked the air for them.

1. Problem Statement

Post-quantum cryptographic (PQC) accelerators, specifically those implementing lattice-based schemes like ML-KEM and ML-DSA (FIPS 203/204), require rigorous side-channel resistance evidence for certification (e.g., FIPS 140-3). Masking is the dominant countermeasure, splitting secrets into randomized shares. Security relies on the invariant that no combinational logic path allows two or more shares of the same secret to converge.

The Challenge:

Scalability Gap: Existing exact formal verification tools (e.g., SILVER, Prover, Coco-Alma) scale only to small gadgets (typically <5,000 cells) and struggle with the massive scale of production PQC accelerators (millions of cells).
Arithmetic Complexity: PQC relies on arithmetic masking over large finite fields (modular arithmetic), which is harder to verify than Boolean masking (XOR).
Multi-Cycle Leakage: Deep pipelines in hardware accelerators create multi-cycle paths where shares, separated in one clock cycle, may recombine after passing through registers. Single-cycle analysis tools miss these cross-register dependencies.
Verification Bottleneck: Manual review of millions of wires is infeasible, and trace-based testing (DPA) requires fabricated hardware and may miss rare leakage paths.

2. Methodology: The QANARY Framework

The authors introduce QANARY (Quantum Canary), a four-stage hierarchical verification framework designed to scale from structural screening to machine-verified security certificates.

Stage 1: Structural Dependency Analysis (D0/D1)

Concept: A sound, necessary condition for first-order security. It checks if a wire's combinational fan-in depends on inputs from both share groups ( $S_0$ and $S_1$ ).
Mechanism: Uses a label lattice $\{ \bot, S_0, S_1, BOTH \}$ to propagate share dependencies through the netlist.
Outcome: Wires depending on both shares are flagged as "structurally insecure." This is a sound over-approximation (zero false negatives, but many false positives due to algebraic independence).

Stage 2: Multi-Cycle Extension (MC-D1)

Innovation: Extends D0/D1 to handle sequential logic. Instead of treating Register (DFF) outputs as free variables, it propagates labels across clock cycles using fixed-point iteration (Jacobi-style).
Result: Detects "cross-register share convergence" where shares merge after traversing pipeline stages, reclassifying modules that appeared clean in single-cycle analysis.

Stage 3: Fresh Masking Refinement (FM)

Mechanism: Checks if a structurally insecure wire is protected by a fresh randomness bit acting as a one-time pad (bijection).
Limitation: Only effective for wires where a single fresh random bit masks the output; ineffective for complex arithmetic carry chains.

Stage 4: Statistical Algebraic Distributional Check (SADC)

Core Contribution: A novel refinement that bridges the gap between structural screening and exact verification.
Boolean SADC: Reparametrizes shares ( $s_0 = x \oplus s_1$ ) and checks if the wire value is independent of the secret $x$ for all mask/randomness assignments.
Arithmetic SADC: Adapts the reparametrization for modular arithmetic ( $s_0 = (x - s_1) \mod q$ ). It symbolically substitutes shares with the secret and mask, then queries an SMT solver (Z3) to verify value-independence.
Dual-Solver Validation: Every arithmetic SADC query is cross-verified by a second solver (CVC5) to rule out solver-specific bugs.

3. Key Contributions

Production-Scale Structural Verification: Successfully applied structural dependency analysis to the Adams Bridge accelerator (1.17 million cells, 30 masked submodules), completing single-cycle analysis in 8.7 seconds.
Multi-Cycle Reclassification (MC-D1): Demonstrated that single-cycle analysis is insufficient for pipelined PQC hardware. MC-D1 reclassified 12 out of 30 modules from "Clean" to "Flagged" by detecting cross-register share convergence.
Arithmetic SADC at Scale: Introduced the first integration of an arithmetic-masking value-independence check into a structural verification pipeline. On the 5,543-cell ML-KEM Barrett reduction module, it machine-verified 198 of 363 structurally flagged wires as secure, leaving only 165 as candidate-insecure (a sound upper bound).
Dual-Solver Reproducibility: Achieved 0 disagreements between Z3 and CVC5 across 363 complex arithmetic queries, providing mathematical certificates for the results.
Triage Efficiency: Reduced the manual review burden from hundreds of thousands of structural flags to a manageable set of actionable candidates with mathematical proofs of security or insecurity.

4. Evaluation Results

The framework was evaluated on the Adams Bridge open-source ML-DSA/ML-KEM accelerator.

Scale: Analyzed 27 of 30 modules (1.17M cells total). Two largest modules timed out (>5 hours) due to memory constraints in the SMT solver, highlighting the limits of current exact tools.
Single-Cycle (SC-D1): Identified 59,061 insecure wires. 15 modules were "Clean," 12 "Insecure."
Multi-Cycle (MC-D1): Identified 614,126 insecure wires (a 10.4x increase). Crucially, it flipped 12 "Clean" modules to "Insecure" (e.g., the ML-KEM butterfly module went from 0 to 59,242 insecure wires).
Root Cause Compression: MC-D1 identified 8,487 true convergence points (where shares first meet). The remaining ~605k wires were propagation artifacts, compressing the triage effort by 98.6%.
SADC Performance (Barrett Module):
- Input: 363 structurally flagged wires.
- FM: Promoted 0 wires (arithmetic carry chains lack single-bit fresh masks).
- Boolean SADC: Confirmed 146 insecure, left 217 indeterminate (cone too large for Boolean enumeration).
- Arithmetic SADC: Resolved all 217 indeterminate wires.
  - 198 wires promoted to SECURE (machine-verified).
  - 165 wires classified as Candidate Insecure (sound upper bound).
  - 0 wires indeterminate.
- Time: ~3 minutes on a single core.
Validation: Results were cross-validated against Coco-Alma (on smaller submodules) and power-trace DPA attacks, showing consistency in identifying architectural leakage patterns.

5. Significance and Impact

Bridging the Gap: This work solves the "scale vs. precision" dilemma. It allows designers to verify production-scale PQC hardware pre-silicon, a task previously impossible with exact tools.
Actionable Feedback: Instead of a binary "Secure/Insecure" verdict on the whole chip, the tool provides a granular list of specific wires. It generates mathematical certificates for the majority of flagged wires, proving they are safe despite structural flags.
Complementarity: The tool does not replace exact verification or physical testing but acts as a powerful filter. It narrows the search space for exact tools (which can only handle small gadgets) and guides physical testing to the most likely leakage points.
Standardization: The methodology supports the FIPS 140-3 certification process for PQC hardware by providing scalable, sound, and reproducible evidence of side-channel resistance.

6. Limitations and Future Work

Value-Independence vs. Distributional Security: The SADC check is sufficient but not necessary. A wire flagged as "candidate insecure" might still be secure under exact distributional analysis (e.g., via threshold implementation rebalancing).
Glitch Modeling: The current analysis uses the standard probing model (stable states) and does not fully model glitch-induced leakage, though it acknowledges this as a future extension.
Higher-Order Masking: Currently limited to first-order ( $d=1$ ) masking. Extending to higher orders increases complexity exponentially.
Timeouts: The two largest modules (NTT butterflies) exceeded the 5-hour timeout, necessitating future work on hierarchical or compositional verification approaches.

In conclusion, the paper presents a breakthrough in hardware security verification, enabling the analysis of million-cell PQC accelerators by combining scalable structural analysis with targeted, mathematically rigorous algebraic checks.