Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes
One of the significant post-quantum cryptographic candidates is the NTRU public key cryptosystem. It operates on polynomial rings, where the parameter largely determines the security of the system. Although NTRU is being studied currently, it has a long and well-established history. There are severa...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10271393/ |
| _version_ | 1797660764244279296 |
|---|---|
| author | Alla Levina Victor Kadykov Maheswara Rao Valluri |
| author_facet | Alla Levina Victor Kadykov Maheswara Rao Valluri |
| author_sort | Alla Levina |
| collection | DOAJ |
| description | One of the significant post-quantum cryptographic candidates is the NTRU public key cryptosystem. It operates on polynomial rings, where the parameter largely determines the security of the system. Although NTRU is being studied currently, it has a long and well-established history. There are several lattice-based attacks on NTRU-like systems that exploit the special structures of the rings used in these systems. The aim of this paper is to analyze the original NTRU, NTRU Encrypt, and NTRU Primes encryption schemes by structuring their common elements and showing the strongest hybrid attack using both lattice reduction and meet-in-the-middle (MITM) search on them. Furthermore, it is noted that, ignoring a polynomial factor of the not-well-studied cost of Block Korkin-Zolotarev (BKZ) algorithm, we estimate the security of the construction of encryption keys and show that by balancing lattice reduction costs and a MITM search cost, one can achieve better performance than using any of these methods on their own. Unlike previous studies, we found the way to ignore polynomial impact 22-24 from BKZ loops with multiple shortest vector problem (SVP) and the factor of 27 was omitted from the cost of one step in guessing the SVP. |
| first_indexed | 2024-03-11T18:35:37Z |
| format | Article |
| id | doaj.art-2d2c72a9682f4518bfdcfbc2bf150592 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-11T18:35:37Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-2d2c72a9682f4518bfdcfbc2bf1505922023-10-12T23:01:31ZengIEEEIEEE Access2169-35362023-01-011110993910995210.1109/ACCESS.2023.332169310271393Security Analysis of Hybrid Attack for NTRU-Class Encryption SchemesAlla Levina0https://orcid.org/0000-0003-4421-2411Victor Kadykov1Maheswara Rao Valluri2Laboratory of Fundamentals of Intelligent Systems “LETI”, Saint Petersburg Electrotechnical University “LETI,”, Saint Petersburg, RussiaLaboratory of Fundamentals of Intelligent Systems “LETI”, Saint Petersburg Electrotechnical University “LETI,”, Saint Petersburg, RussiaQuinfosystems Pvt., Ltd., Telangana, IndiaOne of the significant post-quantum cryptographic candidates is the NTRU public key cryptosystem. It operates on polynomial rings, where the parameter largely determines the security of the system. Although NTRU is being studied currently, it has a long and well-established history. There are several lattice-based attacks on NTRU-like systems that exploit the special structures of the rings used in these systems. The aim of this paper is to analyze the original NTRU, NTRU Encrypt, and NTRU Primes encryption schemes by structuring their common elements and showing the strongest hybrid attack using both lattice reduction and meet-in-the-middle (MITM) search on them. Furthermore, it is noted that, ignoring a polynomial factor of the not-well-studied cost of Block Korkin-Zolotarev (BKZ) algorithm, we estimate the security of the construction of encryption keys and show that by balancing lattice reduction costs and a MITM search cost, one can achieve better performance than using any of these methods on their own. Unlike previous studies, we found the way to ignore polynomial impact 22-24 from BKZ loops with multiple shortest vector problem (SVP) and the factor of 27 was omitted from the cost of one step in guessing the SVP.https://ieeexplore.ieee.org/document/10271393/BKZ algorithmcryptographyidealslatticesLLL algorithmNTRU |
| spellingShingle | Alla Levina Victor Kadykov Maheswara Rao Valluri Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes IEEE Access BKZ algorithm cryptography ideals lattices LLL algorithm NTRU |
| title | Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes |
| title_full | Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes |
| title_fullStr | Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes |
| title_full_unstemmed | Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes |
| title_short | Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes |
| title_sort | security analysis of hybrid attack for ntru class encryption schemes |
| topic | BKZ algorithm cryptography ideals lattices LLL algorithm NTRU |
| url | https://ieeexplore.ieee.org/document/10271393/ |
| work_keys_str_mv | AT allalevina securityanalysisofhybridattackforntruclassencryptionschemes AT victorkadykov securityanalysisofhybridattackforntruclassencryptionschemes AT maheswararaovalluri securityanalysisofhybridattackforntruclassencryptionschemes |