# Post-Quantum Digital Signature: Verkle-Based HORST
## 2 Hash-Based Digital Signatures  
With their strong defense against the dangers of quantum computing, hash-based digital signatures are a viable post-quantum communications option. These strategies rely on hash functions' cryptographic strength, which is derived from their one-way and collision-resistant design. Because it is difficult to identify two different inputs that produce the same hash output, hash-based signatures are intrinsically resistant to quantum attacks, in contrast to conventional number-theoretic systems like RSA and ECC, which require mathematical hard problems.  
The Lamport-Diffie One-Time Signature (L-OTS) is the most basic and fundamental hash-based signature scheme. It works by creating pairs of random secret keys for every bit in the message hash, and then applying a cryptographic hash function to the secret keys to determine the corresponding public keys. L-OTS has practical drawbacks, such as high signature sizes and the constraint of being useable only once, even if it is probably safe under the assumption of collision-resistant hash functions [13]. To address these limitations, the Winternitz One-Time Signature (WOTS) technique was introduced. It uses hash chains rather than individual key pairs to reduce key and signature sizes. WOTS+, a further improvement, strengthens security without appreciably increasing computing burden by adding randomization to the hash chains to counteract multi-target attacks.  
By making it possible to sign several messages with a single public key, the Merkle Signature Scheme (MSS) increased the usefulness of one-time signatures. In order to do this, MSS arranges public keys for one-time signatures into a Merkle tree, with the master public key acting as the tree's root. This method preserves quantum resistance while enabling the effective authentication of several signatures. However, MSS can hinder scalability in large-scale applications due to its statefulness, which requires the signer to keep track of which keys have been used, and its proof sizes, which increase logarithmically with the number of leaves in the Merkle tree [14].  
In order to address these issues, more sophisticated methods such as HORS (Hash to Obtain Random Subset) and its tree-based variant, HORST (HORS with Trees), were created. While HORST adds a Merkle tree to compress public keys and increase performance, HORS uses a subset of secret keys for each signature to minimize key sizes. Nevertheless, HORST continues to rely on Merkle proofs, which increase in size as the tree height increases, and because of its \"few-times\" nature, its security deteriorates as the number of signatures increases.  
It is commonly assumed in the context of randomized algorithms and cryptographic protocols that computers possess an infinite number of really random bits. For cryptographic procedures to remain unpredictable and secure, these random bits are essential. High-quality physical or algorithmic sources of randomness are used in cryptographic systems to produce the random numbers required for safe key creation and signature procedures. Hash-based signature methods are especially attractive in the context of post-quantum cryptography because they offer a very safe and effective method of authentication through the combination of random bit creation and the collision resistance of hash functions.