# Aggregatable Subvector Commitment with Efficient Updates
## 4 Security Analysis
### Security Proof  
This section will prove the soundness of our scheme by the following lemmas. To prove the soundness of the scheme, we use the counterfactual idea that if there exists an adversary \(\mathcal{A}\) who successfully attacks the soundness of our scheme, then let us show how to construct an adversary \(\mathcal{B}\) to violate the above assumptions. We assume that the adversary \(\mathcal{A}\) returns an individual proof, and then returns an aggregated proof. **Lemma 1** (Soundness of Individual Proof). : _The individual proof of our scheme is sound under \(t\)-SDH (see Assumption 1):_  
\[P_{r}\left[ \begin{matrix}\text{pp}\leftarrow\text{Gen}(1^{\lambda},n),\\ (C,i,v_{i},v_{i}^{\prime},\pi_{i},\pi_{i}^{\prime})\leftarrow\mathcal{A}(1^{ \lambda},\text{pp}):\\ 1\leftarrow\text{Ver}(\text{pp},C,i,v_{i},\pi_{i})\wedge\\ 1\leftarrow\text{Ver}(\text{pp},C,i,v_{i}^{\prime},\pi_{i}^{\prime})\wedge\\ v_{i}\
eq v_{i}^{\prime}\end{matrix} \right]\leq\text{negl}(\lambda) \tag{33}\]  
Proof. : First, suppose that \(\mathcal{B}\) obtains the \(t\)-SDH parameter \((g^{\tau^{i}})_{i\in[0,n)}\). \(\mathcal{B}\) guesses the forged index \(i\) of \(\mathcal{A}\) with probability \(\frac{1}{\text{poly}(\lambda)}\) (\(\lambda\) is a security parameter). Subsequently, \(\mathcal{B}\) adapts the SDH public parameters to the protocol public parameters and devises the equation \(\tau-p_{i}=r_{0}(\tau-c)\), where \(r_{0}\) is chosen randomly. Finally, \(\mathcal{B}\) calls \(\mathcal{A}\) using the adjusted public parameters as input. \(\mathcal{A}\) should output the forged index \(i\), the commitment \(C\), and the different proofs \(\pi_{i},\pi_{i}^{\prime}\) at the same index \(i\). \[ \begin{split} e(C/g^{\tau_{i}},g)&=e(\pi_{i},g^{\tau- p_{i}})\\ e(C/g^{\tau_{i}^{\prime}},g)&=e(\pi_{i}^{\prime},g^{\tau- p_{i}})\end{split}  \tag{34}\]  
Dividing the two equations gives the following result:  
\[e(g^{\tau_{i}^{\prime}-v_{i}},g)=e(\pi_{i}/\pi_{i}^{\prime},g^{\tau-p_{i}}) \tag{35}\]  
Substituting \(\tau-p_{i}=r_{0}(\tau-c)\) into the above equation yields:  
\[e(g,g)^{\tau_{i}^{\prime}-v_{i}}=e(\pi_{i}/\pi_{i}^{\prime},g^{\tau_{0}})^{ \tau-c} \tag{36}\]  
Organizing the above equation, we finally obtain  
\[e(g,g)^{\frac{1}{t+c}}=e(\pi_{i}/\pi_{i}^{\prime},g^{\tau_{0}})^{\frac{1}{t_{i }^{\prime}-v_{i}}}, \tag{37}\]which breaks the \(t\)-SDH. Then, we present the soundness lemma for aggregated proof. **Lemma 2** (Soundness of Aggregated Proof). : _Aggregated Proof of our scheme is sound under \(t\)-SBDH (see Assumption 2). For the security parameter \(\lambda\), and \(\forall i\in[0,n)\), where \(I\) is defined in Section 3, in the same way, we define \(J\subseteq[0,n)\):_  
\[P_{r} \begin{bmatrix}\mathsf{pp}\leftarrow\mathsf{Gen}(1^{\lambda},n),\\ (C,I,J,R_{I}(x),R_{J}(x),\pi_{I},\pi_{I})\leftarrow\mathcal{A}(1^{\lambda}, \mathsf{pp})\\ 1\leftarrow\mathsf{Ver}(\mathsf{pp},C,I,v_{1},\pi_{I})\wedge\\ 1\leftarrow\mathsf{Ver}(\mathsf{pp},C,J,v_{1},\pi_{I})\wedge\\ \exists\;i\in I\bigcap J,\\ \text{such that }R_{I}(p_{i})\
eq R_{J}(p_{i})\end{bmatrix} \leq negl(\lambda) \tag{38}\]  
Proof. : We construct the adversary \(\mathcal{B}\) to break the \(t\)-SBDH hypothesis as an illustration of the contradiction that would arise if there existed an adversary \(\mathcal{A}\) that could break Lemma 2. The procedure is as follows: \(\mathcal{B}\) first predicts the index \(i\) of the \(\mathcal{A}\) forgery, where the index \(i\) is the intersection of the two sets of positions \(I,J\).