ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS
The paper explores the properties of non-injective linear forms and their application in knapsack cryptosystems. The primary objective of the study is to analyze the potential of using non-injective knapsacks as private keys to enhance the cryptographic strength of knapsack-based systems against kno...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Joint Stock Company "Experimental Scientific and Production Association SPELS
2025-07-01
|
| Series: | Безопасность информационных технологий |
| Subjects: | |
| Online Access: | https://bit.spels.ru/index.php/bit/article/view/1815 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849735617274970112 |
|---|---|
| author | Maria Sabina A. Volkov |
| author_facet | Maria Sabina A. Volkov |
| author_sort | Maria Sabina A. Volkov |
| collection | DOAJ |
| description | The paper explores the properties of non-injective linear forms and their application in knapsack cryptosystems. The primary objective of the study is to analyze the potential of using non-injective knapsacks as private keys to enhance the cryptographic strength of knapsack-based systems against known types of attacks, including brute-force attacks and lattice basis reduction attacks. Special attention is given to the selection of cryptosystem parameters that provide a balance between security and computational efficiency. It is determined that, in order to protect against lattice-based attacks such as the LLL attack, the knapsack density must be maintained above 1.033. A key length of n = 200 is chosen, where the elements of the public key have a length of 170–200 bits. This provides a sufficient level of cryptographic strength at reasonable computational cost. To control the complexity of the decryption algorithm, methods are proposed to limit the average number of solutions to the knapsack problem. It is established that restricting the number of solutions to 2048 enables acceptable computational complexity while maintaining a high level of security. Additionally, a mechanism for eliminating redundant coefficients is developed, and a 16-bit checksum is introduced to avoid ambiguity during decryption. The results of the study demonstrate that the proposed methods can significantly improve the robustness of the knapsack cryptosystem at moderate computational cost, making it a promising candidate for practical implementation. |
| format | Article |
| id | doaj-art-9a5eaa41e6224cfc8d78ef8d5efa9265 |
| institution | DOAJ |
| issn | 2074-7128 2074-7136 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Joint Stock Company "Experimental Scientific and Production Association SPELS |
| record_format | Article |
| series | Безопасность информационных технологий |
| spelling | doaj-art-9a5eaa41e6224cfc8d78ef8d5efa92652025-08-20T03:07:31ZengJoint Stock Company "Experimental Scientific and Production Association SPELSБезопасность информационных технологий2074-71282074-71362025-07-0132310011110.26583/bit.2025.3.081473ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKSMaria Sabina A. Volkov0Bauman Moscow State Technical UniversityThe paper explores the properties of non-injective linear forms and their application in knapsack cryptosystems. The primary objective of the study is to analyze the potential of using non-injective knapsacks as private keys to enhance the cryptographic strength of knapsack-based systems against known types of attacks, including brute-force attacks and lattice basis reduction attacks. Special attention is given to the selection of cryptosystem parameters that provide a balance between security and computational efficiency. It is determined that, in order to protect against lattice-based attacks such as the LLL attack, the knapsack density must be maintained above 1.033. A key length of n = 200 is chosen, where the elements of the public key have a length of 170–200 bits. This provides a sufficient level of cryptographic strength at reasonable computational cost. To control the complexity of the decryption algorithm, methods are proposed to limit the average number of solutions to the knapsack problem. It is established that restricting the number of solutions to 2048 enables acceptable computational complexity while maintaining a high level of security. Additionally, a mechanism for eliminating redundant coefficients is developed, and a 16-bit checksum is introduced to avoid ambiguity during decryption. The results of the study demonstrate that the proposed methods can significantly improve the robustness of the knapsack cryptosystem at moderate computational cost, making it a promising candidate for practical implementation.https://bit.spels.ru/index.php/bit/article/view/1815np-completeness, knapsack problem, cryptography, knapsack cryptosystem. |
| spellingShingle | Maria Sabina A. Volkov ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS Безопасность информационных технологий np-completeness, knapsack problem, cryptography, knapsack cryptosystem. |
| title | ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS |
| title_full | ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS |
| title_fullStr | ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS |
| title_full_unstemmed | ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS |
| title_short | ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS |
| title_sort | analysis and implementation of a cryptosystem based on non injective knapsacks |
| topic | np-completeness, knapsack problem, cryptography, knapsack cryptosystem. |
| url | https://bit.spels.ru/index.php/bit/article/view/1815 |
| work_keys_str_mv | AT mariasabinaavolkov analysisandimplementationofacryptosystembasedonnoninjectiveknapsacks |