# Re-Keying Scheme Revisited: Security Model and Instantiations
## 6 Security Considerations
### Security of the SCA-Resistant Re-Keying Scheme  
In the scheme in Figure 10, the input and the output of BC are masked with \(g_{2}(mk_{2},r)\), which is unknown to the adversary. Hence, the adversary cannot guess the internal value of BC, nor retrieve the meaningful side channel information. Therefore, it is obvious that the scheme is resistant against the first-order SCA.  
The scheme is a modification of the combinatorial scheme of LRW2 and [PERSON] et al.'s second scheme, restricting the keyed hash function in LRW2 not to leak the side channel information. The security model of the re-keying scheme in Definition 5 is a subset of the tweakable block cipher in Definition 4. From Theorem 3 of [6] and the above discussions, the scheme naturally satisfies Definition 5. More precisely, we have the following theorem for the scheme.  
Figure 11: First-order SCA-resistant re-keying encryption scheme.  
**Theorem 1**.: _Assume that \(\mathsf{BC}\) is a (strong) pseudo-random permutation and that \(g_{1}\) is a pseudo-random permutation. Then, the scheme of Figure 10 is a (strong) pseudo-random re-keying scheme such that:_  
\[\mathsf{Adv}\leq\epsilon_{S_{1}}+q\epsilon_{B},\]  
_where \(\epsilon_{B}\) and \(\epsilon_{S_{1}}\) are upper bounds on the advantage of the adversaries against \(\mathsf{BC}\) and \(g_{1}\), respectively._  
Proof.: For simplicity, this proof is for a pseudo-random permutation \(\mathsf{BC}\). The proof for a strong pseudo-random permutation \(\mathsf{BC}\) is very similar.  
Let \(\mathcal{A}\) be an adversary against the re-keying scheme. \(\mathcal{A}\) has oracle access to \(\mathcal{O}_{\mathsf{RK}}\).  
Let \(\mathcal{D}_{1}\) be an adversary against \(g_{1}\). \(\mathcal{D}_{1}\) runs \(\mathcal{A}\) and simulates \(\mathcal{O}_{\mathsf{RK}}\) for \(\mathcal{A}\). Then,  
\[\Pr[\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\textit{real}}=1]= \Pr[\mathbf{Exp}_{g_{1},\mathcal{D}_{1}}^{\textit{real}}=1]\leq \epsilon_{g_{1}}+\Pr[\mathbf{Exp}_{g_{1},\mathcal{D}_{1}}^{\textit{ rand}}=1].\]  
Let \(\mathcal{D}_{2}\) be an adversary against \(\mathsf{BC}\). \(\mathcal{D}_{2}\) is given \(q\) different oracles, which are either \((\mathsf{BC}(k_{1},\cdot),\ldots,\mathsf{BC}(k_{q},\cdot))\) or \((\pi_{1}(\cdot),\ldots,\pi_{q}(\cdot))\), where each \(k_{i}\) is chosen uniformly at random from \(\{0,1\}^{\ell_{k}}\) and each \(\pi_{i}\) is chosen uniformly at random from the set of all permutations over \(\{0,1\}^{\ell_{k}}\). \(\mathcal{D}_{2}\) runs \(\mathcal{A}\) and simulates \(\mathcal{O}_{\mathsf{RK}}\) for \(\mathcal{A}\). For a query \((r,m)\) made by \(\mathcal{A}\), if there exists a previous query \((r^{\prime},m^{\prime})\) such that \(r=r^{\prime}\), then \(\mathcal{D}_{2}\) asks \(m\) from the oracle from which \(\mathcal{D}_{2}\) asked \(m^{\prime}\). Otherwise, \(\mathcal{D}_{2}\) asks \(m\) from a new oracle. Then,  
\[\Pr[\mathbf{Exp}_{g_{1},\mathcal{D}_{1}}^{\textit{rand}}=1]= \Pr[\mathcal{D}_{2}^{\mathsf{BC}(k_{1},\cdot),\ldots,\mathsf{BC}( k_{q^{\prime}})}=1]\leq q\epsilon_{B}+\Pr[\mathcal{D}_{2}^{\pi_{1}(\cdot),\ldots,\pi_{q}( \cdot)}=1].\]  
It is not difficult to see that:  
\[\Pr[\mathcal{D}_{2}^{\pi_{1}(\cdot),\ldots,\pi_{q}(\cdot)}=1]= \Pr[\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\textit{rand}}=1].\]  
Thus,  
\[\left|\Pr[\mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\textit{real}}=1]-\Pr[ \mathbf{Exp}_{\mathsf{RK},\mathcal{A}}^{\textit{rand}}=1]\right|\leq \epsilon_{g_{1}}+q\epsilon_{B}.\]  
The above theorem holds whether \(\mathsf{BC}\) is secure against the related key attack or not. Although [PERSON] et al.'s second scheme requires the ideal tweakable block cipher (namely, secure against the related key attack), our scheme can relax the requirement for its building block.