Quantum Computing Challenges Cryptography; Researchers Propose Quantum-Resistant Hash Algorithm

Quantum computing is revolutionizing cryptography, posing risks to traditional security methods such as RSA, Finite Field Diffie-Hellman key exchange, and Elliptic Curve Diffie-Hellman key exchange. These methods, which rely on complex mathematical problems, are vulnerable to Shor’s algorithm, which can solve these problems quickly on a quantum computer. To counter this, researchers from the College of Engineering and Technology and Asia University have developed a Quantum-Resistant Hash Algorithm (QRHA) called the Modular Hash Learning Algorithm (MHLA). This algorithm offers improved security and data confidentiality in the quantum era, contributing to the fortification of cryptographic systems against quantum computing threats.

What is the Impact of Quantum Computing on Cryptography?

Quantum computing, a rapidly advancing technology, is changing the way we think about security in cryptography. Hash functions, which are essential for digital security, are particularly vulnerable in this new era. This study delves into the risks posed by quantum computing to traditional security methods and looks at Quantum-Resistant Hash Functions (QRHFs) as a crucial aspect of secure cryptographic systems moving forward.

Quantum computing has the potential to break many public-key cryptography schemes such as RSA, Finite Field Diffie-Hellman key exchange (FFDH), and Elliptic Curve Diffie-Hellman key exchange (ECDH). These schemes use hard math problems like factoring big numbers or finding discrete logarithms to protect data. However, Shor’s algorithm can solve these problems quickly on a quantum computer, making these schemes unsafe.

Hash functions are important for these schemes. They take data and make small digests or hashes from it. These hashes are used for different purposes like checking data, proving identity, and keeping data secret. In RSA, hash functions are used for digital signatures. A sender makes a hash of the message, signs it, and sends it with the message. Receivers can use the sender’s public key to check the signature by making the hash again from the message and comparing it with the signature. Shor’s algorithm could find the private key used for signing, thus breaking the security of these hash-based methods.

How Does Shor’s Algorithm Threaten Cryptography?

Shor’s algorithm poses a threat to certain cryptographic methods like RSA by efficiently factoring the modulus N, which is fundamental to RSA’s security. RSA relies on the complexity of computing a large composite number N formed from two primes p and q. The public key includes N and an encryption exponent e, while the private key involves prime factors p and q along with a decryption exponent d.

Shor’s algorithm aims to efficiently find the prime factors p and q of N by leveraging the quantum computing power. It employs a quantum subroutine called Quantum Phase Estimation (QPE) to determine the order r of a modulo N, where a is randomly chosen such that gcd(a, N) = 1. The order r is the smallest positive integer for which a^r = 1 mod N. QPE encodes this information in a quantum state, allowing us to estimate r efficiently.

After obtaining the quantum state from QPE, classical postprocessing, specifically the continued fractions algorithm, is applied to extract r from the quantum measurement outcomes. If r is even and not equal to N, we can compute d = gcd(a^(r/2) – 1, N). If d is a nontrivial factor of N, i.e., d ≠ 1 and d ≠ N, then N can be factored as N = d * N/d. This reveals the prime factors of N, thus breaking the security of RSA.

What is the Solution to Quantum Threats in Cryptography?

In response to these emerging threats, the paper introduces a novel Quantum-Resistant Hash Algorithm (QRHA) named the Modular Hash Learning Algorithm (MHLA). MHLA has been meticulously designed with a strong focus on fundamental principles of quantum resistance and incorporates advanced mathematical and algorithmic techniques to enhance its security.

The research demonstrates that MHLA offers improved security in the context of the quantum era, ensuring data confidentiality and integrity. Moreover, MHLA boasts an efficient algorithmic complexity with a time complexity of O(mnk) for the matrix-vector product. This research contributes to the ongoing efforts to fortify cryptographic systems against the evolving landscape of quantum computing.

Who are the Key Contributors to this Research?

This research was conducted by a team of researchers from the College of Engineering and Technology and Asia University. The team includes Manraj Singh, Sunil K Singh, Sudhakar Kumar, Mehak Preet from the College of Engineering and Technology, Varsha Arya and Brij B Gupta from Asia University. Their combined expertise in cryptography, hash functions, post-quantum cryptography, quantum-resistant hash functions, and network security has contributed to the development of the Modular Hash Learning Algorithm (MHLA), a novel solution to the security challenges posed by quantum computing.