Paper 2023/318

A Transformation for Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography

Abstract

This is the second update of this report. In this update, we partially solve Open problem 2 and completely solve Open problem 3 from the previous version. By doing this we address one modification of the Panny's attack done by Nils Langius. In the first update we introduced conditions for choosing the parameters that render the attacks (both classical and quantum algorithms attacks) proposed by Lorenz Panny in March 2023 on the first variant, inapplicable. For the classical attack, we prove that the discrete logarithms that he was basing his attack upon do not exist for the new parameters. For the quantum algorithm attacks where he proposed computing a basis of a three-dimensional lattice, as proposed in Kitaev's generalization of Shor's quantum algorithm, we prove that for our transformation, the rank of that lattice (the Abelian Stabiliser in Kitaev's terminology) has a rank one, which makes the Kitaev's quantum algorithm inapplicable. In this paper we construct algebraic structures where rising to the non-associative power indices is no longer tied with the Discrete Logarithm Problem but with a variant of a problem that has been analysed in the last two decades and does not have a quantum polynomial algorithm that solves it. The problem is called Exponential Congruences Problem (ECP). By this, \emph{we disprove} the claims presented in the ePrint report 2021/583 titled "Entropoids: Groups in Disguise" by Lorenz Panny that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} Additionally, we construct an Arithmetic for power indices and propose generic recipe guidelines that we call "Entropic-Lift" for transforming some of the existing classical cryptographic schemes that depend on the hardness of Discrete Logarithm Problem to post-quantum cryptographic schemes that will base their security on the hardness of the Entropoid variant of the Exponential Congruences Problem (EECP). As concrete examples, we show how to transform the classical Diffie-Hellman key exchange, DSA and Schnorr signature schemes. We also post several open problems (two of them now are solved) in relation to EECP and the "Entropic-Lift" transformation.