Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives
Keywords:
computationally complex tasks, cryptography, quantum cryptography, logarithmic signaturesAbstract
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.
Downloads
References
Peter W. Shor. Algorithms for quantum computation: Discrete log-arithms and factoring. In 35th FOCS, pages 124–134. IEEE Comput-er Society Press, November 1994
SS Magliveras , “A cryptosystem from logarithmic signatures of finite groups,” in Proceedings of the 29th Midwest Symposium on Circuits and Systems, pp. 972–975, Elsevier Publishing, Amsterdam, The Netherlands, 1986.
SS Magliveras and ND Memon, “ Algebraic properties of cryp-tosystem PGM,” Journal of Cryptology, vol.5, no.3, pp.167–183, 1992.
A. Caranti and F. Dalla Volta, “The round functions of cryptosys-tem PGM generate the symmetric group,” Designs, Codes and Cryp-tography, vol.38, no.1, pp.147–155, 2006.
S. S. Magliveras , P. Svaba , T. van Trung , and P. Zajac, “On the security of a realization of cryptosystem MST3”, Tatra Mountains Mathematical Publications, vol.41, pp.65– 78, 2008.
P. Svaba and T. van Trung, “Public key cryptosystem MST3 crypt-analysis and realization”, Journal of Mathematical Cryptology, vol. 4, no. 3, pp. 271–315, 2010.
Gennady Khalimov, Yevgen Kotukh, Oleksandr Sievierinov , Svitlana Khalimova , Sang-Yoon Chang, Yaroslav Balytskyi , Strong Encryption Based on the small Ree groups International Conference “Problems of Infocommunications. Science and Technology” (PIC S&T′2022) October 10 – 12, 2022 Kyiv – Kharkiv.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Євген Котух, Геннадій Халімов (Автор)
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in the journal Challenges and Issues of Modern Science are licensed under the Creative Commons Attribution 4.0 International (CC BY) license. This means that you are free to:
- Share, copy, and redistribute the article in any medium or format
- Adapt, remix, transform, and build upon the article
as long as you provide appropriate credit to the original work, include the authors' names, article title, journal name, and indicate that the work is licensed under CC BY. Any use of the material should not imply endorsement by the authors or the journal.