# Post-Quantum Digital Signature: Verkle-Based HORST
## 3. Lamport-Diffie One-Time Signature Scheme  
Digital signatures were changed by [PERSON]'s 1984 proposal [15] for Lamport-Diffie One-Time Signatures (OTS), which relied solely on cryptographic hash functions rather than number-theoretic presumptions like RSA or elliptic curves. Because of its architecture, Lamport-Diffie OTS is a fundamental post-quantum encryption scheme that is naturally resistant to quantum computer attacks. However, a crucial limitation reduces its usefulness: only one message may be safely signed by each key pair. Reusing a private key makes the system vulnerable for repeated use by exposing information that attackers may use to forge signatures. In Lamport-Diffie One-Time Signatures (OTS), the first step in the key creation process is choosing a cryptographic hash function, like SHA-256, which generates an output with a set length (256 bits, for example). The scheme's security depends on the hash function's ability to withstand collisions and preimages, making it computationally impossible to reverse the hash or identify two inputs that result in the same output. The signer first generates 256 pairs of random values, each of which is 256 bits long, in order to construct a key pair. Two lists are created from these pairings, one of which corresponds to message bits of 0 and the other to 1 bit. In particular, 256 random values are present in the first list, represented by the symbol \(sk_{0}\):  
\[sk_{0}=(sk0_{1},sk0_{2},sk0_{3},\dots,sk0_{256}) \tag{1}\]  
There are an additional 256 random values in the second list, \(sk_{1}\):  
\[sk_{1}=(sk1_{1},sk1_{2},sk1_{3},\dots,sk1_{256}) \tag{2}\]  
These two lists combine to create the private key, which has 512 random values overall. Each component of the private key is subjected to the hash function in order to obtain the public key. The hash function is calculated for each value in \(\text{sk}_{0}\) and \(\text{sk}_{1}\), producing two lists of hashed values that correspond to each other. The hashes of the \(\text{sk}_{0}\) values are in the first list, \(\text{pk}_{0}\):  
\[pk_{0}=(H(sk0_{1}),H(sk0_{2}),H(sk0_{3}),\dots,H(sk0_{256})) \tag{3}\]  
The second list \(\text{pk}_{1}\), contains the hashes of the \(\text{sk}_{1}\) values:  
\[pk_{1}=(H(sk1_{1}),H(sk1_{2}),H(sk1_{3}),\dots,H(sk1_{256})) \tag{4}\]  
These two lists are then combined to form the public key:  
\[\text{Public Key }=(pk_{0},pk_{1}) \tag{5}\]  
There are 512 hashed values in the public key overall (256 for \(\text{pk}_{0}\) and 256 for \(\text{pk}_{1}\)). While the public key may be safely shared with verifiers, the private key is guaranteed to stay hidden thanks to this key generation procedure. Based on the message bits, the signer will disclose particular elements of the private key throughout the signing process, and the verifier will confirm the signature using the matching hashed values from the public key. It is necessary to first encode the message as a fixed-length binary string in order to sign it using the Lamport-Diffie one-time signature. In order to guarantee that the message length corresponds to the necessary bit-length of the signature scheme, a cryptographic hash function can be used to generate a fixed-length digest if the message is not already in binary form. A 256-bit message is produced: \(\text{msg }=\left(\text{msg}_{1},\text{ msg }_{2},\dots,\text{ msg }_{256}\right)\). Which part of the secret key is utilized in the signature depends on each bit \(\text{msg}_{i}\): \(\text{sk}0_{i}\) is chosen by the signer if \(\text{msg}_{i}=0\), and \(\text{Sk}1i\) is chosen if \(\text{msg}_{i}=1\). Each bit in the message is represented by one of the 256 values that make up the final signature. The private key is kept from being fully exposed by the signer by just disclosing half of it (the set of 256 values that match to the message bits). However, since an attacker might recreate the remaining secret key components, using the same key for several signatures could undermine security.