# A Redactable Blockchain Scheme Supporting Quantum-Resistance and Trapdoor Updates
## 3 Hierarchical Identity-Based Chameleon Hash with Revocable Subkey
### Security Analysis
#### 3.3.2 Security  
**Theorem 1** (_Correctness_). : _The construction of HIBCH-RS meets the requirement of correctness._  
Proof. : For the hash value \(\boldsymbol{h}\) and identity ID, it is easy to confirm that ID uses the trapdoor information to compute a new \(\boldsymbol{r^{\prime}}\) from \(sampleD\big{(}\boldsymbol{R_{ID}},\boldsymbol{F_{ID}},\boldsymbol{H_{i}}, \boldsymbol{h}-\boldsymbol{E_{ID}^{T}}\cdot\boldsymbol{cmodq},\sigma\big{)}\) so that \(\boldsymbol{F_{ID}}\cdot\boldsymbol{r^{\prime}}+\boldsymbol{E_{ID}^{T}} \cdot\boldsymbol{cmodq}=\boldsymbol{h}\). So HIBCHRS satisfies correctness. **Theorem 2** (_Revocability_). : _The construction of HIBCH-RS meets the requirement of revocability._  
Proof. : We discuss the revocability of HIBCH-RS in the following two scenarios. 1. In [36], \(\boldsymbol{R}\) is also a trapdoor for \(\boldsymbol{A^{\prime}}=\boldsymbol{A}-[0]\boldsymbol{H^{\prime}}\boldsymbol {G}]\) with \(\text{tag}\ (\boldsymbol{H}-\boldsymbol{H^{\prime}})\) for any \(\boldsymbol{H^{\prime}}\), as long as \((\boldsymbol{H}-\boldsymbol{H^{\prime}})\) is invertible modulo q. At this point, the old trapdoor is still available even after updating the public key. However, this useful feature does not apply to HIBCH-RS. To prove the above, we have \(\boldsymbol{F_{ID}}=\left[\overline{A}_{S_{ID}^{\prime}}\middle|\boldsymbol{H }\boldsymbol{G}-\overline{A}_{S_{ID}^{\prime}}\cdot\boldsymbol{S_{ID}}^{ \prime}\middle|\boldsymbol{K}\right]\) with a tag \(\boldsymbol{H}\) and ID. From the \(DelKey\) algorithm, we know that \(\boldsymbol{F_{ID}}\cdot \begin{bmatrix}\boldsymbol{R_{ID}}\\ \boldsymbol{I}\end{bmatrix} =\boldsymbol{H}\boldsymbol{G}\). We now assume that there is an invertible tag \((\boldsymbol{H}-\boldsymbol{H^{\prime}})\) such that \(\boldsymbol{F_{ID}^{\prime}}=\boldsymbol{F_{ID}}-[\boldsymbol{0}]\boldsymbol{ H^{\prime}}\boldsymbol{G}[\boldsymbol{0}]\). So, if \(\boldsymbol{R}\) is also a trapdoor \(\boldsymbol{F_{ID}^{\prime}}\), then \(\boldsymbol{F_{ID}^{\prime}}\cdot \begin{bmatrix}\boldsymbol{R_{ID}}\\ \boldsymbol{I}\end{bmatrix} \) should be equal to \((\boldsymbol{H}-\boldsymbol{H^{\prime}})\boldsymbol{G}\). While currently \(\boldsymbol{H}\boldsymbol{G}-[\boldsymbol{0}]\boldsymbol{H^{\prime}}\boldsymbol {G}[\boldsymbol{0}]\cdot \begin{bmatrix}\boldsymbol{R_{ID}}\\ \boldsymbol{I}\end{bmatrix} =\boldsymbol{H}\boldsymbol{G}-[\boldsymbol{0}] \boldsymbol{H^{\prime}}\boldsymbol{G}\). However, it is obvious that \([\boldsymbol{0}]\boldsymbol{H^{\prime}}\boldsymbol{G}\cdot\boldsymbol{R_{ID} }\
eq\boldsymbol{H^{\prime}}\boldsymbol{G}\). 2. Any \(\boldsymbol{H^{\prime}},\boldsymbol{F_{ID}^{\prime}}\cdot \begin{bmatrix} \boldsymbol{R_{ID}}\\ \boldsymbol{I}\end{bmatrix} \
eq\boldsymbol{H^{\prime}}\boldsymbol{G}\). First of all, we assume \(\exists\boldsymbol{H^{\prime}},\boldsymbol{F_{ID}^{\prime}}\cdot \begin{bmatrix} \boldsymbol{R_{ID}}\\ \boldsymbol{I}\end{bmatrix} =\boldsymbol{H^{\prime}}\boldsymbol{G}\). We also know \(\boldsymbol{F_{ID}^{\prime}}= \begin{bmatrix}A_{S_{ID}^{\prime}}^{\prime} \middle|\boldsymbol{K_{ID}}\end{bmatrix} ,A_{S_{ID}^{\prime}}\cdot\boldsymbol{R_{ ID}}=\boldsymbol{H^{\prime}}\boldsymbol{G}-\boldsymbol{K_{ID}}\). Then, \(\left(A_{S_{ID}^{\prime}}-A_{S_{ID}^{\prime}}^{\prime}\right)\cdot \boldsymbol{R_{ID}}=(\boldsymbol{H}-\boldsymbol{H^{\prime}})\boldsymbol{G}\), so we can derive that \([0](\boldsymbol{H}-\boldsymbol{H^{\prime}})\boldsymbol{G}\cdot\boldsymbol{R_{ID} }=(\boldsymbol{H}-\boldsymbol{H^{\prime}})\boldsymbol{G}\). In other words, we want to confirm a trapdoor \(\boldsymbol{R_{ID}}\) of the form \( \begin{bmatrix}\boldsymbol{R_{ID}^{\prime}}\in\mathbb{Z}_{q}^{\eta\times w} \\ \boldsymbol{I}\in\mathbb{Z}_{q}^{w\times w}\end{bmatrix} \). Since \(\boldsymbol{R_{ID}}\) is the random vector that came from \(sampleD\), we can also represent \(\boldsymbol{R_{ID}}\) as \(\boldsymbol{R_{ID}}= \begin{bmatrix}\boldsymbol{x_{1}}&\cdots&\boldsymbol{x_{w} }\end{bmatrix} \), a form that comes from the definition [36]. We also have\(\mathbf{x}_{i}=