# An Ordered Universal Accumulator Based on a Hash Chain
## 4 Security Analysis  
**Theorem 1**. : _Assuming that the hash function \(H\) is collision-resistant, the HC accumulator satisfies the unforgeability of fake non-membership security property._  
Proof. : In the hash chain accumulator scheme, assume the CheckUpdate algorithm correctly validates update operations. It is computationally infeasible for an adversary \(A\), after a valid addition of element \(x\) to a set \(X\) (resulting in accumulator state \(\mathfrak{A}\mathfrak{c}_{af}\) representing \(X\cup\{\text{x}\}\)), to generate a valid non-membership witness \(w\) that would incorrectly convince the Belongs algorithm that \(x\) is _not_ in the set \(X\cup\{\text{x}\}\). Formally, if \(\text{CheckUpdate}(\text{x},\mathfrak{A}\mathfrak{c}_{bf},\mathfrak{A}\mathfrak{ c}_{bf},\mathfrak{A}\mathfrak{c}_{bf})=1\) and \(\mathfrak{A}\mathfrak{c}_{af}\) represents \(X\cup\{\text{x}\}\), for the collision resistance of \(H\), there exists no witness \(w\) such that Belongs(\(x,w,\mathfrak{A}\mathfrak{c}_{af}\)) would incorrectly return 0 for element \(x\). \(\square\)  
**Theorem 2**. : _Assuming the hash function \(H\) is collision-resistant, the HC accumulator satisfies the uniqueness security property._  
Proof. : There is a game \(\mathbf{G_{uni}}\). Assume \(A\) wins \(\text{G}_{\text{uni}}\) with non-negligible probability. We construct an algorithm \(B\) that uses \(A\) to find a collision in \(H\). \(B\) simulates \(\text{G}_{\text{uni}}\) for \(A\). When \(A\) outputs (\(\mathfrak{A}\mathfrak{c}\mathfrak{c}^{*}\), \(X^{*}\)), by the winning condition, \(\mathfrak{A}\mathfrak{c}\mathfrak{c}^{*}=\)\(H(H(\ldots H(H(\mathfrak{A}\mathfrak{c}_{0},x_{1})||x_{2})||\ldots)||x_{n})\) for \(X^{*}=\{x_{1},\ldots,x_{n}\}\)\(\
eq\)\(X^{\prime}\). Since \(X^{*}\
eq X^{\prime}\), there exists a sequence of hash computations in \(\mathfrak{A}\mathfrak{c}\mathfrak{c}^{*}\) and \(\mathfrak{A}\mathfrak{c}^{\prime}\) (for \(X^{\prime}\)) that diverge. This implies a collision in H, contradicting its collision resistance. Thus, \(\text{Adv}^{\text{A}}_{\text{uni}}(k)\leq\text{Adv}^{\text{H}}_{\text{coll}}(k)\), which is negligible. Uniqueness follows. (The advantage of adversary A (Adv\({}^{\text{A}}\)) is bounded by the collision resistance advantage of the hash function H.) \(\square\)  
**Theorem 3**. : _There is a hash function family \(\mathfrak{H}:K\times M\to Y\). The hash chain accumulator model \(HC\) is a secure strong universal accumulator (with memory) if it uses a hash function \(H\) randomly selected from \(\mathfrak{H}\)._  
Proof. : To demonstrate that HC is a secure strong universal accumulator, we need to show that it satisfies the properties of consistency, secure addition, and secure deletion, as defined in Definition 3, and that any adversary attempting to violate these properties can be reduced to breaking the collision resistance of the hash function H:Assuming that the hash function H is collision-resistant, the hash chain accumulator scheme satisfies consistency. Suppose that the adversary \(A\) can arbitrarily construct a hash chain accumulator model \(HC\), select element \(x\), and compute the corresponding witness \(w_{1}\), \(w_{2}\). If \(A\) selects the element \(x\in X\) and \(Belongs(x,w_{2},\mathfrak{Acc})=0\), this indicates that element \(x\) does not belong to the set \(X\) represented by the current accumulator value \(\mathfrak{Acc}\). According to collision resistance, the adversary will only succeed with negligible probability. If \(A\) selects the element \(x\
ot\in X\) and \(Belongs(x,w_{2},\mathfrak{Acc})=1\), it will violate collision resistance. The hash chain accumulator scheme satisfies secure addition. Suppose that the adversary \(A\) forges an update operation Update = (\(\mathsf{add}\), \([\mathfrak{Acc}_{bf},\mathfrak{Acc}_{af}]\), \([x]\)), and \(\mathfrak{Acc}_{bf}\Rightarrow X\), \(\mathfrak{Acc}_{af}\Rightarrow\)\(X\cup\{x\}\), where \(\mathfrak{Acc}_{af}=H(\mathfrak{Acc}_{bf},x)\).