image: Y-Cx, Y-Cy, and Y-Cz represent the different ansatzes; N-M and GD represent the Nelder-Mead method and gradient descent method respectively; the figures represent the number of iterations. view more
Credit: ©Science China Press
Recently, Professor Guilu Long, Dr. Zeguo Wang, Dr. Shijie Wei from Tsinghua University and Beijing Academy of Quantum Information Sciences, and Professor Lajos Hanzo from the University of Southampton, UK, proposed a quantum attack scheme for symmetric cryptography, which may lead to a deadly threat to the security of symmetric cryptography such as AES.
So far, it is generally believed in the world that although quantum computers bring fatal threats to asymmetric cryptography such as RSA, they do not pose fatal threat to symmetric cryptography such as AES. For symmetric cryptography such as AES, under Grover’s attack, the computational complexity has changed from the n index of 2 (2^n) to the n/2 index of 2 (2^(n/2)), and the exponent complexity remains. Therefore, it is generally believed that as long as the key length is doubled, the corresponding security under a quantum computer can be achieved. At present, the upgrade and migration plan of the cryptosystem has been launched internationally.
The new attack method proposed by Professor Long Guilu and others uses Variational Quantum Algorithm (VQA). They studied the security of the symmetric cryptography S-DES (Simplified Data Encryption Standard) under the VQA attack. They constructed a Hamiltonian based on a pair of known plaintext and its corresponding ciphertext. The ground state of the Hamiltonian corresponds to the quantum state of the chosen ciphertext. By using variational methods, they found ground state of Hamiltonian, then the key can be obtained. Simply put, in VQA, a quantum circuit is constructed in which there are several transformations with parameters, and these parameters are varied to obtain the minimum value of Hamiltonian. They used six ansatzes and two different classical optimization methods to calculate a total of 12 different variational strategies, and the results are shown in Table 2 of the article. Of the two optimization methods, the gradient descent method is better than the simplex method. The key can be obtained by 30-56 searches on average, which is similar to the 32 required by Grover's attack.
Although the average number of iterations is similar to that of Grover's attack, the number of iterations of the variational method is not fixed. In some cases, the number of iterations is much lower than Grover's attack, even as low as 2. Figure 8 in the article shows the distribution of the number of iterations, corresponding to the strategy with gradient descent operation in the third row (A Y-Cz) of Table 2. For the same Hamiltonian and parameters, a total of 30 repeated simulations are performed, and if the simulations with more than 94 iterations has not converged, the simulation is stopped. The minimum number of iterations is 2 and the maximum number of searches is 94. When the number of iterations is between 2 and 5, there are ten times in total, accounting for one-third, which is a large proportion. In the actual calculation, the cutoff of number of searches can be set lower, so that there is more time to try those variational schemes with smaller number of searches.
Variational algorithm has no deterministic complexity, which is a disadvantage of it. However, in cryptanalysis, this complexity uncertainty turns into serious challenges to the security analysis of encryption cryptography such as AES, even the entire classical cryptographic algorithm based on computational complexity, under such attacks in quantum computing. Variational algorithms may bring more serious threats on these cryptographic algorithms than Shor's algorithm and Grover's algorithm. In particular, variational quantum algorithms are available on recent quantum computing hardware. If the results of this study hold in cryptographic algorithms with larger key size, such as AES-128, it will further strengthen this estimation and have a significant impact on the future course of information security.
It is worth noting that, in response to the threat of quantum computing to asymmetric cryptography such as RSA, classical cryptography has developed post-quantum cryptography. Recently the US National Institute of Standards and Technology announced the third-round winner. Analyzing the security of the post-quantum cryptography under variational quantum algorithms attacks is also a serious challenge.
Quantum technologies such as quantum secure direct communication and quantum key distribution can address this challenge. Quantum secure direct communication leaves the eavesdropper without any data related to the message, nothing to decipher, no matter how much computing power the decipherer has. Quantum key distribution makes it impossible for eavesdroppers to obtain any key information, and the use of these keys to encrypt the information with one-time pad has been proved to be undecipherable.
See the article:
Variational quantum attacks threaten advanced encryption standard based symmetric cryptography
https://doi.org/10.1007/s11432-022-3511-5
Journal
Science China Information Sciences