Grover vs. Symmetric Cryptography
By Jaeyoon, Caroline, Jennifer
EXTERNAL MENTOR: Dr. Atul Mantri, Virginia Tech Center for Quantum Information Science and Engineering
Introduction
The proposed research aims to simulate Grover’s search to “attack” toy ciphers. The efficacy of this approach will be demonstrated by comparing it to a classical brute force approach, which is significantly slower than quantum approaches. Grover’s algorithm provides a quadratic speedup compared to classical search algorithms. However, Simon’s algorithm offers an exponential speedup compared to classical algorithms, and its application can be used to further optimize encryption and decryption time efficiencies.
Intellectual Merit
The intellectual merit of this research is rooted in previous research surrounding the Grover and Simon search algorithms. In a previous paper (Kuwakado & Morii, 2013), classical and quantum cryptography algorithms are tested on the Even-Mansour Cipher (EM Cipher), a classical encryption cipher. This cipher is secure if n is large, as it requires O(2N/4) time to break. However, the quantum version is insecure because a key can be recovered in polynomial time of the key length.
This quantum version takes n qubits as plaintext and outputs n qubits as ciphertext. The cipher is represented by a unitary matrix, and using Grover’s algorithm, the cipher can be broken in O(2(N/2)) time, an improvement over the classical approach. However, the newly proposed algorithm in the paper, which is similar to Simon’s algorithm, is able to break the cipher in polynomial time (with the quantum time complexity being O(N) and the classical time complexity being O(N3)). This algorithm and paper demonstrates the advantage quantum cryptography approaches have over classical ones and provides an effective cryptography algorithm that is able to decrypt the EM Cipher exponentially faster than standard approaches.
Broader Impact
The broader impact of this research is preemptively discovering the power of quantum encryption and decryption algorithms, such as Grover’s algorithm and Simon’s algorithm. These algorithms can improve encryption and decryption efficiencies, offering quadratic and even exponential speedups compared to classical brute force algorithms. As a result, quantum algorithms make classical ciphers susceptible to attack and present a major threat to cybersecurity and communications. Demonstrating the computational speedup of Grover’s and Simon’s algorithms can encourage the development of new ciphers, perhaps quantum ciphers, that are more secure against quantum cryptography algorithms. Our research will validate existing research that demonstrates quantum algorithm speedups and creating more secure ciphers is necessary.