On the Structural Dependencies of Post-quantum Cryptographic Standards

On the Structural Dependencies of Post-quantum Cryptographic Standards

Stať ve sborníku v databázi WoS či Scopus

Post-Quantum Cryptography (PQC) standardization efforts have led to the selection of multiple algorithms across different international organizations. While these schemes appear diverse at the algorithmic level, their security ultimately relies on a limited set of underlying hardness assumptions. In this work, we propose a graph-based representation of PQC standards that explicitly links standardized algorithms to their computational problems and captures structural relationships between these assumptions. Using network analysis techniques, we study the organization of the resulting dependency graph. Modularity analysis reveals a strongly structured ecosystem, with a densely connected algebraic core and distinct peripheral components corresponding to alternative paradigms such as hash-based and MPC-in-the-head constructions. Betweenness centrality further identifies a small number of core problems, in particular, the Shortest Vector Problem (SVP), as critical connectors within the network. Extending the analysis across standardization bodies, we observe a significant convergence toward lattice-based constructions, resulting in a concentration of dependencies on closely related hardness assumptions. This structural concentration suggests potential systemic risks, as advances in cryptanalysis could simultaneously affect multiple schemes and standards. In general, our results highlight the importance of considering structural diversity at the level of underlying assumptions in the design and evaluation of PQC ecosystems.

Post-Quantum Cryptography (PQC) standardization efforts have led to the selection of multiple algorithms across different international organizations. While these schemes appear diverse at the algorithmic level, their security ultimately relies on a limited set of underlying hardness assumptions. In this work, we propose a graph-based representation of PQC standards that explicitly links standardized algorithms to their computational problems and captures structural relationships between these assumptions. Using network analysis techniques, we study the organization of the resulting dependency graph. Modularity analysis reveals a strongly structured ecosystem, with a densely connected algebraic core and distinct peripheral components corresponding to alternative paradigms such as hash-based and MPC-in-the-head constructions. Betweenness centrality further identifies a small number of core problems, in particular, the Shortest Vector Problem (SVP), as critical connectors within the network. Extending the analysis across standardization bodies, we observe a significant convergence toward lattice-based constructions, resulting in a concentration of dependencies on closely related hardness assumptions. This structural concentration suggests potential systemic risks, as advances in cryptanalysis could simultaneously affect multiple schemes and standards. In general, our results highlight the importance of considering structural diversity at the level of underlying assumptions in the design and evaluation of PQC ecosystems.

Code-based Cryptography | Cryptographic Standards | Dependency Graph | Hash-based Cryptography | Lattice-based Cryptography | NP-Hardness Assumptions | Post-quantum Cryptography

Code-based Cryptography | Cryptographic Standards | Dependency Graph | Hash-based Cryptography | Lattice-based Cryptography | NP-Hardness Assumptions | Post-quantum Cryptography

RICCI, S.; DZURENDA, P.; HIRNEROVÁ, L.; MUZIKANT, P.

24.08.2026

Springer Science and Business Media Deutschland GmbH

9783032372178

Lecture Notes in Computer Science

Lecture Notes in Computer Science

16903 LNCS

Švýcarská konfederace

423

438

16

https://link.springer.com/chapter/10.1007/978-3-032-37218-5_25

http://hdl.handle.net/11012/527865