Performance and Comparative Analysis of Polynomial Multiplication Methods in Lattice-Based KEM Protocols

Abstract

The ability of quantum computers to solve the hard problems that current public-key cryptographic methods are based on in polynomial time through Shor’s algorithm poses a threat to existing cryptosystems. Standardization processes have been initiated by various organizations, primarily NIST. In this paper, performance metrics such as execution time, energy consumption, and execution time stability of lattice-based solutions, which stand out with their strong security properties in the NIST and KpqC standardization processes, are analyzed based on their reference implementations. Considering the bottleneck caused by intensive operations such as polynomial multiplication, different multiplication methods have been applied to achieve more efficient results. Based on the obtained results, these multiplication methods have been comparatively examined and their contributions to implementation performance have been analyzed.

Keywords

• Post-quantum cryptography
• Key encapsulation mechanism (KEM)
• Lattice-based cryptography
• Polynomial multiplication
• NIST
• KpqC

Kafes Tabanlı KEM Protokollerinin Başarım ve Polinom Çarpım Yöntemleri Üzerine Karşılaştırmalı İnceleme

Abstract

Kuantum bilgisayarların Shor algoritması ile günümüzdeki açık anahtarlı kriptografi yöntemlerinin temel aldığı zor problemleri polinom zamanda çözebilmesi, mevcut kriptosistemler için bir tehdit oluşturmaktadır. ABD Ulusal Standartlar ve Teknoloji Enstitüsü (National Institute of Standards and Technology-NIST) başta olmak üzere çeşitli kuruluşlar tarafından standartlaşma süreçleri başlatılmıştır. Bu çalışmada NIST ve KpqC süreçlerinde güçlü güvenlik özelliği ile ön plana çıkan kafes tabanlı çözümlerin referans uygulamalarındaki çalışma zamanı, enerji tüketimi ve çalışma zamanı kararlılığı gibi performans metrikleri incelenmiştir. Polinom çarpımı gibi yoğun işlemlerin oluşturduğu darboğaz göz önünde bulundurularak, daha verimli sonuçların elde edilebilmesi için farklı çarpım yöntemleri uygulanmıştır. Elde edilen sonuçlar doğrultusunda, çarpım yöntemleri karşılaştırmalı olarak incelenerek bu yöntemlerin uygulama performansına katkıları analiz edilmiştir. Deneysel sonuçlara göre analiz için seçilen 5 farklı kriptosistem arasında SMAUG farklı performans metrikleri açısından en iyi sonuçları sunan algoritma iken performans açısından en fazla darboğaz NTRU+ algoritmasında ortaya çıkmıştır. Seçilen algoritmalarda kullanılan çarpım yöntemlerinin birbirleri yerine kullanılması için gerekli adaptasyonlar ise hem referans algoritma açısından hem de karşılaştırmalı analizlerde çarpım yöntemlerinin performans üzerindeki etkisini kanıtlar düzeyde iyileştirmeler sunmuştur.

Keywords

• Kuantum sonrası kriptografi
• Anahtar paketleme mekanizması
• Kafes-tabanlı kriptografi
• Polinom çarpımı
• NIST
• KpqC

References

1. P. Shor, «Algorithms for quantum computation: discrete logarithms and factoring,» %1 içinde Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 124-134.
2. A. J. Menezes, P. C. v. Oorschot ve S. A. Vanstone, Handbook of Applied Cryptography, Boca Raton: CRC Press, 1997.
3. S. Akleylek ve K. Seyhan, «Kuantum Bilgisayar Çağında Kriptosistemlere Bir Bakış,» %1 içinde Siber Güvenlik ve Savunma-Blokzincir ve Kriptoloji, Ankara, Nobel, 2021, pp. 239-270.
4. K. Seyhan ve S. Akleylek, «A new lattice-based password authenticated key exchange scheme with anonymity and reusable key,» PeerJ Computer Science, cilt 10, p. e1791, 2024.
5. J. Hekkala, M. Muurman, K. Halunen ve V. Vallivaara, «Implementing post-quantum cryptography for developers,» SN Computer Science, cilt 4, no. 4, p. 2023, 2023.
6. NIST, «Announcing Approval of Three Federal Information Processing Standards (FIPS) for Post-Quantum Cryptography,» 13 Ağustos 2024. [Çevrimiçi]. Available: https://csrc.nist.gov/news/2024/postquantum-cryptography-fips-approved. [Erişildi: 2 Haziran 2026].
7. KpqC, «Selected Algorithms from the KpqC Competition Round 2,» 16 Ocak 2025. [Çevrimiçi]. Available: https://www.kpqc.or.kr/competition_02.html. [Erişildi: 2 Haziran 2026].
8. C. Peikert, «Lattice cryptography for the internet,» %1 içinde International workshop on post-quantum cryptography, Springer, 2014, pp. 197-219.

9. C. Peikert, «A decade of lattice cryptography,» Foundations and trends in theoretical computer science, cilt 10, no. 4, pp. 283-424, 2016.
10. X. Wang, G. Xu ve Y. Yu, «Lattice-based cryptography: A survey,» Chinese Annals of Mathematics, Series B, cilt 44, no. 6, pp. 945-960, 2023.
11. [11] C. Zeng, D. He, Q. Feng, C. Peng ve M. Luo, «The implementation of polynomial multiplication for lattice-based cryptography: A survey,» Journal of Information Security and Applications, cilt 83, p. 103782, 2024.
12. M. Bisheh-Niasar, R. Azarderakhsh ve M. Mozaffari-Kermani, «High-speed NTT-based polynomial multiplication accelerator for post-quantum cryptograph,» 2021 IEEE 28th symposium on computer arithmetic (ARITH), pp. 94-101, 2021.
13. A. Alhassani ve M. Benaissa, «High-speed polynomials multiplication hw accelerator for CRYSTALS-Kyber,» IEEE Transactions on Circuits and Systems I: Regular Papers, cilt 71, no. 12, pp. 6105-6113, 2024.
14. Y. Zhu, M. Zhu, B. Yang, W. Zhu, C. Deng, C. Chen, S. Wei ve L. Liu, «LWRpro: An energy-efficient configurable crypto-processor for module-LWR,» IEEE Transactions on Circuits and Systems I: Regular Papers, cilt 68, no. 3, pp. 1146-1159, 2021.
15. T. Xu, Y. Cui, D. Liu, C. Wang ve W. Liu, «Lightweight and efficient hardware implementation for Saber using NTT multiplication,» 2022 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), pp. 601-605, 2022.
16. Y. Tu, S. Bai, J. Xiong ve J. Xie, «SCOPE: Schoolbook-Originated Novel Polynomial Multiplication Accelerators for NTRU-Based PQC,» IEEE Transactions on Very Large Scale Integration (VLSI) Systems, cilt 33, no. 2, pp. 408-420, 2026.
17. R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky ve D. Stehlé, «CRYSTALS-Kyber algorithm specifications and supporting documentation,» NIST PQC Round, cilt 2, no. 4, pp. 1-43, 2019.
18. J.-P. D’Anvers, A. Karmakar, S. Sinha Roy ve F. Vercauteren, «Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM,» Progress in Cryptology--AFRICACRYPT 2018: 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7--9, 2018, Proceedings 10, pp. 282-305, 2018.
19. C. Chen, O. Danba, J. Hoffstein, A. Hulsing, J. Rijneveld, J. M. a. S. P. Schanck, W. Whyte ve Z. Zhang, «Algorithm specifications and supporting documentation,» Brown University and Onboard security company, 2019.
20. J. H. Cheon, H. Choe, D. a. H. J. Hong, H. Seong, J. Shin ve M. Yi, «SMAUG: The key exchange algorithm based on module-LWE and module-LWR,» 4 Kasım 2024. [Çevrimiçi]. Available: https://hmchoe0528.github.io/assets/manuscripts/SMAUG_T_spec_Oct24_v4.0.pdf. [Erişildi: 2 Haziran 2026].
21. WhatsApp, «WhatsApp Encryption Overview Technical white paper,» 19 Ağustos 2024. [Çevrimiçi]. Available: https://scontent.xx.fbcdn.net/v/t39.8562-6/455962147_1148247109601582_1673264986279156121_n.pdf?_nc_cat=101&ccb=1-7&_nc_sid=e280be&_nc_ohc=kPAwtSQ78jQQ7kNvwHxM8JE&_nc_oc=AdliwJG319Ry46OYtijePk06F1iOLbIZF2oJeZXq20IiWOsPK5I0-inmSeQ04Kpcdk8&_nc_zt=14&_nc_ht=. [Erişildi: 2 Haziran 2026].
22. Telegram, «MTProto: End-to-End Encryption, Secret Chats,» [Çevrimiçi]. Available: https://core.telegram.org/api/end-to-end. [Erişildi: 2 Haziran 2026].
23. T. Perrin ve M. Marlinspike, «The Double Ratchet Algorithm,» 20 Kasım 2016. [Çevrimiçi]. Available: https://signal.org/docs/specifications/doubleratchet/doubleratchet.pdf. [Erişildi: 2 Haziran 2026].
24. D. J. Bernstein ve T. Lange, «Post-quantum cryptography,» Nature, cilt 549, no. 7671, pp. 188-194, 2017.
25. P. Ravi, J. Howe, A. Chattopadhyay ve S. Bhasin, «Lattice-based key-sharing schemes: A survey,» ACM Computing Surveys, cilt 54, no. 1, pp. 1-39, 2021.
26. NIST, «Module-Lattice-based Key-Encapsulation Mechanism Standard,» Federal Information Processing Standards Publication, 13 Ağustos 2024. [Çevrimiçi]. Available: https://csrc.nist.gov/pubs/fips/203/final. [Erişildi: 2 Haziran 2026].
27. J. Kim ve J. H. Park, «NTRU+: Compact Construction of NTRU,» Algorithm Specifications And Supporting Documentation, 2024.
28. J. Hoffstein, J. Pipher ve J. H. Silverman, «NTRU: A ring-based public key cryptosystem,» International algorithmic number theory symposium, pp. 267-288, 1998.
29. A. A. Karatsuba ve Y. P. Ofman, «Multiplication of many-digital numbers by automatic computers,» %1 içinde Russian Academy of Sciences, 1962.
30. M. J. Kannwischer, «Polynomial multiplication for post-quantum cryptography,» 4 Nisan 2022. [Çevrimiçi]. Available: https://repository.ubn.ru.nl/bitstream/handle/2066/247905/247905.pdf. [Erişildi: 2 Haziran 2026].
31. A. L. Toom, «The complexity of a scheme of functional elements simulating the multiplication of integers,» %1 içinde Russian Academy of Sciences, 150.
32. afdursun, «afDursun/pqc-kem-performance-poly-mul,» [Çevrimiçi]. Available: https://github.com/afDursun/pqc-kem-performance-poly-mul. [Erişildi: 2 Haziran 2026].
33. T. Xu, Y. Cui, D. Liu, C. Wang ve W. Liu, «Lightweight and efficient hardware implementation for Saber using NTT multiplication,» %1 içinde 2022 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Shenzhen, 2022.