Designs, Codes and Cryptography (2020) 88:1103–1126

https://doi.org/10.1007/s10623-020-00730-1

Generalized related-key rectangle attacks on block ciphers

with linear key schedule: applications to SKINNY and GIFT

Boxin Zhao1 · Xiaoyang Dong2 · Willi Meier3 · Keting Jia4 · Gaoli Wang5

Received: 24 June 2019 / Revised: 1 February 2020 / Accepted: 1 February 2020 /

Published online: 13 February 2020
© Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract
This paper gives a new generalized key-recovery model of related-key rectangle attacks
on block ciphers with linear key schedules. The model is quite optimized and applicable to
various block ciphers with linear key schedule. As a proof of work, we apply the new model to
two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many
candidates of the Lightweight Cryptography (LWC) standardization project by NIST. For
SKINNY, we reduce the complexity of the best previous 27-round related-tweakey rectangle
attack on SKINNY-128-384 from 2331 to 2294 . In addition, the first 28-round related-tweakey
rectangle attack on SKINNY-128-384 is given, which gains one more round than before. For
the candidate LWC SKINNY AEAD M1, we conduct a 24-round related-tweakey rectangle
attack with a time complexity of 2123 and a data complexity of 2123 chosen plaintexts. For
the case of GIFT-64, we give the first 24-round related-key rectangle attack with a time
complexity 291.58 , while the best previous attack on GIFT-64 only reaches 23 rounds at most.

Keywords Key recovery · Rectangle attack · SKINNY · SKINNY AEAD · GIFT ·

Related-key

Mathematics Subject Classification 94A60

1 Introduction

The boomerang attack [47], proposed by Wagner, is a variant of differential cryptanalysis

[16]. It combines two short differentials with high probabilities to get a long distinguisher.
Refinements on the boomerang attack have been published, namely, the amplified boomerang
attack [31], and thereafter the rectangle attack [15]. At ASIACRYPT 2009, Biryukov et al.
[17] introduced the concept of boomerang switch to further increase the probability of the
boomerang distinguisher. Another improvement was made by Dunkelman et al. [24], which
is called sandwich attack. At Eurocrypt 2018, Cid et al. [22] proposed a novel technique

Communicated by T. Iwata.

B Xiaoyang Dong
xiaoyangdong@tsinghua.edu.cn
Extended author information available on the last page of the article

123
1104 B. Zhao et al.

named Boomerang connectivity table (BCT), which solved the problem of incompatibility
in boomerang distinguishers noted by Murphy [36]. Later, the BCT effect in multiple rounds
of boomerang switch was studied by Wang and Peyrin [48] and Song et al. [43].
Boomerang and rectangle attacks in a related-key setting [14] are quite powerful, which
break various important block ciphers, including the key-recovery attacks on KASUMI [12,
24] and AES [17]. Recently, many (tweakable) block ciphers adopt linear key schedules,
such as MANTIS [10], LED [25], MIDORI [4], GIFT [7], Simon [8], CRAFT [11], and the
popular TWEAKEY [30] framework based ciphers, including SKINNY [10], Deoxys-BC
[29], QARMA [3], and Joltik-BC [30]. Notably, in the CAESAR competition [45] for secure
authenticated encryption, Deoxys-II [29], which is based on Deoxys-BC, has been selected
as one of the winners.
With the significant spread of the Internet of Things (IoT) in recent years, lightweight
cryptography is urgently needed in numerous devices with little computing power. Therefore,
NIST launched the Lightweight Cryptography (LWC) standardization project [37] to select
lightweight authenticated encryption with associated data (AEAD) and hashing function. In
2019, about 56 candidates were included in the Round 1 of the project [37]. Among the
candidates, many are based on block ciphers with linear key schedule to become lightweight,
such as SKINNY-AEAD and SKINNY-Hash [9], SUNDAE-GIFT [5], TGIF [26], GIFT-
COFB [6], Remus [27], Romulus [28] and Saturnin [19], etc. The study of boomerang and
rectangle attacks on block ciphers with linear key schedule becomes relevant. At ToSC 2017,
Liu et al. [34] introduced a generalized key-recovery model for the related-key rectangle
attack on block ciphers with linear key schedule. Then, they applied their model to the
attacks on reduced-round SKINNY [10].

1.1 Our contributions

In this paper, we find that Liu et al.’s model [34] can be significantly improved in the phase
of generating quartets. Therefore, we construct a new key-recovery model for the related-key
rectangle attacks on block ciphers with linear key schedules. In order to show the effectiveness
of model, we apply it to the two important block ciphers, i.e. SKINNY [10] and GIFT [7]. Note
that, in the LWC standardization project by NIST [37], many candidates such as SKINNY-
AEAD and SKINNY-Hash [9], SUNDAE-GIFT [5], TGIF [26], GIFT-COFB [6], Remus
[27] and Romulus [28] are based on SKINNY or GIFT. To study SKINNY and GIFT is very
important for the security evaluation of these candidates.
For the sake of a clear comparison between our model and the previous one by Liu et al.
[34], we utilize the same 23-round boomerang distinguishers of SKINNY-128-384 [10] as
proposed by Liu et al. [34] and the same 19-round boomerang distinguishers on GIFT-64 [7]
as proposed by Chen et al. [20] to launch our key-recovery attacks.

– For SKINNY-128-384, we improve the time complexity of the best previous 27-round
attack by a factor of 237 . Moreover, we present the first key-recovery attack on 28-round
SKINNY-128-384 with a time complexity of 2315.25 and 2122 chosen plaintexts.
– In addition, we give a related-tweakey rectangle attack on 24-round SKINNY-128-384
with time and data complexities of 2123 , which is successfully applied to the SKINNY
AEAD member M1 [9] (one of the 56 candidates in the NIST Lightweight Cryptography
selection process). To our knowledge, this is the first attack on round-reduced SKINNY
AEAD M1.

123
Generalized related-key rectangle attacks 1105

Table 1 Summary of analysis results of SKINNY-128-384, GIFT-64 and SKINNY AEAD M1

Rounds Approach Setting Time Data Memory Size set up Ref.

SKINNY-128-384
22 IDC SK 2373.48 292.22 2147.22 k = 384 [46]
22 MITM SK 2382.46 296 2330.99 k = 384 [42]
27 Rectangle RK 2351 2127 2160 k = 384 [34]
Rectangle RK 2331 2123 2155 k = 384 [34]
Rectangle RK 2294 2122 2122.32 k = 384 Sect. 4.4
28 Rectangle RK 2315.25 2122 2122.32 t < 68, k > 316 Sect. 4.5
GIFT-64
14 IC SK 297 263 – k = 128 [7]
15 MITM SK 2120 264 – k = 128 [7]
15 MITM SK 2112 – – k = 128 [40]
19 DC SK 2112 263 – k = 128 [49]
20 DC SK 2112.68 262 2112 k = 128 [21]
21 DC SK 2107.61 264 296 k = 128 [21]
23 Boomerang RK 2126.6 263.3 – k = 128 [33]
23 Rectangle RK 2107 260 260 k = 128 [20]
24 Rectangle RK 291.58 260 260.32 k = 128 Sect. 5.3

SKINNY AEAD M1 Rounds Key size Time Data Memory Approach Ref.

SKINNY M1 24 128 2123 2123 2121 Rectangle Sect. 4.7

(I)DC (impossible) differential cryptanalysis, IC stands for integral cryptanalysis, MITM stands for meet-in-
the-middle attack, SK stands for single-key, RK stands for related-key

– For GIFT-64, we conduct a 24-round attack,1 which gains one more round than the best
previous attacks, and the time complexity is 291.58 .
The cryptanalysis results on SKINNY-128-384, SKINNY AEAD M1 scheme and GIFT-
64 are listed in Table 1.

2 The related-key rectangle attack

The boomerang attack, proposed by Wagner [47], is an extension of the differential attack
using adaptive chosen plaintexts and ciphertexts to analyze block ciphers. It attempts to
generate a quartet structure at an intermediate value halfway through the cipher. When the
adversaries can not find a long differential characteristic with probability higher than for a
random permutation, they can decompose the cipher in two shorter ciphers as E = E 1 ◦E 0 and
connect two short differential trails to conduct the attack. For E 0 , the differential characteristic
is α → β with probability p, and the differential characteristic for E 1 is δ → γ with
probability q.

1 Note that the authors of GIFT [7] do not give any security claim in the related-key setting, but as shown by
Liu et al. [49] and Chen et al. [20], it is still theoretically meaningful to understand its security margin in this
setting.

123
1106 B. Zhao et al.

Fig. 1 Related-key rectangle

distinguisher framework

Then a right quartet can be obtained by a boomerang distinguisher which is the connection
of the two shorter differential characteristics as in the following steps:
1. Randomly choose a plaintext pair (P1 , P2 ) with difference P1 ⊕ P2 = α, and make
queries over E to get the ciphertext pair (C1 , C2 ), where C1 = E(P1 ), C2 = E(P2 ).
2. Generate another ciphertext pair (C3 , C4 ) by C3 = C1 ⊕ δ and C4 = C2 ⊕ δ, then make
queries to the decryption oracle to obtain their plaintexts (P3 , P4 ) with two adaptive
chosen-ciphertext queries.
3. Check whether the difference of (P3 , P4 ) equals to α or not.
The adversary can get a right quartet with a probability of p 2 q 2 , thus the probability of the
distinguisher has to satisfy pq > 2−n/2 .
When the values of α and δ are fixed and don’t restrain the values of β and γ as long
as β  = γ , the boomerang attack is developed into the amplified boomerang attack [31] or
rectangle attack [15], which are chosen-plaintext attacks. The probability of getting a right
quartet is 2−n p̂ 2 q̂ 2 , where
 
p̂ = Pr 2 (α → βi ) and q̂ = Pr 2 (γ j → δ).
i j

If the four plaintexts in a quartet are encrypted under different master keys K 1 , K 2 , K 3
and K 4 respectively, the attack is developed into a related-key rectangle attack [14], where
C1 = E K 1 (P1 ), C2 = E K 2 (P2 ), C3 = E K 3 (P3 ), and C4 = E K 4 (P4 ). Assume one has a
related-key differential α → β over E 0 under a key difference ΔK with a probability p and
another related-key differential γ → δ over E 1 under a key difference ∇ K with probability
q, and K 1 ⊕ K 2 = ΔK , K 3 ⊕ K 4 = ΔK , K 1 ⊕ K 3 = ∇ K . Then a right quartet can be
obtained as follows:
1. Randomly choose two plaintext pairs (P1 , P2 ) and (P3 , P4 ) with difference P1 ⊕ P2 =
α and P3 ⊕ P4 = α, and encrypt them with E to get the ciphertext pairs (C1 , C2 )
and (C3 , C4 ) under four master keys, where K 1 ⊕ K 2 = ΔK , K 3 ⊕ K 4 = ΔK and
K1 ⊕ K3 = ∇ K .
2. Check whether the differences satisfy C1 ⊕ C3 = δ and C2 ⊕ C4 = δ or not. If yes, a
right quartet is obtained, otherwise return to step 1.

123
Generalized related-key rectangle attacks 1107

Fig. 2 Related-key rectangle

attack framework

In the key recovery process, adversaries only need to recover one of the four master keys,
since the values of ΔK and ∇ K are known and the other three master keys can be computed
by the recovered key.
For clarity, the related-key rectangle framework is illustrated in Fig. 1.

3 New model of related-key rectangle attack

Under a related-key rectangle distinguisher, our key recovery algorithm is adapted from
Biham et al.’s algorithm [13] which is a single-key rectangle attack and Liu et al.’s [34]
algorithm which is a related-key rectangle attack. In the key recovery algorithm, we follow
the notations in [34].
We decompose the cipher algorithm E into three components as E = E f ◦ E  ◦ E b ,
where E  is determined by the related-key rectangle distinguisher and E b and E f are the
rounds extended backward from the start and forward from the end of the distinguisher,
respectively. Let c denote the size of a cell (the unit goes through Sbox), k denote the size of
the master key and n be the size of the state in the block cipher. After extending the rectangle
distinguisher backward for several rounds (i.e. E b ) under the related-key difference ΔK , we
denote the number of unknown bits in the difference of plaintexts as rb . Let m b be the number
of involved subkey bits that affect the plaintext difference while encrypting plaintext pairs to
the position of the known difference under E b . Similarly, when extending several rounds for
the difference of the distinguisher δ under E f by the related-key difference ∇ K , we define r f
and m f for E f . The related-key rectangle framework is illustrated in Fig. 2. The algorithm
being composed of data collection and key recovery is as follows:

123
1108 B. Zhao et al.

1. Construct structures including 2rb plaintexts, which traverse all the possible values for
the rb /c active cells while assigning suitable constants to the other cells that hold zero
or known differences.
√ If s denotes the expected number of right quartets, attackers need
to prepare y = s · 2n/2−rb / p̂q̂ different structures.
2. Query the corresponding ciphertexts for the 2rb plaintexts in each structure under the
four related keys K 1 , K 2 , K 3 and K 4 and get four plaintext-ciphertext sets L 1 , L 2 , L 3
and L 4 , where K 1 is the secret key and K 2 = K 1 ⊕ ΔK , K 3 = K 1 ⊕ ∇ K and K 4 =
K 1 ⊕ ΔK ⊕ ∇ K . Insert L 2 and L 4 into hash tables H1 and H2 indexed by the rb bits of
plaintexts.
3. Guess the 2m b possible m b bits of subkey involved in E b :
(a) Initialize a list of 2m f counters, each of which corresponds to a m f -bit subkey guess.
(b) For each set L 1 of every structure, partially encrypt plaintext P1 ∈ L 1 under E b by the
guessed subkeys of K 1 , and partially decrypt it under the subkey of K 2 = K 1 ⊕ΔK to
the plaintext P2 after xoring the known difference α, i.e. P2 = Db K 2 (E b K 1 (P1 ) ⊕ α)
where Db K 2 is the partial decryption process Db using K 2 . Then check H1 to find the
corresponding plaintext-ciphertext pair indexed by the rb bits of P2 . Proceed with a
similar process for sets L 3 and L 4 and obtain two sets as

S1 = {(P1 , C1 , P2 , C2 ) : (P1 , C1 ) ∈ L 1 , (P2 , C2 ) ∈ L 2 , E b K 1 (P1 ) ⊕ E b K 2 (P2 ) = α}

and

S2 = {(P3 , C3 , P4 , C4 ) : (P3 , C3 ) ∈ L 3 , (P4 , C4 ) ∈ L 4 , E b K 3 (P3 )⊕E b K 4 (C4 ) = α}.

(c) There are M = y · 2rb chosen plaintexts under each key, and the sizes of S1 and
S2 are all y · 2rb due to y structures. Denote δ  being the truncated form propagated
from δ under E f with probability 1. There are n − r f bits whose differences are 0 in
δ  . Insert S1 into hash table H3 indexed by the n − r f bits of C1 and n − r f bits of
C2 that are 0 in δ  . Then for each element of S2 , we check the hash table H3 to find
(P1 , C1 , P2 , C2 ) so that (C1 , C3 ) and (C2 , C4 ) collide in the n − r f bits. There will
be about M 2 · 2−2(n−r f ) quartets remaining.
(d) With the quartets obtained in step (c), we conduct the key recovery process for the
subkeys involved in E f . Instead of guessing all the m f -bit subkeys at once, we firstly
determine whether a candidate quartet is useful by guessing only a small fraction of
the unknown involved subkey bits, which is just a guess and filter procedure. We
denote the time complexity in this step as ε.
(e) Select the top 2m f −h hits in the counter to be the candidates, which delivers a h-bit
or higher advantage.
(f) Guess the remaining k − m b − m f unknown key bits exploiting the key schedule
algorithm, and exhaustively search over them to recover the correct master key. If
the guessed m b -bit keys are not right, go to step 3 with another guess.
Since the key recovery attack is a related-key attack, the data complexity is D = 4M =
4y · 2rb chosen plaintexts.
In the quartets collection and key recovery process, we need 2m b · 2M table look-ups in
step 3(b) and 2m b · M table look-ups in step 3(c) resulting in 2m b · 3M to prepare the quartets.
M 2 · 2−2(n−r f ) · ε encryptions in step 3(d) and 2k−h encryptions in step 3(f) are needed to
recover the master key. Thus the total time complexity, which is composed of data collection
and key recovery, is 4M + 2m b · M 2 · 2−2(n−r f ) · ε + 2k−h .
The memory complexity is 4M + M + 2m f = 5M + 2m f .

123
Generalized related-key rectangle attacks 1109

Success probability We use the method by Selçuk [41] to compute the success probability:
√
s S N − −1 (1 − 2−h )
Ps = ( √ ), (1)
SN + 1
where S N is the signal-to-noise ratio and S N = p̂ 2 q̂ 2 /2−n .
Compared to the related-key rectangle attack in [34], the main improvements in time
complexity are summarized as follows:
1. In the data collection program to prepare quartets, paper [34] constructs quartets first,
and then checks whether the quartet can be encrypted to the difference of the start of
the distinguisher one by one to filter all the useless quartets. However, we guess the key
bits involved in the E b and make partial encryption and decryption to construct plaintext
pairs that can be encrypted to the difference of the start of the distinguisher. Therefore,
the quartets we obtained don’t need to be filtered. It makes the time complexity be highly
reduced.
2. In the key recovery process, we don’t guess all the key bits involved in E f but utilize a
process that guess partial key bits one time and filter the useless quartets step by step. It
makes the time complexity reduce further.

4 Application to SKINNY

The SKINNY family [10] provides 64-bit and 128-bit block versions and denotes n as
the block size. Several candidates of the Lightweight Cryptography (LWC) standardization
project by NIST [37] are based on the SKINNY block cipher, such as SKINNY-AEAD and
SKINNY-Hash [9], Remus [27] and Romulus [28]. The family of lightweight block ciphers
SKINNY has three tweakey size versions SKINNY−n − t, where t = n, t = 2n and t = 3n,
and denotes the tweakey state by T K 1 when t = n, by T K 1 and T K 2 when t = 2n, and
finally by T K 1, T K 2 and T K 3 when t = 3n.
Since SKINNY was proposed, there has been a number of third-party cryptanalysis from
all over the world. Tolba et al. [46] applied impossible differential attacks to 18-, 20- and
22-round SKINNY-n-n, SKINNY-n-2n and SKINNY-n-3n, respectively, in the single-key
model at AFRICACRYPT 2017. At ToSC 2017, Liu et al. [34] searched related-tweakey
impossible differentials and related-tweakey rectangle distinguishers and applied them to
analyze up to 19-, 23- and 27-round SKINNY-n-n, SKINNY-n-2n and SKINNY-n-3n respec-
tively. In [1], Abdelkhalek et al. proposed a method to model the DDT of large Sboxes and
verified that no differential characteristic with probability higher than 2−128 for 14-round
SKINNY-128 exists. In [38], Sadeghi et al. presented zero correlation attacks on SKINNY-
64-64/128 and gave a related-tweakey impossible differential attack on SKINNY-128-256
up to 23 rounds. At ASIACRYPT 2018, Shi et al. [42] analyzed 22-round SKINNY-128-
384 by the Demirci–Selcuk meet-in-the-middle attack. At ToSC 2019, Song et al. [43]
revisited the Boomerang Connectivity Table [22] and recalculated the probabilities of some
related-tweakey boomerang distinguishers proposed in [34]. Besides, there are analyses on
SKINNY-64 in [2,39,44].

4.1 Specification of SKINNY and SKINNY AEAD

The block cipher SKINNY [10] is an SPN cipher that uses a compact Sbox, a sparse diffusion
layer and a light key schedule. SKINNY follows the TWEAKEY framework [30], thus except

123
1110 B. Zhao et al.

ART ShiftRows MixColumns

>>> 1
SC AC
>>> 2
>>> 3

Fig. 3 The SKINNY round function

for a plaintext P and a master key K it takes a tweak T as the third input, and different
ciphertexts can be obtained under the same plaintext and master key due to the different
tweaks. Inspired by the TWEAKEY framework [30], SKINNY provides a unified view for
key and tweak by tweakey.
For all versions of SKINNY, the tweak size and the key size can vary according to the
users but the key size should be at least as large as the block size. Both the intermediate state
and tweakey state are viewed as a 4 × 4 square array of cells indexed by
⎡ ⎤
0 1 2 3
⎢4 5 6 7⎥
⎢ ⎥.
⎣8 9 10 11⎦
12 13 14 15
Note that SKINNY adopts a row-wise form rather than column-wise fashion as AES [23],
as it is more hardware-friendly as pointed out in [35].
The round function One encryption round of SKINNY consists of five operations in the
following order: SubCells (SC), AddConstants (AC), AddRoundTweakey (ART),
ShiftRows (SR) and MixColumns (MC), which is illustrated in Fig. 3.
SubCells Apply a 4-bit Sbox in case of n = 64 and an 8-bit Sbox in case of n = 128 to
the 16 cells of the state. It is the non-linear operation in the round function.
AddConstants The round constants are generated by a 6-bit affine LFSR. Three round
constants are xor’ed to the first cell of the first three rows, respectively.
AddRoundTweakey Only the first two rows of the round tweakey are xor’ed to the first
two rows of the internal state. The round tweakey tki in round i is defined as:
– t = n: tki = (T K 1)i ,
– t = 2n: tki = (T K 1)i ⊕ (T K 2)i ,
– t = 3n: tki = (T K 1)i ⊕ (T K 2)i ⊕ (T K 3)i ,
where (T K 1)i , (T K 2)i and (T K 3)i are generated by the tweakey schedule algorithm that
is introduced below.
ShiftRows. Rotate the 4 cells of the j−th row right by ρ[ j] positions, where ρ =
(0, 1, 2, 3).
MixColumns. Pre-multiply the internal state by a 4×4 binary constant matrix M to update
the state. The matrix M and its inverse matrix M−1 are represented as follows:
⎡ ⎤ ⎡ ⎤
1 0 1 1 0 1 0 0
⎢1 0 0 0 ⎥ ⎢0 1 1 1 ⎥
M=⎢ ⎥ −1 ⎢
⎣0 1 1 0 ⎦ , M = ⎣ 0 1 0 1 ⎦ .
⎥

1 0 1 0 1 0 0 1
Definition of the round tweakey (subtweakey) The tweakey schedule algorithm of SKINNY
is a linear transformation. The t-bit tweakey input is firstly divided into z = t/n n-bit blocks,

123
Generalized related-key rectangle attacks 1111

Table 2 The two LFSRs used in SKINNY tweakey schedule

L F S R2 (x7 ||x6 ||x5 ||x4 ||x3 ||x2 ||x1 ||x0 ) → (x6 ||x5 ||x4 ||x3 ||x2 ||x1 ||x0 ||x7 ⊕ x5 )
L F S R3 (x7 ||x6 ||x5 ||x4 ||x3 ||x2 ||x1 ||x0 ) → (x0 ⊕ x6 ||x7 ||x6 ||x5 ||x4 ||x3 ||x2 ||x1 )

and located in T K 1 with t = n, or T K 1, T K 2 with t = 2n or T K 1, T K 2, T K 3 with

t = 3n.
First, a permutation PT is applied to the cells of all tweakey arrays as T K zi ← T K z PT [i]
for all 0 ≤ i ≤ 15 with

PT = [9, 15, 8, 13, 10, 14, 12, 11, 0, 1, 2, 3, 4, 5, 6, 7],

for z ∈ {1, 2} and z ∈ {1, 2, 3}. This is a position permutation with the value unchanged.
Then, each cell in the first two rows of T K 2 (or T K 2 and T K 3) are updated by one (or
two) LFSRs to get (T K m)i (m = 1, 2, 3). The LFSRs are listed in Table 2, we only give the
LFSRs used for the 8-bit cells.
The SKINNY AEAD modes
The SKINNY AEAD modes are proposed by Beierle et al. [9] and included in the Round 1
candidates of the NIST lightweight cryptography competition. The authenticated encryption
scheme follows the CB3 mode [32] and uses either SKINNY-128-384 or SKINNY-128-256
as its internal tweakable block cipher. Totally, there are six AEAD modes proposed and the
SKINNY AEAD M1 based on SKINNY-128-384 is their primary member. M1 is a nonce-
based AEAD and assumed to be nonce-respecting for the adversary. Here, we give a simple
description for the AEAD M1.
The tweakey size of SKINNY AEAD M1 is 384 bits, the last 256 bits of the tweakey is
just the concatenation of the 128-bit nonce N and the 128-bit key K , but the first 128 bits
are different in different blocks in a long message. They can be updated in a series of blocks
in the following way.
The first 128 bits of tweakey store eight bytes that come from a 64-bit LFSR, followed by
seven bytes of zeros and a single byte for the domain separation (d0 or d1 whether the block
is padded). The LFSR is initialized to LFSR0 = 063 ||1 and updated by upd64 that is defined
as

upd64 : x63 ||x62 || · · · ||x1 ||x0 → y63 ||y62 || · · · ||y1 ||y0

with:

yi ← xi−1 for i ∈ {63, 62, . . . , 1}\{4, 3, 1},

y4 ← x3 ⊕ x63 ,
y3 ← x2 ⊕ x63 ,
y1 ← x0 ⊕ x63 ,
y0 ← x63 .

Before the bytes of the LFSR are loaded in the tweakey input, the order of them is reversed,
i.e. rev64 (L F S R)||056 ||d0 (d0 will be replaced by d1 for the padded block), where rev64 is
defined as

123
1112 B. Zhao et al.

Fig. 4 The encryption part of

SKINNY AEAD M1 M0 M1 Mlm −1

......
0d 1d l −1d0
EN,K0 EN,K0 EN,K
m

C0 C1 Clm −1

rev64 :x7 ||x6 ||x5 ||x4 ||x3 ||x2 ||x1 ||x0 −→

x0 ||x1 ||x2 ||x3 ||x4 ||x5 ||x6 ||x7 (∀i : |xi | = 8)

In encryption for each block, the 384-bit tweakey is set to be rev64 (L F S R)||056 ||d0 ||N ||K .
In fact, as described in [9], the 64-bit LFSR plays the same role as a block counter. The
encryption part of SKINNY AEAD M1 is illustrated in Fig. 4. For more details, we refer to
[9].

4.2 Notations and definitions of SKINNY

In this section, the notations are defined as follows:

X i : state before SC and AC operation in Round i, 0 ≤ i ≤ r − 1,
Yi : state after SC and AC operation in Round i, 0 ≤ i ≤ r − 1,
Z i : state after ART and SR operation in Round i,0 ≤ i ≤ r − 1,
The details of the i-th round (0 ≤ i ≤ r − 1) are as follows:
SC ART, SR MC
X i −→ Yi −−−−−→ Z i −→ X i+1 .
AC ST K i

ΔX : difference of the state X ,

X i [ j · · · k]: jth byte, · · · , kth byte of X i , where 0 ≤ j, k ≤ 15,
Yi [ j · · · k]: jth byte, · · · , kth byte of Yi , where 0 ≤ j, k ≤ 15,
Z i [ j · · · k]: jth byte, · · · , kth byte of Z i , where 0 ≤ j, k ≤ 15.

4.3 Properties of SKINNY

Here, we introduce several properties and a lemma on SKINNY that will be used in the
related-tweakey rectangle attack.
1. The matrix used in the MixColumns operation is not an MDS matrix. Therefore, extra
values of some cells may need to be guessed except the active cells in both input and
output of the MC operation, which leads to more subtweakey bytes that need to be
guessed. We use the same example as in [34] which is illustrated in Fig. 5 to explain the
property.
When we backtrack the trail from ΔX 17 to round 14 and guarantee that only ΔX 14 [8]
is active, it is necessary to check whether the differences in ΔX 15 [2, 10, 14] lead to a

123
Generalized related-key rectangle attacks 1113

STK14 X14 Y14 Z14

SC ART MC
AC SR

STK15 X15 Y15 Z15

SC ART MC
AC SR

STK16 X16 Y16 Z16 X17

SC ART MC
AC SR

Both the difference and the value are needed

Zero difference, but the value is needed

Additional key cell that need to be guessed

Fig. 5 Property of MC operation of SKINNY

Fig. 6 The equivalent STK STKeq

subtweakey after SR and MC
0 1 2 3 0 1 2 3
operations 4 5 6 7 SR 0 1 2 3
MC 7 4 5 6
0 1 2 3

single active cell in ΔZ 14 [8]. Therefore, the differences of ΔX 15 [2, 10, 14] are needed
to indicate the values as well as differences at Y15 [2, 10, 14]. To compute the value at
Y15 [10], the value of X 16 [4, 12] is required, thus an additional cell ST K 16 [4] needs to
be guessed.
2. Since the AddRoundTweakey operation follows the SubCells operation, and
ShiftRows and MixColumns operations are all linear transformations, we can xor
an equivalent subtweakey to the internal state after the MC operation, i.e. ST K eq =
MC ◦ S R(ST K ) as can be seen in Fig. 6.

Lemma 1 [34] For any non-zero input-output difference pair (δin , δout ) for the SKINNY Sbox
S, there is one solution x satisfying S(x) ⊕ S(x ⊕ δin ) = δout on average.

Note that MixColumns operation is not omitted in the last round of SKINNY, but it
is well known that MixColumns is a linear operation which does not impact the differ-
ential cryptanalysis. To simplify the discussion, we omit the ShiftRows operation and
MixColumns operation in the last round, and denote S R ◦ MC −1 (C) (i.e. state Z r −1 in
r -round attack) by C in the last round, where C is the ciphertext.

123
1114 B. Zhao et al.

4.4 Related-tweakey rectangle attack on 27-round SKINNY-128-384

We use the same related-tweakey differential trail as in [34] which is listed in Table 3. As
described in [34], the probability of the 11-round related-tweakey differential trail is 2−21 ,
and there are two trails holding with the same probability with the input and output difference
unchanged leading to p̂ = 2−20 . A 12-round differential trail with a probability of 2−37 can
be obtained by extending one round at the start of the 11-round trail, and connecting the
11-round and 12-round trails to construct a 23-round rectangle distinguisher. When using the
boomerang switch technique in [17], four Sboxes can be saved leading to q̂ = 2−36 . Thus
the probability of the 23-round rectangle distinguisher is 2−n · p̂ 2 q̂ 2 = 2−240 .
We prefix two rounds at the beginning of the 23-round distinguisher and append two
rounds at the end to conduct a related-tweakey rectangle attack on 27-round SKINNY-128-
384, which is illustrated in Fig. 7.
In data collection, since ΔY1 = A RT −1 ◦ S R −1 ◦ MC −1 (α), where α is the difference
in the start of the rectangle distinguisher that is known, we only need to guess the 8 bytes
of ST K 0 to construct sets S1 and S2 . There are two bytes of 0 differences in the difference
of plaintexts, rb = 14c, m b = 8c, r f = 13c and m f = 12c where c = 8. Totally, there are
about y 2 · 22rb · 2−2(n−r f ) = y 2 · 2176 quartets as (C1 , C2 , C3 , C4 ) remaining. We give the
details of the key recovery process for the m f bit subtweakeys involved in E f as follows (we
restate that we treat Z 26 to be the ciphertext):

1. In the second column of the ciphertext pair (C1 , C3 ), the value of Z 26 [13] is known and
the value of X 26 [13] can be deduced since there is no subtweaky involved. According
to the inverse of the MixColumns operation, ΔZ 25 [13] = ΔX 26 [13] ⊕ ΔX 26 [1] and
ΔZ 25 [13] = 0. With ΔX 26 [1] = ΔX 26 [13], ΔY26 [1] and as the value as well as the
difference at Z 26 [1] can be obtained from the ciphertext pair, there is one solution for
ST K 26 [1] on average. Similarly, ΔX 26 [5] = ΔX 26 [9] ⊕ ΔX 26 [13] since ΔZ 25 [5] = 0,
and there is one solution for ST K 26 [5] on average.
2. Partially decrypt the second column of ciphertext pair (C1 , C3 ) for one round to get
the values as well as differences at Z 25 [1, 9]. Since the input difference of the Sbox at
X 25 [1] can be obtained from the rectangle distinguisher and the output difference is just
ΔZ 25 [1], there is one solution for ST K 25 [1] on average. But the difference ΔZ 25 [9] can
be mapped to the known difference ΔX 25 [11] with a probability of 2−8 . There are about
y 2 · 2176 · 2−8 = y 2 · 2168 quartets remaining.
3. Partially decrypt the second column of ciphertext pair (C2 , C4 ) to compute the values
and differences at Z 25 [1, 5, 9, 13]. The probability that ΔZ 25 [5, 13] = 0 is 2−16 , the
probability that Z 25 [1] of (C2 , C4 ) can be mapped to the known difference ΔX 25 [1]
under the obtained subtweakey is 2−8 , and the probability that Z 25 [9] of (C2 , C4 ) can be
mapped to the known difference ΔX 25 [11] with no subtweakey involved is 2−8 . Totally,
there are about y 2 · 2168 · 2−32 = y 2 · 2136 quartets remaining.
4. Similarly, for the first column of ciphertext pair (C1 , C3 ), ΔX 26 [4] = ΔX 26 [8] ⊕
ΔX 26 [12] can be deduced since ΔZ 25 [4] = 0 and ΔX 26 [8, 12] can be computed by
the ciphertext pair. We can get one value of ST K 26 [4] on average. Then guess the
value of ST K 26 [0] and compute the values as well as the differences at Z 25 [0, 4, 8, 12],
deduce the value of ST K 25 [0], check whether the known differences ΔX 25 [10, 13] can
be obtained by the values at Z 25 [8, 12]. There are about y 2 · 2136 · 28 · 2−16 = y 2 · 2128
combinations of the remaining quartets associated with the guessed keys, i.e. there
remains 28 candidate values of ST K 26 [0], ST K 25 [0] with about 2120 quartets each. Then
partially decrypt (C2 , C4 ) with the obtained subtweakey involved and check whether

123
Generalized related-key rectangle attacks 1115

Fig. 7 Key-recovery attack against 27-round SKINNY-128-384

ΔZ 25 [4] = 0, ΔX 25 [0] = 0x80, ΔX 25 [10] = 0x83, ΔX 25 [13] = 0x80. There are

about y 2 · 2128 · 2−32 = y 2 · 296 combinations of the quartets associated with the guessed
keys remaining.
5. Utilizing a similar process with step 1 to step 3 to recover ST K 26 [3, 7] and ST K 25 [3],
there are about y 2 · 296 · 2−24 = y 2 · 272 combinations of the quartets associated with
the guessed keys remaining.
6. Since ΔX 26 [6] = ΔZ 26 [6] = 0 and ΔX 26 [2] is unknown, we must guess the values of
ST K 26 [2, 6] to compute the values as well as the differences at Z 25 [6, 14]. Utilizing the
filtration at X 25 [5, 15] and Z 25 [6, 14], there are about y 2 · 272 · 216 · 2−24 = y 2 · 264
combinations of the quartets associated with the guessed keys remaining to count for the
96-bit subtweakeys involved in E f .

123
1116 B. Zhao et al.

7. Output the top 2m f −h counters for the candidates and exhaustively search the other
k − m b − m f bit keys to check whether the guessed key is correct.
√
When the expected number of right quartets s = 1, y = s · 2n/2−rb / p̂q̂ = 28 , the data
complexity is D = 4M = 4 · y · 2rb = 2122 chosen plaintexts. And 2m b · 3M = 2185.58
table look-ups are needed. In each guessed m b -bit subtweakey, M 2 · 2−2(n−r f ) one-round
decryptions are conducted which are equal to M 2 · 2−2(n−r f ) · 1/27 = 2187.25 encryptions,
thus the time complexity is 4M + 2m b · M 2 · 2−2(n−r f ) · ε + 2k−h ≈ 2294 when the size of
the master key is k = 384, and the success probability is 84.39% when h = 90. The memory
complexity is 5M + 2m f ≈ 2122.32 .
When the expected number of right quartets equals 2, the data complexity is 2122.5 chosen
plaintexts, time complexity is 2294 and the memory complexity is 2122.82 . And the success
probability is 92.56% when h = 90.

4.5 Related-tweakey rectangle attack on 28-round SKINNY-128-384

Extending one more round backward from the 27-round attack in Sect. 4.4, all the bytes of
difference in the plaintext are active. However, the ART operation can be conducted after the
MC operation by xoring an equivalent subtweakey as it is described in Sect. 4.3. Therefore,
the 28-round rectangle attack only needs to guess extra 64-bit subtweakeys compared to the
27-round attack. We have rb = 14c, m b = 16c, r f = 13c and m f = 12c where c = 8. The
key recovery process is identical to that in the 27-round attack on SKINNY-128-384.
If the expected number of right quartets s = 1, a 28-round related-tweakey rectangle attack
on SKINNY-128-384 can be conducted with a data complexity of 2122 chosen plaintexts, a
time complexity of 2315.25 + 2304 ≈ 2315.25 encryptions when h = 80, a memory complexity
of 2122.32 and a success probability is 83.15%.

4.6 Related-tweakey rectangle attack on 24-round SKINNY-128-384

We construct a 24-round related-tweakey rectangle attack by extending the 23-round distin-

guisher one round forward, i.e. we delete the first two rounds and the last one round from the
27-round attack for SKINNY-128-384 which is illustrated in Fig. 7, and we treat the state
Z 25 to be the ciphertext. Since there is no round extended from the start of the distinguisher,
no involved subtweakey needs to be guessed. There are four active bytes in the start of the
distinguisher, eight active bytes in ΔZ 25 and four bytes of subtweakey involved in the last
round. Thus rb = 4c, m b = 0, r f = 8c and m f = 4c where c = 8.
We choose y structures of 232 plaintexts each, and M 2 ·2−2(n−r f ) = y 2 ·264 ·2−2(128−64) =
y 2 · 2−64 quartets. The key recovery process can be conducted as follows:

1. Since the difference at X 25 [0] is known, the difference at Y25 [0] and the value at Z 25 [0] can
be obtained from the ciphertext pair (C1 , C3 ), one solution of ST K 25 [0] can be computed
on average. Then by verifying the obtained keys by the ciphertext pair (C2 , C4 ), about
y 2 · 2−72 quartets are remaining. Since no byte of ST K 25 is involved in the computation
of Z 25 [8, 12], the values of Z 25 [8, 12] in both(C1 , C3 ) and (C2 , C4 ) can be computed
to the known differences ΔX 25 [10, 13] with a probability of 2−32 , and about y 2 · 2−104
quartets are remaining.
2. Conducting a process similar to that in step 1 to the other three columns of Z 25 , about
y 2 · 2−160 quartets are remaining to count for the 32-bit subtweakey.

123
Generalized related-key rectangle attacks 1117

√
When the expected number of right quartets s = 4 and advantage h = 20, y = s ·
2n/2−rb / p̂q̂ = 289 , a 24-round related-tweakey rectangle attack on SKINNY-128-384 can
be conducted with a data complexity of 2123 chosen plaintexts, a time complexity of 2123 +
2114 /24+2100 ≈ 2123 encryptions, and the success probability is 97.6%. Since no subtweakey
needs to be guessed in the upper part, we don’t need to store the chosen plaintexts, and the
memory complexity is 2121 .

4.7 Related-tweakey rectangle attack on SKINNY AEAD

We have analyzed the tweakable block cipher SKINNY-128-384 by a related-tweakey rect-

angle attack in Sect. 4, where there is no constraint to the value and difference of the tweak.
However, the SKINNY AEAD member M1 adopts SKINNY-128-384 as its internal prim-
itive, but M1 initializes the tweakey bytes in a more complex process which leads to more
constraints appearing when the adversary conducts a related-tweakey attack on it. Here, we
summarize the constraints as follows.
The first and most important, as depicted by the designers, the SKINNY AEAD member
M1 employs a 384-bit tweakey input but a 128-bit master key. And for all versions of SKINNY
AEAD, they claim full 128-bit security for key recovery, confidentiality and integrity in the
nonce-respecting mode. Moreover, when using the recommended parameters given in [9], the
total size of the message does not exceed 264 blocks and the maximum number of messages
that can be handled under the same key is 2128 in SKINNY AEAD member M1. Therefore,
only the attack on SKINNY-128-384 with time complexity ≤ 2128 can be applied to SKINNY
AEAD M1.
Secondly, a restriction to the difference of T K 1 appears due to the specific initialization
of the first 128-bit tweakey. The first 128-bit tweakey is composed of a 64-bit number that is
updated by a linear transformation rev64 and a LFSR, 7 bytes of zeros and a single byte for the
domain separation that is a constant. The other 256-bit tweakey is the concatenation of nonce
N and key K . Thus, in a related-tweakey attack, the last 64 bits of T K 1 can not contain any
difference. Fortunately, both ΔK used in the upper trail and ∇ K used in the lower trail don’t
contain any difference in the 64 bits in the 23-round related-tweakey rectangle distinguisher.
Thirdly, for a AEAD scheme, no decryptions are proceeded when a tag is invalid and
only a null character is returned. This implies that the adversary can only make queries to
the encryption oracle, which prevents any chosen ciphertext attack. But it is not problematic
to the rectangle attack where only chosen plaintext is needed.
Finally, the nonce input of the AEAD mode may be a problem in data collection. SKINNY
AEAD M1 is a nonce-respecting scheme, the adversary can only query a nonce once under
the same key, but a nonce can be queried several times in different keys i.e. in the related-key
setting. In the case of SKINNY AEAD M1, the nonce N is used in tweakey input together with
the master key and some other string, which implies that the tweakey input is controlled for
the adversary. Thus the adversary can make queries in advance and conduct a related-tweakey
rectangle attack on its internal primitive SKINNY-128-384.

4.7.1 Explanation for the data collection.

As described in [9], the 384-bit tweakey of the SKINNY AEAD M1 consist of a 128-bit
rev64 (L F S R)||056 ||d0 , a 128-bit nonce N and a 128-bit secret key K , where rev64 (L F S R)
play the same role as a block counter that traverses from 0 to 264 − 1. The attacker can make
queries to the encryption oracle as follows:

123
1118 B. Zhao et al.

1. The attacker can choose an arbitrary nonce N1 and query a plaintext chain with a size of
264 blocks under the secret key K 1 , the block counter denoted by l1 will traverse from 0
to 264 − 1. Note that there is no constraint to the plaintexts, the attacker can set arbitrary
value to each plaintext block.
2. The attacker choose another nonce N2 and query a plaintext chain with a size of 264
blocks under the secret key K 2 , the block counter denoted by l2 will also traverse from 0
to 264 −1. But the nonce N2 and secret key K 2 must satisfy that N1 ⊕ N2 and K 1 ⊕ K 2 are
equal to the differences in ΔK . For each value of block counter l1 and the corresponding
plaintext block P1 , there exists a value of block counter l2 that l1 ⊕ l2 satisfies the
differences in ΔK , so the value of the plaintext block P2 corresponding to block counter
l2 must satisfies that P1 ⊕ P2 is equal to the difference in the start of the attack. Totally,
the attacker can obtain 264 plaintext pairs in the two steps to proceed the attack.
3. Utilizing a way similar to steps 1 and 2, the attacker can make queries under nonces
N3 , N4 and secret keys K 3 , K 4 . The values of plaintext blocks under N3 and K 3 can be
arbitrary, but the differences N1 ⊕ N3 and K 1 ⊕ K 3 must be equal to the differences in
∇ K . The values of plaintext blocks under N4 and K 4 will be set according to the value
of block counter following the same way as in step 2, and the differences N3 ⊕ N4 and
K 3 ⊕ K 4 need to be equal to the differences in ΔK .

Note that each query made by the attacker is used to construct plaintext pairs without
waste. Therefore, the attack on SKINNY AEAD M1 does not need a higher data complexity.
The related-tweakey rectangle attack on 24-round SKINNY-128-384 has a data complexity
of 2123 chosen plaintexts and a time complexity 2123 , which is applicable to the SKINNY
AEAD M1.

5 Application to GIFT-64

The GIFT block cipher, proposed by Banik et al. at CHES 2017 [7], is an improved version
of PRESENT [18]. In the NIST Lightweight Cryptography Standardization process [37],
the candidates SUNDAE-GIFT [5], TGIF [26] and GIFT-COFB [6] are based on the GIFT
block cipher. GIFT has two versions, GIFT-64 and GIFT-128, according to the block size,
while both versions support the 128-bit key size. At IWSEC 2018, Sasaki [40] introduced a
MitM attack on 15-round GIFT-64 with a time complexity 2112 . At CT-RSA 2019, Zhu et
al. [49] analyzed the 19-round GIFT-64 with a 12-round differential characteristic under the
single-key mode, and give a 22-round differential attack for GIFT-128. At ACISP 2019, Liu
and Sasaki [33] explored the BCT effect on GIFT-64 and GIFT-128 by a SAT-based method,
and gave a 23-round key-recovery attack on GIFT-64. Concurrently, Chen et al. [20] also
gave a 23-round key-recovery attack based on the generalized model of related-key rectangle
attack by Liu et al. [34]. In this paper, we use the same distinguisher given by Chen et al.
[20] to launch a new 24-round key-recovery attack based on our new generalized model of
related-key rectangle attack.

5.1 Specification of GIFT

GIFT [7], proposed by Banik et al. in 2017, is an SPN cipher. There are two versions for GIFT
according to the block size i.e., GIFT-64 and GIFT-128. Both versions have a key length of
128-bit and the number of rounds is 28 and 40 for GIFT-64 and GIFT-128, respectively.

123
Generalized related-key rectangle attacks 1119

Table 3 11-round trail for

SKINNY-128-384 in [34]. The 0, aa, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
23-round distinguisher uses the ΔK 0, e6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
11-round trail for the upper part 0, cf, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
and in the lower part the 0, 20, 0, 0, 10(7b), 0, 0, 0, 0, 0, 0, 10, 0, 0, 10, 0
12-round trail which is extended R1 0, 83, 0, 0, 40, 0, 0, 0, 0, 0, 0, 40, 0, 0, 40, 0
backward for one round from the 0, 83, 0, 0, 0, 0, 0, 0
11-round one where 0x7b is used 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0
instead. In each round, the rows R2 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 04, 0, 0
represent input/output differences 0, 0, 0, 0, 0, 0, 0, 0
of the Sbox layer and the round
tweakey difference 04, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R3 01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
01, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R4 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R5 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R6 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R7 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R8 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
R9 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 01, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 01, 0, 0, 0, 0
R10 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 20, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 20, 0, 0
R11 0, 80, 0, 0, 0, 0, 0, 0, 0, 80, 0, 0, 0, 80, 0, 0
0, 0, 0, 0, 0, 83, 0, 0

The round function is composed of three subfunctions named SubCells, PermBits

and AddRoundKey, which are defined as follows:
1. SubCells Apply the 4-bit Sbox to every nibble of the internal state, where the Sbox is
defined as Table 4.
2. PermBits Update the internal state by a linear bit permutation as b P(i) ← bi , ∀i ∈
{0, 1, . . . , n − 1}, where the P(i)s are expressed as
i i mod 16
P64 (i) =4  + 16 3 + (i mod 4)mod 4 + (i mod 4),
16 4
i i mod 16
P128 (i) =4  + 32 3 + (i mod 4 mod 4) + (i mod 4),
16 4
for GIFT-64 and GIFT-128, respectively.
3. AddRoundKey An n/2-bit round key R K is extracted from the key state and is further
partitioned into 2 s-bit words R K = U ||V = u s−1 . . . u 0 ||vs−1 v0 , where s = n/4.

123
1120 B. Zhao et al.

Table 4 The Sbox of GIFT

x 0 1 2 3 4 5 6 7 8 9 a b c d e f
G S(x) 1 a 4 c 6 f 3 9 2 d b 7 5 0 8 e

For GIFT-64, the round key is XORed to the state as

b4i+1 ← b4i+1 ⊕ u i , b4i ← b4i ⊕ vi , ∀i ∈ {0, . . . , 15}.
For GIFT-128, the round key is XORed to the state as
b4i+2 ← b4i+2 ⊕ u i , b4i+1 ← b4i+1 ⊕ vi , ∀i ∈ {0, . . . , 31}.
For both versions, a single bit “1” and a 6-bit constant C are XORed into the internal
state at positions n − 1, 23, 19, 15, 11, 7 and 3 respectively.
The key schedule for GIFT is very simple. The 128-bit master key is initialized as K =
k7 ||k6 || · · · ||k0 , where |ki | = 32. For GIFT-64, the round key R K is R K = U ||V = k1 ||k0 .
For GIFT-128, the round key R K is R K = U ||V = k5 ||k4 ||k1 ||k0 . And for both versions,
the key state is updated as follows,
k7 ||k6 || · · · ||k0 ← k1 >>> 2||k0 >>> 12|| · · · ||k3 ||k2 ,
where ≫ i is an i-bit right rotation within a 16-bit word. For more details of GIFT, we refer
to [7].

5.2 Notations and definitions of GIFT

In this section, the notations are defined as follows:

ΔP : The difference in plaintext.
ΔX iS : The difference after SubCells operation in Round i, 0 ≤ i ≤ r − 1.
ΔX iP : The difference after PermBits operation in Round i, 0 ≤ i ≤ r − 1.
ΔX iK : The difference after AddRoundKey operation in Round i, 0 ≤ i ≤ r − 1.
”?” : Represent an unknown difference.
ΔX iS [ j · · · k] : jth byte, · · · , k th byte of ΔX iS .

5.3 24-Round attack on GIFT-64

We use the same 19-round related-key rectangle distinguisher of GIFT-64 listed in Table 5
by Chen et al. [20] to give the first 24-round key-recovery attack on GIFT-64. We append
three rounds backward and two rounds forward to the distinguisher to conduct a 24-round
related-key rectangle attack. The propagation of the differentials is illustrated in Table 6.
Note that, there is no whitening key xored to the plaintext, we collect data in ΔX 0P , which
is similar to the previous works [20,33,49]. There are 46 unknown bits in ΔX 0P denoted by
“?” which affect 12 Sboxes in Round 1 and four Sboxes in Round 2, thus rb = 46 and the
number of key bits needed to be guessed in the upper part is m b = 24. Similarly, we have
r f = 20 and m f = 12 for the lower part. Totally, there are y 2 · 22rb · 2−2(n−r f ) = y 2 · 24
quartets remaining for each guessed m b -bit key. The key recovery part is very similar to that
in Sect. 4.4, we give the brief description of it as follows (For generalization, we treat the
“1” in ΔX 22S and ΔX K as “?”):
22

123
Generalized related-key rectangle attacks 1121

Table 5 Differential paths of 19-round GIFT-64 [20], where “*” denotes the probability of the rounds that are
evaluated for the ladder switch
Round Difference Δki Δki+1 Probability

1r 0000 00a0 0000 6000 (4, 0, 0, 0) (0, 1, 0, 0) 2−4

2r 0000 0000 0000 0000 (0, 0, 0, 0) (0, 0, 0, 0) 1
3r 0000 0000 0000 0000 (0, 0, 0, 2) (0, 0, 0, 0) 1
4r 0000 0000 0000 0010 (0, 0, 0, 0) (0, 0, 0, 0) 2−3
5r 0000 0008 0000 0000 (0, 0, 0, 4) (0, 0, 4, 0) 2−2
6r 0000 0000 0000 0000 (0, 0, 0, 0) (0, 0, 0, 0) 1
7r 0000 0000 0000 0000 (0, 0, 2, 0) (0, 0, 0, 0) 1
8r 0000 0000 0010 0000 (0, 0, 0, 0) (0, 0, 0, 0) 2−3
9r 0000 0080 0000 0000 (0, 0, 4, 0) (0, 0, 1, 0) 2−2
10r 0100 0000 0102 0200 (0, 0, 0, 0) (0, 0, 0, 0) 1∗
11r 00a2 0000 8020 0044 (0, 2, 0, 0) (0, 0, 0, 0) 1∗
10r 0000 0e03 0000 0073 (0, 0, 0, 1) (0, 0, 0, 0) 1∗
11r 0000 050c 0a00 0000 (0, 2, 0, 0) (0, 0, 0, 0) 1∗
12r 0a00 0000 0000 0000 (0, 8, 0, 0) (0, 0, 0, 0) 2−2
13r 0000 0000 0000 0000 (0, 0, 0, 0) (0, 0, 0, 0) 1
14r 0000 0000 0000 0000 (0, 0, 1, 0) (0, 0, 0, 0) 1
15r 0000 0000 0001 0000 (2, 0, 0, 0) (0, 0, 0, 0) 2−3
16r 0090 0000 0000 0000 (8, 0, 0, 0) (0, 0, 0, 0) 2−3
17r 0000 0000 0000 0000 (0, 0, 0, 0) (0, 0, 0, 0) 1
18r 0000 0000 0000 0000 (0, 1, 0, 0) (0, 0, 0, 0) 1
19r 0000 0001 0000 0000 (0, 0, 2, 0) (0, 0, 0, 0) 2−3

1. The difference of ΔX 23 S [60, 61, 62, 63] can be computed by the cipertext pair (C 1 , C 3 )
and the difference of ΔX 22 K [60, 62, 63] = 0 is known. Thus we guess the 2 possible
2

values of involved key bits in this Sbox and partially decrypt cipertext pairs (C1 , C3 ) and
(C2 , C4 ) and check whether the difference of ΔX 22 K [60, 62, 63] is 0 or not. If yes, we keep
the guessed key and the quartet, otherwise discard it. There are about y 2 ·24 ·22 ·2−6 = y 2
combinations of the remaining quartets associated with the guessed 2-bit keys, i.e. there
remains about y 2 · 2−2 quartets with 22 candidate values of the 2-bit involved keys each.
2. Conducting a similar process to all the active Sboxes in Round 23, there are about
y 2 · 2−4×4 = y 2 · 2−16 combinations of the remaining quartets associated with the
guessed keys,.
3. Partially decrypt all the remaining quartets with the obtained key bits in steps 1 and 2.
The difference of ΔX 21K [56, 57, 58, 59] can be obtained from the end of the distinguisher,
thus guess the 22 possible values of the key bits involved in this Sbox. For each guess,
only 2−8 of the quartets remain i.e. y 2 · 2−16 · 22 · 2−8 = y 2 · 2−22 . Utilize the remaining
quartets to count the m f = 12 key bits.
√
When the expected number of right quartets s = 4, we need to choose y = s ·
2n/2−rb / p̂q̂ = 212 structures of 246 plaintexts each, and the data complexity is 4M = 260
chosen plaintexts. 2m b · 3M = 291.58 table lookups are needed to prepare quartets. For
each guessed m b -bit key, y 2 · 24 · 22 one-round encryptions are conducted which are

123
 1122

123
Table 6 Related-key rectangle attack of 24-round GIFT-64

ΔP ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ????
ΔX 0S 0??? ?0?? 1?0? ?1?0 0??? ?0?? ??0? ???0 0??? ?0?? ??0? ???0 0??? ?0?? ??0? ???0
ΔX 0P ???? ???? ???? ???? 11?? ???? ???? ???? ???? ???? ???? ???? 0000 0000 0000 0000
ΔX 0K ???? ???? ???? ???? 11?? ???? ???? ???? ???? ???? ???? ???? 0000 0000 0000 0000
ΔX 1S 000? ?000 0?00 00?0 0100 00?0 000? 1000 0?0? ?0?0 0?0? ?0?0 0000 0000 0000 0000
ΔX 1P 0000 11?? ???? 0000 0000 0000 0000 0000 ???? 0000 ???? 0000 0000 0000 0000 0000
ΔX 1K 0000 11?? ???? 0000 0000 0000 0000 0000 ???? 0000 ???? 0000 0000 0000 0000 0000
ΔX 2S 0000 0100 0010 0000 0000 0000 0000 0000 0010 0000 1000 0000 0000 0000 0000 0000
ΔX 2P 0000 0000 0000 0000 0000 0000 1010 0000 0000 0000 0000 0000 0110 0000 0000 0000
ΔX 2K 0000 0000 0000 0000 0000 0000 1010 0000 0000 0000 0000 0000 0110 0000 0000 0000
.
.
. Distinguisher of 19-round GIFT-64
ΔX 21
K 0000 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
ΔX 22
S 0000 ??11 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
ΔX 22
P 0010 0000 0000 0000 0001 0000 0000 0000 ?000 0000 0000 0000 0?00 0000 0000 0000
ΔX 22
K 0010 0000 0000 0001 0001 0000 0000 0000 ?000 0000 0000 0000 0?00 0000 0000 0000
ΔX 23
S ???? 0000 0000 ???? ???? 0000 0000 0000 ???? 0000 0000 0000 ???? 0000 0000 0000
ΔX 23
P ??00 0?00 0?00 0?00 0??0 00?0 00?0 00?0 00?? 000? 000? 000? ?00? ?000 ?000 ?000
ΔX 23
K ??00 0?00 0?00 0?00 0??0 00?0 00?0 00?0 00?? 000? 000? 000? ?00? ?000 ?000 ?000
B. Zhao et al.
Generalized related-key rectangle attacks 1123

equal to y 2 · 24 · 22 /24 ≈ 225.42 encryptions. If we choose the advantage h = 40,

2m b ·225.42 +2128−48 ≈ 288 encryptions are needed to recover all the key bits, and the success
probability is 97.41%. Thus the time complexity is bounded by the 2m b · 3M = 291.58 table
lookups. The memory complexity is 5M + 2m f ≈ 260.32 .

6 Conclusion

In this paper, we give a new model of the generalized related-key rectangle attack. Based
on the new model, we give improved attacks on both, round-reduced SKINNY-128-384 and
GIFT-64. We also give the first third party cryptanalysis on SKINNY AEAD M1, which is a
candidate of the NIST Lightweight Cryptography project. As one open problem, our model
may be also applicable to more SKINNY-based or GIFT-based authenticated encryption
candidates of the ongoing NIST Lightweight Cryptography project, such as SUNDAE-GIFT
[5], TGIF [26], GIFT-COFB [6], Remus [27] and Romulus [28]. Another open problem is
to apply our model to evaluate the security of other block ciphers with linear key schedules,
such as Saturnin [19], Simon [8].

Acknowledgements This work is supported by the National Key Research and Development Program of China
(No. 2017YFA0303903), the National Natural Science Foundation of China (No. 61902207), the National
Cryptography Development Fund (Nos. MMJJ20180101, MMJJ20170121). Gaoli Wang is supported by the
National Cryptography Development Fund (No. MMJJ20180201) and the International Science and Technol-
ogy Cooperation Projects (No. 61961146004).

References
1. Abdelkhalek A., Sasaki Y., Todo T., Tolba M., Youssef A.M.: MILP modeling for (large) s-boxes to
optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99–129
(2017).
2. Ankele R., Banik S., Chakraborti A., List E., Mendel F., Sim S.M., Wang G.: Related-key impossible-
differential attack on reduced-round skinny. In: Proceedings of Applied Cryptography and Network
Security—15th International Conference, ACNS 2017, Kanazawa, Japan, July 10–12, 2017, pp. 208–
228 (2017).
3. Avanzi R.: The QARMA block cipher family. almost MDS matrices over rings with zero divisors, nearly
symmetric even-mansour constructions with non-involutory central rounds, and search heuristics for
low-latency s-boxes. IACR Trans. Symmetric Cryptol. 2017(1), 4–44 (2017).
4. Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block
cipher for low energy. In: Proceedings of Advances in Cryptology—ASIACRYPT 2015—21st Interna-
tional Conference on the Theory and Application of Cryptology and Information Security, Auckland,
New Zealand, November 29–December 3, 2015, Part II, pp. 411–436 (2015).
5. Banik S., Bogdanov A., Peyrin T., Sasaki Y., Sim S.M., Tischhauser E., Todo Y.: SUNDAE-GIFT. Sub-
mission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).
6. Banik S., Chakraborti A., Iwata T., Minematsu K., Nandi M., Peyrin T., Sasaki Y., Sim S.M., Todo Y.:
GIFT-COFB. Submission to Round 1 of the NIST Lightweight Cryptography Standardization process
(2019).
7. Banik S., Pandey S.K., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT: a small present—towards reach-
ing the limit of lightweight encryption. In: Proceedings of Cryptographic Hardware and Embedded
Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, pp.
321–345 (2017).
8. Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L.: The SIMON and SPECK
families of lightweight block ciphers. IACR Cryptol. ePrint Arch. 2013, 404 (2013).
9. Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.:
SKINNY-AEAD and SKINNY-Hash v1.0. Submission to Round 1 of the NIST Lightweight Cryptography
Standardization process (2019).

123
1124 B. Zhao et al.

10. Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The
SKINNY family of block ciphers and its low-latency variant MANTIS. In: Proceedings of Advances in
Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA,
USA, August 14–18, 2016, Part II, pp. 123–153 (2016).
11. Beierle C., Leander G., Moradi A., Rasoolzadeh S.: CRAFT: lightweight tweakable block cipher with
efficient protection against DFA attacks. IACR Trans. Symmetric Cryptol. 2019(1), 5–45 (2019).
12. Biham E., Dunkelman O., Keller N.: A related-key rectangle attack on the full KASUMI. In: Proceed-
ings of Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and
Application of Cryptology and Information Security, Chennai, India, December 4–8, pp. 443–461 (2005).
13. Biham E., Dunkelman O., Keller N.: New results on boomerang and rectangle attacks. In: Fast Software
Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, February 4–6, 2002, Revised
Papers, pp. 1–16 (2002).
14. Biham E., Dunkelman O., Keller N.: Related-key boomerang and rectangle attacks. In: Proceedings of
Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and
Applications of Cryptographic Techniques, Aarhus, Denmark, May 22–26, 2005, pp. 507–525 (2005).
15. Biham E., Dunkelman O., Keller N.: The rectangle attack—rectangling the serpent. In: Proceedings of
Advances in Cryptology—EUROCRYPT 2001, International Conference on the Theory and Application
of Cryptographic Techniques, Innsbruck, Austria, May 6–10, 2001, pp. 340–357 (2001).
16. Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes A., Vanstone
S.A. (eds.) Advances in Cryptology—CRYPTO 90, vol. 537, pp. 2–21. Lecture Notes in Computer
ScienceSpringer, New York (1991).
17. Biryukov A., Khovratovich D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Pro-
ceedings of Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory
and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009, pp. 1–18
(2009).
18. Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkel-
soe C.: PRESENT: an ultra-lightweight block cipher. In: Proceedings of Cryptographic Hardware and
Embedded Systems—CHES 2007, 9th International Workshop, Vienna, Austria, September 10–13, 2007,
pp. 450–466 (2007).
19. Canteaut A., Duval S., Leurent G., Naya-Plasencia M., Perrin L., Pornin T., Schrottenloher A.: Saturnin
v1: a suite of lightweight symmetric algorithms for post-quantum security. Submission to Round 1 of the
NIST Lightweight Cryptography Standardization process (2019).
20. Chen L., Wang G., Zhang G.: MILP-based related-key rectangle attack and its application to GIFT,
Khudra, MIBS. Accepted by The Computer Journal.
21. Chen H., Zong R., Dong X.: Improved Differential Attacks on GIFT-64. To appear in ICICS 2019.
22. Cid C., Huang T., Peyrin T., Sasaki Y., Song L.: Boomerang connectivity table: a new cryptanalysis tool. In:
Proceedings of Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference
on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29–May 3, 2018,
Part II, pp. 683–714 (2018).
23. Daemen J., Rijmen V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Information
Security and CryptographySpringer, New York (2002).
24. Dunkelman O., Keller N., Shamir A.: A practical-time related-key attack on the KASUMI cryptosystem
used in GSM and 3g telephony. In: Proceedings of Advances in Cryptology—CRYPTO 2010, 30th Annual
Cryptology Conference, Santa Barbara, CA, USA, August 15–19, 2010, pp. 393–410 (2010).
25. Guo J., Peyrin T., Poschmann A., Robshaw M.J.B.: The LED block cipher. In: Proceedings of Crypto-
graphic Hardware and Embedded Systems—CHES 2011—13th International Workshop, Nara, Japan,
September 28–October 1, 2011, pp. 326–341 (2011).
26. Iwata T., Khairallah M., Minematsu K., Peyrin T., Sasaki Y., Sim S.M., Sun L.: Thank Goodness It’s
Friday (TGIF). Submission to Round 1 of the NIST Lightweight Cryptography Standardization process
(2019).
27. Iwata T., Khairallah M., Minematsu K., Peyrin T.: Remus v1. Submission to Round 1 of the NIST
Lightweight Cryptography Standardization Process (2019).
28. Iwata T., Khairallah M., Minematsu K., Peyrin T.: Romulus v1. Submission to Round 1 of the NIST
Lightweight Cryptography Standardization Process (2019).
29. Jean J., Nikolić I., Peyrin T., Seurin Y.: Submission to Caesar: Deoxys v1.41, (October 2016).
30. Jean J., Nikolic I., Peyrin T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Proceed-
ings of Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and
Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7–11, 2014,
Part II, pp. 274–288 (2014).

123
Generalized related-key rectangle attacks 1125

31. Kelsey J., Kohno T., Schneier B.: Amplified boomerang attacks against reduced-round MARS and serpent.
In: Proceedings of Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA,
April 10–12, 2000, pp. 75–93 (2000).
32. Krovetz T., Rogaway P.: The software performance of authenticated-encryption modes. In: Fast Software
Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011, Revised
Selected Papers, pp. 306–327 (2011).
33. Liu Y., Sasaki Y.: Related-key boomerang attacks on GIFT with automated trail search including bct
effect. Cryptology ePrint Archive, Report 2019/669 (2019).
34. Liu G., Ghosh M., Song L.: Security analysis of SKINNY under related-tweakey settings (long paper).
IACR Trans. Symmetric Cryptol. 2017(3), 37–72 (2017).
35. Moradi A., Poschmann A., Ling S., Paar C., Wang H.: Pushing the limits: a very compact and a threshold
implementation of AES. In: Proceedings of Advances in Cryptology—EUROCRYPT 2011—30th Annual
International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia,
May 15–19, 2011, pp. 69–88 (2011).
36. Murphy S.: The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57(4), 2517–2521
(2011).
37. National Institute of Standards and Technology (NIST): Lightweight cryptography (LWC) standardization
process. https://csrc.nist.gov/Projects/Lightweight-Cryptography/Round-1-Candidates (2019).
38. Sadeghi S., Mohammadi T., Bagheri N.: Cryptanalysis of reduced round SKINNY block cipher. IACR
Trans. Symmetric Cryptol. 2018(3), 124–162 (2018).
39. Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects - reveal-
ing structural properties of several ciphers. In: Proceedings of Advances in Cryptology—EUROCRYPT
2017—36th Annual International Conference on the Theory and Applications of Cryptographic Tech-
niques, Paris, France, April 30–May 4, 2017, Part III, pp. 185–215 (2017).
40. Sasaki Y.: Integer linear programming for three-subset meet-in-the-middle attacks: application to GIFT.
In: Proceedings of Advances in Information and Computer Security—13th International Workshop on
Security, IWSEC 2018, Sendai, Japan, September 3–5, 2018, pp. 227–243 (2018).
41. Selçuk A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptol. 21(1), 131–147
(2008).
42. Shi D., Sun S., Derbez P., Todo Y., Sun B., Hu L.: Programming the demirci-selçuk meet-in-the-middle
attack with constraints. In: Proceedings of Advances in Cryptology—ASIACRYPT 2018—24th Inter-
national Conference on the Theory and Application of Cryptology and Information Security, Brisbane,
QLD, Australia, December 2–6, 2018, Part II, pp. 3–34 (2018).
43. Song L., Qin X., Lei H.: Boomerang connectivity table revisited. Application to SKINNY and AES. IACR
Trans. Symmetric Cryptol. 2019(1), 118–141 (2019).
44. Sun S., Gerault D., Lafourcade P., Yang Q., Todo Y., Qiao K., Lei H.: Analysis of AES, SKINNY, and
others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017).
45. The CAESAR Committee: CAESAR: competition for authenticated encryption: security, applicability,
and robustness (2014).
46. Tolba M., Abdelkhalek A., Youssef A.M.: Impossible differential cryptanalysis of reduced-round
SKINNY. In: Proceedings of Progress in Cryptology—AFRICACRYPT 2017—9th International Con-
ference on Cryptology in Africa, Dakar, Senegal, May 24–26, 2017, pp. 117–134 (2017).
47. Wagner D.A.: The boomerang attack. In: Proceedings of Fast Software Encryption, 6th International
Workshop, FSE ’99, Rome, Italy, March 24–26, 1999, pp. 156–170 (1999).
48. Wang H., Peyrin T.: Boomerang switch in multiple rounds. Application to AES variants and Deoxys.
IACR Trans. Symmetric Cryptol. 2019(1), 142–169 (2019).
49. Zhu B., Dong X., Yu H.: MILP-based differential attack on round-reduced GIFT. In: Proceedings of
Topics in Cryptology—CT-RSA 2019—The Cryptographers’ Track at the RSA Conference 2019, San
Francisco, CA, USA, March 4–8, 2019, pp. 372–390 (2019).

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and
institutional affiliations.

123
1126 B. Zhao et al.

Affiliations

Boxin Zhao1 · Xiaoyang Dong2 · Willi Meier3 · Keting Jia4 · Gaoli Wang5

Boxin Zhao
boxinzhao@mail.sdu.edu.cn
Willi Meier
willi.meier@fhnw.ch
Keting Jia
ktjia@tsinghua.edu.cn
Gaoli Wang
glwang@sei.ecnu.edu.cn
1 Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education,
School of Mathematics, Shandong University, Jinan 250100, China
2 Institute for Advanced Study, Tsinghua University, Beijing 100084, China
3 FHNW, Institute ISE, Windisch, Aargau, Switzerland
4 Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
5 Shanghai Key Lab of Trustworthy Computing, East China Normal University, Shanghai 200062,
China

123