This presentation tries to convey the big ideas in an easy-to-understand manner.
To keep things simple I'll be a little less formal when it comes to definitions and mathematical notation.
Create a digital signature for a single bit (\(0\) or \(1\)) using only a Cryptographic Hash function
\[ sk \rightarrow pk \]
\[ sk \not\leftarrow pk \]
\[ sign_{sk}(m) = \sigma \]
\[ verify_{pk}(m, \sigma) \overset{?}{=} \text{true} \]
\[ H(m) \rightarrow h \]
\[ m \not\leftarrow h \]
Given \(m\), it's easy to compute \(h\)
Given \(h\), it's hard to find \(m\)
-–-
Given \(sk\), it's easy to compute \(pk\)
Given \(pk\), it's hard to compute \(sk\)
Use one-wayness of Cryptographic Hash function to derive \(pk\) from \(sk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H(sk) \]
We can hand out the public key \(pk\) and later on prove that we knew its corresponding private key \(sk\) by sharing it publicly.
\[ H(sk) \overset{?}{=} pk \]
(Like a Hash-Based Commitment Scheme)
A Private- and Public Key can be interpreted as a concatenation of multiple instances.
\[ sk_i \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ sk = sk_0 \mathbin\Vert sk_1 \mathbin\Vert \ldots \mathbin\Vert sk_n \]
\[ pk_i = H(sk_i) \]
\[ pk = pk_0 \mathbin\Vert pk_1 \mathbin\Vert \ldots \mathbin\Vert pk_n \]
Create a digital signature for a single bit (\(0\) or \(1\)) using only a Cryptographic Hash function
\[ sk_0 \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ sk_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk_0 = H(sk_0) \]
\[ pk_1 = H(sk_1) \]
\[ m = \{0, 1\} \]
\[ sk_i = \begin{cases} sk_0 & \text{if } m = 0\\ sk_1 & \text{if } m = 1 \end{cases} \]
\[ \sigma = sk_i \]
\[ \sigma = sk_i \]
\[ pk_i = \begin{cases} pk_0 & \text{if } m = 0\\ pk_1 & \text{if } m = 1 \end{cases} \]
\[ H(\sigma) = H(sk_i) \overset{?}{=} pk_i \]
How do we sign messages with more than \(1 \text{ bit}\)?
Split message \(m\) into individual bits and repeat process for every single bit.
There's just one problem…
The longer the message, the more keys we have to generate!
The more keys there are, the longer the signature!
Rather than iterating over bits of message \(m\), we hash it first and iterate over the bits of the hash \(h = H(m)\).
Assuming \(H\) produces hashes of length \(256 \text{ bits}\)
\[ \begin{aligned} len_{\text{payload}} &= pk + \sigma \text{ bits} \\ &= 131.072 + 65.536 \text{ bits} \\ &= 196.608 \text{ bits} \\ &\approx 192 \text{ kb} \end{aligned} \]
Why is it a One-Time Signature (OTS) Scheme?
\(\sigma_1 = 0001\)
\(\sigma_2 = 1000\)
-–-
\(\sigma' = 1001\)
How could we make it more efficient?
Given that for any input \(m\), the Hash function \(H\) produces a fixed-length random value \(h\), we could call it again-and-again (\(i\) times) to iteratively derive new values.
\[ H^i(m) = H(H(...H(m))) \]
If we have a hash \(h = H^i(m)\) in the middle of this "hash-chain", we can hash it again to derive its subsequent hash value \(H^{i+1}\).
\[ H^{i+1} = H(h) = H(H^i(m)) \]
We could use these hash-chains to derive multiple Public Keys \(pk_i\) from one Private Key \(sk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk_0 = sk \]
\[ pk_1 = H(sk) \]
…
\[ pk_i = H(...H(H(sk))) \]
If we have message values ranging from \(0\) to \(n\), then we can generate "interim" Public Keys \(pk_i\) for each potential message value \(m_i\).
\[ m_0 = 0 \rightarrow pk_0 = sk \]
\[ m_1 = 1 \rightarrow pk_1 = H(sk) \]
…
\[ m_{n} = n \rightarrow pk_{n} = H(...H(sk)) \]
If we know that our message can be represented as a value from \(0\) to \(n\), then we can chain \(n\) Hash function calls to generate a final public key \(pk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H^n(sk) = H(...H(H(sk))) \]
If one gets \(pk_i\) and knows \(n\), then they can hash \(pk_i\) again \(n-i\) times to see if they end up with \(pk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H^{2^n-1}(sk) = H(...H(H(sk))) \]
\[ h = H(m) \]
\[ x = h_{\text{10}} \]
\[ \sigma = H^x(sk) \]
\[ j = (2^n - 1) - x \]
\[ H^j(\sigma) \overset{?}{=} pk \]
Assuming \(H\) produces hashes of length \(256 \text{ bits}\)
\[ \begin{aligned} len_{\text{payload}} &= pk + \sigma \text{ bits} \\ &= 256 + 256 \text{ bits} \\ &= 512 \text{ bits} \end{aligned} \]
\(512 \text{ bits}\) vs. \(196.608 \text{ bits}\)!
Computing hashes over-and-over again is a computationally intensive task that can be slow.
Hash-chain computations are sequential and can't be parallelized.
Have multiple hash-chains rather than just one!
Make number of hash-chains configurable to trade-off on message size vs. work.
Given \(\sigma\), one can easily compute \(\sigma' = H(\sigma)\).
Compute a checksum and append it to the data that will be signed.
Checksum changes whenever any \(\sigma_i\) is changed.
\[ c = \sum_{i=0}^{l-1} ((2^w - 1) - x_i) \]
Sum of all the missing hash iterations necessary to reach \(pk_i\) for each individual chunk \(l_i\).
Whenever we forge a signature \(\sigma' = H(\sigma)\) for a chunk \(l\), \(c\) will be reduced by \(1\).
As \(c\) is also signed as \(\sigma_c = H^c(sk_c)\), we'd need to undo one hash iteration.
This isn't possible due to the one-wayness of Cryptographic Hash functions.
This was just an introduction to the main ideas behind Hash-Based Signature Schemes, LD-OTS and Winternitz-OTS.
If this piqued your interested, then you can use the resources I used to make this presentation to dive deeper into the specifics.