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 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.