Abstract
The advent of quantum computing threatens the public-key cryptography that underlies modern blockchains, including ECDSA, Ed25519, and ECDH. Although NIST has standardized lattice-based schemes (ML-KEM and ML-DSA) as quantum-safe standards, their large key and signature sizes (several kilobytes each) pose scalability challenges for blockchains. We propose a quantum-safe blockchain architecture based entirely on multivariate polynomial cryptography, specifically the MPPK KEM key encapsulation mechanism and HPPK DS digital signature scheme. Using their linear configuration, MPPK KEM, and HPPK DS produce compact public keys (196-536 bytes) and signatures (144-272 bytes) – considerably smaller than ML-DSA’s 2–3 KB. We present a blockchain design that natively integrates these primitives. We analyze its security under classical and quantum adversarial models. We estimate transaction throughput and block capacity. Compared to lattice-based alternatives, our projections suggest that compact representations significantly improve transaction throughput and reduce on-chain storage. This work aims to contribute to ongoing quantum-safe standardization efforts, including those within ETSI, by demonstrating a concrete architectural pathway.
References
Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. Highspeed high-security signatures. In Cryptographic Hardware and Embedded Systems – CHES 2011, volume 6917 of Lecture Notes in Computer Science, pages 124–142. Springer, 2012.
Jintai Ding, John Deaton, Daniel S. Schmidt, V. Vishakha, and Zhenfei Zhang. Cryptanalysis of the lifted unbalanced oil vinegar signature scheme. In Advances in Cryptology – CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science, pages 279–298. Springer, 2020.
Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
Randy Kuang, Maria Perepechaenko, and Michel Barbeau. A new post-quantum multivariate polynomial public key encapsulation algorithm. Quantum Information Processing, 21(10):360, 2022.
Randy Kuang, Maria Perepechaenko, Mahmoud Sayed, and Dafu Lou. Homomorphic polynomial public key with Barrett transformation for digital signature. Academia Quantum, 1(1), 2024.
Randy Kuang, Maria Perepechaenko, Ryan Toth, and Michel Barbeau. Benchmark performance of the multivariate polynomial public key encapsulation mechanism. In Slim Kallel, Mohamed Jmaiel, Mohammad Zulkernine, Ahmed Hadj Kacem, Frederic Cuppens, and Nora Cuppens, editors, Risks and Security of Internet and Systems, pages 239–255, Cham, 2023. Springer Nature Switzerland.
Adam Langley, Mike Hamburg, and Sean Turner. Elliptic curves for security (curve25519 and curve448). RFC 7748, 2016. IETF Standard.
Christopher Moore and Stephan Mertens. The Nature of Computation. Oxford University Press, 2011.
Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf, 2008. Accessed: 2026-04-30.
National Institute of Standards and Technology. Status report on the third round of the NIST post-quantum cryptography standardization process. NIST Interagency Report NIST IR 8413, National Institute of Standards and Technology, 2022.
National Institute of Standards and Technology, Gorjan Alagic, Quynh Dang, Dustin Moody, Angela Robinson, Hamilton Silberg, and Daniel Smith-Tone. Module-latticebased key-encapsulation mechanism standard. Technical Report NIST FIPS 203, National Institute of Standards and Technology, August 2024. Published August 13, 2024.
National Institute of Standards and Technology, Thinh Dang, Jacob Lichtinger, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, and Angela Robinson. Module-lattice-based digital signature standard. Technical Report NIST FIPS 204, National Institute of Standards and Technology, August 2024. Published August 13, 2024.
National Institute of Standards and Technology. Post-quantum cryptography standardization: Selected algorithms. https://csrc.nist.gov/projects/post-quantum-cryptography 2024. Accessed: 2026-04-30.
Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2):303–332, 1999.
Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger. https://ethereum.github.io/yellowpaper/paper.pdf, 2014.
Ed stands for Edwards-curve Digital Signature Algorithm (EdDSA), 255 means that the algorithm utilizes a 255-bit (32-byte) private key, and 19 is the prime number 2255−19 that sets the mathematical boundary for the curve.
Level 1 (III or V) is at least as hard to break as a 128 (192 or 256)-bit key search on a block cipher such as AES-128 (192 or 256).