New Quantum-Safe Versions of Decisional Diffie-Hellman Assumption in the General Linear Group and Their Applications: Two New Key-agreements
It addresses the critical problem of quantum threats to widely used cryptographic protocols, offering incremental improvements by adapting existing schemes with noise-based security.
This paper tackles the vulnerability of Diffie-Hellman and RSA to quantum attacks by proposing two new matrix-based key-agreement schemes that avoid reliance on discrete logarithm and integer factoring problems, proving their security under new quantum-safe hardness assumptions.
Diffie-Hellman key-agreement and RSA cryptosystem are widely used to provide security in internet protocols. But both of the two algorithms are totally breakable using Shor's algorithms. This paper proposes two connected matrix-based key-agreements: (a) Diffie-Hellman Key-Agreement with Errors and (b) RSA-Resemble Key-agreement, which, respectively, bear resemblance to Diffie-Hellman key-agreement and RSA cryptosystem and thereby they gain some of the well-known security characteristics of these two algorithms, but without being subject to Shor's algorithms attacks. That is, the new schemes avoid the direct reliance on the hardness of Discrete Logarithm and Integer Factoring problems which are solvable by Shor's algorithms. The paper introduces a new family of quantum-safe hardness assumptions which consist of taking noisy powers of binary matrices. The new assumptions are derived from Decisional Diffie-Hellman (DDH) assumption in the general linear group GL(n,2) by introducing random noise into a quadruple similar to that which define the DDH assumption in GL(n,2(. Thereby we make certain that the resulting quadruple is secure against Shor's algorithm attack and any other DLP-based attack. Thence, the resulting assumptions, are used as basis for the two key-agreement schemes. We prove that these key-agreements are secure -- in key indistinguishability notion -- under the new assumptions.