Computing the FORS signature

This page describes how to compute the FORS signature SIG_FORS as part of an example SLH-DSA signature.

We use JavaScript to display the mathematics on this page. Please enable JavaScript in your browser for it to work.

Let’s recap about a FORS signature.

FORS is a Few Time Signature (FTS) scheme where we have a very large number of possible private keys such that we can sign a “few” messages using a one-time-signature construction with the same key without compromising security (too much).

FORS_sign algorithm
Compute the randomizer R
Compute H_msg
Split H_msg into message digest, tree address and leaf index
Compute the first FORS secret key
The first authentication path
Compute the remaining FORS signatures
Compressing the tree root values to form the FORS public key

FORS_sign algorithm

Input: Message M, private key SK = (SK.seed, SK.prf, PK.seed, PK.root),
       (optional) additional randomness addrnd

if addrnd then 
   opt_rand = addrnd
else
   opt_rand = PK.seed
endif

Input values for this example

D5213BA4BB6470F1B9EDA88CBC94E627   # SK.seed
7A58A951EF7F2B81461DBAC41B5A6B83   # SK.prf
FA495FB834DEFEA7CC96A81309479135   # PK.seed
A67029E90668C5A58B96E60111491F3D   # PK.root

Input message [3 bytes]
M = 00003F

addrnd = NULL # Use deterministic variant

Step 1 - Compute the randomizer $R$

Compute the randomizer $R$ of $n$ bytes.

R = PRF_msg(SK.prf, opt_rand, M)

where SK.prf is part of the private key, M is the message to be signed, and opt_rand is a $n$-byte string of either additional randomness if in hedged mode or, if in deterministic mode, the value of PK.seed

Using SHA-256, PRF_msg is defined using HMAC-SHA-256 with SK.prf as the key.

PRF_msg(SK.prf, opt_rand, M) = HMAC-SHA-256(SK.prf, opt_rand || M) # truncated to 16 bytes

In this case, we have

SK.prf =7A58A951EF7F2B81461DBAC41B5A6B83
opt_rand=PK.seed=FA495FB834DEFEA7CC96A81309479135
M=00003F
hence R =

BD40E6D66893F38D5C5FAD99E4885329

This is the first 16-byte line of the signature. So set SIG = R.

Note that this randomizer value $R$ is completely determined by the SLH-DSA private key and the message itself, and perhaps some optional random material.

Python code

from slh_sha256 import HMAC_SHA256
# Generate the randomizer R of 16 bytes using hex strings
sk_prf='7A58A951EF7F2B81461DBAC41B5A6B83'
optrand='FA495FB834DEFEA7CC96A81309479135'  # <- PK.seed for deterministic
msg= '00003F'  # M' = Input content 0x3F prefixed by two zero bytes
R = HMAC_SHA256(sk_prf, optrand + msg)
R = R[:32] # Truncate to 16 bytes
print("R =", R)
# R = BD40E6D66893F38D5C5FAD99E4885329

Step 2 - Compute `H_msg`

We compute H_msg from the message, M, the public key, and the randomizer, R.

With SHA-256 we use MGF1 from PKCS#1 as an XOF (eXtendable Output Function).

H_msg(R, PK.seed, PK.root, M, m)
  = MGF1-SHA-256(R||PKseed||SHA-256(R||PKseed||PKroot||M), m)

In our case, we require an output of $m=34$ bytes (see below).

Python code to compute $H_{\text{msg}}$

from slh_sha256 import SHA256, MGF1_SHA256
R = 'bd40e6d66893f38d5c5fad99e4885329'
PKseed = 'FA495FB834DEFEA7CC96A81309479135'
PKroot = 'A67029E90668C5A58B96E60111491F3D'
msg= \
'00003F'
m = 34
h = SHA256(R + PKseed + PKroot + msg)
h_msg = MGF1_SHA256(R + PKseed + h, m)
print("H_msg:", h_msg)
# cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072fcdcef4b8fdb03b028

Note that the function to derive H_msg using SHA-256 has changed since the original computations for SPHINCS+ version 3.0.

Split `H_msg` into message digest, tree address and leaf index

We need to split H_msg into a message digest md of md_bytes, a tree address of tree_bits and a leaf index of leaf_bits. We do this on byte boundaries.

For our example, we have the following parameters

$h=66$, $d=22$, $k=33$, $a=6$, $t=2^a=64$

The formulae to compute the required lengths are

$\mathtt{md\_bytes}=\left\lceil \dfrac{k\cdot a}{8} \right\rceil = 25$ bytes

$\mathtt{tree\_bits}=h - h/d = 66 - 66/22 = 63$ bits, hence $\mathtt{tree\_bytes}=\left\lceil \dfrac{\mathtt{tree\_bits} }{8} \right\rceil = 8$ bytes

$\mathtt{leaf\_bits}=h/d = 66/22 = 3$ bits, hence $\mathtt{leaf\_bytes}=\left\lceil \dfrac{\mathtt{leaf\_bits} }{8} \right\rceil = 1$ byte

So, in our case, we require 25 bytes for the message digest (md), enough bytes for a 63-bit tree address (8 bytes) and a 3-bit leaf index (1 byte) making $m=34$.

Split H_msg into md (25 bytes), tree address (8 bytes) and leaf index (1 byte).

H_msg = cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072 fcdcef4b8fdb03b0 28
md = cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072

Then decode the tree address and leaf index byte strings to unsigned integers truncated to 63 and 3 bits, respectively

treeaddr = 0xfcdcef4b8fdb03b0 & 0x7fffffffffffffff  # 63 bits
= 0x7cdcef4b8fdb03b0
idx_leaf = 28 & 0x7  # 3 bits
= 0x0

Compute SIG_FORS

INPUT: md, SK.seed, PK.seed, ADRS

Interpret 25-byte md as 33 $\times$ 6-bit ($k\times a$-bit) unsigned integers using the base_2$^b$ algorithm.

md = cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072
indices (in decimal):  
50 47 49 35 39 21 57 21 02 00 31 56 18 58 58 31 
31 43 35 26 08 07 31 13 21 57 63 20 33 05 08 32 
28

Each of these 33 indices gives the index (0-63) of a secret key in each of the $k=33$ FORS trees.

The first index (value 50 decimal) selects the 50th secret key in the 1st tree, the second (value 47) selects the 47th key in the 2nd tree, … and finally the 33rd index (value 28) selects the 28th key in the 33rd tree.

These $k=33$ secret keys are "revealed" in the signature along with their authentication paths.

Python code to compute indices

def base_2_b(X, b, out_len):
    # Algorithm 4: base_2^b(X, b, out_len)
    # Compute the base 2^b representation of X
    # INPUT:
    # Byte string X, integer b, output length out_len.
    two_to_b = 1 << b  # 2^b
    baseb = [0] * out_len
    i = 0
    bits = 0
    total = 0

    for out in range(out_len):
        while bits < b:
            total = (total << 8) + X[i]
            i = i + 1
            bits = bits + 8
        bits = bits - b
        baseb[out] = (total >> bits) & (two_to_b - 1)  # mod 2^b
        total &= (two_to_b - 1)
    return baseb

X = bytes.fromhex('cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072')
print(f"X={X.hex()}")
indicies = base_2_b(X, 6, 33)
print("indicies:\n", [m for m in indicies])
# [50, 47, 49, 35, 39, 21, 57, 21, 2, 0, 31,
# 56, 18, 58, 58, 31, 31, 43, 35, 26, 8, 7,
# 31, 13, 21, 57, 63, 20, 33, 5, 8, 32, 28]

Compute the first FORS secret key

The tree_index part of ADRS is computed as

$\mathtt{tree\_index} = i\cdot t + \text{indices}[i]$ for $i = 0,\ldots, k-1$ where $k=33$ and $t=2^a=64$.

For the first tree $i=0$ we have an index of 50 giving

tree_index = 0*64 + 50 = 50 = 0x32

The FORS secret key is computed by

sk = PRF(PK.seed, SK.seed, ADRS)

where ADRS is constructed with type 6 (FORS_PRF). We are at layer 0, tree height 0, the leaf index (key pair address) is 0, and the tree_index is 0x32.

In SHA-2 compressed form ADRS_c, this is represented by

layer   treeaddr  type  idxleaf  tree ht treeindex
[1]          [8]   [1]      [4]      [4]      [4]
00 7cdcef4b8fdb03b0 06 00000000 00000000 00000032
                             ^^

Note that our particular example has idxleaf=0, but if it were nonzero it would show in the byte marked ^^ above.

The secret key value is computed using the PRF function:

sk = PRF(PK.seed, SK.seed, ADRS)
   = SHA-256(PK.seed || toByte(0, 64 − n) || ADRS_c || SK.seed)[n]
   = SHA256('FA495FB834DEFEA7CC96A81309479135' 
      + '000000000000000000000000000000000000000000000000'
      + '000000000000000000000000000000000000000000000000'   
      + '007cdcef4b8fdb03b006000000000000000000000032'
      + 'D5213BA4BB6470F1B9EDA88CBC94E627')[:32]
   = 925bb207d49e62bcb9b1c4685154a8b3

Hence the first FORS secret key value revealed in the signature is

925bb207d49e62bcb9b1c4685154a8b3  # fors_sig_sk[0]

Set SIG = SIG || fors_sig_sk[0]

This is followed by the $6n$-byte FORS authentication path along the $a=6$ levels from the secret key to the FORS tree root. See below.

The first authentication path

The authentication path is computed using the $\mathsf{TreeHash}$ algorithm, explained in Authentication Path for a Merkle Tree.

The same principle is used except we use the specific SLH-DSA hash functions, $F()$ and $H()$, both of which both take an ADRS parameter which is different each time it is used:

Compute the public keys $pk$ on the base layer at height 0 using $pk = F(sk)$, where the FORS secret key $sk$ is computed as above
Then compute the parent nodes using $H(left||right)$ where the hash function $H()$ uses a different ADRS parameter each time.

The root of each tree is also computed and stored in a list for later use.

In our example, the first public key is derived from the secret key computed above using the F hash function with a type 3 address (FORS_TREE)

ADRS = 007cdcef4b8fdb03b003000000000000000000000032
                         ^^
sk = PRF(PK.seed, SK.seed, ADRS)
   = 925bb207d49e62bcb9b1c4685154a8b3
pk = F(PK.seed, ADRS, sk)
   = 81a7b89d408f2f91d81e9303d77b49c6

All the other leaf nodes ($pk$ values) required for the TreeHash algorithm are derived in the same way

The resulting authpath for the first secret key in our example is

2e58b70c7aed0e28507f31b49ec7ed6e  # fors_auth_path[0]
d6dcb8db2da90fe938994d75c80e6712
f2421c22def8af88906b768333e7ebf6
ddf7b84dc01f06731dd640cf93f57927
bb56f9da9d4b2abe60c81d863a20f8e5
c5cce74326d6181d01b74e3cd7f794a9

and this FORS tree has root value root[0]=fb0f55d9717066cf3c666854d1e2f928 (not part of the signature, but stored to compute the FORS public key later).

Set SIG = SIG || fors_auth_path[0]

We can demonstrate how to start computing the authentication path for the first FORS tree where the index is 50. The diagram below shows the relevant part of the tree with the 16-byte node values shortened to 3 bytes for brevity.

FORS tree in neighborhood of index 50

The secret key values are computed deterministically from the private key and their type 6 address (FORS_PRF) using

sk = PRF(PK.seed, SK.seed, ADRS)

sk[48]=06d6bddd89f5d5815063ca395e9b963d
sk[49]=ac6e9f1dc2226ed1cb2f86e3872f3fe0
sk[50]=925bb207d49e62bcb9b1c4685154a8b3  #fors_sig_sk[0]
sk[51]=c7005085cda77e80444a44480c67d454

The corresponding public keys (the nodes at height 0) are computed using F with a type 3 address (FORS_TREE)

pk = F(PK.seed, ADRS, sk)

adrs_c='007cdcef4b8fdb03b003000000000000000000000030' # 48=0x40
pk[48]=631195810d16cd1cf504d77e747317c7
adrs_c='007cdcef4b8fdb03b003000000000000000000000031' # 49=0x31
pk[49]=392e83145264282b3f728af62cd8fad8
adrs_c='007cdcef4b8fdb03b003000000000000000000000032' # 50=0x32
pk[50]=81a7b89d408f2f91d81e9303d77b49c6
adrs_c='007cdcef4b8fdb03b003000000000000000000000033' # 51=0x33
pk[51]=2e58b70c7aed0e28507f31b49ec7ed6e

The parent nodes are computed using the $H$ function

adrs_c  ="007cdcef4b8fdb03b003000000000000000100000018"  # 24
node[24]=H(PKseed, adrs_c, pk[48], pk[49])
        =d6dcb8db2da90fe938994d75c80e6712
adrs_c  ="007cdcef4b8fdb03b003000000000000000100000019"  # 25
node[25]=H(PKseed, adrs_c, pk[50], pk[51])
        =2364eb5855b474c27760b3933e0f911f
adrs_c  ="007cdcef4b8fdb03b00300000000000000020000000c"  # 12
node[12]=H(PKseed, adrs_c, node[24], node[25])
        =086fe170a5e4a56e952077e676cd4484

This process is repeated up to the root of the tree, recording the required authentication path values and saving the root value.

Python code

Here is some Python code to reproduce the above values using hardcoded ADRS values.

from slh_sha256 import PRF, SHA256, F, H
SKseed = 'D5213BA4BB6470F1B9EDA88CBC94E627'
PKseed = 'FA495FB834DEFEA7CC96A81309479135'

# Compute sk[i], pk[i] for i = 48 to 51

# ADRS to compute sk is type 6 (FORS_PRF)
# layer 0, tree height 0, leaf index 0, tree index = 48-51
adrs_c = '007cdcef4b8fdb03b006000000000000000000000030'  # 48=0x30
sk = PRF(PKseed, SKseed, adrs_c)
print(f"sk[48]={sk}") # 06d6bddd89f5d5815063ca395e9b963d
# ADRS to compute pk is type 3 (FORS_TREE)
adrs_c = '007cdcef4b8fdb03b003000000000000000000000030'
pk_48 = F(PKseed, adrs_c, sk)
print(f"pk[48]={pk_48}") # 631195810d16cd1cf504d77e747317c7

adrs_c = '007cdcef4b8fdb03b006000000000000000000000031'  # 49=0x31
sk = PRF(PKseed, SKseed, adrs_c)
print(f"sk[49]={sk}") # ac6e9f1dc2226ed1cb2f86e3872f3fe0
adrs_c= '007cdcef4b8fdb03b003000000000000000000000031'
pk_49 = F(PKseed, adrs_c, sk)
print(f"pk[49]={pk_49}") # 392e83145264282b3f728af62cd8fad8

adrs_c = '007cdcef4b8fdb03b006000000000000000000000032'  # 50=0x32
sk = PRF(PKseed, SKseed, adrs_c)
print(f"sk[50]={sk}") # 925bb207d49e62bcb9b1c4685154a8b3
adrs_c= '007cdcef4b8fdb03b003000000000000000000000032'
pk_50 = F(PKseed, adrs_c, sk)
print(f"pk[50]={pk_50}") # 81a7b89d408f2f91d81e9303d77b49c6

adrs_c = '007cdcef4b8fdb03b006000000000000000000000033'  # 51=0x33
sk = PRF(PKseed, SKseed, adrs_c)
print(f"sk[51]={sk}") # c7005085cda77e80444a44480c67d454
adrs_c = '007cdcef4b8fdb03b003000000000000000000000033'
pk_51 = F(PKseed, adrs_c, sk)
print(f"pk[51]={pk_51}") # 2e58b70c7aed0e28507f31b49ec7ed6e

# Compute values required for authpath
# node = H(left||right)
# ADRS type 3 (FORS_TREE) tree height=1, tree index=24=0x18
adrs_c = "007cdcef4b8fdb03b003000000000000000100000018"  # 24
node_24 = H(PKseed, adrs_c, pk_48, pk_49)
print(f"node[24]={node_24}") # d6dcb8db2da90fe938994d75c80e6712

adrs_c = "007cdcef4b8fdb03b003000000000000000100000019"  # 25
node_25 = H(PKseed, adrs_c, pk_50, pk_51)
print(f"node[25]={node_25}") # 2364eb5855b474c27760b3933e0f911f

# tree height=2 tree index=12
adrs_c = "007cdcef4b8fdb03b00300000000000000020000000c"  # 12
node_12 = H(PKseed, adrs_c, node_24, node_25)
print(f"node[12]={node_12}") # 086fe170a5e4a56e952077e676cd4484

Compute the remaining FORS signatures ($i=1,\ldots, 32$)

For the 2nd key ($i=1$) we have an index of 47 giving tree_index = 1*64 + 47 = 111 = 0x6f and the ADRS is updated to

ADRS_c = 00 7cdcef4b8fdb03b0 06 00000000 00000000 0000006f
sk = PRF(PK.seed, SK.seed, ADRS_c)
   = 8b4ed7a791a1b77c561a6e7ae64e4e17

Hence

8b4ed7a791a1b77c561a6e7ae64e4e17   # fors_sig_sk[1]

and the authentication path (computed separately) is

481de4ce7e26065d90ae21c965feba33  # fors_auth_path[1]
02102d7564e3b7414e1aa62271e9b4df
b42c57c44726af6fe7f3bdd486d7d578
b4b4ba8ebc1f5d7243f94d2d2d4cb55b
7f95c3020e05a6ccbe12cbdffd6466b5
b34369fa56839a0e05af5c6613e4a229

with tree root value root[1]=34c0d2ad1439f436a03efb94c1ce92dc (to be used to compute the FORS public key later)

Set SIG = SIG || fors_sig_sk[1] || fors_auth_path[1]

This process is repeated for all $k$ of the trees giving 33 FORS signature values and authentication path sequences.

The 33rd and final FORS signature ($i=32$) is computed as follows

We have an index of 28 giving tree_index = 32*64 + 28 = 2076 = 0x81c

ADRS_c = 00 7cdcef4b8fdb03b0 06 00000000 00000000 0000081c
sk = PRF(PK.seed, SK.seed, ADRS_c)
   = 2b38f096578c9a974ac0ce9a28d92351

Hence

2b38f096578c9a974ac0ce9a28d92351  # fors_sig_sk[32]

with authentication path

5c1fd369cda5f3fa35e7358efdb91a07  # fors_auth_path[32]
71f3daa64e685f5e24bc819c93486b28
71fe59a0a2749a15bcfe36c4ab4ac2ed
4803015faf8bd4c309ee883d4f58131f
778fbb608f07c3fb62e588cc47902b6a
0c646676640ab0ee1b342537e9376ce5

and root value for this tree root[32]=df3658bc1eaafcf157b2485e924b39ef.

Set SIG = SIG || fors_sig_sk[i] || fors_auth_path[i] for $i=2,\ldots, 33$

We now have FORS_SIG consisting of $k$ secret keys of $n$ bytes and $k$ authpaths of $a \cdot n$ bytes.

Plus we have stored $k$ root values of $n$ bytes in a list.

Compressing the tree root values to form the FORS public key

We have stored 33 $n$-byte root values for each of the $k=33$ trees. These are

roots=
fb0f55d9717066cf3c666854d1e2f928
34c0d2ad1439f436a03efb94c1ce92dc
6df0754919401d2f9a6a9d0143483178
b72f2d742429d2b014e4d9b0f6908589
acbaddfc1bbea958690b47b54da5437f
3f5529c3812ce9fe4b3a8ef4cc7ebf1d
76b0e70df7d9ac867186906a6a623188
a20c75e80be927d2256cab3092782e1a
4846ed7e0710391d31081175ab37af8a
4a4be9954a695b4255d1d459dcc0f14a
db43fe896787ea1dca4e91297f9ed053
ae0a12a089f7155af337e6ffaed8f234
22342fe15d5449b797268dfeeb0baa80
e9abce61c3b44b3914f1ec0d296dc520
b776498d75b925f09cc6d4c67c67eecf
b124ead4ccf45a5f53a3335dd4399289
e755365d8d8b69bc57167580a527c2fa
c0f8a2415b36951f57dee3b3552bb324
d5e15ae7e2bb82322ffcbb452c278af9
d6193f996b723cb70adaece4f7688676
14ab44994fd2a11ece0fc1f68e5c3b95
08837cde074f236bdc61d1f79127dc7e
c83f42a3890a72caeb82d0e5dbd2fdc2
d73808678126b32f03afeccae1a1e194
62ea003a0d5fc26fc4eb6eb238745274
2694235143fbde05c8e200d235e6cedf
798c3627804dfad4407e92b017f355df
3cd28a70bd5400b5c9fa2ca8287a592c
d52e12a26fab95a1f5883e1ce5cc5bfd
8aee8a58f5babef3a0e11f8f1ef7626d
f4b9f8d9ce3183b15ba6282b495a921b
8527aa43cf500c9075484efbb6646161
df3658bc1eaafcf157b2485e924b39ef

We don't save these tree root values explicitly - a verifier can recompute them using the revealed secret keys and the given authentication paths.

To compute the FORS public key, we use the T_k function to hash all these together with PK.seed and an ADRS parameter of type FORS_ROOTS=4.

ADRS=00 7cdcef4b8fdb03b0 04 00000000 00000000 00000000
FORS_PK = T_k(PK.seed, ADRS, roots)
        = SHA256_t(BlockPad(PK.seed) || ADRS || roots)
        = 33af163817cd6c2bea881ddf7d2b89ab

This FORS public key value (33af163817cd6c2bea881ddf7d2b89ab) is not explicitly included in the signature, but is used as an input to the hypertree signature.

<< previous: The ADRS parameter in SLH-DSA

Contents

next: The Hyper Tree Signature (SIG_HT) >>

Rate this page

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 16 February 2026.

Computing the FORS signature

FORS_sign algorithm

Step 1 - Compute the randomizer $R$

Python code

Step 2 - Compute H_msg

Python code to compute $H_{\text{msg}}$

Split H_msg into message digest, tree address and leaf index

Compute SIG_FORS

Python code to compute indices

Compute the first FORS secret key

The first authentication path

Python code

Compute the remaining FORS signatures ($i=1,\ldots, 32$)

Compressing the tree root values to form the FORS public key

Rate this page

Contact us

Step 2 - Compute `H_msg`

Split `H_msg` into message digest, tree address and leaf index