# Re-Keying Scheme Revisited: Security Model and Instantiations
## 2 Preliminaries  
### Block Cipher  
The block cipher is a fundamental tool used for secure communication. It is also a building block of the re-keying scheme in the latter. Let us start with a review of a pseudo-random function, and then, we will review the definitions of the secure block cipher.  
**Definition 1**.: _Let \(\Phi\) be a family of functions with \(\ell_{n}\)-bit input and \(\ell_{m}\)-bit output. We say that \(\mathsf{g}(\cdot,\cdot)\) is a pseudo-random function with \(\ell_{n}\)-bit input and \(\ell_{m}\)-bit output parameterized by an \(\ell_{k}\)-bit key \(k\), if the advantage \(\mathsf{Adv}\) below is negligible for any polynomial time adversary \(\mathcal{A}\) who makes oracle queries to either \(\mathsf{g}(k,\cdot)\) or \(\varphi\in\Phi\) up to \(q\) times:_  
\[\mathsf{Adv}:=\max_{\mathcal{A}}|\Pr[\mathbf{Exp}_{\mathsf{g},\mathcal{A}}^{ \textit{real}}=1]-\Pr[\mathbf{Exp}_{\mathsf{g},\mathcal{A}}^{\textit{rand}}=1]|,\]  
_where experiments \(\mathbf{Exp}_{\mathsf{g},\mathcal{A}}^{\textit{real}}\) and \(\mathbf{Exp}_{\mathsf{g},\mathcal{A}}^{\textit{rand}}\) are as in Figure 1. In these experiments, \(\mathcal{O}_{\mathsf{g}}(k,\cdot)\) and \(\mathcal{O}_{\varphi}(\cdot)\) are oracles, which, with \(\ell_{n}\)-bit input \(x\), return \(\mathsf{g}(k,x)\) and \(\varphi(x)\), respectively._  
**Definition 2**.: _Let \(\Pi\) be a family of \(\ell_{n}\)-bit permutations. We say that \((\mathsf{BC},\mathsf{BC}^{-1})\) is a pair of \(\ell_{n}\)-bit pseudo-random permutations parameterized by an \(\ell_{k}\)-bit key \(k\), if the advantage \(\mathsf{Adv}\) below is negligible for any polynomial time adversary \(\mathcal{A}\) who makes oracle queries, with an \(\ell_{n}\)-bit input (plaintext), to either \(\mathsf{BC}\) or \(\pi\in\Pi\) up to \(q\) times._  
\[\mathsf{Adv} := \max_{\mathcal{A}}|\Pr[\mathbf{Exp}_{\mathsf{BC},\mathcal{A}}^{ \textit{real}}=1]-\Pr[\mathbf{Exp}_{\mathsf{BC},\mathcal{A}}^{\textit{rand}}=1]|\]  
_where experiments \(\mathbf{Exp}_{\mathsf{BC},\mathcal{A}}^{\textit{real}}\) and \(\mathbf{Exp}_{\mathsf{BC},\mathcal{A}}^{\textit{rand}}\) are as in Figure 2. In these experiments, \(\mathcal{O}_{\mathsf{BC}}(k,\cdot)\) and \(\mathcal{O}_{\pi}(\cdot)\) are oracles, which, with \(\ell_{n}\)-bit input \(x\), return the ciphertext \(\mathsf{BC}(k,x)\) and \(\pi(x)\), respectively._  
Figure 1: Experiments for a pseudo-random function.  
Similarly, we say that \((\mathsf{BC},\mathsf{BC}^{-1})\) is a strong pseudo-random permutation, if the advantage is negligible even if \(\mathcal{A}\) allows making oracle queries, with an \(\ell_{n}\) bit input (plaintext or ciphertext), to either \((\pi,\pi^{-1})\) or \((\mathsf{BC},\mathsf{BC}^{-1})\), up to \(q\) times in total.  
Definition 3: Let \(\Pi\) be a family of \(\ell_{n}\)-bit permutations. We say that \((\mathsf{BC},\mathsf{BC}^{-1})\) is a pair of \(\ell_{n}\)-bit pseudo-random permutations_ against related key attacks _parameterized by an \(\ell_{k}\)-bit key \(k\), if the advantage \(\mathsf{Adv}\) below is negligible for any polynomial time adversary \(\mathcal{A}\) who makes oracle queries to either \(\mathcal{O}_{\mathsf{BC}}\) or \(\mathcal{O}_{\Pi}\) up to \(q\) times.  
\[\mathsf{Adv} := \max_{\mathcal{A}}|\Pr[\mathbf{Exp}_{\mathsf{BC},\mathcal{A}_{ nk}}^{\text{real}}=1]-\Pr[\mathbf{Exp}_{\mathsf{BC},\mathcal{A}_{nk}}^{\text{rand}}=1]|\]  
where experiments \(\mathbf{Exp}_{\mathsf{BC},\mathcal{A}_{nk}}^{\text{real}}\mathbf{Exp}_{ \mathsf{BC},\mathcal{A}_{nk}}^{\text{rand}}\) are as in Figure 3. Within them, \(\mathcal{O}_{\mathsf{BC}}(k,\cdot,\cdot)\) and \(\mathcal{O}_{\Pi}(l,\cdot,\cdot)\), given a difference \(\Delta\in\{0,1\}^{\ell_{k}}\) and a plaintext \(m\) from \(\mathcal{A}_{rk}\), return \(\mathcal{O}_{\mathsf{BC}}(k,\Delta,m)=\mathsf{BC}(k\oplus\Delta,m)\) and \(\mathcal{O}_{\Pi}(l,\Delta,m)=\pi(m)\), respectively, where \(\pi\) is chosen from \(\Pi\) in accordance with \(l\oplus\Delta\).  
Similar to Definition 2, we have the notion of strong pseudo-random permutation against the related key attack.