# Re-Keying Scheme Revisited: Security Model and Instantiations
## 4 Security Model of the Re-Keying Scheme in Considering the SCA  
In this section, we introduce a security model considering the SCA. Except the SCA resistance, the model is similar to that of the tweakable block cipher. Namely, the re-keying scheme is secure if it is indistinguishable from a random function. To take the SCA resistance into consideration, we assume that the encryption and decryption oracles leak the side channel information.  
Unlike the tweakable block cipher, we assume that the encryption device chooses a randomness (which corresponds to the tweak in the tweakable block cipher) uniformly random for each encryption. Hence, we disallow the adversary from choosing it in the encryption oracle query. On the other hand, the decryption device receives the randomness as one of the inputs; therefore, we allow the adversary to choose it in the decryption query.  
Figure 5: [PERSON] et al.’s scheme.  
Figure 6: [PERSON] et al.’s first scheme.  
As for the side channel information, we introduce a leakage function \(\mathcal{L}(\mathsf{BC})\), which returns the leakages (e.g., a power consumption trace) through the block cipher operation. In the real world, the SCAs on the key loading and XORing with the key have been reported. However, there are protection mechanisms to decrease the platform leakage (e.g., for the key loading), and the leakage is small in XORing compared to the complex operations in the block cipher. Hence, we omit them. Moreover, we assume that the re-keying function is properly designed not to leak the side channel information of the key.  
Definition 5: Let \(\Pi\) be a family of \(\ell_{n}\)-bit permutations parameterized by an \(\ell_{r}\)-bit randomness. \((E,E^{-1})\) is a pair of \(\ell_{n}\)-bit pseudo-random permutations parameterized by an \(\ell_{r}\)-bit randomness 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 plaintext, to either \(E\) or \(\Pi\) up to \(q\) times.  
\[\mathsf{Adv} := \max_{\mathcal{A}}|\Pr[\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{ \mbox{real}}=1]-\Pr[\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\mbox{rand}}=1]|\]  
where experiments \(\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\mbox{real}}\), \(\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\mbox{rand}}\) are as in Figure 7. Within them, \(\mathcal{O}_{\mathsf{RK}}(k,R,\cdot)\), given a plaintext \(m\) from \(\mathcal{A}\), returns both \(\mathsf{RK}(k,r,m)\) for a fresh randomness \(r\) chosen by the oracle itself and \(\mathcal{L}(\mathsf{BC}(tk,m))\), where \(tk\) is a session key derived from the re-keying function with \(k\) and \(r\). On the other hand, \(\mathcal{O}_{\Pi}(R,\cdot)\), given a plaintext \(m\) from \(\mathcal{A}\), returns both \(\pi(r,m)\) for a fresh randomness \(r\) chosen by the oracle itself and \(\mathcal{L}(\mathsf{BC}(tk,m^{\prime}))\), where \(tk\) and \(m^{\prime}\) are a session key derived from the re-keying function with \(k\) and \(r\) and an \(\ell_{n}\)-bit random plaintext chosen by the oracle itself, respectively.  
Similar to Definition 2, we have the notion of strong pseudo-random permutation for the re-keying scheme. In this case, note that the adversary is allowed to choose the randomness \(r\) as an input of the decryption oracle.