Abstract
In recent years, the application of machine learning and deep learning to classical cryptanalysis is an active research field.
In this project, we perform quantum cryptanalysis that combines quantum with machine learning and artificial neural network. To the best of our knowledge, our work is the first attempt in the world to apply QNN(Quantum Neural Network) and QML(Quantum Machine Learning) to cryptanalysis. Finally, for evaluation between classical and quantum, we implement and compare three types of cryptanalysis: classic, quantum and hybrid. During this hackathon, we found interesting results for quantum cryptanalysis using QML and QNN.
Members
Hyunji Kim, Kyungbae Jang, Yeajun Kang, Wonwoong Kim, Sejin Lim, Seyoung Yoon, Yujin Oh
Related Works
Cryptanalysis is the analysis of the security of cryptographic algorithms in cryptography.
In general, cryptanalysis analyzes the resistance against various possible attacks on cryptographic algorithms.
One of the principles of secure cryptographic design is that plaintext-ciphertext pairs should be indistinguishable.
In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. (See https://en.wikipedia.org/wiki/Distinguishing_attack)
In this project, we perform quantum cryptanalysis, classical cryptanalysis, and hybrid(quantum & classic) cryptanalysis.
Artificial neural networks are learning algorithms inspired by neural networks in biology.
A neural network is constructed in the form of stacked layers of multiple nodes. Nodes existing in each layer perform a weighted sum operation using the node values and weights of the previous layer connected to them, and are then calculated as a single value through an activation function, which is a non-linear function. In this way, the loss value is obtained after passing through all the layers. Then, the weights inside the neural network are updated in the direction of minimizing the loss through the backpropagation process. By repeating this process, a neural network that guarantees generalization performance for untrained data is constructed. When the trained model is used for actual inference, inference proceeds by inputting data with the weights of the neural network fixed. Through this, it is possible to learn, classify, and predict by extracting features of input data (image, time series, language, graph, etc.).
A quantum neural network is an artificial intelligence that utilizes quantum mechanics phenomenon (entanglement and superposition). Quantum neural network consists of qubits and quantum gates on a quantum computer. Therefore, it learns quantum state data (parameterized quantum circuit) by encoding the classical data into quantum data. The parameters of the circuit are set using the input data, and each qubit passes through gates and then the value changes. When qubits are observed, the state of the qubits is determined. Through this process, a quantum neural network works.
The security evaluation of cryptographic algorithms is carried out by analyzing attacks that can be performed on classical computers. However, since the best cryptanalysis tool called quantum computer has appeared, the security of existing cryptographic algorithms needs to be reevaluated.
The most well-known quantum attacks on cryptography are the Shor's algorithm for public key cryptography and the Grover algorithm for symmetric key cryptography. For this reason, studies on the application of Grover's algorithm and Shor's algorithm to cryptography are being proposed.
Grover's algorithm in cryptanalysis
Shor's algorithm in cryptanalysis
On the other hand, machine learning and deep learning are recently applied to classical cryptanalysis, but there is no case where quantum is combined. In this project we do this.
Our works
-
Quantum Cryptanalysis using Hybrid Neural Network
We utilize the library provided by Qiskit to use a hybrid neural network combining classical and quantum. (https://qiskit.org/textbook/ch-machine-learning/machine-learning-qiskit-pytorch.html)
In this hybrid neural network, the input is classical data and the output layer is composed of quantum circuits. Then, the loss is calculated using the quantum circuit output value. In this way, neural network training proceeds, and this library is applying it to MNIST classification examples.
We apply this hybrid neural network to the problem of classifying whether ciphertext-plaintext pairs are correct or random bit pairs. An ideal encryption algorithm should not be able to find any correlation between plaintext and ciphertext. Our hybrid neural network finds real plaintext-ciphertext pairs when random bit pairs and plaintext-ciphertext pairs generated by an encryption algorithm are input. Since it is a binary classification problem that determines whether it is real or fake, our hybrid neural network maintains the existing binary classification structure using 1 qubit(Figure 1).
Figure 1. Quantum circuit as layer(1-qubit)
We perform quantum cry5ptography analysis on the following encryption algorithms: Caesar, Vigenere, Simple-DES, and PRESENT-Toy. If the trained neural network correctly distinguishes the real plaintext-ciphertext pair, the security of the encryption algorithm is evaluated as weak. Conversely, if it is difficult to distinguish, the security is evaluated as high.
First, four encryption algorithms are implemented in Python to generate plaintext-ciphertext pairs for training. The generated plaintext-ciphertext pairs are labeled as 1 (real) and random bit pairs are generated for fake data, which are labeled as 0 (fake). For cryptanalysis of the reduced encryption algorithm, a total of 150 data of 75 8-bit plaintext-ciphertext pairs and 75 fake bit pairs are used(Figure 2). The layer is modified for 16-bit input (plaintext-ciphertext) and one more layer is added for accuracy. This is shown in Figure 3.
Figure 2. Part of the training data(1 is a real plaintext-ciphertext pair, 0 is a fake bit pair, csv file)
Figure 3. Network structure
-
Quantum Cryptanalysis using Quantum Support Vector Machine
We constructed a quantum circuit by utilizing the FeatureMap of the QSVM library provided by IBM's Qiskit.
The feature map was selected considering whether it satisfies features such as second order or entanglement.
Currently, a gate that can express an expression representing this feature map is not provided.
Therefore, the feature map uses gate combinations such as Controlled NOT, Rotation Z for nonlinear features.
We also have control over qubits, either through a linear option to entangle a qubit with one next qubit, or a pull option to entangle a qubit with all qubits that follow it.
The smaller the circuit depth, the shorter the execution time and the higher the accuracy, so we use the linear option.
Through this, a quantum circuit as a kernel of QSVM is constructed and used for training.
By repeatedly executing the designed quantum circuit, the parameters of the circuit are updated.
Measurement is performed on each qubit to determine the state of the qubit with a single value.
the qubits of circuit are measured multiple times to classify them with high probability.
Finally, the trained circuit is used as a classifier.
Evaluation
-
Classical, quantum-classical hybrid and quantum neural network-based cryptanalysis
Experiments were conducted when the number of data is 150 and 250. Figure 4 and 5 compare the loss graphs when the number of data is 150. Training was performed with the same epoch (20) in the same environment.
As a result of analyzing it by dividing it into hybrid and classic, we found that the loss rapidly decreased while showing an ideal graph of a hybrid neural network combining both.
Additionally, we found that the loss graph of the hybrid neural network has more dynamic flow compared to the classical neural network. We believe this is a unique phenomenon when we combine quantum mechanics. The hybrid neural network trained in this way shows interesting results. See Table 1 and 2.
Figure 4. Classical Neural Network loss graph
Figure 5. Hybrid Neural Network loss graph
Table 1 is the performance of the same trained hybrid and classical neural networks. The hybrid neural network provides good accuracy with few epochs. (If it is the same epoch, the accuracy of the hybrid is higher)
Table 2 is the performance for more data(250). Also, with fewer epochs, the hybrid neural network provides higher accuracy than the classical neural network.
One thing to point out is the accuracy of PRESENT. PRESENT has lower accuracy(50%) in both classic and hybrid. This means that the plaintext-ciphertext pair generated by PRESENT is difficult to distinguish from a fake bit pair, which means that it is cryptographically secure. The classification model generated by this hybrid neural network is effective for cryptographic analysis. *For QuantumNN,8 qubits are used. Because, in the case of 8-bit plaintext and ciphertext, 16 qubits are required.
However, since the kernel is turned off during circuit execution, a 4-bit dataset is used.
Table 1. Performance(150 data)
Table 2. Performance(250 data)
Conclusion
In this project, we performed quantum cryptography analysis that combines quantum, machine learning, and neural networks. We also analyzed three types of cryptanalysis(classic, hybrid and quantum) and compared their performance. Our work will be the basis for applying quantum neural networks and quantum machine learning to cryptanalysis. From data generation to model evaluation, the codes used are all available online, and quantum cryptography researchers can leverage it.
Future works
In QNN, we plan to use fewer qubits by applying dimensionality reduction techniques such as qubit reuploading or PCA. For hybrid networks, hyperparameter tuning is required to achieve higher performance in the future.
GitHub repo(Source code)
https://github.com/starj1023/2022-Hackathon
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent