Open Access iconOpen Access



Accelerating Falcon Post-Quantum Digital Signature Algorithm on Graphic Processing Units

Seog Chung Seo1, Sang Woo An2, Dooho Choi3,*

1 Kookmin University, Seoul, 02707, Korea
2 Telecommunications Technology Association (TTA), Gyeonggi-do, 13591, Korea
3 Korea University, Sejong, 30019, Korea

* Corresponding Author: Dooho Choi. Email: email

Computers, Materials & Continua 2023, 75(1), 1963-1980.


Since 2016, the National Institute of Standards and Technology (NIST) has been performing a competition to standardize post-quantum cryptography (PQC). Although Falcon has been selected in the competition as one of the standard PQC algorithms because of its advantages in short key and signature sizes, its performance overhead is larger than that of other lattice-based cryptosystems. This study presents multiple methodologies to accelerate the performance of Falcon using graphics processing units (GPUs) for server-side use. Direct GPU porting significantly degrades performance because the Falcon reference codes require recursive functions in its sampling process. Thus, an iterative sampling approach for efficient parallel processing is presented. In this study, the Falcon software applied a fine-grained execution model and reported the optimal number of threads in a thread block. Moreover, the polynomial multiplication performance was optimized by parallelizing the number-theoretic transform (NTT)-based polynomial multiplication and the fast Fourier transform (FFT)-based multiplication. Furthermore, dummy-based parallel execution methods have been introduced to handle the thread divergence effects. The presented Falcon software on RTX 3090 NVIDA GPU based on the proposed methods with Falcon-512 and Falcon-1024 parameters outperform at 35.14, 28.84, and 34.64 times and 33.31, 27.45, and 34.40 times, respectively, better than the central processing unit (CPU) reference implementation using Advanced Vector Extensions 2 (AVX2) instructions on a Ryzen 9 5900X running at 3.7 GHz in key generation, signing, and verification, respectively. Therefore, the proposed Falcon software can be used in servers managing multiple concurrent clients for efficient certificate verification and be used as an outsourced key generation and signature generation server for Signature as a Service (SaS).


Cite This Article

APA Style
Seo, S.C., An, S.W., Choi, D. (2023). Accelerating falcon post-quantum digital signature algorithm on graphic processing units. Computers, Materials & Continua, 75(1), 1963-1980.
Vancouver Style
Seo SC, An SW, Choi D. Accelerating falcon post-quantum digital signature algorithm on graphic processing units. Comput Mater Contin. 2023;75(1):1963-1980
IEEE Style
S.C. Seo, S.W. An, and D. Choi "Accelerating Falcon Post-Quantum Digital Signature Algorithm on Graphic Processing Units," Comput. Mater. Contin., vol. 75, no. 1, pp. 1963-1980. 2023.

cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 872


  • 410


  • 1


Share Link