Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives

Yevhen Kotukh; Hennadii Khalimov

Authors

Yevhen Kotukh Dnipro University of Technology Author https://orcid.org/0000-0003-4997-620X
Hennadii Khalimov Kharkiv National University of Radio Electronics Author https://orcid.org/0000-0002-2054-9186

Keywords:

computationally complex tasks, cryptography, quantum cryptography, logarithmic signatures

Abstract

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

Download data is not yet available.

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.