# Re-Keying Scheme Revisited: Security Model and Instantiations
## 2 Preliminaries
### Tweakable Block Cipher  
The tweakable block cipher [8] is a variant of the block cipher. Besides the plaintext and the key, it takes an auxiliary input, called _a tweak_, which acts as an initial vector of the mode of operations [11]. By using different tweaks, ciphertexts differ even though the pair of the plaintext and the key is unique. This property makes the statistical analysis difficult.  
Note that the tweak can be shared between a sender and a receiver in public. For example, the sender may select a tweak at random to send it with a ciphertext; or if both the sender and receiver are stateful and if they share a seed for tweaks, they synchronously compute a tweak without sending it. For simplicity, we assume that the sender sends a tweak along with a ciphertext over the public channel.  
The tweakable block cipher consists of a pair of two algorithms \((\mathsf{TBC},\mathsf{TBC}^{-1})\). The encryption algorithm \(\mathsf{TBC}\) takes, as inputs, a key \(k\), a tweak \(t\), and a plaintext \(m\) with bit lengths \(\ell_{k}\), \(\ell_{t}\), and \(\ell_{n}\), respectively, to output an \(\ell_{n}\)-bit ciphertext \(c\). The decryption algorithm \(\mathsf{TBC}^{-1}\) takes, as inputs, \(k\), \(t\), and \(c\) to recover \(m\). They should satisfy the completeness; namely, \(\mathsf{TBC}^{-1}(k,t,\mathsf{TBC}(k,t,m))=m\) holds for arbitrary \(k\), \(t\), and \(m\). We then review its security model.  
Figure 3: Experiments for the block cipher with related key attack.  
Figure 2: Experiments for the block cipher.  
**Definition 4**.: _Let \(\Pi\) be a family of \(\ell_{n}\)-bit permutations parameterized by an \(\ell_{t}\)-bit tweak. \((\mathsf{TBC},\mathsf{TBC}^{-1})\) is a pair of \(\ell_{n}\)-bit pseudo-random permutations parameterized by an \(\ell_{t}\)-bit tweak and an \(\ell_{k}\)-bit key, if the advantage \(\mathsf{Adv}\) below is negligible for any polynomial time adversary \(\mathcal{A}\) who makes oracle queries, with a tweak and a plaintext, to either \(\mathsf{TBC}\) or \(\Pi\) up to \(q\) times._  
\[\mathsf{Adv} := \max_{\mathcal{A}}|\Pr[\mathbf{Exp}_{\mathsf{TBC},\mathcal{A}}^ {\text{real}}=1]-\Pr[\mathbf{Exp}_{\mathsf{TBC},\mathcal{A}}^{\text{rand}}=1]|\]  
_where experiments \(\mathbf{Exp}_{\mathsf{TBC},\mathcal{A}}^{\text{real}}\), \(\mathbf{Exp}_{\mathsf{TBC},\mathcal{A}}^{\text{rand}}\) are as in Figure 4. Within them, \(\mathcal{O}_{\mathsf{TBC}}(k,\cdot,\cdot)\) and \(\mathcal{O}_{\pi}(\cdot,\cdot)\), given a tweak \(t\) and a plaintext \(m\) from \(\mathcal{A}\), return \(\mathsf{TBC}(k,t,m)\) and \(\pi(t,m)\), respectively._  
_Similar to Definition 2, we have the notion of strong pseudo-random permutation for the tweakable block cipher._  
Note that, unlike the key, the tweaks may be selected in an insecure manner (using the time information or sequential number, for example) and the adversary may control the manner. Especially, as for the (stateless) decryption, the adversary can make oracle queries with arbitrary tweaks of his/her choice. Therefore, the above definitions assume the adversary in the related tweak attack setting, i.e., the open-tweak model [12]. Moreover, similar to the block cipher, the security model can be extended against the related key attacks. The model is similar to Definition 3, and we omit it here.