Scalable Batch Verification for Post-Quantum Hash-Based Signatures Using STARKs
Resumo
This paper introduces a STARK-based batch verifier for a Merkle Signature Scheme (MSS) built from parallel Lamport-style one-time signatures and implemented in the Winterfell framework. The method compresses the validation of N signatures under a single Merkle root into a compact proof of 50-75 KiB. Verification then requires only a few dozen hash evaluations and completes in under 3.1 s for N = 64, outperforming naı̈ve per-signature checks for all N ≥ 8. Requiring no trusted setup, this approach paves the way for scalable, efficient validation of multiple post-quantum signatures.Referências
Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. (2018a). Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, pages 14:1–14:17, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. (2018b). Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018/046.
Chakraborty, S., Hofheinz, D., Langrehr, R., Nielsen, J. B., Striecks, C., and Venturi, D. (2025). Malleable snarks and their applications. In Advances in Cryptology – EUROCRYPT 2025, pages 184–213, Cham. Springer Nature Switzerland.
Chen, B., Bünz, B., Boneh, D., and Zhang, Z. (2023). Hyperplonk: Plonk with linear-time prover and high-degree custom gates. In Advances in Cryptology – EUROCRYPT 2023, Lecture Notes in Computer Science, pages 499–530. Springer.
Drake, J., Khovratovich, D., Kudinov, M., and Wagner, B. (2025). Hash-based multi-signatures for post-quantum ethereum. Cryptology ePrint Archive, Paper 2025/055.
El-Hajj, M. and Oude Roelink, B. (2024). Evaluating the efficiency of zk-snark, zk-stark, and bulletproof in real-world scenarios: A benchmark study. Information (Switzerland), 15(8). Publisher Copyright: © 2024 by the authors.
Ernstberger, J., Chaliasos, S., Kadianakis, G., Steinhorst, S., Jovanovic, P., Gervais, A., Livshits, B., and Orrù, M. (2023). zk-bench: A toolset for comparative evaluation and performance benchmarking of SNARKs. Cryptology ePrint Archive, Paper 2023/1503.
Khaburzaniya, I., Chalkias, K., Lewi, K., and Malvai, H. (2021). Aggregating and thresh-oldizing hash-based signatures using STARKs. Cryptology ePrint Archive, Paper 2021/1048.
NIST (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208, National Institute of Standards and Technology.
Sekulić, J., Čapko, D., Erdeljan, A., Grbić, T., and Nenadić, K. (2025). A short survey of zk-friendly hash functions. In 2025 24th International Symposium, pages 1–5.
Wei, Y., Zhang, X., and Deng, Y. (2025). Transparent snarks over galois rings. In Jager, T. and Pan, J., editors, Public-Key Cryptography – PKC 2025, pages 418–451, Cham. Springer Nature Switzerland.
Wu, F., Zhou, B., Song, J., and Xie, L. (2025). Quantum-resistant blockchain and performance analysis. The Journal of Supercomputing, 81(3).
Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. (2018b). Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018/046.
Chakraborty, S., Hofheinz, D., Langrehr, R., Nielsen, J. B., Striecks, C., and Venturi, D. (2025). Malleable snarks and their applications. In Advances in Cryptology – EUROCRYPT 2025, pages 184–213, Cham. Springer Nature Switzerland.
Chen, B., Bünz, B., Boneh, D., and Zhang, Z. (2023). Hyperplonk: Plonk with linear-time prover and high-degree custom gates. In Advances in Cryptology – EUROCRYPT 2023, Lecture Notes in Computer Science, pages 499–530. Springer.
Drake, J., Khovratovich, D., Kudinov, M., and Wagner, B. (2025). Hash-based multi-signatures for post-quantum ethereum. Cryptology ePrint Archive, Paper 2025/055.
El-Hajj, M. and Oude Roelink, B. (2024). Evaluating the efficiency of zk-snark, zk-stark, and bulletproof in real-world scenarios: A benchmark study. Information (Switzerland), 15(8). Publisher Copyright: © 2024 by the authors.
Ernstberger, J., Chaliasos, S., Kadianakis, G., Steinhorst, S., Jovanovic, P., Gervais, A., Livshits, B., and Orrù, M. (2023). zk-bench: A toolset for comparative evaluation and performance benchmarking of SNARKs. Cryptology ePrint Archive, Paper 2023/1503.
Khaburzaniya, I., Chalkias, K., Lewi, K., and Malvai, H. (2021). Aggregating and thresh-oldizing hash-based signatures using STARKs. Cryptology ePrint Archive, Paper 2021/1048.
NIST (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208, National Institute of Standards and Technology.
Sekulić, J., Čapko, D., Erdeljan, A., Grbić, T., and Nenadić, K. (2025). A short survey of zk-friendly hash functions. In 2025 24th International Symposium, pages 1–5.
Wei, Y., Zhang, X., and Deng, Y. (2025). Transparent snarks over galois rings. In Jager, T. and Pan, J., editors, Public-Key Cryptography – PKC 2025, pages 418–451, Cham. Springer Nature Switzerland.
Wu, F., Zhou, B., Song, J., and Xie, L. (2025). Quantum-resistant blockchain and performance analysis. The Journal of Supercomputing, 81(3).
Publicado
01/09/2025
Como Citar
MENESES, Rodrigo Duarte de; HENRIQUES, Marco Amaral.
Scalable Batch Verification for Post-Quantum Hash-Based Signatures Using STARKs. In: WORKSHOP DE TRABALHOS DE INICIAÇÃO CIENTÍFICA E DE GRADUAÇÃO EM ANDAMENTO - SIMPÓSIO BRASILEIRO DE CIBERSEGURANÇA (SBSEG), 25. , 2025, Foz do Iguaçu/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 325-330.
DOI: https://doi.org/10.5753/sbseg_estendido.2025.11845.
