# Linear Cryptanalysis through the Lens of Clauser-Horne-Shimony-Holt Game

Arpita Maitra1, Ravi Anand2, Suman Dutta3 1TCG Centre for Research and
Education in Science and Technology,
Kolkata-700091, West Bengal, India, 2R C Bose Centre for Cryptology and
Security, Indian Statistical Institute, 203 B.T. Road, Kolkata 700108, West
Bengal, India, 3 Applied Statistic Unit, Indian Statistical Institute, 203
B.T. Road, Kolkata-700108, West Bengal, India<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

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 game can be exploited to
improve the bias of some ciphers and hence can be used in cryptanalysis. In
the present initiative, we showed the application of the game in linear
cryptanalysis on a lightweight cipher named SIMON. This observation opens a
new direction of research in quantum cryptography.

##  I Introduction

Bell inequality bell  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
chsh  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\wedge y=a\oplus b$.

In classical domain where there is no existence of entanglement, the best
strategy to win the game would be as follows.

  1. 1.

Alice and Bob both output $0$ irrespective of their inputs.

  2. 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 Mayer ; acin06a ;
acin06b ; scarani06 ; VV ; lim ; giustina . If the shared states are maximally
entangled, then from the monogamy relation of entanglement tomamichel ; ruv13
; terhal , 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+\epsilon$, then $\epsilon$ 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 simon . 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$.

Till date, Quantum Cryptanalysis on Symmetric Ciphers exploits Grover’s search
algorithm grover , Simon period finding algorithm Simon1  and the combination
of both. Block ciphers like AES aesg ; aes1 ; aes2 ; aes3 , Even-Mansour
construction fx  and McEliece system eliece  have been studied subsequently.
It is also proven that classically secure ciphers can be broken with quantum
algorithms 3roun ; kaplan ; kaplan1 ; demeric ; fx . Quantum algorithm can be
used to speed up classical attacks kaplan2 ; hs ; tho  too.

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 stinson . 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 stinson  lightweight block
ciphers with 10 different block sizes and key sizes (Table 1).

Block Size $(2n)$ | Key Size $(k=mn)$ | word size $(n)$ | keywords $(m)$ | Rounds $(T)$
---|---|---|---|---
32 | 64 | 16 | 4 | 32
48 | 72,96 | 24 | 3,4 | 36,36
64 | 96,128 | 32 | 3,4 | 42,44
96 | 96, 144 | 48 | 2,3 | 52,54
128 | 128,192,256 | 64 | 2,3,4 | 68,69,72

Table 1: SIMON parameters

The round function used in the Feistel structure of SIMON block ciphers
consists of circular shift, bitwise AND and bitwise XOR operations. The state
update function is defined as,

$\displaystyle F(x,y)=(y\oplus S^{1}(x)S^{8}(x)\oplus S^{2}(x)\oplus k,x)$ (1)

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
simon  for detailed description of the lightweight ciphers, SIMON and SPECK.

Figure 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}),\cdots,(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.

$\displaystyle R_{i+2}(j)$ $\displaystyle=$ $\displaystyle L_{i+1}(j)$
$\displaystyle=$ $\displaystyle R_{i}(j)\oplus
K_{i}(j)\oplus(L_{i}(j+1)\&L_{i}(j+8))\oplus L_{i}(j+2),$

where, $0\leq i\leq(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)\oplus L_{i+1}(j)$. That is we are establishing a
linear relationship between the $j$th bit of $i$th round and the $j$th 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.

$\displaystyle L_{i}(j)\oplus R_{i}(j)\oplus
K_{i}(j)\oplus(L_{i}((j+1))\&L_{i}((j+8)))$ $\displaystyle\oplus L_{i}(j+2))$

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.

$\displaystyle\Pr(L_{i}(j)\oplus L_{i+1}(j)=0|R_{i}(j)=K_{i}(j))=3/4$
$\displaystyle\Pr(L_{i}(j)\oplus L_{i+1}(j)=1|R_{i}(j)=K_{i}(j))=1/4$

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. 1.

For a given plaintext-ciphertext pairs for two round SIMON , check if
$L_{i}(j)=L_{i+1}(j+2)$. Note that $L_{i+1}(j+2)=R_{i+2}(j+2)$.

  2. 2.

Calculate $\Pr(L_{i}(j)\oplus L_{i+1}(j)=0)$ and $\Pr(L_{i}(j)\oplus
L_{i+1}(j)=1)$.

  3. 3.

Iff $\Pr(L_{i}(j)\oplus L_{i+1}(j)=0)=3/4$ or $\Pr(L_{i}(j)\oplus
L_{i+1}(j)=1)=1/4$, conclude $K_{i}(j)=R_{i}(j)$.

The variants of such attack has been studied in somitra ; Abed ; Alkhzaimi .
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 function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. Here, the function
$f:\\{0,1\\}^{4}\rightarrow\\{0,1\\}$ and $f=(x\wedge y)\oplus(a\oplus b)$.
The corresponding circuit is given below.

Figure 2: Boolean version of classical CHSH game

In the circuit, $q0_{0}=x$, $q0_{1}=y$, $q0_{3}=a$ and $q0_{4}=b$. Qubit
$q0_{2}$ stores the functional value $f$.

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}=\begin{pmatrix}\cos{\theta/2}&-\sin{\theta/2}\\\
\sin{\theta/2}&\cos{\theta/2}\end{pmatrix}$. The corresponding circuit is
given in Fig 3.

Figure 3: Boolean version of quantum CHSH game

According to the quantum strategy, Alice and Bob share maximally entangle
state prior to the game. Applying Hadamard gate on $q0_{3}$ followed by CNOT
on both $q0_{3}$ and $q0_{4}$, where $q0_{3}$ is the controlled bit, we
generate the maximally entangle state
$\frac{1}{\sqrt{2}}(\left|00\right\rangle+\left|11\right\rangle)$ between
Alice and Bob. Controlled-Hadamard serves Alices’s strategy, i.e., if $x=0$,
Alice will measure her sub-system in
$\\{\left|0\right\rangle,\left|1\right\rangle\\}$ basis (no Hadamard applied
), else she will measure it in
$\\{\left|+\right\rangle,\left|-\right\rangle\\}$ basis (Hadamard applied),
where
$\left|+\right\rangle=\frac{1}{\sqrt{2}}(\left|0\right\rangle+\left|1\right\rangle)$
and
$\left|-\right\rangle=\frac{1}{\sqrt{2}}(\left|0\right\rangle-\left|1\right\rangle)$.
Similarly, $CU_{3}$ serves Bob’s strategy, i.e., if $y=0$, Bob will measure
his sub-system in $\\{\left|\pi/8\right\rangle,\left|-\pi/8\right\rangle\\}$
basis (first $CU_{3}$ from left) and else in
$\\{\left|3\pi/8\right\rangle,\left|-3\pi/8\right\rangle\\}$ basis (second
$CU_{3}$ from left), where
$\left|\pi/8\right\rangle=\cos(\pi/8)\left|0\right\rangle+\sin(\pi/8)\left|1\right\rangle$,
$\left|-\pi/8\right\rangle=-\sin(\pi/8)\left|0\right\rangle+\cos(\pi/8)\left|1\right\rangle$,
and
$\left|3\pi/8\right\rangle=\cos(3\pi/8)\left|0\right\rangle+\sin(3\pi/8)\left|1\right\rangle$,
$\left|-3\pi/8\right\rangle=-\sin(3\pi/8)\left|0\right\rangle+\cos(3\pi/8)\left|1\right\rangle$.
Note that $\pi/4=0.785$. That is why we set $\theta$ 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 SIMON , 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 qinp .

  1. 1.

‘AND’ is replaced by Toffoli

  2. 2.

‘XOR’ is replaced by CNOT

Thus the quantum version of SIMON round function will be as follows.

$\displaystyle F(x,y)$ $\displaystyle=$ $\displaystyle
CNOT((CNOT(K_{i}(j),R_{i}(j)),$ $\displaystyle CNOT((Toffoli(L_{i}(j+1),$
$\displaystyle L_{i}(j+8),R_{i}(j)),L_{i}(j+2))))$

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.

Figure 4: Quantum version of SIMON round update function

Here, $l_{0}$, $l_{1}$ and $l_{2}$ represent $L_{i}(j+2)$, $L_{i}(j+1)$ 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.

$\displaystyle\Pr(L_{i}(j)\oplus L_{i+1}(j)=0|R_{i}(j)=K_{i}(j))=3/4$
$\displaystyle\Pr(L_{i}(j)\oplus L_{i+1}(j)=1|R_{i}(j)=K_{i}(j))=1/4$

Figure 5: Quantum version of linear approximation

In this circuit, $q_{0}$, $q_{1}$, $q_{2}$ and $q_{3}$ represent $L_{i}(j)$,
$L_{i}(j+1)$, $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)\oplus
L_{i+1}(j)$.

We modify the circuit with Boolean CHSH game and observe that
$\Pr(L_{i}(j)\oplus L_{i+1}(j)=0|R_{i}(j)=K_{i}(j))=0.85$ and
$\Pr(L_{i}(j)\oplus 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)$.

Figure 6: Modified version of linear approximation

We have implemented all the circuits in IBMQ interface. For the experiments,
we use IBMQ simulator. The codes for the linear approximation and its modified
version are also provided in VI.

##  V Discussions and Conclusion

In the present initiative, we have shown how to improve the bias of a
classical lightweight cipher called SIMON 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 grover , Simon period
finding algorithm Simon1  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.

## References

  * (1) Bell, J.S., On the einstein podolsky rosen paradox. Physics Physique Fizika, 1(3), p.195, 1964.
  * (2) Clauser, J.F., Horne, M.A., Shimony, A. and Holt, R.A., Proposed experiment to test local hidden-variable theories. Physical review letters, 23(15), p.880, 1969.
  * (3) Mayers, D. and Yao, A., November. Quantum cryptography with imperfect apparatus. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280) (pp. 503-509). IEEE, 1998.
  * (4) Acín, A., Gisin, N. and Masanes, L., From Bell?s theorem to secure quantum key distribution. Physical review letters, 97(12), p.120405, 2006.
  * (5) Acín, A., Massar, S. and Pironio, S., Efficient quantum key distribution secure against no-signalling eavesdroppers. New Journal of Physics, 8(8), p.126, 2006.
  * (6) Scarani, V., Gisin, N., Brunner, N., Masanes, L., Pino, S. and Acín, A., Secrecy extraction from no-signaling correlations. Physical Review A, 74(4), p.042339, 2006.
  * (7) Vazirani, U. and Vidick, T., Fully device independent quantum key distribution. Communications of the ACM, 62(4), pp.133-133, 2019.
  * (8) Lim, C.C.W., Portmann, C., Tomamichel, M., Renner, R. and Gisin, N., Device-independent quantum key distribution with local Bell test. Physical Review X, 3(3), p.031006, 2013.
  * (9) Giustina, M., Mech, A., Ramelow, S., Wittmann, B., Kofler, J., Beyer, J., Lita, A., Calkins, B., Gerrits, T., Nam, S.W. and Ursin, R., Bell violation using entangled photons without the fair-sampling assumption. Nature, 497(7448), pp.227-230, 2013.
  * (10) Tomamichel, M., Fehr, S., Kaniewski, J. and Wehner, S., One-sided device-independent QKD and position-based cryptography from monogamy games. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 609-625). Springer, Berlin, Heidelberg, 2013,
  * (11) Reichardt, B., Unger, F., and Vazirani, U., A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games. ITCS ’13, 2013.
  * (12) Terhal, B.M., Is entanglement monogamous?. IBM Journal of Research and Development, 48(1), pp.71-78, 2004.
  * (13) Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B. and Wingers, L., The SIMON and SPECK lightweight block ciphers. In Proceedings of the 52nd Annual Design Automation Conference (pp. 1-6), 2015.
  * (14) Grover, L.K., A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219), 1996.
  * (15) Simon, D.R., On the power of quantum computation. SIAM journal on computing, 26(5), pp.1474-1483, 1997.
  * (16) Grassl, M., Langenberg, B., Roetteler, M. and Steinwandt, R., February. Applying Grover?s algorithm to AES: quantum resource estimates. In Post-Quantum Cryptography (pp. 29-43). Springer, Cham, 2016.
  * (17) Jaques, S., Naehrig, M., Roetteler, M. and Virdia, F., Implementing Grover oracles for quantum key search on AES and LowMC. Advances in Cryptology-EUROCRYPT 2020, 12106, p.280, 2020.
  * (18) Langenberg, B., Pham, H. and Steinwandt, R., Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Transactions on Quantum Engineering, 1, pp.1-12, 2020.
  * (19) Bonnetain, X., Naya-Plasencia, M. and Schrottenloher, A., Quantum security analysis of AES. IACR Transactions on Symmetric Cryptology, 2019(2), pp.55-93, 2019.
  * (20) Leander, G. and May, A., Grover meets Simon–quantumly attacking the FX-construction. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 161-178). Springer, Cham, 2017.
  * (21) Bernstein, D.J., Grover vs. Mceliece. In International Workshop on Post-Quantum Cryptography (pp. 73-80). Springer, Berlin, Heidelberg, 2010, May.
  * (22) Kuwakado, H. and Morii, M., Security on the quantum-type Even-Mansour cipher. In 2012 International Symposium on Information Theory and its Applications (pp. 312-316). IEEE, 2012, October.
  * (23) Kaplan, M., Quantum attacks against iterated block ciphers. arXiv preprint arXiv:1410.1434, 2014.
  * (24) Kaplan, M., Leurent, G., Leverrier, A. and Naya-Plasencia, M., Breaking symmetric cryptosystems using quantum period finding. In Annual international cryptology conference (pp. 207-237). Springer, Berlin, Heidelberg, 2016.
  * (25) Hosoyamada, A. and Sasaki, Y., Quantum demiric-selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions. In International Conference on Security and Cryptography for Networks (pp. 386-403). Springer, Cham, 2018.
  * (26) Hosoyamada, A. and Sasaki, Y., Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In Cryptographers? Track at the RSA Conference (pp. 198-218). Springer, Cham, 2018.
  * (27) Leurent, G., Kaplan, M., Leverrier, A. and Naya-Plasencia, M., Quantum differential and linear cryptanalysis. In FSE 2017-Fast Software Encryption, 2017.
  * (28) Santoli, T. and Schaffner, C., Using Simon’s Algorithm to Attack Symmetric-Key Cryptographic Primitives. Quantum Information and Computation, 17(1&2), pp.65-78, 2017.
  * (29) Stinson, D.R., 2005, Cryptography: Theory and Practice, Third Edition, Chapman & Hall/CRC.
  * (30) Abed, F., List, E., Lucks, S. and Wenzel, J., Differential and linear cryptanalysis of reduced-round SIMON. Cryptology ePrint Archive, Report 2013/526, 2013.
  * (31) Alizadeh, J., Bagheri, N., Gauravaram, P., Kumar, A. and Sanadhya, S.K., Linear Cryptanalysis of Round Reduced SIMON. IACR Cryptol. ePrint Arch., 2013, p.663, 2013.
  * (32) AlKhzaimi, H. and Lauridsen, M.M., 2013. Cryptanalysis of the SIMON Family of Block Ciphers. IACR Cryptol. ePrint Arch., 2013 p.543, 2013.
  * (33) Alizadeh, J., Alkhzaimi, H.A., Aref, M.R., Bagheri, N., Gauravaram, P., Kumar, A., Lauridsen, M.M. and Sanadhya, S.K., Cryptanalysis of SIMON variants with connections. In International Workshop on Radio Frequency Identification: Security and Privacy Issues (pp. 90-107). Springer, Cham, 2015.
  * (34) Anand, R., Maitra, A. and Mukhopadhyay, S., Grover on SIMON. Quantum Information Processing, 19(9), pp.1-17, 2020.
  * (35) Supplementary Material; all the calculations and the codes for IBMQ implementation are available here.
  * (36) Matsui, M., Linear cryptanalysis method for DES cipher. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 386-397). Springer, Berlin, Heidelberg, 1993.
  * (37) Selçuk, A.A., On probability of success in linear and differential cryptanalysis. Journal of Cryptology, 21(1), pp.131-147, 2008.

##  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
$\left|r_{0}k_{0}\right\rangle$ 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, $\left|r_{0}k_{0}\right\rangle$ is in
a maximally entangled state,
$\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)$.
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
$\left|r_{0}\right\rangle$. 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.

$\displaystyle\left|r_{0}k_{0}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)\xrightarrow{I\otimes
U\left(-\theta,0,0\right)}$
$\displaystyle\frac{1}{\sqrt{2}}\left[\left|0\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle-\sin{\frac{\theta}{2}}\left|1\right\rangle\right)+\left|1\right\rangle\left(\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\cos{\frac{\theta}{2}}\left|00\right\rangle-\sin{\frac{\theta}{2}}\left|01\right\rangle+\sin{\frac{\theta}{2}}\left|10\right\rangle+\cos{\frac{\theta}{2}}\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{CX_{k_{0},r_{0}}}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\cos{\frac{\theta}{2}}\left|00\right\rangle-\sin{\frac{\theta}{2}}\left|11\right\rangle+\sin{\frac{\theta}{2}}\left|10\right\rangle+\cos{\frac{\theta}{2}}\left|01\right\rangle\right).$

Therefore the probability is given by,
$\displaystyle\Pr\left(r_{0}=0\right)=\frac{1}{2}\left(\cos^{2}{\frac{\theta}{2}}+\cos^{2}{\frac{\theta}{2}}\right)=\cos^{2}{\frac{\theta}{2}}.$
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 $\left|r_{0}k_{0}\right\rangle$ evolves as follows.

$\displaystyle\left|r_{0}k_{0}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)\xrightarrow{I\otimes
U\left(\theta,0,0\right)}$
$\displaystyle\frac{1}{\sqrt{2}}\left[\left|0\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle+\sin{\frac{\theta}{2}}\left|1\right\rangle\right)+\left|1\right\rangle\left(-\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\cos{\frac{\theta}{2}}\left|00\right\rangle+\sin{\frac{\theta}{2}}\left|01\right\rangle-\sin{\frac{\theta}{2}}\left|10\right\rangle+\cos{\frac{\theta}{2}}\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{CX_{k_{0},r_{0}}}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\cos{\frac{\theta}{2}}\left|10\right\rangle+\sin{\frac{\theta}{2}}\left|01\right\rangle-\sin{\frac{\theta}{2}}\left|00\right\rangle+\cos{\frac{\theta}{2}}\left|11\right\rangle\right).$

Thus the probability is given by
$\displaystyle\Pr\left(r_{0}=0\right)=\frac{1}{2}\left(\cos^{2}{\frac{\theta}{2}}+\cos^{2}{\frac{\theta}{2}}\right)=\cos^{2}{\frac{\theta}{2}}.$
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.

$\displaystyle\left|r_{0}k_{0}\right\rangle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{H\otimes I}$
$\displaystyle\frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle-\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{I\otimes U\left(-\theta,0,0\right)}$
$\displaystyle\frac{1}{2}\left[\left|0\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle-\sin{\frac{\theta}{2}}\left|1\right\rangle\right)+\left|0\right\rangle\left(\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right.$
$\displaystyle\hskip
142.26378pt\left.+\left|1\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle-\sin{\frac{\theta}{2}}\left|1\right\rangle\right)-\left|1\right\rangle\left(\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left[\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|00\right\rangle+\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|01\right\rangle+\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|10\right\rangle-\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|11\right\rangle\right]$
$\displaystyle\xrightarrow{CX_{k_{0},r_{0}}}$
$\displaystyle\frac{1}{2}\left[\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|00\right\rangle+\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|11\right\rangle+\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|10\right\rangle-\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|01\right\rangle\right]$

Therefore,
$\displaystyle\Pr\left(r_{0}=0\right)=\frac{1}{4}\left[\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)^{2}+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)^{2}\right]=\frac{1}{2}\left(1+\sin{\theta}\right).$
Case IV. $q_{1}=1,\,q_{3}=1$:
Since both $q_{1}=q_{3}=1$, the $CH$ gate controlled by $q_{1}$ and the $CCX$
gate controlled by $q_{1},q_{3}$, both will be activated and therefore the
evolution of the starting state will be as follows.

$\displaystyle\left|r_{0}k_{0}\right\rangle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{H\otimes I}$
$\displaystyle\frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle-\left|11\right\rangle\right)$
$\displaystyle\xrightarrow{I\otimes U\left(\theta,0,0\right)}$
$\displaystyle\frac{1}{2}\left[\left|0\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle+\sin{\frac{\theta}{2}}\left|1\right\rangle\right)+\left|0\right\rangle\left(-\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right.+$
$\displaystyle\hskip
142.26378pt\left.\left|1\right\rangle\left(\cos{\frac{\theta}{2}}\left|0\right\rangle+\sin{\frac{\theta}{2}}\left|1\right\rangle\right)-\left|1\right\rangle\left(-\sin{\frac{\theta}{2}}\left|0\right\rangle+\cos{\frac{\theta}{2}}\left|1\right\rangle\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left[\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|00\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|01\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|10\right\rangle-\left(\sin{\frac{\theta}{2}}-\cos{\frac{\theta}{2}}\right)\left|11\right\rangle\right]$
$\displaystyle\xrightarrow[q_{1}=q_{3}=1]{CCX_{q_{1},q_{3},r_{0}}}$
$\displaystyle\frac{1}{2}\left[\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|10\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|11\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|00\right\rangle-\left(\sin{\frac{\theta}{2}}-\cos{\frac{\theta}{2}}\right)\left|01\right\rangle\right]$
$\displaystyle\xrightarrow{CX_{k_{0},r_{0}}}$
$\displaystyle\frac{1}{2}\left[\left(\cos{\frac{\theta}{2}}-\sin{\frac{\theta}{2}}\right)\left|10\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|01\right\rangle+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)\left|00\right\rangle-\left(\sin{\frac{\theta}{2}}-\cos{\frac{\theta}{2}}\right)\left|11\right\rangle\right]$

Therefore, the probability is given by

$\Pr\left(r_{0}=0\right)=\frac{1}{4}\left[\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)^{2}+\left(\cos{\frac{\theta}{2}}+\sin{\frac{\theta}{2}}\right)^{2}\right]=\frac{1}{2}\left(1+\sin{\theta}\right).$

To maximize the probabilities, we can form a function
$h(\theta)=\cos^{2}{\frac{\theta}{2}}+\frac{1}{2}\left(1+\sin{\theta}\right)$
and using the derivative test we can show that $h$ becomes maximum for
$\theta=\frac{\pi}{4}$. Therefore, when $\theta=\frac{\pi}{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.

⬇

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 linear approximation

q = QuantumRegister(4, ’q’)

r = QuantumRegister(1, ’r’)

k = QuantumRegister(1, ’k’)

qc=QuantumCircuit(q,r,k)

# Initialization

qc.h(q[0])

qc.h(q[1])

qc.cx(q[0],q[2])

qc.h(q[3])

qc.h(r)

qc.cx(r,k)

qc.barrier()

# Update function

qc.ccx(q[1],q[3],r)

qc.cx(q[2],r)

qc.cx(k,r)

qc.barrier()

qc.cx(q[0],r)

# Calculating the Probabilities

simulator=Aer.get_backend

(’statevector_simulator’)

result=execute

(qc,backend=simulator).result()

Statevector=result.get_statevector()

rho = np.outer

(Statevector, np.conj(Statevector))

trace_system=[0,1,2,3,5]

rho_sub=qi.DensityMatrix

(partial_trace(rho, trace_system)

.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.

⬇

qc.ch(q[1],r)

qc.x(q[3])

qc.cu3(-np.pi/4,0,0,q[3],k)

qc.x(q[3])

qc.cu3(np.pi/4,0,0,q[3],k)

qc.ccx(q[1],q[3],r)

qc.cx(q[2],r)

qc.cx(k,r)

qc.barrier()

qc.cx(q[0],r)

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},\ldots,X_{k}$, taking
on values from the set $\\{0,1\\}$. Suppose, $\Pr\left(X_{i}=0\right)=p_{i}$
and $\Pr\left(X_{i}=0\right)=1-p_{i}$ denote the individual probability
distribution for $X_{i}$ and $\epsilon_{i}=p_{i}-1/2$ denotes the
corresponding bias, where $0\leq p_{i}\leq 1$ for all $i=1,2,\ldots,k$. Then,
the following result, which gives a formulation for the bias of the random
variable $X_{i_{1}}\oplus X_{i_{2}}\ldots\oplus X_{i_{k}}$ is known as the
Piling-up lemma.

######  Lemma 1 (Piling-up lemma).

If $\epsilon_{{i_{1}}{i_{2}}\ldots{i_{k}}}$ denotes the bias of the random
variable $X_{i_{1}}\oplus X_{i_{2}}\ldots\oplus X_{i_{k}}$. Then

$\epsilon_{{i_{1}}{i_{2}}\ldots{i_{k}}}=2^{k-1}{\displaystyle\prod_{j=1}^{k}\epsilon_{i_{j}}}$

For the proof of this lemma, readers are requested to refer to the book,
mentioned above.