Relatively Little Signatures for SLH-DSA

This repository contains a tool to search the solution space for SLH-DSA parameter sets. It also contains some suggested parameter sets for the following scenarios:

• Code signing (limited to 2^24 signatures, tuned for signature size & verification time)
• General purpose (limited to 2^30 signatures tuned for signature size & overuse safety)

Outline

• Prior Work
• How to Build
• How to Use
• Parameter Sets
  • Code Signing (2^24 Signatures)
    • Level 1
    • Level 3
    • Level 5
  • General Purpose (2^30 Signatures)
    • Level 1
    • Level 3
    • Level 5

Prior Work

This project is heavily based on (and is tested against) Scott Fluhrer's work at https://github.com/sfluhrer/sphincs-param-set-search, and Scott Fluhrer and Quynh Dang's paper "Smaller Sphincs+" ¹. This project allows a greater variety of searches across the parameter set space of SLH-DSA, to customize the search for the constraints of firmware and software signing.

How to Build

go build ./cmd/slushfind

How to Use

The following flags can be used to customize the search:

• --target_security_level: the target security level (in bits), e.g., 128 for security level 1; 256 for security level 5.
• --overuse_security_level: the security level (in bits) for overuse analysis
• --min_sig_count: the (log_2 of the) minimum number of signatures the parameter sets need to support at full security strength
• --min_sig_count_at_overuse: the (log_2 of the) minimum number of signatures the parameter sets need to support at the reduced overuse security level
• --max_sig_size: the maximum size (in bytes) of signatures
• --min_sig_hashes: the minimum number of hashes the signer needs to compute in order to produce a signature
• --max_sig_hashes: the maximum number of hashes the signer needs to compute in order to produce a signature
• --max_cached_sig_hashes: the maximum number of hashes the signer needs to compute in order to produce a signature (assuming they cached the entire upper hypertree)
• --compare_cached_sig_hashes: when comparing parameter sets based on signing performance, compare the cached-hypertree cost instead of the full uncached cost
• --max_verify_hashes: the maximum number of hashes the verifier needs to compute in order to verify a signature
• --eval_sig_size: the weight for signature size when comparing parameter sets
• --eval_sig_hashes: the weight for signature cost when comparing parameter sets
• --eval_verify_hashes: the weight for verification cost when comparing parameter sets
• --table_format: the format to output the table in
• --name_prefix: a prefix to give to the parameter set IDs

Parameter Sets

The following parameter sets are generated by print_candidates.sh.

Code Signing (2^24 Signatures)

The following parameter sets are generated for use cases where a single message will be verified millions of times more often than it is signed, and where verification time and overall signature size are the most important considerations. Such use cases include, but are not limited to:

• Software signing
• Firmware signing
• DNS and similar record signing

These parameter sets choose 2^24 as the full-strength usage limit.

A 2^24-use key that is used to sign for 30 years should be rate-limited to one signature per ~1 minute (30 years / (2^24) = 56 seconds). Per ¹, a typical HSM's hash rate is less than 1 million hashes per second, so on typical HSM hardware, these parameter sets tend to self-enforce rate-limiting due to their high signing cost. For example, rls128c2 should take a typical HSM in 2025 around 1190 seconds (around 20 minutes) to sign a single message if the hypertree is not cached, otherwise it will take around 44 seconds. Even at one signature per 44 seconds, it will take over 23 years of constant use to drop below the full (128-bit / Level 1) security strength, and over 222 years to drop below 112 bits of security.

Comparison criteria:

• [50% (logarithmic)] signature size
• [50% (logarithmic)] verification cost

Other search constraints:

• max signature hashes: 3 billion to keep signing somewhat reasonable
• max signature size: 4096/8192/16384 bytes for level 1/3/5 to be competitive with other suggested reduced-size parameter sets, rounding up to multiples of 4096 (a common page size boundary)
• max verify hashes: 1000

Target security level 128, 2^24 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 112
rls128cs1	22	1	22	24	6	2	21	3856	1.45B	302M	311	27.25
rls128cs2	23	1	23	24	6	2	21	3872	2.6B	302M	312	28.25
rls128cs3	22	1	22	21	7	2	22	3920	1.19B	44M	315	26.87
rls128cs4	21	1	21	25	6	2	22	3936	1.18B	604M	316	27.29
rls128cs5	23	1	23	21	7	2	22	3936	2.34B	44M	316	27.87
rls128cs6	22	1	22	25	6	2	22	3952	1.75B	604M	317	28.29
rls128cs7	22	1	22	24	6	3	21	3504	1.85B	302M	359	27.25
rls128cs8	23	1	23	25	6	2	22	3968	2.9B	604M	318	29.29
rls128cs9	20	1	20	26	6	2	23	4016	1.5B	1.21B	321	27.31
rls128cs10	21	1	21	22	7	2	23	4016	663M	88.1M	321	26.93
rls128cs11	22	1	22	19	8	2	22	4016	1.16B	12.6M	321	26.85
rls128cs12	22	1	22	21	7	3	22	3568	1.6B	44M	363	26.87
rls128cs13	21	1	21	26	6	2	23	4032	1.78B	1.21B	322	28.31
rls128cs14	22	1	22	22	7	2	23	4032	1.24B	88.1M	322	27.93
rls128cs15	23	1	23	19	8	2	22	4032	2.31B	12.6M	322	27.85
rls128cs16	21	1	21	25	6	3	22	3584	1.38B	604M	364	27.29
rls128cs17	22	1	22	26	6	2	23	4048	2.36B	1.21B	323	29.31
rls128cs18	22	1	22	17	9	2	23	4048	1.15B	3.54M	323	26.32
rls128cs19	23	1	23	22	7	2	23	4048	2.39B	88.1M	323	28.93
rls128cs20	22	1	22	25	6	3	22	3600	2.16B	604M	365	28.29

Target security level 192, 2^24 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 128
rls192cs1	21	1	21	25	9	3	32	7752	2.03B	906M	526	30.65
rls192cs2	21	1	21	23	10	3	32	7896	1.38B	252M	532	30.65
rls192cs3	22	1	22	23	10	3	32	7920	2.51B	252M	533	31.65
rls192cs4	22	1	22	19	12	3	32	7920	2.28B	18.9M	533	30.31
rls192cs5	20	1	20	26	9	3	33	7944	2.38B	1.81B	534	29.66
rls192cs6	21	1	21	26	9	3	33	7968	2.94B	1.81B	535	30.66
rls192cs7	22	1	22	21	11	3	32	7968	2.33B	69.2M	535	31.35
rls192cs8	22	1	22	18	13	3	33	8088	2.27B	10.2M	540	30.12
rls192cs9	20	1	20	24	10	3	33	8112	1.07B	503M	541	29.66
rls192cs10	21	1	21	24	10	3	33	8136	1.63B	503M	542	30.66
rls192cs11	22	1	22	24	10	3	33	8160	2.76B	503M	543	31.66
rls192cs12	20	1	20	22	11	3	34	8184	703M	138M	544	29.65
rls192cs13	21	1	21	20	12	3	33	8184	1.17B	37.7M	544	30.32
rls192cs14	21	1	21	25	9	4	32	7368	2.62B	906M	666	30.65
rls192cs15	21	1	21	23	10	4	32	7512	1.97B	252M	672	30.65
rls192cs16	20	1	20	26	9	4	33	7560	2.67B	1.81B	674	29.66
rls192cs17	20	1	20	24	10	4	33	7728	1.36B	503M	681	29.66
rls192cs18	21	1	21	24	10	4	33	7752	2.22B	503M	682	30.66
rls192cs19	20	1	20	22	11	4	34	7800	996M	138M	684	29.65
rls192cs20	21	1	21	20	12	4	33	7800	1.75B	37.7M	684	30.32

Target security level 256, 2^24 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 192
rls256cs1	21	1	21	25	12	2	41	14944	2.33B	1.21B	602	29.98
rls256cs2	22	1	22	23	13	2	41	14976	2.57B	327M	603	30.2
rls256cs3	21	1	21	22	14	2	42	15264	1.3B	176M	612	29.26
rls256cs4	22	1	22	22	14	2	42	15296	2.42B	176M	613	30.26
rls256cs5	21	1	21	25	12	3	41	13568	2.72B	1.21B	696	29.98
rls256cs6	21	1	21	24	13	2	42	15360	1.77B	654M	615	30.22
rls256cs7	22	1	22	24	13	2	42	15392	2.89B	654M	616	31.22
rls256cs8	21	1	21	21	15	2	43	15520	1.21B	94.4M	620	29.17
rls256cs9	22	1	22	21	15	2	43	15552	2.33B	94.4M	621	30.17
rls256cs10	20	1	20	23	14	2	44	15680	912M	352M	625	29.27
rls256cs11	21	1	21	22	14	3	42	13888	1.69B	176M	706	29.26
rls256cs12	19	1	19	25	13	2	44	15712	1.59B	1.31B	626	28.73
rls256cs13	21	1	21	23	14	2	44	15712	1.47B	352M	626	30.27
rls256cs14	21	1	21	20	16	2	43	15712	1.17B	50.3M	626	28.96
rls256cs15	20	1	20	25	13	2	44	15744	1.87B	1.31B	627	29.73
rls256cs16	22	1	22	20	16	2	43	15744	2.29B	50.3M	627	29.96
rls256cs17	22	1	22	23	14	2	44	15744	2.59B	352M	627	31.27
rls256cs18	21	1	21	25	13	2	44	15776	2.43B	1.31B	628	30.73
rls256cs19	21	1	21	24	13	3	42	13984	2.17B	654M	709	30.22
rls256cs20	21	1	21	19	17	2	44	15840	1.15B	26.7M	630	28.65

General Purpose (2^30 Signatures)

The following parameter sets are generated for more general use cases.

These parameter sets choose 2^30 as the full-strength usage limit, but also require good overuse resilience (retaining 112/128/192 bits of security all the way up to 2^40 signatures).

A 2^30-use key that is used to sign for 30 years should be rate-limited to one signature per ~1 second (30 years / (2^30) = 0.88 seconds). In order to hit 2^40 signatures (the overuse scenario), the key would need to accidentally be used to sign a message every ~millisecond (30 years / (2^40) = 0.86 ms).

Comparison criteria:

• (100%) signature size

Other search constraints:

• max signature hashes:
  • uncached hypertree: 1.5 billion (half that of the code-signing case)
  • cached hypertree: 300 million (5 minutes on a single HSM)
• max signature size: 4096/8192/16384 bytes (as in the code-signing case)
• max verify hashes: 100000 (it is hard to actually reach this limit though)

Target security level 128, 2^30 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 112
rls128gp1	45	3	15	23	5	8	21	3520	579M	126M	7082	44
rls128gp2	45	3	15	19	6	8	21	3520	463M	9.44M	7082	43.02
rls128gp3	42	3	14	24	5	8	21	3552	478M	252M	7084	42.75
rls128gp4	48	3	16	16	7	8	20	3552	908M	1.38M	7084	44.64
rls128gp5	42	3	14	20	6	8	21	3568	245M	18.9M	7085	42.1
rls128gp6	42	3	14	17	7	8	21	3568	229M	2.75M	7085	41.21
rls128gp7	48	3	16	23	5	8	21	3568	1.03B	126M	7085	47
rls128gp8	48	3	16	19	6	8	21	3568	916M	9.44M	7085	46.02
rls128gp9	48	3	16	14	8	8	20	3568	907M	393K	7085	44.12
rls128gp10	42	3	14	15	8	8	21	3600	227M	786K	7087	40.94
rls128gp11	45	3	15	24	5	8	21	3600	705M	252M	7087	45.75
rls128gp12	39	3	13	21	6	8	22	3616	151M	37.7M	7088	40.68
rls128gp13	45	3	15	20	6	8	21	3616	472M	18.9M	7088	45.1
rls128gp14	45	3	15	13	9	8	21	3616	453M	221K	7088	42.48
rls128gp15	45	3	15	17	7	8	21	3616	456M	2.75M	7088	44.21
rls128gp16	39	3	13	18	7	8	22	3632	119M	5.51M	7089	40.05
rls128gp17	45	3	15	15	8	8	21	3648	454M	786K	7090	43.94
rls128gp18	48	3	16	24	5	8	21	3648	1.16B	252M	7090	48.75
rls128gp19	42	3	14	21	6	8	22	3664	264M	37.7M	7091	43.68
rls128gp20	45	3	15	19	6	7	21	3664	274M	9.44M	4202	43.02

Target security level 192, 2^30 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 128
rls192gp1	32	2	16	23	9	8	30	7224	1.1B	226M	6908	40.76
rls192gp2	34	2	17	22	9	7	31	7248	1.12B	113M	4085	41.75
rls192gp3	36	2	18	21	9	6	30	7272	1.2B	56.6M	2414	42.73
rls192gp4	34	2	17	18	11	7	31	7296	1.02B	8.65M	4087	40.28
rls192gp5	32	2	16	21	10	8	31	7320	936M	62.9M	6912	40.18
rls192gp6	34	2	17	20	10	7	31	7320	1.04B	31.5M	4088	41.16
rls192gp7	36	2	18	19	10	6	30	7320	1.16B	15.7M	2416	42.11
rls192gp8	32	2	16	23	9	7	30	7416	730M	226M	4092	40.76
rls192gp9	36	2	18	16	12	6	30	7416	1.14B	2.36M	2420	41.14
rls192gp10	39	3	13	23	8	8	29	7440	365M	201M	10220	45.96
rls192gp11	34	2	17	22	9	6	31	7440	684M	113M	2421	41.75
rls192gp12	48	3	16	22	8	8	28	7464	1.41B	101M	10221	53.92
rls192gp13	34	2	17	23	9	7	32	7464	1.23B	226M	4094	42.76
rls192gp14	34	2	17	17	12	7	32	7464	1.01B	4.72M	4094	40.24
rls192gp15	34	2	17	18	11	6	31	7488	580M	8.65M	2423	40.28
rls192gp16	36	2	18	22	9	6	31	7488	1.26B	113M	2423	43.75
rls192gp17	36	3	12	21	9	8	29	7512	138M	56.6M	10223	42.73
rls192gp18	42	3	14	23	8	8	29	7512	529M	201M	10223	48.96
rls192gp19	45	3	15	20	9	8	29	7512	683M	28.3M	10223	50.67
rls192gp20	32	2	16	21	10	7	31	7512	566M	62.9M	4096	40.18

Target security level 256, 2^30 signatures

id	h	d	h'	a	k	w	m	sig bytes	sign time	sign cached	verify time	sigs at 192
rls256gp1	34	2	17	21	13	7	41	12768	1.39B	81.8M	5316	40.12
rls256gp2	45	3	15	22	11	8	37	12832	994M	138M	13359	49.25
rls256gp3	42	3	14	19	13	8	37	12960	448M	20.4M	13363	45.8
rls256gp4	39	3	13	21	12	8	38	12992	289M	75.5M	13364	43.76
rls256gp5	39	3	13	23	11	8	38	12992	491M	277M	13364	44.4
rls256gp6	34	2	17	20	14	7	41	13024	1.35B	44M	5324	40.17
rls256gp7	39	3	13	18	14	8	38	13056	225M	11M	13366	42.84
rls256gp8	45	3	15	19	13	8	37	13056	876M	20.4M	13366	48.8
rls256gp9	42	3	14	21	12	8	38	13088	503M	75.5M	13367	46.76
rls256gp10	42	3	14	23	11	8	38	13088	705M	277M	13367	47.4
rls256gp11	42	3	14	18	14	8	38	13152	439M	11M	13369	45.84
rls256gp12	34	2	17	21	13	6	41	13152	837M	81.8M	3204	40.12
rls256gp13	36	3	12	20	13	8	38	13184	148M	40.9M	13370	41.01
rls256gp14	39	3	13	17	15	8	38	13184	220M	5.9M	13370	42.7
rls256gp15	45	3	15	21	12	8	38	13184	931M	75.5M	13370	49.76
rls256gp16	45	3	15	23	11	8	38	13184	1.13B	277M	13370	50.4
rls256gp17	34	2	17	22	13	7	42	13184	1.47B	164M	5329	41.17
rls256gp18	34	2	17	19	15	7	42	13216	1.33B	23.6M	5330	40.07
rls256gp19	39	3	13	15	17	8	38	13248	216M	1.67M	13372	41.92
rls256gp20	39	3	13	16	16	8	38	13248	217M	3.15M	13372	42.39

Footnotes

1. Fluhrer, Dang. "Smaller Sphincs+" https://eprint.iacr.org/2024/018.pdf ↩ ↩²