Abstract
We propose a new construction of tweakable block ciphers from standard block ciphers. Our construction, dubbed \(\mathsf {XHX2}\), is the cascade of two independent \(\mathsf {XHX}\) block ciphers, so it makes two calls to the underlying block cipher using tweak-dependent keys. We prove the security of \(\mathsf {XHX2}\) up to \(\min \{2^{2(n+m)/3},2^{n+m/2}\}\) queries (ignoring logarithmic factors) in the ideal cipher model, when the block cipher operates on n-bit blocks using m-bit keys. The \(\mathsf {XHX2}\) tweakable block cipher is the first construction that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher in the ideal cipher model.
Jooyoung Lee was supported by a National Research Foundation of Korea (NRF) grant funded by the Korean government (Ministry of Science and ICT), No. NRF-2017R1E1A1A03070248.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Tweakable block ciphers, first introduced in [9], are a generalization of standard block ciphers that accept extra inputs called tweaks. The tweak, providing inherent variability to the block cipher, makes it easy to design various higher level cryptographic schemes such as message authentication codes and modes of operation.
Tweakable block ciphers can either be designed from scratch [4, 5, 17], or be built upon off-the-shelf cryptographic primitives such as block ciphers and (public) permutations [3, 8, 11, 14]. In this work, we will specifically focus on block cipher-based constructions; one of the advantages of such constructions is that the trust in extensively-studied block ciphers can be transferred to the tweakable block ciphers via security reductions. In this line of research, it has been suggested that changing tweaks should be cheaper than changing keys. Following this principle, early proposals including \(\mathsf {LRW1}\) and \(\mathsf {LRW2}\) [8, 9], and their cascades used their underlying block ciphers with fixed keys, namely tweak independent keys. So changing tweaks does not require rekeying the underlying block cipher. The security of tweakable block ciphers without tweak-rekeying has typically been analyzed in the standard model, where the block cipher with a secret random key is replaced by a secret random permutation.
Recently, a unified vision for the tweak and key inputs has been proposed within the TWEAKEY framework [6]. From this point of view, tweakable block ciphers using tweak dependent keys have been studied [10, 18]. By using tweak dependent keys, one might expect a higher level of security (than using fixed keys), whereas the security of such constructions is typically analyzed in the ideal cipher model.
Our Results. Suppose that a \(\kappa \)-bit key tweakable block cipher \(\mathsf {TBC}\) has been built on an m-bit key n-bit block cipher E (modeled as an ideal cipher). Typically, each evaluation of \(\mathsf {TBC}\) would need a fixed number of calls to the underlying block cipher E, and hence \(O(2^{\kappa })\) block cipher queries will be sufficient to mount an exhaustive key search on \(\mathsf {TBC}\). However, if \(n+m<\kappa \), then one would be able to find its secret key (in an information theoretic sense) by making all possible \(2^{n+m}\) block cipher queries. Therefore, \(\mathsf {TBC}\) will not be provably secure beyond \(2^{\min \{\kappa ,n+m\}}\) queries in the ideal cipher model. In this line of research, recent work has been aimed at achieving security beyond \(2^{n/2}\) (precisely, \(2^n\)) assuming \(\kappa =m=n\) [10, 18]. This level of security is optimal, but still it is only the birthday bound with respect to the input size of the ideal cipher, namely \(n+m\). If a tweakable block cipher accepts sufficiently large keys (for example, if \(\kappa >n=m\)), then one might expect security beyond \(2^n\). The problem that we tackle in this paper is to construct a tweakable block cipher secure beyond the birthday bound with respect to the input size of the underlying block cipher in the ideal cipher model (as the counterpart of \(\mathsf {LRW2}[2]\) in the standard model), assuming \(\kappa >n+m\).Footnote 1
We begin with \(\mathsf {XHX}\) proposed by Jha et al. [7]. Let \(E: \{0,1\} ^m \times \{0,1\} ^n \rightarrow \{0,1\} ^n\) be an m-bit key n-bit block cipher, let \(\mathcal {T}\) be a tweak space, and let \(\mathcal {G}\) and \(\mathcal {H}\) be families of functions \(g:\mathcal {T}\rightarrow \{0,1\} ^n\) and \(h:\mathcal {T}\rightarrow \{0,1\} ^m\), respectively. Then the \(\mathsf {XHX}\) tweakable block cipher accepts a key \((g,h)\in \mathcal {G}\times \mathcal {H}\) and a tweak \(t\in \mathcal {T}\), and encrypts a plaintext \(x\in \{0,1\} ^n\) by computing
If \(\mathcal {G}\) is \(\delta \)-almost uniform and \(\delta \)-almost XOR-universal, and if \(\mathcal {H}\) is \(\delta '\)-almost uniform and \(\delta '\)-almost universal with \(\delta \approx 1/2^n\) and \(\delta '\approx 1/2^m\), then \(\mathsf {XHX}\) is proved to be secure up to \(2^{(n+m)/2}\) queries in the ideal cipher model.
Our main contribution is to prove the security of the cascade of two independent \(\mathsf {XHX}\) constructions (see Fig. 1), dubbed \(\mathsf {XHX2}\), up to
queries. To the best of our knowledge, this is the first construction of a tweakable block cipher that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher.
For simplicity, we will prove the security of \(\mathsf {XHX2}\) under the assumption that the first and the second block cipher calls are made to independent block ciphers. However, in the ideal cipher model, a single key bit will be sufficient to separate a single block cipher into two independent ones with negligible security loss.
We believe that our results are not only of theoretical interest, but also practically relevant in certain environments, in particular where stronger security is required with block ciphers operating on (relatively) small blocks (e.g., \(\mathsf {CAST}\)-128 [1], \(\mathsf {KATAN}\), \(\mathsf {KTANTAN}\) [2], \(\mathsf {Simeck}\) [19]). For example, \(\mathsf {CAST}\)-128 (used in GPG and PGP) operates on 64-bit blocks using 128-bit keys. Based on this block cipher, the resulting \(\mathsf {XHX2}\) provides 128-bit security (ignoring log factors and constants), while this level of security would not be achieved with any other existing construction. On the other hand, the key schedule of the underlying block cipher should not be too simple (being secure against related-key and known-/chosen-key distinguishing attacks) since every block cipher key is supposed to define an independent permutation in our security model.
Comparison. A comparison of \(\mathsf {XHX2}\) with the existing tweakable block ciphers is given in Table 1. In this table, security is evaluated by the threshold number of queries in \(\log _2\). In \(\mathsf {Min}\), |t| denotes the fixed tweak length. All the constructions with tweak-rekeying are analyzed in the ideal cipher model, while the constructions without tweak-rekeying are in the standard model. Efficiency is evaluated by the number of block cipher calls, the number of multiplications or universal hashes, and the use of tweak dependent keys (represented by TDK).
Discussion. It is notable that our result for \(\mathsf {XHX2}\) implies beyond-birthday-bound security for the cascade of two independent \(\mathsf {XTX}\) [13] constructions (for the first time).
In typical TBC-based modes of operation (such as \(\mathsf {TBC}\), \(\mathsf {TAE}\) [9] and \(\mathsf {SCT}\) [15]), nonces and counters are placed into the tweak; when the tweak size is limited to the key size of the underlying block cipher, the hash computation can be defined as a single multiplication, namely \(t\cdot k\) for a hash key k and a tweak t. In this case, different tweaks map to different block cipher keys, removing the possibility of (C-14), and hence the term \(2^{n+m/2}\) from the security bound.
Overview of the Proof. Our security proof is based on the standard H-coefficient technique. We begin by defining a set of bad transcripts. The badness will be determined solely by the choice of hash keys \(g_1\), \(g_2\), \(h_1\) and \(h_2\). Once the hash keys are fixed, we can associate each construction query (t, x, y) with a 5-tuple \((h_1(t),h_2(t),x\oplus g_1(t),y\oplus g_2(t),g_1(t)\oplus g_2(t))\), which will be called a “reduced query”. As long as the hash keys are not bad, the reduced queries will be all distinct. Let \(k=h_1(t)\), \(l=h_2(t)\), \(u=x\oplus g_1(t)\), \(v=y\oplus g_2(t)\) and \(\varDelta =g_1(t)\oplus g_2(t)\). The relation between a reduced query \((k,l,u,v,\varDelta )\) and its original query (t, x, y) can be pictorially represented as follows.
The core of the proof is to show that the probabilities to obtain any good transcript are close in the real and in the ideal world, or particularly, to tightly lower bound the probability of obtaining a good transcript in the real world. In the real world, randomness comes only from the underlying ideal ciphers \(E_1\) and \(E_2\). For example, suppose that \(E_1(k,u)\) has been determined by a block cipher query (i.e., query history \(\mathcal {Q}_E\)). Then the probability that \(E_1\) and \(E_2\) complete the reduced query \((k,l,u,v,\varDelta )\) becomes the probability that \(E_2\) maps \(E_1(k,u)\oplus \varDelta \) to v with key l, where we can assume that \(E_2(l,E_1(k,u)\oplus \varDelta )\) and \(E_2^{-1}(l,v)\) have not been fixed excluding bad keys (of (C-9) and (C-10)). Fixing \(E_2(l,E_1(k,u)\oplus \varDelta )=v\) might affect the freedom of other construction queries, making the analysis complicated. The notion of a reduced query helps systematically dealing with this problem; we will carefully classify the reduced queries into five classes, and compute the (conditional) probability of completing each class of queries one by one. This classification will be defined in detail at Sect. 3.3.
2 Preliminaries
Basic Notation. In all the following, we fix positive integers m and n, and denote \(N=2^n\). Given a non-empty set \(\mathcal {X}\), \(x \leftarrow _{\$} \mathcal {X}\) denotes that x is chosen uniformly at random from \(\mathcal {X}\). For a set \(\mathcal {X}\) and an integer \(b\ge 1\), we write \(x_1,\ldots ,x_b\in ^{\ne } \mathcal {X}\) to mean that \(x_1,\ldots ,x_b\) are pairwise distinct elements of \(\mathcal {X}\). The set of all sequences that consist of b pairwise distinct elements of \(\mathcal {X}\) is denoted \(\mathcal {X}^{*b}\). For integers \(1\le b\le a\), we will write \((a)_b=a(a-1)\cdots (a-b+1)\) and \((a)_0=1\) by convention. If \(|\mathcal {X}|=a\), then \((a)_b\) becomes the size of \(|\mathcal {X}^{*b}|\). When two sets \(\mathcal {X}\) and \(\mathcal {Y}\) are disjoint, we denote \(\mathcal {X}\sqcup \mathcal {Y}\) their (disjoint) union.
Useful Lemma. The following lemma, viewed as a generalization of Lemma 5 in [3], will be used in the security proof of \(\mathsf {XHX2}\).
Lemma 1
Let N, a, b, c, d be positive integers such that \(a+b\le N/2\), \(a+c\le N/2\), \(d \le b\) and \(d \le c\). Then
Due to the space limit, the proof of this lemma will be given in the full version.
Uniform, Universal and XOR-Universal Hash Functions. We will need the following definitions of almost uniform, almost universal (AU) and almost XOR-universal (AXU) hash functions.
Definition 1
Let \(\delta >0\), and let \(\mathcal {H}\) be a family of functions \(h:\mathcal {T}\rightarrow \mathcal {Y}\) for non-empty sets \(\mathcal {T}\) and \(\mathcal {Y}\).
-
1.
\(\mathcal {H}\) is said to be \(\delta \)-almost uniform if for any \(x\in \mathcal {T}\) and any \(y\in \mathcal {Y}\),
$$ \Pr \left[ {h \leftarrow _{\$} \mathcal {H}:h(x)=y}\right] \le \delta . $$ -
2.
\(\mathcal {H}\) is said to be \(\delta \)-almost universal (\(\delta \)-AU) if for any distinct x and \(x'\in \mathcal {T}\),
$$ \Pr \left[ {h \leftarrow _{\$} \mathcal {H}:h(x)= h(x')}\right] \le \delta . $$ -
3.
When \(\mathcal {Y}= \{0,1\} ^n\), \(\mathcal {H}\) is said to be \(\delta \)-almost XOR-universal (\(\delta \)-AXU) if for any distinct \(x,x'\in \mathcal {T}\) and any \(y\in \mathcal {Y}\),
$$ \Pr \left[ {h \leftarrow _{\$} \mathcal {H}:h(x)\oplus h(x')=y}\right] \le \delta . $$
Remark 1
Hash functions in \(\mathcal {H}\) are typically indexed by keys in a certain key space, written as \(\mathcal {H}:\mathcal {K}\times \mathcal {T}\rightarrow \mathcal {Y}\) for a key space \(\mathcal {K}\). For example, let \(\mathcal {K}=\mathcal {Y}= \{0,1\} ^n\) and let \(\mathcal {T}= \{0,1\} ^{dn}\setminus \{(0,\ldots ,0)\}\) for a positive integer d. Identifying \( \{0,1\} ^n\) with a finite field \(\mathbf {GF}(2^n)\) with \(2^n\) elements and representing an element \(t\in \mathcal {T}\) as a concatenation of n-bit elements \(t_{d},\ldots ,t_1\), define
Then it is not hard to show that \(\mathcal {H}\) is \(\frac{d}{2^n}\)-almost uniform and \(\frac{d}{2^n}\)-almost XOR-universal. As seen in this example, for any n, one can define a \(\delta \)-almost uniform and \(\delta \)-almost XOR-universal family of functions with n-bit key, n-bit output, and \(\delta \approx 1/2^n\) (ignoring d).
The Ideal Cipher Model. A block cipher with key space \(\mathcal {K}\) and message space \(\mathcal {X}\) is a mapping \(E:\mathcal {K}\times \mathcal {X}\rightarrow \mathcal {X}\) such that, for any key \(k\in \mathcal {K}\), \(x\mapsto E(k,x)\) is a permutation of \(\mathcal {X}\). Throughout this paper, we will fix \(\mathcal {K}= \{0,1\} ^m\) and \(\mathcal {X}= \{0,1\} ^n\), and write \( \mathsf {BC} (m,n)\) to mean the set of all such block ciphers.
In the ideal cipher model, a block cipher E is chosen from \( \mathsf {BC} (m,n)\) uniformly at random. It allows for two types of oracle queries E(k, x) and \(E^{-1}(k,y)\) for \(x,y\in \{0,1\} ^{n}\) and \(k\in \{0,1\} ^m\). The response to an inverse query \(E^{-1}(k,y)\) is \(x\in \{0,1\} ^{n}\) such that \(E(k,x)=y\).
Tweakable Block Ciphers. A tweakable permutation with tweak space \(\mathcal {T}\) and message space \(\mathcal {X}\) is a mapping \( \widetilde{P} :\mathcal {T}\times \mathcal {X}\rightarrow \mathcal {X}\) such that, for any tweak \(t\in \mathcal {T}\), \(x\mapsto \widetilde{P} (t,x)\) is a permutation of \(\mathcal {X}\). Throughout the paper, we will fix \(\mathcal {X}= \{0,1\} ^n\), and write \( \mathsf {Perm} (\mathcal {T},n)\) to mean the set of all tweakable permutations with tweak space \(\mathcal {T}\) and message space \( \{0,1\} ^n\).
A tweakable block cipher \(\mathsf {TBC}\) with key space \(\mathcal {K}\), tweak space \(\mathcal {T}\) and message space \(\mathcal {X}\) is a mapping \(\mathsf {TBC}:\mathcal {K}\times \mathcal {T}\times \mathcal {X}\rightarrow \mathcal {X}\) such that for any key \(\mathbf {k}\in \mathcal {K}\), \((t,x)\mapsto \mathsf {TBC}(\mathbf {k},t,x)\) is a tweakable permutation with tweak space \(\mathcal {T}\) and message space \(\mathcal {X}\).
Indistinguishability. For \(s\ge 1\), we will consider a tweakable block cipher \(\mathsf {TBC}\) based on a set of block ciphers
So each key \(\mathbf {k}\in \mathcal {K}\) and a set of block ciphers \(\mathcal {E}=(E_1,\ldots ,E_s)\in \mathsf {BC} (m ,n)^s\) define a tweakable permutation, denoted \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}]\), with tweak space \(\mathcal {T}\) and message space \(\mathcal {X}\). Specifically, we have \(s=1\) for \(\mathsf {XHX}\) and \(s=2\) for \(\mathsf {XHX2}\), and \(\mathcal {X}= \{0,1\} ^n\) for both constructions.
In the real world, a secret key \(\mathbf {k}\in \mathcal {K}\) is chosen uniformly at random. A set of s block ciphers \(E_1,\ldots , E_s\) are also chosen independently at random from \( \mathsf {BC} (m,n)\). A distinguisher \(\mathcal {D}\) is given oracle access to \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}]\) as well as \(\mathcal {E}=(E_1,\ldots , E_s)\). In the ideal world, \(\mathcal {D}\) is given a random tweakable permutation \( \widetilde{P} \in \mathsf {Perm} (\mathcal {T},n)\) instead of \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}]\). However, oracle access to \(\mathcal {E}=(E_1,\ldots , E_s)\) is still allowed in this world.
The adversarial goal is to tell apart the two worlds \((\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}],\mathcal {E})\) and \(( \widetilde{P} ,\mathcal {E})\) by adaptively making forward and backward queries to the construction and each of the block ciphers. Formally, \(\mathcal {D}\)’s distinguishing advantage is defined by
For p, \(q>0\), we define
where the maximum is taken over all adversaries \(\mathcal {D}\) making at most p queries to each of the block ciphers and at most q queries to the outer tweakable permutation.
H-coefficient Technique. Suppose that a distinguisher \(\mathcal {D}\) makes p queries to each of the block ciphers, and q queries to the construction oracle. The queries made to the construction oracle are recorded in a query history
So according to the instantiation, it would imply either \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}](t_{i},x_{i})=y_{i}\) or \( \widetilde{P} (t_{i},x_{i})=y_{i}\). For \(j=1,\ldots ,s\), the queries made to \(E_j\) are recorded in a query history
where \((j,u_{j,i},v_{j,i})\) represents the evaluation \(E_{j}(k_{j,i},u_{j,i})=v_{j,i}\) obtained by the i-th query to \(E_j\). We will often omit the index j when it is clear from context. Let
Then the pair of query histories \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\) will be called the transcript of the attack: it contains all the information that \(\mathcal {D}\) has obtained at the end of the attack. In this work, we will only consider information theoretic distinguishers. Therefore we can assume that a distinguisher is deterministic without making any redundant query, and hence the output of \(\mathcal {D}\) can be regarded as a function of \(\tau \), denoted \(\mathcal {D}(\tau )\) or \(\mathcal {D}(\mathcal {Q}_C,\mathcal {Q}_E)\).
Fix a transcript \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\), a key \(\mathbf {k}\in \mathcal {K}\), a tweakable permutation \( \widetilde{P} \in \mathsf {Perm} (\mathcal {T},n)\), a tuple of block ciphers \(\mathcal {E}=(E_1,\ldots , E_s)\in \mathsf {BC} (m,n)^s\) and \(j\in \{1,\ldots ,s\}\): if \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}](t_{i},x_{i})=y_{i}\) (resp. \( \widetilde{P} (t_{i},x_{i})=y_{i}\)) for every \(i=1,\ldots ,q\), then we will write \(\mathsf {TBC}_{\mathbf {k}}[\mathcal {E}]\vdash \mathcal {Q}_{C}\) (resp. \( \widetilde{P} \vdash \mathcal {Q}_{C}\)). Similarly, if \(E_{j}(k_{j,i},u_{j,i})=v_{j,i}\) for every \(i=1,\ldots ,p\), then we will write \(E_{j}\vdash \mathcal {Q}_{E_{j}}\). We will write \(\mathcal {E}\vdash \mathcal {Q}_E\) if \(E_{j}\vdash \mathcal {Q}_{E_{j}}\) for every \(j=1,\ldots ,s\).
If there exist \( \widetilde{P} \in \mathsf {Perm} (\mathcal {T},n)\) and \(\mathcal {E}\in \mathsf {BC} (m,n)^s\) that outputs \(\tau \) at the end of the interaction with \(\mathcal {D}\), then we will call the transcript \(\tau \) attainable. So for any attainable transcript \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\), there exist \( \widetilde{P} \in \mathsf {Perm} (\mathcal {T},n)\) and \(\mathcal {E}\in \mathsf {BC} (m,n)^s\) such that \( \widetilde{P} \vdash \mathcal {Q}_C\) and \(\mathcal {E}\vdash \mathcal {Q}_E\). For an attainable transcript \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\) and a key \(\mathbf {k}\in \mathcal {K}\), let
With respect to an attainable transcript \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\), we will define a set of “bad” keys, denoted \(\mathcal {K}_{\mathsf {bad}}\), such that the probability of a uniform random key being bad is small, while the ratio \(\mathsf {p}_{\mathsf {re}}^{\mathbf {k}}(\mathcal {Q}_C|\mathcal {Q}_E)/\mathsf {p}_{\mathsf {id}}(\mathcal {Q}_C|\mathcal {Q}_E)\) is close to 1 for any “good” key \(\mathbf {k}\in \mathcal {K}\setminus \mathcal {K}_{\mathsf {bad}}\). With these definitions, the following lemma, the core of the H-coefficients technique, will be also used in our security proof.
Lemma 2
Let \(\varepsilon _1, \varepsilon _2>0\). Suppose that for any attainable transcript \(\tau =(\mathcal {Q}_C,\mathcal {Q}_E)\), there exists \(\mathcal {K}_{\mathsf {bad}}\subset \mathcal {K}\) such that \(|\mathcal {K}_{\mathsf {bad}}|/|\mathcal {K}|\le \varepsilon _1\) and for any \(\mathbf {k}\in \mathcal {K}\setminus \mathcal {K}_{\mathsf {bad}}\)
Then one has
3 Security Proof for \(\mathsf {XHX2}\)
Let \(E_1,E_2: \{0,1\} ^m \times \{0,1\} ^n \rightarrow \{0,1\} ^n\) be m-bit key n-bit block ciphers, let \(\mathcal {T}\) be a tweak space, and let \(\mathcal {G}\) and \(\mathcal {H}\) be families of hash functions \(g:\mathcal {T}\rightarrow \{0,1\} ^n\) and \(h:\mathcal {T}\rightarrow \{0,1\} ^m\), respectively. The \(\mathsf {XHX2}\) tweakable block cipher accepts a key and a tweak \(t\in \mathcal {T}\), and encrypts a plaintext \(x\in \{0,1\} ^n\) by computing
Theorem 1
Let \(\delta , \delta '>0\), let \(\mathcal {G}\) be a \(\delta \)-almost uniform and universal family of hash functions from \(\mathcal {T}\) to \( \{0,1\} ^n\) and let \(\mathcal {H}\) be a \(\delta '\)-almost uniform and XOR-universal family of hash functions from \(\mathcal {T}\) to \( \{0,1\} ^m\). Then for any integers p and q, one has
3.1 Giving Free Queries to the Distinguisher
For the security proof of \(\mathsf {XHX2}\), we will make an additional assumption on the attack model; a distinguisher \(\mathcal {D}\) will be given free queries at the end of the attack by the following rule.
-
1.
If \(\mathcal {D}\) has made N / 4 or more block cipher queries to \(E_1\) (resp. \(E_2\)) for a fixed key \(k\in \{0,1\} ^m\), then \(\mathcal {D}\) will be given \(E_1(k,u)\) (resp. \(E_2(k,u)\)) for all unqueried u (if any).
-
2.
If \(\mathcal {D}\) has made N / 16 or more queries to the construction oracle C for a fixed tweak \(t\in \mathcal {T}\), then \(\mathcal {D}\) will be given C(t, x) for all unqueried x (if any).
This modification would not degrade the adversarial distinguishing advantage since \(\mathcal {D}\) is free to ignore the additional information. Suppose that \(\mathcal {D}\) makes at most p queries to each of the block ciphers and at most q queries to the outer tweakable permutation. Then the number of free queries given to \(\mathcal {D}\) is upper bounded by 3p for each block cipher, and by 15q for the tweakable permutation. So this assumption can be viewed as transforming \(\mathcal {D}\) into a new distinguisher \(\mathcal {D}'\) that
-
(i)
makes at most 4p queries to each of the block ciphers and at most 16q queries to the outer tweakable permutation;
-
(ii)
makes either all N queries or less than N / 4 queries for each key and each of the block ciphers;
-
(iii)
makes either all N queries or less than N / 16 construction queries for each tweak.
Let
where the maximum is taken over all adversaries \(\mathcal {D}'\) that make at most p queries to each of the block ciphers and at most q queries to the outer tweakable permutation satisfying conditions (ii) and (iii). Then we have
Henceforth, we will assume that a modified adversary \(\mathcal {D}'\) makes p primitive queries to each of the block ciphers and q construction queries.
For an attainable transcript \(\tau = (\mathcal {Q}_C, \mathcal {Q}_{E})\), we will use the following notations: for r, \(s\in \{0,1\} ^m\), and \(w\in \mathcal {T}\),
Note that either \(|\mathcal {Q}_{E_i}(r)|<N/4\) or \(|\mathcal {Q}_{E_i}(r)|=N\) for any \(r\in \{0,1\} ^m\) and \(i=1,2\). Similarly, we have either \(|\mathcal {Q}_C(w)|<N/16\) or \(|\mathcal {Q}_C(w)|=N\) for any \(w\in \mathcal {T}\). In particular, we will write
3.2 Bad Keys
Fix an attainable transcript \(\tau = (\mathcal {Q}_C, \mathcal {Q}_{E})\), and positive integers \(M_1, M_2, M_3\) (that will be optimized later). Let
A key \(\mathbf {k}=(g_1,h_1,g_2,h_2)\in \mathcal {K}\) is defined to be bad if one of the following conditions is fulfilled:
-
(C-1)
\(|\mathcal {A}_i|\ge M_1\) for some \(i=1,2\);
-
(C-2)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) and \((k, u, v), (k', u', v') \in \mathcal {Q}_{E_1}\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (k, u), \\ (h_1(t'), x' \oplus g_1(t'))&= (k', u'),\\ (h_2(t), v \oplus g_1(t) \oplus g_2(t))&=(h_2(t'), v' \oplus g_1(t') \oplus g_2(t')); \end{aligned}$$ -
(C-3)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) and \((k, u, v), (k', u', v') \in \mathcal {Q}_{E_2}\) such that
$$\begin{aligned} (h_2(t), y \oplus g_2(t))&= (k, v), \\ (h_2(t'), y' \oplus g_2(t'))&= (k', v'), \\ (h_1(t), u \oplus g_1(t) \oplus g_2(t))&=(h_1(t'), u' \oplus g_1(t') \oplus g_2(t')); \end{aligned}$$ -
(C-4)
\(|\mathcal {B}_i|\ge M_2\) for some \(i=1,2,3,4\);
-
(C-5)
\(|\mathcal {C}_i|\ge M_3\) for some \(i=1,2,3,4\);
-
(C-6)
there exist \((t, x, y), (t', x', y'), (t'', x'', y'') \in \mathcal {Q}_C\) such that \((t, x, y)\ne (t', x', y')\), \((t, x, y)\ne (t'', x'', y'')\) and
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (h_1(t'), x' \oplus g_1(t')), \\ (h_2(t), y \oplus g_2(t))&= (h_2(t''), y'' \oplus g_2(t'')); \end{aligned}$$ -
(C-7)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (h_1(t'), x' \oplus g_1(t')), \\ (h_2(t), g_1(t) \oplus g_2(t))&= (h_2(t'), g_1(t') \oplus g_2(t')); \end{aligned}$$ -
(C-8)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) such that
$$\begin{aligned} (h_1(t), g_1(t) \oplus g_2(t))&= (h_1(t'), g_1(t') \oplus g_2(t')),\\ (h_2(t), y \oplus g_2(t))&= (h_2(t'), y' \oplus g_2(t')); \end{aligned}$$ -
(C-9)
there exist \((t, x, y) \in \mathcal {Q}_C\), \((k,u,v) \in \mathcal {Q}_{E_1}\) and \((k', u',v') \in \mathcal {Q}_{E_2}\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (k, u), \\ (h_2(t), y \oplus g_2(t))&= (k', v'); \end{aligned}$$ -
(C-10)
there exist \((t, x, y) \in \mathcal {Q}_C\), \((k, u, v) \in \mathcal {Q}_{E_1}\) and \((k', u',v') \in \mathcal {Q}_{E_2}\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (k, u), \\ (h_2(t), v \oplus g_1(t) \oplus g_2(t))&= (k', u'); \end{aligned}$$ -
(C-11)
there exist \((t, x, y) \in \mathcal {Q}_C\), \((k, u, v) \in \mathcal {Q}_{E_1}\) and \((k', u', v') \in \mathcal {Q}_{E_2}\) such that
$$\begin{aligned} (h_1(t), u' \oplus g_1(t) \oplus g_2(t))&= (k, v),\\ (h_2(t), y \oplus g_2(t))&= (k', v'); \end{aligned}$$ -
(C-12)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) and \((k, u,v) \in \mathcal {Q}_{E_1}\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (k, u), \\ (h_2(t), y \oplus g_2(t))&= (h_2(t'), y' \oplus g_2(t')); \end{aligned}$$ -
(C-13)
there exist \((t, x, y), (t', x', y') \in ^{\ne } \mathcal {Q}_C\) and \((k, u,v) \in \mathcal {Q}_{E_2}\) such that
$$\begin{aligned} (h_1(t), x \oplus g_1(t))&= (h_1(t'), x' \oplus g_1(t')),\\ (h_2(t), y \oplus g_2(t))&= (k, v); \end{aligned}$$ -
(C-14)
there exist \(k\in \{0,1\} ^m\) and \(h\in \{h_1,h_2\}\) such that
$$\frac{N}{4}\le |\{(t, x, y)\in \mathcal {Q}_C\setminus \mathcal {Q}_C^*:h(t)=k\}|.$$
Figure 2 pictorially represents bad conditions (C-2), (C-3) and (C-6) to (C-13) in terms of reduced queries (as defined in Sect. 3.3). The probability of having bad keys in the ideal world is upper bounded as follows.
Lemma 3
For an attainable transcript \(\tau = (\mathcal {Q}_C, \mathcal {Q}_{E})\), let \(\mathcal {K}_{\mathsf {bad}}\) be the set of bad keys defined as above. Then we have
For \(i=1,\ldots ,14\), let \(\mathsf {E}_i\) denote the event that a uniform random key \(\mathbf {k}\in \mathcal {K}\) satisfies condition (C-i). Then we have
Here we only upper bound \( \Pr \left[ {\mathsf {E}_{14}}\right] \); the analysis of the other events are rather straightforward. Due to the space limit, the complete proof will be given in the full version.
Upper Bounding. \( \Pr \left[ {\mathsf {E}_{14}}\right] \). Let
for \(i=1,\ldots ,n-4\). Then we have
For each \(h\in \{h_1,h_2\}\) and \(i\in \{1,\ldots ,n-4\}\), we define two random variables
Since \(|\mathcal {T}^i|\le \frac{q}{2^{i-1}}\) and by the \(\delta '\)-almost uniformity of \(\mathcal {H}\), we have
for \(i=1,\ldots ,n-4\). Since \(Y_i(Y_i-1)\le X_i\) and by Markov’s inequality, we have
for any \(C>0\). Therefore, for each \(k\in \{0,1\} ^m\) and \(h\in \{h_1,h_2\}\), we have
except with probability at most n / C. By letting \(C=\left( \frac{N}{16nq}\right) ^2\frac{1}{\delta '}\) (satisfying \(2nq\sqrt{C\delta '}=N/8\)), we have
3.3 Lower Bounding \(\mathsf {p}_{\mathsf {re}}^{\mathbf {k}}(\mathcal {Q}_C|\mathcal {Q}_E)/\mathsf {p}_{\mathsf {id}}(\mathcal {Q}_C|\mathcal {Q}_E)\) For a Good Key
This section will be devoted to the proof of the following lemma.
Lemma 4
For an attainable transcript \(\tau = (\mathcal {Q}_C, \mathcal {Q}_{E})\) and a good key \(\mathbf {k}=(g_1,h_1,g_2,h_2)\in \mathcal {K}\), one has
3.3.1 Useful Definitions and Properties
Let
The elements of \(\overline{\mathcal {Q}_C}\) will be called reduced queries (or simply queries). The reduced queries of \(\overline{\mathcal {Q}_C}\) are all distinct, namely, if \((t,x,y)\ne (t',x',y')\), then
since \(\mathbf {k}\) does not satisfy condition (C-6). Let
Each class of queries are pictorially represented in Fig. 3.
Property 1
Sets \(\mathcal {Q}^{(i)}\), \(i=1,2,3,4,5\), partition \(\overline{\mathcal {Q}_C}\), namely,
Proof
The union of \(\mathcal {Q}^{(i)}\), \(i=1, 2, 3, 4, 5\), is \(\overline{\mathcal {Q}_C}\) by the definition of \(\mathcal {Q}^{(5)}\). Furthermore, they are pairwise disjoint; in particular,
-
1.
\(\mathcal {Q}^{(1)} \cap \mathcal {Q}^{(2)} = \emptyset \) by excluding bad keys satisfying (C-9);
-
2.
\(\mathcal {Q}^{(1)} \cap \mathcal {Q}^{(4)} = \emptyset \) by excluding bad keys satisfying (C-12);
-
3.
\(\mathcal {Q}^{(2)} \cap \mathcal {Q}^{(3)} = \emptyset \) by excluding bad keys satisfying (C-13);
-
4.
\(\mathcal {Q}^{(3)} \cap \mathcal {Q}^{(4)} = \emptyset \) by excluding bad keys satisfying (C-6).
\(\square \)
We will further classify the queries and count each class using the following notations.
-
1.
For \(r,s \in \{0,1\} ^m\), \(d \in \{0,1\} ^n\) and \(i\in \{1,2,3,4,5\}\), let
$$\mathcal {Q}^{(i)}_{r,s,d} = \{(k,l,u,v,\varDelta ) \in \mathcal {Q}^{(i)} : (k,l,\varDelta )=(r,s,d)\},$$and let
$$\begin{aligned} \mathcal {Q}^{(i)}_{r,s}&= \bigsqcup _{d\in \{0,1\} ^n}\mathcal {Q}^{(i)}_{r,s,d},&\mathcal {Q}^{(i)}_{r,*}&= \bigsqcup _{l\in \{0,1\} ^m}\mathcal {Q}^{(i)}_{r,l},&\mathcal {Q}^{(i)}_{*,s}&= \bigsqcup _{k\in \{0,1\} ^m}\mathcal {Q}^{(i)}_{k,s}. \end{aligned}$$ -
2.
For \(w\in \mathcal {T}\), \(r,s \in \{0,1\} ^m\), \(d \in \{0,1\} ^n\) and \(i\in \{1,2,3,4,5\}\), let
$$\begin{aligned} q_w&=|\mathcal {Q}_{C}(w)|,&p_{r,*}&=|\mathcal {Q}_{E_1}(r)|,&p_{*,s}&=|\mathcal {Q}_{E_2}(s)|,\\ q^{(i)}_{r,s,d}&= |\mathcal {Q}^{(i)}_{r,s,d}|,&q^{(i)}_{r,s}&= |\mathcal {Q}^{(i)}_{r,s}|,&\\ q^{(i)}_{r,*}&=|\mathcal {Q}^{(i)}_{r,*}|,&q^{(i)}_{*,s}&=|\mathcal {Q}^{(i)}_{*,s}|.&\end{aligned}$$
Given the partition of the queries, we can also define the following sets.
-
1.
For \(r, s\in \{0,1\} ^m\), let
$$\begin{aligned} U_1(r)&= \{u\in \{0,1\} ^n:\exists v\in \{0,1\} ^n\text { such that }(u,v)\in \mathcal {Q}_{E_1}(r)\},\\ V_1(r)&= \{v\in \{0,1\} ^n:\exists u\in \{0,1\} ^n\text { such that }(u,v)\in \mathcal {Q}_{E_1}(r)\},\\ U_2(s)&= \{u\in \{0,1\} ^n:\exists v\in \{0,1\} ^n\text { such that }(u,v)\in \mathcal {Q}_{E_2}(s)\},\\ V_2(s)&= \{v\in \{0,1\} ^n:\exists u\in \{0,1\} ^n\text { such that }(u,v)\in \mathcal {Q}_{E_2}(s)\}. \end{aligned}$$ -
2.
For \(r, s\in \{0,1\} ^m\) and \(i\in \{1,2,3,4,5\}\), let
$$\begin{aligned} U^{(i)}_1(r)&= \{u\in \{0,1\} ^n:\exists s, v,\varDelta \text { such that }(r,s,u,v,\varDelta )\in \mathcal {Q}^{(i)}\},\\ V^{(i)}_2(s)&= \{v\in \{0,1\} ^n:\exists r, u,\varDelta \text { such that }(r,s,u,v,\varDelta )\in \mathcal {Q}^{(i)}\}. \end{aligned}$$
Sets \(U^{(i)}_1(r)\) and \(V^{(i)}_2(s)\), \(i=1, 2, 3, 4, 5\), are pictorially represented in Fig. 4. We have the following properties on these sets.
Property 2
For \(r, s\in \{0,1\} ^m\), one has
-
1.
\(U^{(1)}_1(r)\subset U_1(r)\);
-
2.
\(U_1(r)\) and \(U^{(i)}_1(r)\), \(i=2,3,4,5\), are pairwise disjoint;
-
3.
\(V^{(1)}_2(s)\subset V_2(s)\);
-
4.
\(V_2(s)\) and \(V^{(i)}_2(s)\), \(i=1,3,4,5\), are pairwise disjoint.
Proof
By definition, \(U^{(1)}_1(r)\subset U_1(r)\). \(U_1(r)\) and \(U^{(2)}_1(r)\) are disjoint by excluding bad keys of (C-9); \(U_1(r)\) and \(U^{(3)}_1(r)\) are disjoint since \(\mathcal {Q}^{(1)}\) and \(\mathcal {Q}^{(3)}\) are disjoint; \(U_1(r)\) and \(U^{(4)}_1(r)\) are disjoint by excluding bad keys of (C-12); \(U^{(2)}_1(r)\) and \(U^{(3)}_1(r)\) are disjoint by excluding bad keys of (C-13); \(U^{(2)}_1(r)\) and \(U^{(4)}_1(r)\) are disjoint by excluding bad keys of (C-13) and since \(\mathcal {Q}^{(2)}\) and \(\mathcal {Q}^{(4)}\) are disjoint; \(U^{(3)}_1(r)\) and \(U^{(4)}_1(r)\) are disjoint by excluding bad keys of (C-6). Since \(\mathcal {Q}^{(1)}\cup \mathcal {Q}^{(2)}\cup \mathcal {Q}^{(3)}\cup \mathcal {Q}^{(4)}\) and \(\mathcal {Q}^{(5)}\) are disjoint, \(U^{(1)}_1(r)\cup U^{(2)}_1(r)\cup U^{(3)}_1(r)\cup U^{(4)}_1(r)\) and \(U^{(5)}_1(r)\) are also disjoint. The remaining properties are proved similarly. \(\square \)
Property 3
For \(r,s \in \{0,1\} ^m\), one has
-
1.
\(|U_1(r)|=|V_1(r)|=p_{r,*}\);
-
2.
\(|U_2(s)|=|V_2(s)|=p_{*,s}\);
-
3.
\(|U^{(i)}_1(r)|=q^{(i)}_{r,*}\) for \(i=2,4,5\);
-
4.
\(|V^{(i)}_2(s)|=q^{(i)}_{*,s}\) for \(i=1,3,5\).
Proof
It is straightforward to prove the first two properties. Every \((k, l, u, v, \varDelta ) \in \mathcal {Q}^{(2)}_{r, *}\) (resp. \(\mathcal {Q}^{(4)}_{r,*}\)) contains a distinct u since otherwise we would find queries satisfying (C-13) (resp. (C-6)), which implies \(|U^{(2)}_1(r)| = q^{(2)}_{r,*}\) (resp. \(|U^{(4)}_1(r)| = q^{(4)}_{r,*}\)). We also have \(|U^{(5)}_1(r)| = q^{(5)}_{r,*}\) since \(\mathcal {Q}^{(5)}\) and \(\mathcal {Q}^{(3)}\) are disjoint. The last property is proved similarly. \(\square \)
We define \(a^{(3)}_{r,*}=|U^{(3)}_1(r)|\) and \(a^{(4)}_{*,s}=|V^{(4)}_2(s)|\).
Property 4
For \(r,s \in \{0,1\} ^m\) and \(d\in \{0,1\} ^n\), one has
-
1.
\(p_{r,*} \ge q^{(1)}_{r,s,d}\);
-
2.
\(p_{*,s} \ge q^{(2)}_{r,s,d}\);
-
3.
\(a^{(3)}_{r,*} \ge q^{(3)}_{r,s,d}\);
-
4.
\(a^{(4)}_{*,s} \ge q^{(4)}_{r,s,d}\).
Proof
Every \((k, l, u, v, \varDelta ) \in \mathcal {Q}^{(1)}_{r,s,d}\) contains a distinct u since otherwise we would find queries satisfying (C-7). Therefore we have \(p_{r,*}=|U_1(r)| \ge q^{(1)}_{r,s,d}\). The other properties are proved similarly. \(\square \)
For a subset \(\mathcal {Q}\subset \overline{\mathcal {Q}_C}\), we will write \((E_1,E_2) \vdash \mathcal {Q}\) if
for every \((k,l,u,v,\varDelta ) \in \mathcal {Q}\). With this notation, let
Then we have
3.3.2 Computing \(\mathsf {p}_1\)
Suppose that \((k,l,u,v,\varDelta )\in \mathcal {Q}^{(1)}\). It means that \(E_1(k,u)\) has been already determined by \(\mathcal {Q}_{E_1}\). In order for \((E_1,E_2)\) to complete this query, \(E_2\) should map \(E_1(k,u)\oplus \varDelta \) to v with key l. In this situation, the following properties are noteworthy.
-
1.
Not either \(E_2^{-1}(l,v)\) or \(E_2(l,E_1(k,u)\oplus \varDelta )\) has been determined by \(\mathcal {Q}_{E_2}\) since \(\mathbf {k}\) does not satisfy either (C-9) or (C-10).
-
2.
There is no collision on the input to \(E_2\) by the queries of \(\mathcal {Q}^{(1)}\); precisely, for any \((k,l,u,v,\varDelta )\), \((k',l',u',v',\varDelta ')\in ^{\ne }\mathcal {Q}^{(1)}\) such that \(l=l'\), we have \(E_1(k,u)\oplus \varDelta \ne E_1(k',u')\oplus \varDelta '\) since \(\mathbf {k}\) does not satisfy (C-2).
-
3.
There is no collision on the output from \(E_2\) by any other query of \(\overline{\mathcal {Q}_C}\); precisely, for any distinct queries \((k,l,u,v,\varDelta )\in \mathcal {Q}^{(1)}\) and \((k',l',u',v',\varDelta ')\in \overline{\mathcal {Q}_C}\) such that \(l=l'\), we have \(v\ne v'\) since \(\mathbf {k}\) does not satisfy (C-12).
For a fixed \(s\in \{0,1\} ^m\), \(\mathcal {Q}_{E_2}\) determines \(p_{*,s}\) evaluations of \(E_2(s,\cdot )\). On the other hand, the number of queries \((k,l,u,v,\varDelta )\in \mathcal {Q}^{(1)}\) such that \(l=s\) is \(q^{(1)}_{*,s}\) (by definition). Such queries determine all different inputs and outputs of \(E_2(s,\cdot )\), so \(E_2(s,\cdot )\) would complete the queries with probability \(1/(N - p_{*,s})_{q^{(1)}_{*,s}}\). Therefore we have
Applying a similar argument to \(\mathcal {Q}^{(2)}\) (excluding bad key satisfying (C-3), (C-9), (C-11) or (C-13)), we have
3.3.3 Computing \(\mathsf {p}_2\)
Subject to
we will lower bound the probability of completing the reduced queries of \(\mathcal {Q}^{(3)}\cup \mathcal {Q}^{(4)}\) when extending the evaluations of \(E_1\) and \(E_2\). For \(r,s\in \{0,1\} ^m\), we can fix
Property 5
For any \(r\in \{0,1\} ^m\) such that \(U^{(3)}_1(r)\ne \emptyset \), \(|V_1(r)\cup V^{(2)}_1(r)|<N/2\).
Proof
We distinguish two cases.
-
Case (1)
There exists no tweak \(w\in \mathcal {T}^*\) such that \(h_1(w)=r\). In this case,
-
(i)
\(|V_1(r)|< N/4\) since we have modified the adversary so that the number of block cipher queries is either N or less than N / 4 (for any fixed key), and \(U_1^{(3)}(r)\) being nonempty implies that the number of block cipher queries cannot be N, and
-
(ii)
\(|V_1^{(2)}(r)|< N/4\) since we are excluding bad keys of (C-14) (with no tweak w in \(\mathcal {T}^*\) such that \(h_1(w)=r\)).
Therefore we have
$$\begin{aligned} |V_1(r)\cup V^{(2)}_1(r)|\le |V_1(r)|+|V^{(2)}_1(r)|<\frac{N}{4}+\frac{N}{4}=\frac{N}{2}. \end{aligned}$$ -
(i)
-
Case (2)
There exists \(w\in \mathcal {T}^*\) such that \(h_1(w)=r\); we again distinguish three cases. Let \(s=h_2(w)\).
-
(i)
\(|\mathcal {Q}_{E_1}(r)|=N\); we have \(U_1(r)= \{0,1\} ^n\), and hence \(U^{(3)}_1(r)=\emptyset \).
-
(ii)
\(|\mathcal {Q}_{E_2}(s)|=N\); since \(w\in \mathcal {T}^*\), all possible N construction queries are made with tweak w, and they are all contained in \(\mathcal {Q}^{(2)}\) since \(|\mathcal {Q}_{E_2}(s)|=N\) for \(s=h_2(w)\). This means that \(U_1^{(2)}(r)= \{0,1\} ^n\). Since \(U_1^{(2)}(r)\) and \(U_1^{(3)}(r)\) are disjoint by Property 2, we have \(U^{(3)}_1(r)=\emptyset \).
-
(iii)
\(|\mathcal {Q}_{E_1}(r)|, |\mathcal {Q}_{E_2}(s)|<N/4\); there is no query \((k,l,u,v,\varDelta )\in \mathcal {Q}^{(2)}\) such that \(k=r\) and \(l\ne s\) since otherwise we will see queries satisfying (C-13). Therefore \(|V^{(2)}_1(r)|\) counts the number of queries \((k,l,u,v,\varDelta )\in \mathcal {Q}^{(2)}\) such that \(k=r\) and \(l=s\). Such queries correspond to queries in \(\mathcal {Q}_{E_2}(s)\), where \(|\mathcal {Q}_{E_2}(s)|<N/4\). Since \(|V_1(r)|\le |\mathcal {Q}_{E_1}(r)|<N/4\), we have \(|V_1(r)\cup V^{(2)}_1(r)|<N/2\). \(\square \)
-
(i)
Similarly, we can prove the following property.
Property 6
For any \(s\in \{0,1\} ^m\) such that \(V^{(4)}_2(s)\ne \emptyset \), \(|U_2(s)\cup U^{(1)}_2(s)|<N/2\).
In order to estimate the probability that \(E_1\) and \(E_2\) complete \(\mathcal {Q}^{(3)} \cup \mathcal {Q}^{(4)}\), we will choose an (ordered) set of \(a^{(3)}_{r,*}\)( = \(|U^{(3)}_1(r)|\)) elements, denoted \(V^{(3)}_1(r)\), from \( \{0,1\} ^n\setminus (V_1(r)\cup V^{(2)}_1(r))\) for each \(r\in \{0,1\} ^m\). Once \(V^{(3)}_1(r)\) is chosen, we will compute the probability that the queries of \(\mathcal {Q}^{(3)}\) are completed satisfying \(E_1(r,U^{(3)}_1(r))=V^{(3)}_1(r)\).Footnote 2 Similarly, for each \(s\in \{0,1\} ^m\), we will choose a set of \(a^{(4)}_{*,s}\) elements, denoted \(U^{(4)}_2(s)\), from \( \{0,1\} ^n\setminus (U_2(s)\cup U^{(1)}_2(s))\), and compute the probability that the queries of \(\mathcal {Q}^{(4)}\) are completed via the elements of \(U^{(4)}_2(s)\) (as \(E_2^{-1}(l, v)\)).
Without any restriction, the number of ways of choosing \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\) (over all the keys r, \(s\in \{0,1\} ^m\)) would be
However, in order to make the analysis simpler, we will avoid certain bad conditions when choosing \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\); suppose that y has been chosen as \(E_1(r,u)\) from \( \{0,1\} ^n\setminus (V_1(r)\cup V^{(2)}_1(r))\) for a query \((r,s,u,v,\varDelta )\in \mathcal {Q}^{(3)}\). In order for \(E_2\) complete this query, one should have \(E_2(s,y\oplus \varDelta )=v\). Here we would like the element \(y\oplus \varDelta \) to be “free”, namely to lie outside \(U_2(s)\cup U^{(1)}_2(s)\cup U^{(4)}_2(s)\). We would also like the elements \(y\oplus \varDelta \) to be all distinct for each key of \(E_2\). Similarly, for each element x that has been chosen as \(E_2^{-1}(s,v)\) for a query \((r,s,u,v,\varDelta )\in \mathcal {Q}^{(4)}\), we would like \(x\oplus \varDelta \) to be outside \(V_1(r)\cup V^{(2)}_1(r)\cup V^{(3)}_1(r)\). For each key of \(E_1\), there should be no collision between \(x\oplus \varDelta \). More precisely, the undesirable “colliding” events can be classified as follows.Footnote 3
Property 7
The probabilities of \(\mathsf {Col}_i\), \(i=1,\ldots , 8\), (over random choices of \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\)) are all upper bounded by \(2M_2/N\).
Proof
To estimate the probability of \(\mathsf {Col}_3\), consider pairs of distinct queries \((k, l, u, v, \varDelta )\), \((k', l', u', v', \varDelta ')\in \mathcal {Q}^{(3)}\) such that \(l=l'\). The set of such pairs can be partitioned into the following two types;
-
1.
there exists a query \((k'', l'', u'', v'', \varDelta '')\) such that \((k'',u'')=(k,u)\) and
$$(k'', l'', u'', v'', \varDelta '')\notin \{(k, l, u, v, \varDelta ), (k', l', u', v', \varDelta ')\};$$ -
2.
there exists no query \((k'', l'', u'', v'', \varDelta '')\) such that \((k'',u'')=(k,u)\) and
$$(k'', l'', u'', v'', \varDelta '')\notin \{(k, l, u, v, \varDelta ), (k', l', u', v', \varDelta ')\}.$$
Since \((k, l, u, v, \varDelta )\in \mathcal {Q}^{(3)}\), one always has a query \((k^*, l^*, u^*, v^*, \varDelta ^*)\) such that \((k^*,u^*)=(k,u)\) and \((k^*, l^*, u^*, v^*, \varDelta ^*)\ne (k, l, u, v, \varDelta )\), so if a pair of queries falls into the second type, then it means that \((k^*, l^*, u^*, v^*, \varDelta ^*)=(k', l', u', v', \varDelta ')\), and hence \((k,l,u)=(k',l',u')\). Then by excluding bad keys of (C-7), we have \(\varDelta \ne \varDelta '\). So for any pair of queries of the second type, it cannot be the case that \(E_1(k, u) \oplus \varDelta = E_1(k', u') \oplus \varDelta '\). On the other hand, the number of the pairs of the first type is upper bounded by \(|\mathcal {B}_1|\), which is smaller than \(M_2\) by excluding bad keys of (C-4). For each pair, the probability that \(E_1(k, u) \oplus \varDelta = E_1(k', u') \oplus \varDelta '\) is upper bounded by 2 / N (since \(| \{0,1\} ^n\setminus (V_1(r)\cup V^{(2)}_1(r))|>N/2\) by Property 5). Therefore, we have
The other bounds are proved similarly. \(\square \)
The number of ways of choosing \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\) over all \(r, s\in \{0,1\} ^m\), without fulfilling any of the bad conditions \(\mathsf {Col}_i\), \(i=1,\ldots ,8\), is lower bounded by
For each of “good” choices for \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\), \((E_1, E_2)\) complete the queries of \(\mathcal {Q}^{(3)}\) and \(\mathcal {Q}^{(4)}\) (via \(V^{(3)}_1(r)\) and \(U^{(4)}_2(s)\), respectively) with probability
By (6), (7) and Property 7, we have
3.3.4 Computing \(\mathsf {p}_3\)
Subject to
we can fix
evaluations of \(E_1(r, \cdot )\) and
evaluations of \(E_2(s, \cdot )\) for each \((r,s) \in \{0,1\} ^m\times \{0,1\} ^m\). Let
Let
and let \(\mathcal {R}'= \{0,1\} ^m \setminus \mathcal {R}\) and \(\mathcal {S}'= \{0,1\} ^m \setminus \mathcal {S}\).
Property 8
With the above definitions, the following hold:
-
1.
\(\mathcal {Q}^{(5)}\) is partitioned into \(\mathcal {Q}^{(5)}_1\) and \(\mathcal {Q}^{(5)}_2\), namely, \(\mathcal {Q}^{(5)}=\mathcal {Q}^{(5)}_1\sqcup \mathcal {Q}^{(5)}_2\);
-
2.
\(\mathcal {Q}^{(5)}_1=\bigsqcup \limits _{(r,s)\in \mathcal {R}\times \mathcal {S}}\mathcal {Q}^{(5)}_{r,s}\);
-
3.
\(\mathcal {Q}^{(5)}_2=\bigsqcup \limits _{(r,s)\in \mathcal {R}'\times \mathcal {S}'}\mathcal {Q}^{(5)}_{r,s}\);
-
4.
\(\mathcal {Q}^{(5)}_{r,s}=\emptyset \) for \((r,s)\notin (\mathcal {R}\times \mathcal {S}) \cup (\mathcal {R}'\times \mathcal {S}')\).
Proof
By definition, we have
Therefore it is obvious that \(\mathcal {Q}^{(5)}_1\) and \(\mathcal {Q}^{(5)}_2\) are disjoint. If \((r,s,u,v,\varDelta )\in \mathcal {Q}^{(5)}\setminus \mathcal {Q}^{(5)}_2\), then it should be the case that either \(r=h_1(t)\) or \(s=h_2(t)\) for some \(t\in \mathcal {T}^*\); if \(r=h_1(t)\) for some \(t\in \mathcal {T}^*\), then we would have a query \((r',s',u',v',\varDelta ')\in \overline{\mathcal {Q}_C}\) such that \(u'=u\), \(r'=h_1(t)=r\) and \(s'=h_2(t)\). Since \(\mathcal {Q}^{(5)}\) is disjoint from \(\mathcal {Q}^{(3)}\), it must be the case that \((r',s',u',v',\varDelta ')=(r,s,u,v,\varDelta )\). Since \(r=r'=h_1(t)\) and \(s=s'=h_2(t)\), we have \((r,s,u,v,\varDelta )\in \mathcal {Q}^{(5)}_1\). With a similar argument for the case that \(s=h_2(t)\) for some \(t\in \mathcal {T}^*\), we have \(\mathcal {Q}^{(5)}=\mathcal {Q}^{(5)}_1\sqcup \mathcal {Q}^{(5)}_2\). The remaining properties are immediate from the first one (combined with the observation (12)). \(\square \)
Let
where both probabilities are conditioned on (9). Then by Property 8, we have
Computing. \(\mathsf {p}'_3\). We begin with the following property.
Property 9
For \((r,s)\in \mathcal {R}\times \mathcal {S}\), one has
-
1.
\(q^{(1)}_{r,*}=q^{(1)}_{*,s} = q^{(1)}_{r,s} = p_{r,*}\);
-
2.
\(q^{(2)}_{r,*} = q^{(2)}_{*,s} = q^{(2)}_{r,s} = p_{*,s}\);
-
3.
\(q^{(3)}_{*,s} = a^{(3)}_{r,*}= q^{(3)}_{r,s}\);
-
4.
\(q^{(4)}_{r,*} = a^{(4)}_{*,s}= q^{(4)}_{r,s}\);
-
5.
\(q^{(1)}_{r,s} + q^{(2)}_{r,s}+ q^{(3)}_{r,s} + q^{(4)}_{r,s} + q^{(5)}_{r,s}=N\);
-
6.
\(b_r=c_s=N-q^{(5)}_{r,s}\).
Proof
Define a function
Since \(r=h_1(t)\) for some \(t\in \mathcal {T}^*\), \(\phi \) is surjective. Suppose that \((k,l,u,v,\varDelta )\ne (k',l',u',v',\varDelta ')\in \mathcal {Q}^{(1)}_{r,s}\) with \((k,l)=(k',l')=(r,s)\) and \(u=u'\). If their original queries contain an identical tweak in \(\mathcal {T}\), then we have \(\varDelta =\varDelta '\), which is a contradiction since we are excluding bad keys of (C-7). If their original queries contain different tweaks in \(\mathcal {T}\), then we would be able to find queries satisfying (C-6). So \(\phi \) is injective. This implies that \(q^{(1)}_{r,s} = p_{r,*}\). Since \(U^{(1)}_1(r)=U_1(r)\), we also have \(q^{(1)}_{r,*} = p_{r,*}\). Furthermore, for any \(r' \in \{0,1\} ^m\) such that \(r' \ne r\), we have \(q^{(1)}_{r',s} = 0\) since otherwise we could find queries satisfying (C-12). So we have \(q^{(1)}_{*,s} = q^{(1)}_{r,s}\). The second property is proved similarly.
Define a function
Since \(s=h_2(t)\) for some \(t\in \mathcal {T}^*\), \(\psi \) is surjective. Suppose that \((k,l,u,v,\varDelta )\ne (k',l',u',v',\varDelta ')\in \mathcal {Q}^{(3)}_{r,s}\) with \((k,l)=(k',l')=(r,s)\) and \(u=u'\). If their original queries contain an identical tweak in \(\mathcal {T}\), then we have \(\varDelta =\varDelta '\), which is a contradiction since we are excluding bad keys of (C-7). If their original queries contain different tweaks in \(\mathcal {T}\), then we would be able to find queries satisfying (C-6). So \(\phi \) is injective. This implies that \(q^{(3)}_{*,s} = a^{(3)}_{r,*}\). Furthermore, for any \(r' \in \{0,1\} ^m\) such that \(r' \ne r\), we have \(q^{(3)}_{r',s} = 0\) since otherwise we could find queries satisfying (C-12). So we have \(q^{(3)}_{*,s} = q^{(3)}_{r,s}\). The remaining properties are proved similarly. \(\square \)
Fix \((r,s)\in \mathcal {R}\times \mathcal {S}\). If \(q^{(5)}_{r, s}=0\), then we have \(N-b_r=0\). If \(q^{(5)}_{r, s}>0\), then there would exist \(w\in \mathcal {T}^*\) such that \(r=h_1(w)\) and \(s=h_2(w)\), and \(E_1(r,\cdot )\) and \(E_2(s,\cdot )\) might complete the queries in \(\mathcal {Q}^{(5)}_{r,s}\) that contain w (in their original forms). In this case, it cannot be the case that either \(r\ne h_1(w')\) or \(s\ne h_2(w')\) for any \(w'\in \mathcal {T}^*\) such that \(w'\ne w\) since the existence of such a tweak would imply \(\mathcal {Q}^{(5)}_{r,s}=\emptyset \). Note that
where \(\varDelta =g_1(w)\oplus g_2(w)\), and \(q^{(5)}_{r, s} = N - b_r =N - c_s\). So the probability that \(E_1(r, \cdot )\) and \(E_2(s,\cdot )\) complete all the queries of \(\mathcal {Q}^{(5)}_{r,s}\) is \(1/(N - b_r)!\), and hence
Computing. \(\mathsf {p}''_3\). We first fix a lexicographical order on \(\mathcal {R}'\times \mathcal {S}' \times \{0,1\} ^n\); \((r,s,d)<(r',s',d')\) if and only if \(r<r'\) or (\(r=r'\) and \(s<s'\)) or (\(r=r'\), \(s=s'\) and \(d<d'\)).
Next, we fix \((r,s,d)\in \mathcal {R}'\times \mathcal {S}'\times \{0,1\} ^n\), and suppose that \(E_1\) and \(E_2\) have completed all the queries of \(\mathcal {Q}^{(5)}_{r',s',d'}\) for \((r',s',d')<(r,s,d)\). Subject to this event, let
be the set of all elements y for which \(E_1^{-1}(r, y)\) have been determined, and the set of all elements y for which \(E_2(s, y\oplus d)\) have been determined, respectively. We will choose an (ordered) set of \(q^{(5)}_{r,s,d}\) elements, denoted Y, from \( \{0,1\} ^n\setminus (B_{r,s,d}\cup C_{r,s,d})\) and consider the probability that each \((r,s,u,v,d) \in \mathcal {Q}^{(5)}_{r,s,d}\) is completed with \(E_1(r,u)=y\) and \(E_2(s,y\oplus d)=v\) for a distinct \(y\in Y\).
Let \(b_{r,s,d} = |B_{r,s,d}|\) and \(c_{r,s,d} = |C_{r,s,d}|\). Then we have
Define a function
where \(E_1(k,u)\) has already been determined. Suppose that \((k,l,u,v,\varDelta )\) and \((k',l',u',v',\varDelta ')\) are mapped to the same \(E_1(k,u)=E_1(k',u')\). Since both queries are contained in \(\bigsqcup _{i=1}^4\mathcal {Q}^{(i)}_{r,s,d}\), we have \((k,l,\varDelta )=(k',l',\varDelta ')=(r,s,d)\). It implies that \(u=u'\) and \(v=E_2(l,E_1(k,u)\oplus \varDelta )=E_2(l',E_1(k',u')\oplus \varDelta ')=v'\), and hence \((k,l,u,v,\varDelta )=(k',l',u',v',\varDelta ')\). So we see that \(\phi \) is injective. Therefore we have
where
Overall, the number of ways of choosing Y so that \(E^{-1}_1(r,y)\) and \(E_2(s,y\oplus d)\) have not been determined for any \(y \in Y\) is at least
Property 10
For \((r,s,d)\in \mathcal {R}'\times \mathcal {S}'\times \{0,1\} ^n\) such that \(\mathcal {Q}^{(5)}_{r,s,d}\ne \emptyset \), one has
-
1.
\(q^{(5)}_{r,s,d} + b_{r,s,d} < N/2\);
-
2.
\(q^{(5)}_{r,s,d} + c_{r,s,d} < N/2\).
Proof
Note that
where \(p_{r,*}<N/4\) (since \(\mathcal {Q}^{(5)}_{r,s,d}\ne \emptyset \)), and the sum of the remaining summands is upper bounded by the number of queries \((k,l,u,v,\varDelta )\) such that \(k=r\), which is smaller than N / 4 since there is no tweak \(t\in \mathcal {T}^*\) such that \(r=h_1(t)\) and by excluding bad keys of (C-14). Therefore we have \(q^{(5)}_{r,s,d} + b_{r,s,d} < N/2\). The second property is proved similarly. \(\square \)
Thanks to Property 10, we can apply Lemma 1 to lower bound the probability that \(E_1\) and \(E_2\) complete the queries of \(\mathcal {Q}^{(5)}_{r,s,d}\) by
Therefore we have
By replacing \((b_{r,s,d} - e_{r,s,d})\) and \((c_{r,s,d} - e_{r,s,d})\) by \((p_{r,*} + (b_{r,s,d} - p_{r,*} - e_{r,s,d}))\) and \((p_{*,s}+(c_{r,s,d}-p_{*,s} - e_{r,s,d}))\), respectively, we have
Each term of (17) is upper bounded as follows.
Property 11
One has the following upper bounds:
-
1.
\(\sum \limits _{\begin{array}{c} (r, s) \in \mathcal {R}'\times \mathcal {S}'\\ d \in \{0,1\} ^n \end{array}}q^{(5)}_{r,s,d} p_{r,*} p_{*,s}\le M_3\);
-
2.
\(\sum \limits _{\begin{array}{c} (r, s) \in \mathcal {R}'\times \mathcal {S}'\\ d \in \{0,1\} ^n \end{array}}q^{(5)}_{r,s,d} (b_{r,s,d} - p_{r,*} - e_{r,s,d}) p_{*,s}\le M_3\);
-
3.
\(\sum \limits _{\begin{array}{c} (r, s) \in \mathcal {R}'\times \mathcal {S}'\\ d \in \{0,1\} ^n \end{array}}q^{(5)}_{r,s,d} (c_{r,s,d} - p_{*,s} - e_{r,s,d}) p_{r,*}\le M_3\);
-
4.
\(\sum \limits _{\begin{array}{c} (r, s) \in \mathcal {R}'\times \mathcal {S}'\\ d \in \{0,1\} ^n \end{array}}q^{(5)}_{r,s,d} (b_{r,s,d} - p_{r,*} - e_{r,s,d})(c_{r,s,d} - p_{*,s} - e_{r,s,d})\le M_3\).
Proof
We will prove the third upper bound; the other bounds are proved similarly.
Consider
A triple of queries from this set corresponds to a triple
(in their original forms) such that \(t \ne t'\), \(h_2(t)= h_2(t')\) and \(h_1(t) = k\). (Note that if two queries (r, s, u, v, d) and \((r',s',u',v',d')\) share a common tweak, then we would have \((r,s,d)=(r',s',d')\).) Since such a triple is contained in \(\mathcal {C}_2\) and \(|\mathcal {C}_2|\le M_3\) by excluding bad keys of (C-5), the size of this set is also upper bounded by \(M_3\).
For \((r, s) \in \mathcal {R}'\times \mathcal {S}'\) and \(d \in \{0,1\} ^n\), we have
Therefore we have
\(\square \)
By (17) and Property 11, we have
and by plugging it into (16), we obtain
3.3.5 Lower Bounding the Ratio
For each \((r,s,d)\in \{0,1\} ^m\times \{0,1\} ^m\times \{0,1\} ^n\), let
Then we have a partition of \(\mathcal {T}\), namely,
Since \(\sum _{w\in \mathcal {T}(r,s,d)}q_w=q^{(1)}_{r,s,d}+q^{(2)}_{r,s,d}+q^{(3)}_{r,s,d}+q^{(4)}_{r,s,d}+q^{(5)}_{r,s,d}\), we have
By (4), (5), (8), (13), (14), (15), (18), (19), we can prove
which completes the proof of Lemma 4. The detailed computation will be given in the full version of this paper.
3.4 Putting the Pieces Together
Theorem 1 follows from (1), Lemma 2, Lemma 3 and Lemma 4 with
Notes
- 1.
This assumption is similar to the study of key length extension, where the key size of the entire scheme is sometimes larger than the input size of the underlying block cipher.
- 2.
\(U^{(3)}_1(r)\) and \(V^{(3)}_1(r)\) are viewed as ordered sets, and \(E_1(r,U^{(3)}_1(r))=V^{(3)}_1(r)\) means that each element of \(U^{(3)}_1(r)\) is mapped to the corresponding element of \(V^{(3)}_1(r)\) (with respect to the ordering) under \(E_1(r,\cdot )\).
- 3.
For \((k, l, u, v, \varDelta )\in \mathcal {Q}^{(3)}\cup \mathcal {Q}^{(4)}\), we will write \(E_1(k,u)\) and \(E^{-1}_2(l,v)\) to denote the elements determined by the choice of \(V^{(3)}_1(k)\) and \(U^{(4)}_2(l)\), respectively.
References
Adams, C.M.: Constructing symmetric ciphers using the CAST design procedure. Des. Codes Cryptogr. 12(3), 283–316 (1997)
De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN — a family of small and efficient hardware-oriented block ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_20
Cogliati, B., Lampe, R., Seurin, Y.: Tweaking even-mansour ciphers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 189–208. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_9
Crowley, P.: Mercy: a fast large block cipher for disk sector encryption. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 49–63. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_4
Ferguson, N., et al.: The skein hash function family. In: Submission to NIST (round 3), 7(7.5), 3 (2010)
Jean, J., Nikolić, I., Peyrin, T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 274–288. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_15
Jha, A., Mishra, S., List, E., Minematsu, K., Nandi, M.: XHX - a framework for optimally secure tweakable block ciphers from classical block ciphers and universal hashing. In: Latincrypt (2017, to appear). https://eprint.iacr.org/2017/1075.pdf
Landecker, W., Shrimpton, T., Terashima, R.S.: Tweakable blockciphers with beyond birthday-bound security. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 14–30. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_2
Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_3
Mennink, B.: Optimally secure tweakable blockciphers. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 428–448. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_21
Mennink, B.: XPX: generalized tweakable even-mansour with improved security guarantees. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 64–94. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_3
Minematsu, K.: Beyond-birthday-bound security based on tweakable block cipher. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 308–326. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03317-9_19
Minematsu, K., Iwata, T.: Tweak-length extension for tweakable blockciphers. In: Groth, J. (ed.) IMACC 2015. LNCS, vol. 9496, pp. 77–93. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27239-9_5
Naito, Y.: Tweakable blockciphers for efficient authenticated encryptions with beyond the birthday-bound security. IACR Trans. Symmetric Cryptol. 2017(2), 1–26 (2017)
Peyrin, T., Seurin, Y.: Counter-in-Tweak: authenticated encryption modes for tweakable block ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 33–63. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_2
Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30539-2_2
Schroeppel, R., Orman, H.: The hasty pudding cipher. In: AES Candidate Submitted to NIST, p. M1 (1998)
Wang, L., Guo, J., Zhang, G., Zhao, J., Gu, D.: How to build fully secure tweakable blockciphers from classical blockciphers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 455–483. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_17
Yang, G., Zhu, B., Suder, V., Aagaard, M.D., Gong, G.: The Simeck family of lightweight block ciphers. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 307–329. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48324-4_16
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 International Association for Cryptologic Research
About this paper
Cite this paper
Lee, B., Lee, J. (2018). Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model. In: Peyrin, T., Galbraith, S. (eds) Advances in Cryptology – ASIACRYPT 2018. ASIACRYPT 2018. Lecture Notes in Computer Science(), vol 11272. Springer, Cham. https://doi.org/10.1007/978-3-030-03326-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-03326-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03325-5
Online ISBN: 978-3-030-03326-2
eBook Packages: Computer ScienceComputer Science (R0)