# Post-Quantum Digital Signature: Verkle-Based HORST
## 10 Security Proof  
Here, we show that the security of the suggested Verkle-based HORST signature method can be reduced to the binding property of the vector commitments utilized in the Verkle tree and the collision resistance of the basic hash function. We contend that an adversary cannot effectively manufacture a legitimate signature inside the suggested \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Scheme**} & \multirow{2}{*}{**Type**} & \multicolumn{2}{c}{**Signature Size**} & \multicolumn{1}{c}{**Verification**} & \multicolumn{1}{c}{**Public/Private**} & \multirow{2}{*}{**Complexity**} & \multirow{2}{*}{**Security Basis**} \\  & & **(KB)** & **Time (ms)** & & & & \\ \hline V-HORST & Hash & 3.2 & 1.4 & 32 B/64 B & O(k) signature, O(1) & CR + KZG \\  & & & & verification & Binding \\ M-HORST & Hash & 12.8 & 5.6 & 32 B/64 B & O(klogt) & Collision \\  & & & & & Resistance \\ SPHINCS+ & Hash & 8.1 & 2.3 & 32 B/64 B & O(logt) & Collision \\  & & & & & Resistance \\ XMSS & Hash & 2.5 & 2.8 & 32 B/64 B & O(logt) & Collision \\  & & & & & Resistance \\ Dilithium3 & Lattice & 2.7 & 1.1 & 1.3 KB/2.5 KB & O(n\({}^{2}\)) & Module-LWE \\  & & & & & Hardness \\ Rainbow-III & Multivariate & 160 & 37.5 & 161 KB/103 KB & O(n\({}^{3}\)) & Quadratic \\  & & & & & Hardness \\  & & & & & Syndrome \\ McEliece & Code-based & 0.2 & 18.2 & 0.9 MB/1.2 MB & O(nlogn) & Decoding \\  & & & & Hardness \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Efficiency comparison. method, guaranteeing post-quantum security, by relying on the difficulty of identifying hash collisions and violating the binding quality of vector promises. Even in the face of quantum assaults, these cryptographic presumptions are computationally challenging. The Verkle-based HORST signature method is safe from EUF-CMA (Existential Unforgeability under Chosen Message Attacks) if the hash function \(H\) is collision-resistant and the vector commitment scheme is binding. Let us prove the stated theorem. 1. **Adversary Setup**  
Let \(\mathcal{A}\) be a polynomial-time adversary that can forge a signature in the Verkle-based HORST scheme with non-negligible probability \(\epsilon\mathcal{A}\) makes a maximum of \(Q\) signing queries and outputs a forgery \(\left(m^{\star},\sigma^{\star}\right)\) with probability \(\epsilon\). 2. **Simulator Construction**  
The simulator \(\mathcal{S}\) receives a collision-resistant hash function \(H\) and a binding vector commitment scheme Commit. \(\mathcal{S}\) configures the public parameters of the Verkle-based HORST scheme as follows:  
* Generate \(t\) random secret key elements \(\text{sk}=\left(\text{sk}_{1},\text{sk}_{2},\dots,\text{sk}_{t}\right)\). * Compute the leaf nodes by hashing each secret key element: \[\text{leaf}_{i}=H(\text{sk}_{i})\text{ for }i=1,2,\dots,t\] (28)
* Create the Verkle tree by recursively applying vector commitments to groups of leaf nodes: \[\text{node}_{j,k}=\text{ Commit}(\text{node}_{j-1,2k},\text{ node }_{j-1,2k+1})\] (29)
* The root of the Verkle tree is the public key \(\text{pkVerkleHORST}~{}=~{}\text{root}\). \(\mathcal{S}\) provides \(\mathcal{A}\) with the public key \(\text{pkVerkleHORST}\). 3. **Signing Oracle Simulation**  
For each signing query \(m_{i}\) from \(\mathcal{A},\mathcal{S}\) generates a valid signature \(\sigma_{i}\) as follows:  
* Compute the message digest \(\text{msgDigest}_{i}=H(m_{i})\). * Split the digest into \(k\) indexes \((~{}\text{index}_{1},~{}\text{index}_{2},\dots,~{}\text{index}_{k})=\text{ msgDigest}_{i}\text{mod}t\). * Reveal the corresponding secret key elements, reveal secrets \(\text{sigHORS}_{i}=\left(\text{sk}_{\text{index}_{1}},\text{sk}_{\text{index }_{2}},\dots,\text{sk}_{\text{index}_{k}}\right)\).