GPU Acceleration of VOLEitH-Based Post-Quantum Signatures: A Reusable Fragment-Graph Framework

• Victor Shyba UFSC https://orcid.org/0009-0006-4662-6182
• Ricardo Felipe Custódio UFSC https://orcid.org/0000-0001-9611-5694

DOI: https://doi.org/10.5753/sbseg.2026.29317

Resumo

Post-quantum digital signature schemes based on the Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm represent a promising direction in the NIST Post-Quantum Cryptography standardization process for additional digital signatures. FAEST, an AES-based scheme, was selected for the third round in May 2026 [Alagic et al. 2026]; PERK, based on the Permuted Kernel Problem, was not selected but adopted the VOLEitH framework and serves here as an architectural case study. To the best of our knowledge, this is the first reported GPU implementation of a VOLEitH-based signature pipeline. This paper presents the design, implementation, and evaluation of a reusable GPU framework for VOLEitH-based signatures, implemented in CUDA and applied to FAEST and PERK. The architecture adopts a fragment-graph model over caller-owned workspaces, covering seed expansion via AES-CTR, GGM tree construction, BAVC commitments, VOLE operations, and scheme-specific stages. Experiments on an NVIDIA H100 GPU report throughput of up to 34,026 sig/s for FAEST-128f and speedups of 1.23×–2.77× for signing and 1.99×–7.59× for verification over a normalized 16-worker AVX CPU baseline across all six FAEST v2 variants. The PERK GPU implementation achieves a speedup of 5.65×–9.64× in signing speed under the same methodology, providing empirical evidence of the developed infrastructure.

Referências

Alagic, G., Bros, M., Ciadoux, P., Dang, Q., Dang, T. H., Kelsey, J., Lichtinger, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., and Waller, N. (2026). Status report on the second round of the additional digital signature schemes for the NIST post-quantum cryptography standardization process. NIST Internal Report NIST IR 8610, National Institute of Standards and Technology, Gaithersburg, MD.

Alagic, G. et al. (2022). Status report on the third round of the nist post-quantum cryptography standardization process. NIST IR 8413, National Institute of Standards and Technology.

Aragon, N. et al. (2020). BIKE: Bit flipping key encapsulation. Submission to NIST Post-Quantum Cryptography Standardization Round 3.

Aranha, D. F., Degn, J., Eilath, J., Nielsen, K., and Scholl, P. (2025). Faest for memory-constrained devices with side-channel protections. Cryptology ePrint Archive.

Baum, C., Braun, L., Saint Guilhem, C. D. d., Klooss, M., Orsini, E., Roy, L., and Scholl, P. (2023). Publicly verifiable zero-knowledge and post-quantum signatures from vole-in-the-head. Cryptology ePrint Archive, Paper 2023/996.

Baum, C. et al. (2025). FAEST v2: Algorithm Specifications.

Bernstein, D. J. et al. (2020a). Classic McEliece: Conservative code-based cryptography. Submission to NIST Post-Quantum Cryptography Standardization Round 3.

Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., and Schwabe, P. (2020b). SPHINCS+: Stateless hash-based signatures. Submission to NIST Post-Quantum Cryptography Standardization Round 3.

Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., and Stehlé, D. (2018). CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353–367. IEEE.

Diffie, W. and Hellman, M. E. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654.

Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehlé, D. (2018). CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268.

Fiat, A. and Shamir, A. (1987). How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology–CRYPTO’86, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pages 212–219. ACM.

Ishai, Y., Kushilevitz, E., Ostrovsky, R., and Sahai, A. (2007). Zero-knowledge from secure multiparty computation. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pages 21–30. ACM.

Joseph, D. et al. (2022). Transitioning organizations to post-quantum cryptography. Nature, 605(7909):237–243.

Lee, W.-K., Seo, H. J., Seo, S. C., and Hwang, S. O. (2022). Efficient implementation of aes-ctr and aes-ecb on gpus with applications for high-speed frodokem and exhaustive key search. IEEE Transactions on Circuits and Systems II: Express Briefs, 69(6):2962–2966.

National Institute of Standards and Technology (2022). Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. Updated October 2022.

PERK Team (2024). Improvements for the perk signature scheme. Submission to NIST Post-Quantum Cryptography Standardization – Additional Digital Signatures Round 2.

Quisquater, J.-J., Guillou, L. C., and Berson, T. A. (1990). How to explain zero-knowledge protocols to your children. In Advances in Cryptology–CRYPTO’89 Proceedings, volume 435 of Lecture Notes in Computer Science, pages 628–631. Springer.

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.

Shen, S., Yang, H., Dai, W., Zhang, H., Liu, Z., and Zhao, Y. (2024). High-throughput gpu implementation of dilithium post-quantum digital signature. IEEE Transactions on Parallel and Distributed Systems.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134. IEEE.

Wan, L., Zheng, F., Fan, G., Wei, R., Gao, L., Wang, Y., Lin, J., and Dong, J. (2022). A novel high-performance implementation of crystals-kyber with ai accelerator. In European Symposium on Research in Computer Security, pages 514–534. Springer.

Wang, Z., Dong, X., Chen, H., Kang, Y., and Wang, Q. (2024). Cuspx: Efficient gpu implementations of post-quantum signature sphincs+. IEEE Transactions on Computers.

Wu, J., Yu, Y., Chen, Z., Yang, H., Li, C., and Liu, Z. (2025). Cbpspx: A cuda-based batch parallel optimization of post-quantum signature sphincs+. IEEE Internet of Things Journal.