Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations
The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10177902/ |
| _version_ | 1797778043178057728 |
|---|---|
| author | Ardianto Satriawan Infall Syafalni Rella Mareta Isa Anshori Wervyan Shalannanda Aleams Barra |
| author_facet | Ardianto Satriawan Infall Syafalni Rella Mareta Isa Anshori Wervyan Shalannanda Aleams Barra |
| author_sort | Ardianto Satriawan |
| collection | DOAJ |
| description | The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity <inline-formula> <tex-math notation="LaTeX">$O(n \log {n})$ </tex-math></inline-formula> when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT is particularly useful in lattice-based cryptography, which relies on the hardness of certain mathematical problems to ensure security. Its importance in these fields continues to grow as quantum computing technology advances and traditional encryption methods become vulnerable. In this report, we discuss the mathematical concepts of polynomial multiplications using NTT and provide a comprehensive review of the latest implementation and state-of-the-art of NTT in both PQC and HE schemes. |
| first_indexed | 2024-03-12T23:12:35Z |
| format | Article |
| id | doaj.art-86b391b57c7b47e7b19d1a8a8cc8a3e5 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-12T23:12:35Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-86b391b57c7b47e7b19d1a8a8cc8a3e52023-07-17T23:00:22ZengIEEEIEEE Access2169-35362023-01-0111702887031610.1109/ACCESS.2023.329444610177902Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its ImplementationsArdianto Satriawan0https://orcid.org/0000-0001-5400-0995Infall Syafalni1Rella Mareta2Isa Anshori3https://orcid.org/0000-0001-5134-7264Wervyan Shalannanda4Aleams Barra5School of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung, IndonesiaSchool of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung, IndonesiaDepartment of Information and Communication Engineering, Inha University, Incheon, South KoreaSchool of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung, IndonesiaSchool of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung, IndonesiaFaculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, IndonesiaThe Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity <inline-formula> <tex-math notation="LaTeX">$O(n \log {n})$ </tex-math></inline-formula> when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT is particularly useful in lattice-based cryptography, which relies on the hardness of certain mathematical problems to ensure security. Its importance in these fields continues to grow as quantum computing technology advances and traditional encryption methods become vulnerable. In this report, we discuss the mathematical concepts of polynomial multiplications using NTT and provide a comprehensive review of the latest implementation and state-of-the-art of NTT in both PQC and HE schemes.https://ieeexplore.ieee.org/document/10177902/Number theoretic transformpost quantum cryptographyhomomorphic encryption |
| spellingShingle | Ardianto Satriawan Infall Syafalni Rella Mareta Isa Anshori Wervyan Shalannanda Aleams Barra Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations IEEE Access Number theoretic transform post quantum cryptography homomorphic encryption |
| title | Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations |
| title_full | Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations |
| title_fullStr | Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations |
| title_full_unstemmed | Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations |
| title_short | Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations |
| title_sort | conceptual review on number theoretic transform and comprehensive review on its implementations |
| topic | Number theoretic transform post quantum cryptography homomorphic encryption |
| url | https://ieeexplore.ieee.org/document/10177902/ |
| work_keys_str_mv | AT ardiantosatriawan conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations AT infallsyafalni conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations AT rellamareta conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations AT isaanshori conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations AT wervyanshalannanda conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations AT aleamsbarra conceptualreviewonnumbertheoretictransformandcomprehensivereviewonitsimplementations |