math/notes_hash-based-signatures.tex
notes_hash-based-signatures.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4\usepackage{amsthm}
5\usepackage{amsmath}
6\usepackage{enumerate}
7\usepackage{hyperref}
8\usepackage{amssymb}
9
10\usepackage{float}
11\usepackage{graphicx}
12
13\begin{filecontents}[overwrite]{notes_hash-based-signatures.bib}
14@misc{cryptoeprint:2014/795,
15 author = {Daniel J. Bernstein and Daira Hopwood and Andreas Hülsing and Tanja Lange and Ruben Niederhagen and Louiza Papachristodoulou and Michael Schneider and Peter Schwabe and Zooko Wilcox-O'Hearn},
16 title = {{SPHINCS}: practical stateless hash-based signatures},
17 howpublished = {Cryptology {ePrint} Archive, Paper 2014/795},
18 year = {2014},
19 url = {https://eprint.iacr.org/2014/795}
20}
21@misc{rfc8391,
22 series = {Request for Comments},
23 number = 8391,
24 howpublished = {RFC 8391},
25 publisher = {RFC Editor},
26 doi = {10.17487/RFC8391},
27 url = {https://www.rfc-editor.org/info/rfc8391/},
28 author = {A. Huelsing and D. Butin and S. Gazdag and J. Rijneveld and A. Mohaisen},
29 title = {{XMSS: eXtended Merkle Signature Scheme}},
30 pagetotal = 74,
31 year = 2018,
32 month = may,
33}
34\end{filecontents}
35\nocite{*}
36
37
38\theoremstyle{definition}
39
40
41
42\title{Notes on hash-based signatures}
43\author{arnaucube}
44\date{December 2025}
45
46\begin{document}
47
48\maketitle
49
50\begin{abstract}
51 Notes taken while studying hash-based signatures.
52
53 Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
54\end{abstract}
55
56\tableofcontents
57
58\vspace{1.0cm}
59
60\section{Preliminaries}
61\subsection{Lamport signatures (1979)}
62(OTS: One Time Signature scheme)
63
64\paragraph{key gen}
65
66sk:
67$$((s_{0,0}, s_{0,1}), (s_{1,0}, s_{1,1}), (s_{2,0}, s_{2,1}), \ldots, (s_{255,0}, s_{255,1}))$$
68where each $s_{i,j} \in \{0, 2^256 -1\}$.
69
70pk:
71$$((h(s_{0,0}), h(s_{0,1})), (h(s_{1,0}), h(s_{1,1})), (h(s_{2,0}), h(s_{2,1})), \ldots, (h(s_{255,0}), h(s_{255,1})))$$
72
73\paragraph{sign}
74hash the 256 bits of the msg: $(m_0, \ldots, m_{255})$
75
76and the signature is
77$$(s_{0, m_0}, s_{1, m_1}, s_{2, m_2}, \ldots, s_{255, m_{255}})$$
78
79\paragraph{verify}
80compare hashes of signature components to elements of the public key.
81
82\vspace{0.5cm}
83Sizes: 16 kB sk and pk, 8 kB signature.
84
85\subsection{Adding Merkle Trees (1979)}
86idea: put a binary hash tree on top of all pk's: leaves are the hashes of pks.
87
88Public key: root of the tree (256 bits)
89
90Signature: OTS plus the authentication path (merkle proofs)
91
92\paragraph{some numbers}
93Fix to $2^{32}$ signatures.
94\begin{itemize}
95 \item key gen: compute the tree: $2^{33} -1$ hashes
96 \item pk size: 32 bytes
97 \item sk: the seed for the one-time signature (OTS) secret keys: 32 bytes
98 \item signature size: $\approx$ 25 kB:
99 \begin{itemize}
100 \item 8 kB Lamport signature
101 \item 16 kB Lamport pk
102 \item 32 $\cdot$ 32 = 1024 B of authentication path (merkle proofs)
103 \item 4 B for the index of the leaf node
104 \end{itemize}
105\end{itemize}
106
107Main issue: have to remember the state, to update the secret key after each signing.
108
109
110\subsection{Goldreich's approach (1986)}
111
112\begin{itemize}
113 \item make the tree huge (eg. height h=256), such that one can pick leaves at random
114 \item each node corresponds to an OTS key pair
115 \item leaf nodes are used to sign messages
116 \item all OTS secret keys are generated from a seed
117\end{itemize}
118
119Numbers
120\begin{itemize}
121 \item pk and sk are still small, 32 bytes
122 \item key gen is fast (only generate root OTS key pair)
123 \item signing requires 2h=512 OTS key generations and h=256 OTS signatures
124 \item signature is very large, eg. with Lamport OTS:
125 \begin{itemize}
126 \item 256 $\cdot$ 24 kB for Lamport signatures and pks
127 \item 256 $\cdot$ 32 B for authentication paths
128 \item 32 B for the index of the leaf node
129 \end{itemize}
130 total size: 6 MB
131\end{itemize}
132
133
134\subsection{WOTS+}
135Winternitz One-Time Signature.
136
137\paragraph{Chaining function} $c^i(x,r)$
138
139input values: $x \in \{0,1\}^n$, iteration counter: $i \in \mathbb{N}$,
140
141bitmasks: $r=(r_1, \ldots, r_j) \in \{0,1\}^{n \times j}$, where $j \geq i$.
142
143\begin{itemize}
144 \item if $i=0$, return $x$; ie. $c^0(x,r)=x$
145 \item if $i>0$,
146 $$c^i(x,r)= F(c^{i-1}(x,r) \oplus r_i)$$
147 (where $\oplus$ is the bitwise XOR)
148\end{itemize}
149
150\paragraph{key generation}
151
152$$sk, pk \leftarrow WOTS.keygen(S,r)$$
153
154input seed: $S \in \{0,1\}^n$
155
156bitmask: $r \in \{0,1\}^{n \times (w-1)}$
157
158compute sk:
159
160($G_l$ is a pseudorandom generator)
161
162$$sk=(sk_1, \ldots, sk_l) \leftarrow G_l(S)$$
163ie. the $n$ bit seed is expanded to $l$ values of $n$ bits
164
165$$pk = (pk_1, \ldots, pk_l) = (c^{w-1}(sk_1, r), \ldots, c^{w-1}(sk_l, r))$$
166
167\paragraph{signature:} $\sigma \leftarrow~ WOTS.sign(M, S, r)$
168
169for a message $M \in \{0.1\}^n$
170
171compute a base-w representation of $M$:
172$$M = (M_1, \ldots, M_l),~~ M_i \in \{0, \ldots, w-1\}$$
173
174compute checksum:
175$$C = \sum_{i=1}^{l_1} (w-1-M_i)$$
176and its base $w$ representation
177$$C=(C_1, \ldots, C_{l_2})$$
178
179set $B=(b_1, \ldots, b_l)=M||C$ (concatenation)
180
181obtain sk with $sk \leftarrow~ WOTS.keygen(S,r)$
182
183signature:
184
185$$\sigma = (\sigma_1, \ldots, \sigma_l) = (C^{b_1}(sk_1, r), \ldots, C^{b_l}(sk_l, r))$$
186
187\paragraph{verification:} $pk' \leftarrow~ WOTS.vf(M, \sigma, r)$
188
189compute $b_i$ for $1 \leq i \leq l$ as described above
190
191return:
192$$pk' = (pk_1', \ldots, pk_l')\\
193=(C^{w-1-b_1}(\sigma_1, r_{\stackrel{b+1, w-1}{1}}), \ldots, C^{2-1-b_l}(\sigma_l, r_{\stackrel{b+1, w-1}{l}}))
194$$
195
196and check that $pk \stackrel{?}{=} pk'$.
197
198\subsection{HORST}
199\paragraph{parameters}
200
201$k, t=2^\tau$, with $k\tau=m$ (length of the message signed).
202
203in SPHINCS-256: $t=2^16,~ k=32$.
204
205\paragraph{key generation:} $pk \leftarrow HORST.keygen(S, Q)$
206
207input seed: $S \in \{0,1\}^n$
208
209bitmasks: $Q \in \{0,1\}^{2n \times \log t}$
210
211$$sk=(sk_1, \ldots, sk_t) \leftarrow G_t(S)$$
212
213Leaves of the tree are computed as $L_i=F(sk_i)$ for $i \in [t-1]$, and the tree is constructed using bitmasks $Q$.
214
215pk: root node of a binary tree of height $\log t$.
216
217
218\paragraph{signature:} $(\sigma, pk) \leftarrow~ HORST.sign(M, S, Q)$
219
220$M \in \{0,1\}^m,~ S \in \{0,1\}^n,~ Q \in \{0,1\}^{2n \times \log t}$
221
222Let $M=(M_0, \ldots, M_{k-1})$ be the $k$ numbers obtained by splitting $M$ into $k$ strings of length $\log t$ bits each, and interpreting each as an unsigned integer.
223
224Signature:
225$$\sigma = (\underbrace{\sigma_0, \ldots, \sigma_{k-1}}_{\stackrel{\sigma_i=(sk_{M_i}, Auth_{M_i})}{\text{for}~ i\in [k-1]}}, \sigma_k)$$
226
227$Auth_{M_i}$: lower $\tau - x$ elements of the authentication path of the corresponding leaf $(A_0, \ldots, A_{\tau-1-x})$
228
229$\sigma_k$: all the $2^x$ nodes of the binary tree on level $\tau-x$, $(N_{0,\tau-x}, \ldots, N_{2^x -1, \tau-x})$.
230
231\paragraph{verification:} $pk' \leftarrow~ HORST.vf(M, \\sigma, Q)$
232
233first compute $M_i$ as described in the signature step.
234
235Then, for $i \in [k-1], ~ y_i = \lfloor M_i / 2^{\tau}-x \rfloor$, it computes $N'_{y_i, \tau-x}$ using root computation with index $M_i,~ L_{M_i}F(\sigma_i^1),~ Auth_{M_i}=\sigma_i^2$.
236
237Then check $\forall~ i \in [k-1]$:
238$$N'_{y_i, \tau-x} \stackrel{?}{=} N_{y_i, \tau-x}$$
239
240ie. computed nodes match those in $\sigma_k$.
241
242If ok, use $\sigma_k$ to compute the root ($= ~ N_{0, h}$), and return the root as $pk'$.
243
244
245
246\section{SPHINCS (2015)}
247
248\subsection{High level view}
249
250\begin{itemize}
251 \item hyper-tree of total height $h$
252 \item each tree has height $h/d$
253 \item inside the tree, use Merkle approach
254 \item between trees use Goldreich approach
255 \item sign messages with a "few-time" signature scheme (FTS)
256\end{itemize}
257
258\paragraph{SPHINCS-256} (128 bits of security)
259\begin{itemize}
260 \item 12 trees of height 5 each
261 \item use WOTS as one-time-signature (OTS) scheme
262 \item use HORST (HORS with tree) as few-time signature (FTS) scheme
263 \item fix $n=256$ as bitlength of hashes in WOTS and HORST
264 \item fix $m=512$ as size of the message hash (Blake-512)
265 \item use ChaCha12 as pseudorandom generation
266\end{itemize}
267
268\subsection{SPHINCS construction}
269\subsubsection{Parameters}
270
271Security parameter: $n \in \mathbb{N}$
272
273Hash functions:
274\begin{align*}
275&F: \{0,1\}^n \longrightarrow \{0,1\}^n\\
276&H: \{0,1\}^{2n} \longrightarrow \{0,1\}^n\\
277&\mathcal{H}: \{0,1\}^n \times \{0,1\}^* \longrightarrow \{0,1\}^m
278\end{align*}
279
280for $m=poly(n)$
281
282Height of the hyper-tree: $h \in \mathbb{N}$ (and $h|d$):\\
283\hspace*{2em}$d$ layers of trees, each of height $h/d$.
284
285
286Each tree: leaves are $2^{h/d}$ L-Tree root nodes, that each is a pk of WOTS+.\\
287\hspace*{2em}$\Longrightarrow$ a tree is a keypair that can be used to sign $2^{h/d}$ messages.
288
289
290The hyper-tree has $d$ layers
291\begin{itemize}
292 \item on layer $d-1$ it has a single tree
293 \item on layer $d-2$ it has $2^{h/d}$ trees
294 \begin{itemize}
295 \item roots signed using WOTS+ key pairs of the tree on layer $d-1$
296 \end{itemize}
297\end{itemize}
298
299In general: layer $i$: $2^{(d-1-i)(h/d)}$ trees, and the roots of these trees are signed using the WOTS+ key pairs of the trees on layer $i+1$.
300
301Layer 0: each WOTS+ keypair is used to sign a HORST pk.
302
303$\longrightarrow$ Full tree structure is never computed, values are determined by the seed and the bit masks.
304
305\begin{figure}[H]
306 \centering
307 \includegraphics[width=0.9\textwidth]{img/sphincs-trees.jpg}
308 % \caption{ }
309 \label{fig:trees}
310\end{figure}
311
312An address is a bit string of length
313$$a=\lceil
314\underbrace{\log(d+1)}_{\text{WOTS+ keypair addr}}
315\rceil +
316\underbrace{(d-1)(h/d)}_{\stackrel{\text{index of the tree}}{\text{in the layer}}}
317+
318\underbrace{(h/d)}_{\stackrel{\text{index of the WOTS+}}{\text{key pair within the tree}}}
319$$
320$$= \lceil \log(d+1) \rceil + h$$
321
322$\longrightarrow$ in SPHINCS-256, an address needs 64 bits.
323
324
325\vspace{0.6cm}
326
327\subsubsection{key generation:} $(sk, pk) \leftarrow keygen(1^n)$
328
329sample $(sk_1, pk_1) \in \{0,1\}^n \times \{0,1\}^n$
330
331$sk_1$: used for pseudorandom key generation
332
333$sk_2$: used to generate an unpredictable index in 'sign' and pseudorandom values to randomize the msg hash in 'sign'.
334
335
336Sample bitmasks: $p$ uniformly random n-bit values
337$$Q \leftarrow^R \{0,1\}^{p \times n}$$
338
339where $p = max \{ w-1, 2(h+ \lceil \log(l) \rceil), 2 \log t \}$.
340
341
342We use
343\begin{itemize}
344 \item $Q_{WOTS+}$ for the fist $w-1$ bitmasks (of length $n$) in $Q$
345 \item $Q_{HORST}$ for the first $2 \log t$
346 \item $Q_{L-Tree}$ for the first $2 \lceil \log l \rceil$
347 \item $Q_{Tree}$ for the $2h$ strings of length $n$ in $Q$ that follow $Q_{L-Tree}$
348\end{itemize}
349
350Remaining logic in keygeneration: generate the root node of the tree on layer $d-1$.
351
352
353
354WOTS+R keypairs for the single tree at layer $d-1$ are generated\\
355$\longrightarrow$ seed for the keypair with address $A=(d-1 || 0 || i)$ with $i \in [2^{h/d}-1]$ is computed as
356$$S_A \leftarrow \mathcal{F}_a(A, sk_1)$$
357where $\mathcal{F}$ is a PRF.
358
359
360WOTS+ pub key:
361$$pk_A \leftarrow WOTS.keygen(S_A, Q_{WOTS+})$$
362
363
364The i-th leaf $L_i$ of the tree is the root of an L-Tree that compresses $pk_A$ using bitmasks $Q_{L-Tree}$.
365
366Finally, a binary tree is build using the constructed leaves and its root node becomes $pk_1$.
367
368\vspace{0.5cm}
369SPHINCS $sk=(sk_1, sk_2, Q)$, $pk=(pk_1, Q)$.
370
371\subsubsection{Signature algorithm} $\Sigma \leftarrow sign(M, sk)$
372
373$M \in \{0,1\}^*$
374
375Compute a randomized message digest $D \in \{0,1\}^m$:\\
376compute pseudorandom $R=(R_1, R_2) \in \{0,1\}^n \times \{0,1\}^n$
377$$R \leftarrow \mathcal{F}(M, sk_2)$$
378
379then
380$$D \leftarrow \mathcal{H}(R_1, M)$$
381ie. randmized hash of $M$; where $R_1$ are the first $n$ bits of $R$.
382
383$R_2$ (later $n$ bits of $R$) are used to select a HORST keypair:\\
384compute an $h$ bit index $i \leftarrow CHOP(R_2, h)$ as the first $h$ bits of $R_2$.
385
386Given index $i$, HORST key pair with address
387$$A_{HORST} = (d || i(9,(d-1) h/d) || i ((d-1)h/d, h/d))$$
388is used to sign the message digest $D$.\\
389\hspace*{4em}ie. first $(d-1)h/d$ bits of $i$ are used as tree index and the remaining bits for the index within the tree.
390
391The HORST signature and public key
392
393$$(\sigma_H, pk_H) \leftarrow (D, S_{A_{HORST}}, Q_{HORST})$$
394are computed using the HORST bitmasks and the seed
395$$S_{A_{HORST}} \leftarrow \mathcal{F}_a(A_{HORST}, sk_1)$$
396
397Signature:
398$$\Sigma = (i, R_1, \sigma_H, \sigma_{W,0}, Auth_{A_0}, \sigma_{W,d-1}, Auth_{A_{d-1}})$$
399
400where
401\begin{itemize}
402 \item[ ] $\sigma_H$: HORST signature
403 \item[ ] $\sigmA_{W,0}$: WOTS+ signature
404 \item[ ] $Auth_{A_0}$: one auth path per layer.
405\end{itemize}
406
407\subsubsection{Verification} $b \leftarrow vf(M, \Sigma, pk)$
408
409compute message digest $D \leftarrow \mathcal{H}(R_1, M)$ ($R_1$ comes from $\Sigma$)
410
411$$pk_H \leftarrow HORST.vf(D, \sigma_H, Q_{HORST})$$
412where $Q_{HORST}$ comes from $pk$.
413
414$$pk_{W,0} \leftarrow WOTS.vf(pk_H, \sigma_{W,0}, Q_{WOTS+})$$
415
416where $\sigma_{W,0}$ is the WOTS+ signature, and $Q_{WOTS+}$ is the WOTS+ bitmask.
417
418An L-Tree is used to compute $L_{i((-1)h/d, h/d)}$, ie. the leaf corresponding to $pk_{W,0}$.
419
420Then, compute $Root_0$ with index $i((d-1)h/d, h/d)$, leaf $L_{i((d-1)h/d, h/d)}$ and authentication path $Auth_0$.
421
422This procedure is repeated for layers $1$ to $d-1$ with the following differences:
423\begin{enumerate}
424 \item on layer $1 \leq j < d$, the root of the previous tree, $Root_{j-1}$, is used to compute the WOTS+ $pk_{w,j}$.
425
426 \item the leaf from $pk_{w,j}$ using an L-Tree is $L_{i((d-1)h/d, h/d)}$; ie. the index of the leaf within the tree can be computed cutting off the last $j(h/d)$ bits of $i$ and then using the last $(h/d)$ bits of the resulting bit string.
427\end{enumerate}
428
429The result of the final repetition on layer $d-1$ is a value $Root_{d-1}$ (root of the single tree on the top layer).
430
431Then verifier checks
432$$pk_1 \stackrel{?}{=} Root_{d-1}$$
433
434\subsubsection{Sizes of SPHINCS-256}
435\begin{itemize}
436 \item pk: 1056 bytes
437 \item sk: 1088 bytes
438 \item sig: 41000 bytes
439\end{itemize}
440
441\begin{figure}[H]
442 \centering
443 \includegraphics[width=0.9\textwidth]{img/sphincs-hyper-tree.jpg}
444 % \caption{Hyper-Tree}
445 \label{fig:hyper-tree}
446\end{figure}
447
448\section{XMSS (2011)}
449After seeing the previous schemes of this document, XMSS signatures are quite straight forward:
450
451MerkleTree which leaves are WOTS+ public keys. Each leaf has a corresponding
452one-time key $(sk_i, pk_i)$
453
454To sign message number $i$:
455$$\sigma_i = (i, R, \sigma_{WOTS+, i}, AuthPath_i)$$
456
457Verifier reconstructs $pk_i$ from the WOTS+ signature, and then follows the authentication path to obtain the root.
458
459\vspace{0.6cm}
460Important: Never use the same WOTS+ leaf more than once. Thus it is important to keep track of the used leaves. ie. keep a state.
461
462\bibliographystyle{unsrt}
463\bibliography{notes_hash-based-signatures.bib}
464
465\end{document}