# Post-Quantum Digital Signature: Verkle-Based HORST
## 8 Horst: HORS with Trees Signature Scheme  
An upgrade to the HORS (Hash to Obtain a Random Subset) method, the HORST (HORS with Trees) signature technique adds a binary Merkle tree to authenticate HORS public keys, increasing security. This stops an attacker from using key reuse to create fake signatures. A popular component of SPHNCS, a scalable, post-quantum safe signature system, is the stateless signature technique HORST. By including a Merkle tree structure, HORST solves the key exposure issue in HORS [22]. This guarantees that an attacker cannot create a legitimate signature without generating a corresponding Merkle root, even if portions of the private key are made public. Similar to HORS, HORST uses a vast collection of random numbers for its private key and a cryptographic hash function. For the private key, t randomly generated values are used: \(\text{sk}\,=(\text{sk}_{1},\text{sk}_{2},\dots,\text{sk}_{t})\). HORST constructs the hashed private key values into a Merkle tree rather than utilizing them directly as the public key. Leaf nodes are initially created by hashing each private key value:  
\[\text{leaf}\,_{i}=\text{H}(\text{sk}_{i})\forall i\in[1,t] \tag{19}\]  
The tree is then formed by iteratively hashing pairs of nodes to produce the parent nodes:  
\[\text{node}_{j+1}=\text{H}\big{(}\text{node}_{j}\|\text{node}_{j+1}\big{)} \tag{20}\]  
In this case, \(\text{node}_{j}\) indicates a node at level j, and \(\|\) indicates concatenation. The public key is the last root node in the Merkle tree \((\text{pkHORST}\,=\,\text{root})\). By adding a layer of security, the Merkle tree makes HORST far more resilient than HORS. This extra structure guarantees that an attacker cannot fabricate a valid signature without generating a matching Merkle root, even if portions of the private key are exposed. The signature procedure in HORST follows the HORS method but contains extra authentication channels to validate the integrity of the exposed private key parts. First, the message digest is calculated and transformed into k indexes \((\text{index}_{1},\text{ index}_{2},\dots,\text{ index}_{k})=\text{Hash}(\text{message})\text{mod}t\). The matching private key component for each chosen index is made visible as a component of the signature:  
\[\text{sigHORS}=\big{(}\text{ sk index}_{1},\text{skindex}_{2},\dots,\text{ sk index}_{k}\big{)} \tag{21}\]  
Additionally, the signer contains authentication pathways to allow verification of the Merkle root. Every authentication path has the brother nodes required to reconstruct the root \(\text{authPath}\ =(\text{node}_{1},\text{ node}_{2},\dots,\text{node}_{h})\). Together with the authentication paths, the HORS signature makes up the final HORST signature: signature \(=(\text{sigHORS},\text{ authPath})\). Because they enable the verifier to verify that the disclosed private key parts are a part of the original Merkle tree without needing the transmission or storage of the complete tree, the authentication path is essential for verification. In order to validate a HORST signature, the verifier first determines if the HORS signature is legitimate before utilizing the authentication path to reconstruct the Merkle root. The verifier collects the indices and calculates the message digest \((\text{index}_{1},\text{ index}_{2},\dots,\text{ index}_{k})=H(\text{message})\text{mod}t\). The verifier calculates the hash of each disclosed private key element and determines if it corresponds to the relevant leaf node in the Merkle tree. The verifier then gradually reconstructs the Merkle root using the authentication paths:  
\[\text{node}_{j+1}=H\big{(}\text{node}_{j}\|\text{authPath}_{j}\big{)} \tag{22}\]  
If the calculated root matches the known public key root, the signature is legitimate; otherwise, it is denied. This process ensures the signature's authenticity and integrity. A key-encryption system called HORST improves HORS by lowering the possibility of key exposure.