Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives
Computationally complex tasks, or "hard problems" for brevity, is a broad term that encompasses problems that require a significant number of resources to solve. Cryptography uses them by establishing an equivalence between the security of a scheme and the intractability of a complex prob...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Oles Honchar Dnipro National University
2024-06-01
|
| Series: | Challenges and Issues of Modern Science |
| Subjects: | |
| Online Access: | https://cims.fti.dp.ua/j/article/view/119 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823858776047878144 |
|---|---|
| author | Yevhen Kotukh Hennadii Khalimov |
| author_facet | Yevhen Kotukh Hennadii Khalimov |
| author_sort | Yevhen Kotukh |
| collection | DOAJ |
| description |
Computationally complex tasks, or "hard problems" for brevity, is a broad term that encompasses problems that require a significant number of resources to solve. Cryptography uses them by establishing an equivalence between the security of a scheme and the intractability of a complex problem. Two hard problems have been widely used in public-key cryptography: integer factorization and the discrete logarithm problem. In 1994, Shor showed that these classical complex problems can be easily solved on a large-scale quantum computer.
Quantum-resistant cryptosystems based on lattices and other post-quantum candidates also exploit computationally complex tasks. We would venture to assume that any algorithm that has regularity properties in its structured data will be broken by a quantum computer. The properties of superposition and quantum entanglement make it possible to perform calculations on all states of the qubit register simultaneously. This property models the full set of states of a classical computer. The presence of regularity in the computational data of the algorithm, for example, periodicity (frequency resonances) in algebraic structures (rings, groups, lattices, etc.) can potentially be filtered by some algorithm with a complexity less than Grover's algorithm. In article, we propose to change the approach to the design of cryptosystems. We replace the concept of a problem that is difficult to solve with a problem that has many equivalent solutions without regularities when all solutions are equally likely. In this case, quantum cryptanalysis is reduced to Grover's scheme with exponential implementation complexity. We will set linear equations concerning the unknowns for which we use the values of the logarithmic signatures. The number of equations for secret values of logarithmic signatures is less than their number. This leads to an incomplete system of linear equations concerning unknowns and the impossibility of solving them in polynomial time.
|
| format | Article |
| id | doaj-art-72e86dea17264dcea666e248b67ffa84 |
| institution | Kabale University |
| issn | 3083-5704 |
| language | English |
| publishDate | 2024-06-01 |
| publisher | Oles Honchar Dnipro National University |
| record_format | Article |
| series | Challenges and Issues of Modern Science |
| spelling | doaj-art-72e86dea17264dcea666e248b67ffa842025-02-11T09:55:48ZengOles Honchar Dnipro National UniversityChallenges and Issues of Modern Science3083-57042024-06-012Advantages of Logarithmic Signatures in the Implementation of Crypto PrimitivesYevhen Kotukh0https://orcid.org/0000-0003-4997-620XHennadii Khalimov1https://orcid.org/0000-0002-2054-9186Dnipro University of TechnologyKharkiv National University of Radio Electronics Computationally complex tasks, or "hard problems" for brevity, is a broad term that encompasses problems that require a significant number of resources to solve. Cryptography uses them by establishing an equivalence between the security of a scheme and the intractability of a complex problem. Two hard problems have been widely used in public-key cryptography: integer factorization and the discrete logarithm problem. In 1994, Shor showed that these classical complex problems can be easily solved on a large-scale quantum computer. Quantum-resistant cryptosystems based on lattices and other post-quantum candidates also exploit computationally complex tasks. We would venture to assume that any algorithm that has regularity properties in its structured data will be broken by a quantum computer. The properties of superposition and quantum entanglement make it possible to perform calculations on all states of the qubit register simultaneously. This property models the full set of states of a classical computer. The presence of regularity in the computational data of the algorithm, for example, periodicity (frequency resonances) in algebraic structures (rings, groups, lattices, etc.) can potentially be filtered by some algorithm with a complexity less than Grover's algorithm. In article, we propose to change the approach to the design of cryptosystems. We replace the concept of a problem that is difficult to solve with a problem that has many equivalent solutions without regularities when all solutions are equally likely. In this case, quantum cryptanalysis is reduced to Grover's scheme with exponential implementation complexity. We will set linear equations concerning the unknowns for which we use the values of the logarithmic signatures. The number of equations for secret values of logarithmic signatures is less than their number. This leads to an incomplete system of linear equations concerning unknowns and the impossibility of solving them in polynomial time. https://cims.fti.dp.ua/j/article/view/119computationally complex taskscryptographyquantum cryptographylogarithmic signatures |
| spellingShingle | Yevhen Kotukh Hennadii Khalimov Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives Challenges and Issues of Modern Science computationally complex tasks cryptography quantum cryptography logarithmic signatures |
| title | Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives |
| title_full | Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives |
| title_fullStr | Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives |
| title_full_unstemmed | Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives |
| title_short | Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives |
| title_sort | advantages of logarithmic signatures in the implementation of crypto primitives |
| topic | computationally complex tasks cryptography quantum cryptography logarithmic signatures |
| url | https://cims.fti.dp.ua/j/article/view/119 |
| work_keys_str_mv | AT yevhenkotukh advantagesoflogarithmicsignaturesintheimplementationofcryptoprimitives AT hennadiikhalimov advantagesoflogarithmicsignaturesintheimplementationofcryptoprimitives |