November 06, 2023

Hacking Cryptographic Protocols with Advanced Variational Quantum Attacks

Today’s world is all about information. Beyond the im- pact of other technologies, secure communications have become one of the cornerstones of modern society. In this era more than ever, information is both an asset and a vulnerability, and therefore cryptology’s relevance has escalated to unprecedented levels in history. Infor- mation control is critical, and it is therefore no surprise that quantum computing has emerged as one of the key disruptive technologies in this ambit, given the poten- tial of quantum computers to hack current cybersecurity standards. Whoever wins the quantum computing race, is also called to win the information race.

The field of cryptology serves as the cornerstone of secure digital communication, encompassing both cryp- tography and cryptanalysis. It provides tools for en- crypting sensitive data, thereby ensuring its confiden- tiality and integrity during transmission over insecure networks. Cryptanalysis, the counterpart to cryptogra- phy, aims to break these secure communication channels. It employs a variety of techniques, ranging from brute- force attacks (which involve an exhaustive search through all possible keys) to more structured approaches. These last may include ciphertext-only, known-plaintext, and chosen-plaintext attack, each one posing a specific set of challenges for the attacker. Over the years, cryptanalysis has become an art in itself.

Cryptographic functions are the backbone of these secure communication systems. Divided into Hash al- gorithms, symmetric algorithms and asymmetric algo- rithms, each scheme provides specific and valuable fea- tures. For instance, hash algorithms are crucial for data integrity and password verification [1], and are central to cryptocurrencies such as Bitcoin. Symmetric key al- gorithms, like DES [2], Blowfish [3], and AES [4], use a single secret key for both encryption and decryption providing speed advantages over its counterpart public-

key cryptography. This latter is exemplified by RSA [5], which uses a public key for encryption and a private key for decryption, being thus an example of asymmetric cryptography. Public-key cryptography can be employed for establishing the secret key that will be used in a sym- metric protocol, the combination of both cryptographic methods often results in establishing more secure com- munication channels.

In this context, quantum computing [6] has chal- lenged the very foundations of cryptology. By leveraging the principles of quantum mechanics, quantum comput- ers hold the promise of polynomial or even exponential speed-ups for certain computational tasks, including the ones often encountered in cryptography. Quantum com- puters therefore pose a significant threat to classical cryp- tographic systems. The factoring algorithm by Shor [7] showed that quantum computers could, in practice, hack RSA and related cybersecurity protocols efficiently. Re- cent estimations point out that one would require around 20 million noisy qubits to factor 2048-bit RSA integers in 8 hours [8], still beyond reach of current quantum proces- sors. More generically, brute-force attacks can also be en- hanced via quantum computing using Grover’s algorithm for searching unstructured databases [9], and which has been tested for symmetric DES protocols [10].

In the current era of Noisy Intermediate-Scale Quan- tum (NISQ) devices, progress has also been made along the lines of of variational quantum algorithms. For exam- ple, the so-called Variational Quantum Attack Algorithm (VQAA) [11] implements a variational quantum circuit aiming at decoding the key of AES-like symmetric proto- cols specifically designed for the Simplified-Data Encryp- tion Standard (S-DES) [12]. In practice, VQAA encodes a known ciphertext in the lowest-energy state of a clas- sical Hamiltonian, akin to a cost function, and aims to find such state by trying out different keys, effectively re- trieving the secret key by optimizing a set of variational parameters. As stated, however, the VQAA algorithmstill uses a very large number of qubits, making it thus impractical for real-life ciphers.

Full paper here