{'fraction_non_alphanumeric': 0.046122403888643394, 'fraction_numerical': 0.018448961555457357, 'mean_word_length': 3.931898665213838, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Linear Cryptanalysis through the Lens of Clauser-Horne-Shimony-Holt Game

Application of CHSH game in Linear Cryptanalysis is presented. Till date, the known usage of CHSH game in Quantum Cryptology is to verify the device independence of the protocols. We observed that the classical symmetric ciphers having the bias equal to 0:25 can be improved to 0:35 exploiting the game which indicates clear improvement over existing Linear and Differential cryptanalysis. In the present initiative, we showed the application of the game in linear cryptanalysis on a lightweight cipher named SIMON. However, the approach can be extended to Differential cryptanalysis too. This observation opens a new direction of research in quantum cryptography.


I. INTRODUCTION
Bell inequality [1] certifies the non-local relationship between two correlated systems. In other words, Bell inequality confirms the quantumness of the system. This inequality can be described in form of a game, named CHSH [2] game.
In CHSH game, there are one referee and two players whom we generally call Alice and Bob. Referee provides a bit x to Alice and a bit y to Bob. After receiving the bits, Alice and Bob each outputs a bit, say, a for Alice and b for Bob. The players win the game if x ∧ y = a ⊕ b.
In classical domain where there is no existence of entanglement, the best strategy to win the game would be as follows.
1. Alice and Bob both output 0 irrespective of their inputs.
2. Alice and Bob both output 1 irrespective of their inputs.
In such case, they will win the game with probability 0.75. On the other hand, in quantum domain where one can take the advantage of entanglement, wins the game with better probability. In this case, Alice and Bob share maximally entangled state prior to the game. After receiving the inputs from referee, the players measure their respective systems in some specified bases. The basis choice depends on the input bits. It is well proven that in such strategy, Alice and Bob can improve their winning probability upto 0.85.
In quantum cryptography, CHSH game is used for testing the device independence of the protocols. Precisely, 0.85 probability certifies the existence of maximally entangled state amongst the legitimate parties [3][4][5][6][7][8][9]. If the shared states are maximally entangled, then from the monogamy relation of entanglement [10][11][12], it is guaranteed that the information about the raw key extracted by an eavesdropper, generally familiar as Eve, can not be greater than the information extracted by Bob (one of the authenticated parties).
The probability is calculated from input-output statistics. For example, in case of Quantum Key Distribution (QKD) protocols, the QKD boxes are available as Black boxes to the legitimate parties. Each box can take an input bit (x or y) and provides an output bit (a or b). If the input-output statistics satisfies the winning condition with probability 0.85, then there must exists a non-local maximal correlation between the boxes available to the authenticated parties. This non-local correlation guarantees the absolute security of the protocol. In the present initiative, we report another application of the game in quantum cryptography.
In cryptography, cipher is the encrypted form of message. Message is encrypted in the motivation towards hiding the information from the eavesdropper. The encryption as well as the decryption function are known to all, however the secret thing is the key. The encryption function is chosen in such a way so that without any knowledge of the key it is not possible to decrypt the cipher. Even the designer of the crypto-system also can not decipher it without the knowledge of the key. Hence, extracting the key bits is the prime motivation for attacking the cipher. Formally, we name it as cryptanalysis (breaking the code).
It is expected that the ciphers are designed in such a way so that the random variables 0 and 1 come from a probability distribution {1/2, 1/2}. However, any shifting from this distribution may cause loopholes in the cipher. Exploiting this one can extract the key bit(s). The deviation from 1/2 is called bias. Thus, finding a bias for a given cipher is another important job in cryptanalysis. Now, consider that there are two probability distributions {p, 1 − p} and {q, 1 − q}. To distinguish these two probability distributions with confidence very close to 1, the number of samples required is approximately 1/pq 2 . If the value of q increases, then the number of samples decreases. If p = 1/2 and q = 1/2 + , then is called bias for the random variables. Hence, improving the bias is very significant contribution in cryptanalysis.
In the present draft, we observe that if we can convert the classical ciphers in quantum ciphers, i.e, bits will be converted to qubits and the classical gates used in the ciphers will be converted to the quantum gates, then we may exploit quantum advantage to improve the bias present in the classical cipher. Here, we consider a lightweight cipher named SIMON [13]. It is a symmetric cipher, i.e, the sender and the receiver use the same secret key. SIMON is a lightweigh cipher designed by NSA (National Security Agency of USA). That is why this cipher is very important in the domain of classical cryptography.
In classical domain, it was observed that this cipher has some bias and the optimal bias found is 0.25 i.e., here q = 0.75. On the other hand, exploiting Boolean version of CHSH game, we can successfully improve the bias upto 0.35, i.e., in this case, q will be 0.85.
Contrary to these, in the current manuscript, we exploit CHSH game and improve the bias of the cipher. This improvement should have major impact in linear and differential cryptanalysis [29]. We believe that this will open up a new avenue of research in the paradigm of quantum cryptography .
The draft is organized as follows. Section II deals with a brief description of classical cipher SIMON, its encryption and decryption algorithms, existing cryptanalysis on the cipher. In Section III, we discuss Boolean implementation of CHSH game. In section Section IV we show how the Boolean circuit of the game can be exploited in SIMON. We implement the idea in IBMQ simulator for an arbitrary round i. Section V concludes the paper.

II. BRIEF DESCRIPTION OF SIMON
SIMON is a family of balanced Feistel structured [29] lightweight block ciphers with 10 different block sizes and key sizes (Table I)  The round function used in the Feistel structure of SI-MON block ciphers consists of circular shift, bitwise AND and bitwise XOR operations. The state update function is defined as, The structure of one round SIMON encryption is depicted in Figure 1, where S j represents a left circular shift by j bits, L i and R i are n-bit words which constitutes the state of SIMON at the i-th round and k i is the round key which is generated by key scheduling algorithm. The description is out of the scope for the paper.
Interested readers may explore [13] for detailed description of the lightweight ciphers, SIMON and SPECK.

FIG. 1: SIMON round function
Let (L 0 , R 0 ) be the initial state and the state propagate as (L 0 , R 0 ), (L 1 , R 1 ), (L 2 , R 2 ), · · · , (L T , R T ) upto T rounds. If K is the key for a round i, then from the state update function of SIMON , one can write the following.
where, 0 ≤ i ≤ (n/2). Here i stands for round number and j mod (n/2) denotes the position of the bit. Now, we consider L i (j) ⊕ L i+1 (j). That is we are establishing a linear relationship between the jth bit of ith round and the jth bit of i + 1 round. In other words, we are establishing a linear relation between a bit and its encrypted cipher bit. Due to the encryption function (round update function) of SIMON , this will be equal to the following expression.
The Boolean function 'AND' (&) plays a vital role in this linear relationship. A close observation reveals that if L i (j) = L i (j + 2), then due to the presence of 'AND' operation we can write the followings.
These imply that there is certain bias in the cipher. Hence, for a sufficient number of plaintext-ciphertext pairs for a round i, it is possible to find such bias. This can be further extended for two conjecutive rounds, i.e., for i and i + 2. This is because of the advantage of Feistel construction. In Feistel construction, L i+1 (j) = R i+2 (j). Hence, it is rather better to say that for a sufficient number of plaintext-ciphertext pairs for two rounds SIMON, it is possible to find the above bias.
The procedure would be the following.
1. For a given plaintext-ciphertext pairs for two round The variants of such attack has been studied in [30][31][32]. However, the bias better than 0.25 for a round has not been found yet. In this backdrop, we observed that as the bias comes from 'AND' operation, one can take the advantage of CHSH game and hence can improve the bias for a round. Before going to the implementation of CHSH game in SIMON , we like to discuss the Boolean implementation of CHSH game which is the pilar of improving the bias.

III. BOOLEAN IMPLEMENTATION OF CHSH GAME
In this section, CHSH game will be viewed as a Boolean According to the classical strategy for winning the game with maximum probability, Alice and Bob output the same bits. This has been depicted using first CNOT gate (from left) as a cloning operator on q0 3 . It copies q0 3 in q0 4 resulting a = b always. Hadamard gates are used to take care of all possible choices of x, y and a. If we compute the probability considering the reduced density matrix of q0 2 , we will get 0.75 for the bit 0 and 0.25 for the bit 1. Now, to implement quantum strategy we took the help of Controlled-Hadamard (CH) and Controlled-U3 (CU 3 ) gate, where U 3 = cos θ/2 − sin θ/2 sin θ/2 cos θ/2 . The corresponding circuit is given in Fig 3. According to the Note that π/4 = 0.785. That is why we set θ as 0.785 when U 3 has been constructed. We compute the probability considering the reduced density matrix of q0 2 . We obtained 0.85 (taking two decimal places) for the bit 0 and 0.15 for the bit 1.
In the following section, we will show how we exploit this Boolean circuit in SIMON and improve the bias.

IV. BOOLEAN CHSH GAME FOR IMPROVING THE BIAS OF SIMON
To exploit the Boolean circuit of CHSH game in SI-MON , we need to design SIMON round function in quantum domain. We assume that we have k-qubits reserved for the key, K, and n-qubits each for L and R. The classical Boolean operations are now replaced by the quantum reversible gates. The replacement is as follows. For detail explanation one may explore [34].

'XOR' is replaced by CNOT
Thus the quantum version of SIMON round function will be as follows.
where, L i (j + m) represents m bits shift on L i (j), i.e., S m (L i (j)). The corresponding circuit is presented in Fig 4. Here, l 0 , l 1 and l 2 represent L i (j + 2), L i (j + 1)

FIG. 4: Quantum version of SIMON round update function
and L i (j + 8) respectively. r 0 represents R i (j) and k 0 stand for K i (j). Hadamard gates are taking care of all possible input states. In this case, there is no bias found, i.e, probability of the random variable 0 is 1/2 and probability of the random variable 1 is also 1/2. However, we observe that if for a round i, L i (j) = L i (j + 2), then the followings happen. Such situation is picturized by the circuit given in Fig 5.

FIG. 5: Quantum version of linear approximation
L i (j + 2) and L ( j + 8) respectively. As L i (j) = L i (j + 2), we put CNOT gate on q 0 and q 2 considering q 0 as control bit. CNOT gate operates as a cloning machine here. q 0 is copied into q 2 making L i (j) = L i (j + 2). Similarly, as R i (j) = K i (j), we again apply CNOT gate on r 0 so that it will be copied into k 0 . Other parts of the circuit remain same. After the second barrier, we apply CNOT gate on q 0 and r 0 to take care of the linear relation between L i (j) and L i+1 (j), i.e., L i (j) ⊕ L i+1 (j). We modify the circuit with Boolean CHSH game and observe that Pr(L i (j) ⊕ L i+1 (j) = 0|R i (j) = K i (j)) = 0.85 and Pr(L i (j) ⊕ L i+1 (j) = 1|R i (j) = K i (j)) = 0.15. The modified circuit is given in Fig 6. We also prove that the optimal probability is 0.85. Calculations for different choices of q 1 and q 3 , i.e., for all possible options between L i (j +1) and L i (j +8) are shown in the Appendix. We do not consider other bits, as in this case, L i (j) = L i (j + 2) and K i (j) = R i (j). We have implemented all the circuits

V. DISCUSSIONS AND CONCLUSION
In the present initiative, we have shown how to improve the bias of a classical lightweight cipher called SI-MON in linear cryptanalysis exploiting CHSH game. In the domain of Quantum Cryptanalysis on Symmetric Ciphers we mainly study the impact of Grover's search algorithm [14], Simon period finding algorithm [15] and the combination of both on block ciphers. It is also shown that classically secure ciphers can be broken with quantum algorithms. Quantum algorithm can be used to speed up classical attacks too.
Contrary to these, in the present draft, we present different kind of attack where bias of a random variable has been improved. This should have major impact in linear and differential cryptanalysis.
Here, we consider lightweight cipher SIMON only. However, we can construct a lot many CHSH like games which can be used to improve the bias of classical symmetric ciphers: stream as well as block ciphers. The present finding is the tip of the iceberg. This finding will open-up new direction of research in the domain of quantum cryptography.
Finally, the result again proves the quantum advantage over classical domain showing that in quantum regime, the symmetric ciphers are not as secure as those are in classical domain. We may need less samples to distinguish two probability distribution functions p and q. This signals that we should be very careful when designing a cipher for post quantum era.
Our future research will be directed towards linear and differential cryptanalysis of different symmetric ciphers using the result presented in the paper as well as designing various CHSH like games which might be exploited to improve the bias of existing ciphers.

VI. APPENDIX
We begin this section by providing the mathematical derivations for modified linear approximations using CHSH game. We look into the evolution of qubits |r 0 k 0 corresponding to the quantum circuit given in Figure  6. For a better readability, the same quantum circuit is provided again. Observe that, before the first barrier, |r 0 k 0 is in a maximally entangled state, 1 √ 2 (|00 + |11 ).
Here we consider four different possibilities for q 1 and q 3 , namely, q 1 q 3 = 00, 01, 10 or 11 and measure the modified bias from the qubit |r 0 . Notice that, since q 0 = q 2 and both q 2 (before the second barrier) and q 0 (at the end ) are being XOR-ed with r 0 without any modification, they will nullify each other and we can skip them while studying the state evolution.
Case I. q 1 = 0, q 3 = 0: Since q 1 = q 3 = 0, the CH gate controlled by q 1 and the CCX gate controlled by both q 1 , q 3 will not be activated here. Thus the starting state evolves as follows.
Case II. q 1 = 0, q 3 = 1: Since q 1 = 0, the CH gate controlled by q 1 and the CCX gate controlled by both q 1 , q 3 will not be activated here. Therefore, the starting state |r 0 k 0 evolves as follows.
Case III. q 1 = 1, q 3 = 0: Here the CH gate controlled by q 1 will be activated. However, since q 3 = 0 the CCX gate controlled by both q 1 , q 3 will not be activated here. Hence the state evolution will be as follows.
To maximize the probabilities, we can form a function h(θ) = cos 2 θ 2 + 1 2 (1 + sin θ) and using the derivative test we can show that h becomes maximum for θ = π 4 . Therefore, when θ = π 4 , individual probabilities also becomes maximum and the bias is given by 0.853.
In the next part, we provide the QISKIT codes for implementing the quantum version of SIMON round function. We first design the classical linear approximation, where we obtain the bias to be 0.75 and then we provide the modified version, proposed by us, where the bias obtained is given by 0.854. The bias observed from QISKIT simulation is equivalent with the theoretical bias shown above. The notations we use here are consistent with the main manuscript. % matplotlib inline from qiskit import * from qiskit .tools. visualization import plot histogram , plot bloch multivector import qiskit . quantum info as qi from qiskit . quantum info . states import partial trace import numpy as np # Quantum l i n e a r approximation q = QuantumRegister (4, 'q') r = QuantumRegister (1, 'r') k = QuantumRegister (1, 'k') qc= QuantumCircuit (q,r,k) # I n i t i a l i z a t i o n  .data) probs = rho sub . probabilities () print(probs) qc.draw( output ='mpl ') The above code outputs the respective probabilities as [0.75, 0.25] and the corresponding quantum circuit is presented in Figure 5.
In the modified version of linear approximation ( Figure  6.), the QISKIT code remains same as above except the 'Update function' part which can be designed as follows. And finally we obtain the corresponding probabilities to be [0.85355339, 0.14644661].
Next we give a brief introduction to the Piling-up lemma. For a better understanding readers may refer to the book Cryptography: Theory and Practice by Douglas R. Stinson.

Consider
k independent random variables, X 1 , X 2 , . . . , X k , taking on values from the set {0, 1}. Suppose, Pr (X i = 0) = p i and Pr (X i = 0) = 1 − p i denote the individual probability distribution for X i and i = p i − 1/2 denotes the corresponding bias, where 0 ≤ p i ≤ 1 for all i = 1, 2, . . . , k. Then, the following result, which gives a formulation for the bias of the random variable X i1 ⊕ X i2 . . . ⊕ X i k is known as the Piling-up lemma.
Lemma 1 (Piling-up lemma). If i1i2...i k denotes the bias of the random variable X i1 ⊕ X i2 . . . ⊕ X i k . Then For the proof of this lemma, readers are requested to refer to the book, mentioned above.