LULA is Ring0 Labs’ research family of hash-based signature schemes. This first paper studies signing with a reusable cache.

Summary

The cache stores work in advance, making signing fast. For the same key and message, an honest restore leaves the signature unchanged whenever signing completes.

Cache ready
3.6 ms
Sign with the prepared data already in memory.
After restarting
5.7 s
Load the saved cache, then produce the first signature.
Cache missing
~5.5 min
Recompute the data needed for one signature.

Same key + same message → same signature, whenever signing completes.

32-byte messages. The first two times are medians. Cache loss: three runs (330–338 s), with recomputation required again for later signatures.

Measured comparison

32-byte messages. All times are milliseconds. Signing and verification are measured separately. N is the number of calls; “max” is the maximum observed, not a guarantee.

Prepared cache: stability campaign

Six blocks on one machine, one pinned logical processor. Different signing-query targets: LULA I 2^40, conditional; SLH-DSA 2^64. Hash backends differ; the physical core was not isolated.

ImplementationSignature (bytes)Sign median / p99 / max (ms)Verify median (ms)N
LULA I, cache in memory5,7203.59 / 6.32 / 57.260.1196,000
SLH-DSA-SHA2-128f, OpenSSL17,08810.78 / 16.92 / 125.570.6316,000
SLH-DSA-SHA2-128s, OpenSSL7,856232.17 / 330.25 / 605.570.2301,200

Separate exploratory measurements

Earlier campaign, with background load and different state and preprocessing assumptions. These rows are not pooled with the stability results. Small N limits the interpretation of p99.

Implementation / modeSignature (bytes)Sign median / p99 / max (ms)Verify median (ms)N
SHRINCS C B32, stateful324–3,50848.52 / 71.83 / 96.670.120200
SHRINCS C B32, forced fallback3,680471.96 / 616.74 / 616.740.44820
Compact PORS+FP, third-party Go4,0361,897.78 / 4,450.32 / 4,450.320.90512
Compact WOTS+C, our C reconstruction3,9523,613.61 / 4,128.47 / 4,128.470.54220

The compact rows use third-party or reconstructed code for Kudinov–Nick configurations, not the authors’ optimized implementation. SHRINCS sizes cover 200 measured indices; forced fallback was timed separately. Values are rounded.

After a restore

A backup can rewind a counter and make a signer reuse a one-time key. LULA I keeps no key-use counter.

Interactive · Restoring a snapshot

A counter goes back. A function does not.

Same snapshot, same events. Sign, restore, sign again. The tag is a toy stand-in for the signature.

Signer with a counter

no reuseno signatures yet

Counter now
0
Keys used for two messages
0

LULA I, deterministic signer

same outputno signatures yet

Tag for A
–
Tag for B
–

The cache is not modelled. Under honest restoration, it affects computation time rather than returned bytes. Reuse across two messages is an exposure event, not by itself a demonstrated forgery.

The cache occupies about 72 MiB. Signatures are 5,720 bytes; public keys are 32 bytes. The 5.7-second restart result includes loading and first signing, across 15 restarts. Cache-loss runs took 330.0, 331.8 and 337.6 seconds.

Those cache-loss runs used one CPU thread. GPU acceleration could reduce recomputation time; no GPU speedup has been measured for LULA I.

Read the paper

Published on Zenodo, DOI 10.5281/zenodo.23353281, CC BY 4.0. Developed by Ring0 Labs; published by Lugel Labs.

Open PDFDownload PDFZenodo record

Loading paper…

A note on the name

“I named it LULA because I felt like it. Sorry, friends—I need to have some fun sometimes.”