Skip to content
BranchesTags

Repository files navigation

Threshold-HBS

Implementation of a post-quantum threshold signature scheme based on LMS (Leighton-Micali Signature), following the k-of-k One-Time Threshold Signatures scheme described in:

John Kelsey, Nathalie Lang, and Stefan Lucks, Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures: Delegate Your Signing Capability, and Distribute it Among Trustees. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/a6ksudy6b

The end goal is for signatures produced by the threshold scheme to be indistinguishable from standard LMS signatures, directly verifiable with OpenSSL 4.

Table of Contents

Overview

The scheme implements a k-of-k threshold signature over LMS/LM-OTS. The core idea is that no individual trustee holds the LMS private key; instead, the Dealer distributes the sensitive information XOR-masked across all trustees. Only if the k trustees of a coalition collaborate can the final signature be reconstructed — a standard LMS object verifiable by any RFC 8554-compliant implementation.

The project includes two variants of the protocol:

  • Flat variant (KK_Setup / KK_Sign1 / KK_Sign2 / KK_Aggregator_Sign): a single fixed coalition of k trustees, all required for every signature. This is the ℓ-of-ℓ case described in the KLL paper, kept in the code as a reference baseline.
  • Sharded variant (ShardSetup / ShardSign1 / ShardSign2 / AggregatorSign): each KeyID of the LMS tree is assigned to a different coalition of trustees via a coalition list CL, enabling real threshold/distributed signatures without requiring every trustee for every signature. This is the variant used by ProtocolRunner.main and the one recommended for actual use.

Security stems from two properties:

  • One-time use: each (K[t], KeyID) pair is used exactly once. The Trustee rejects any reuse attempt (via usedKeyIDs in the flat variant, and by consuming the entry from its keylist in the sharded variant).
  • Round authentication: in Round 2, the Trustee verifies via KK_Auth that the received randomizer R is consistent with its own share, preventing substitution attacks by the Aggregator.

Project Structure

threshold-hbs/
├── src/
│   ├── main/java/es/uma/nicslab/hbs/
│   │   ├── lms/
│   │   │   ├── LM_OTS_WITH_CHAIN.java      # Generation of the full Winternitz chain (SK[i][j])
│   │   │   ├── LMOtsChain.java             # Container for the full chain
│   │   │   ├── LMSHashUtils.java           # Auxiliary LMS hash functions (H, computeH)
│   │   │   ├── LMSSerializer.java          # Converts a ThresholdSignature to the RFC 8554 wire format
│   │   │   └── ...                         # Remaining Bouncy Castle LMS/HSS classes
│   │   ├── model/
│   │   │   ├── CRV.java                    # Masked values: R, CHK, PATH, SK
│   │   │   ├── Round1Msg.java              # Round 1 message: (R_t, CHK_t)
│   │   │   ├── Round2Msg.java              # Round 2 message: (Z_t, PATH_t)
│   │   │   ├── SetupDealer.java            # Result of ShardSetup: trustees + board
│   │   │   └── ThresholdSignature.java     # Final assembled signature: (R, PATH, Z)
│   │   ├── protocol/
│   │   │   ├── PublicBulletinBoard.java    # CRV, CL, public key — public information shared by all parties
│   │   │   └── ProtocolRunner.java         # Orchestrates the full protocol (sharded variant)
│   │   ├── roles/
│   │   │   ├── Dealer.java                 # KK_Setup / ShardSetup
│   │   │   ├── Trustee.java                # KK_Sign1/KK_Auth/KK_Sign2 and ShardSign1/ShardSign2
│   │   │   └── Aggregator.java             # KK_Aggregator_Sign and AggregatorSign
│   │   ├── bench/
│   │   │   └── Benchmark.java              # Benchmarking harness (setup, signing, verification)
│   │   └── util/
│   │       ├── PRF.java                    # PRF built on KMAC-256 with 5 domain-separation labels
│   │       ├── ByteUtils.java              # XOR, concat, intToBytes, constantTimeEquals
│   │       └── LMSExporterOpenSSL.java     # Exports keys and signatures for OpenSSL
│   └── test/java/es/uma/nicslab/hbs/
│       └── roles/
│           ├── AggregatorTest.java
│           ├── TrusteeTest.java
│           └── DealerTest.java
├── LMSOpenSSL/
│   ├── cert.pem
│   ├── lmspub.pem
│   ├── message.bin
│   └── sig.file
├── ThresholdOpenSSL/
│   ├── lmspubthreshold.pem
│   ├── messagethreshold.bin
│   └── sigthreshold.file
├── bench/
│   └── results/                            # Raw benchmarking logs (see Benchmarking section)
├── pom.xml
└── README.md

Protocol Design

Roles

Role Responsibility Secret knowledge
Dealer Runs KK_Setup/ShardSetup exactly once. Generates and publishes the CRV (and, with sharding, the CL) on the PublicBulletinBoard. Takes no further part after setup. The keys K[1..k] of every trustee (only during setup)
Trustee Takes part in the two signing rounds, for the KeyIDs of its coalition(s). Only its own PRF key K[t]
Aggregator Coordinates the two rounds, reconstructs the values via XOR and assembles the final signature. The (public) CRV and the trustees' round messages. Knows no K[t].

Two-round flow

Dealer  ──KK_Setup / ShardSetup──►  CRV (+ CL) on the PublicBulletinBoard

         ┌─── Round 1 ───────────────────────────────────────┐
         │  Aggregator ──(KeyID, M)──► Trustee t             │
         │  Trustee t  ──(R_t, CHK_t)──► Aggregator          │
         └───────────────────────────────────────────────────┘

         ┌─── Round 2 ───────────────────────────────────────┐
         │  Aggregator ──(R, CHK'[t])──► Trustee t           │
         │  Trustee t  ──(Z_t, PATH_t)──► Aggregator         │
         └───────────────────────────────────────────────────┘

Aggregator assembles (R, PATH, Z) → standard LMS signature, verifiable with OpenSSL

Round 1 in detail:

  1. The Aggregator sends (KeyID, M) to each Trustee t belonging to the coalition for that KeyID.
  2. The Trustee checks that KeyID has not been used before (one-time protection) and that no other signature is in progress.
  3. Each Trustee computes R_t = PRF^R_{K[t]}(KeyID, n) and CHK_t = PRF^CHK_{K[t]}(KeyID, |CHK|) and returns them to the Aggregator.
  4. The Aggregator reconstructs R = CRV.R ⊕ R_1 ⊕ ... ⊕ R_k and CHK = CRV.CHK ⊕ CHK_1 ⊕ ... ⊕ CHK_k.

Round 2 in detail:

  1. The Aggregator sends (R, CHK[t]) to each Trustee t (where CHK[t] is the t-th block of the reconstructed CHK array).
  2. The Trustee runs KK_Auth: it checks that PRF^AUTH_{K[t]}(KeyID, R, n) == CHK[t]. If it fails, it returns ⊥.
  3. If authentication succeeds, the Trustee computes the message hash h, computes its share of the signature Z_t by walking the Winternitz chains over SK_t[i][j], and its share of the Merkle path PATH_t = PRF^PATH_{K[t]}(KeyID, |PATH|).
  4. The Aggregator reconstructs PATH = CRV.PATH ⊕ PATH_1 ⊕ ... ⊕ PATH_k and assembles Z by applying the Winternitz chains over CRV.SK and combining with the Z_t shares.

Sharding: coalitions per KeyID

In the flat variant, the k trustees passed to Dealer take part in every signature. With sharding, ShardSetup additionally takes an int[][] CL of length D (the number of KeyIDs in the tree), where CL[keyID] is the array of trustee indices authorized to sign with that particular KeyID.

  • Each Trustee calls TrusteeSetup(trusteeIndex, CL) after setup, which builds its keylist: the subset of KeyIDs it takes part in.
  • ShardSign1 only proceeds if the requested KeyID is in the trustee's keylist, and it consumes it from the list upon use (the one-time protection specific to this variant).
  • Aggregator.AggregatorSign(message, keyID) obtains the coalition from board.getCL()[keyID] automatically — the caller does not choose which trustees take part; the CL published at setup does.
  • Signing with one KeyID does not consume a trustee's availability for other KeyIDs belonging to different coalitions: one-time state is tracked per KeyID, not globally.

Main Data Structures

CRV (Common Reference Values)

The CRV holds the original LMS values, XOR-masked with the shares of every trustee in the corresponding coalition. It is public information (published on the PublicBulletinBoard), but it reveals no secret, since recovering any original value requires all the shares of the coalition at once.

Field Type Content
R byte[] R ⊕ R_1 ⊕ ... ⊕ R_k
CHK byte[] concat(CHK[1..k]) ⊕ CHK_1 ⊕ ... ⊕ CHK_k
PATH byte[] concat(PATH[1..h]) ⊕ PATH_1 ⊕ ... ⊕ PATH_k
SK byte[][][] SK[i][j] ⊕ SK_1[i][j] ⊕ ... ⊕ SK_k[i][j]

Where R is the LM-OTS randomizer, CHK is the trustees' authentication value, PATH is the Merkle authentication path, and SK[i][j] is the j-th element of Winternitz chain i. With sharding, k is the size of the coalition assigned to that particular KeyID (CL[keyID].length), which can vary from one KeyID to another.

PRF — Domain Separation Labels

The PRF is implemented with KMAC-256 using five domain-separation labels, to guarantee that outputs from different uses are independent of one another even though they share the same key K[t] and the same KeyID.

Label Invocation Use
R PRF^R_{K[t]}(KeyID, n) Randomizer share R_t
CHAIN PRF^CHAIN_{K[t]}(KeyID, i, j, n) Winternitz chain share SK_t[i][j]
CHK PRF^CHK_{K[t]}(KeyID, |CHK|) Verification-value share CHK_t
PATH PRF^PATH_{K[t]}(KeyID, |PATH|) Merkle path share PATH_t
AUTH PRF^AUTH_{K[t]}(KeyID, R, n) Randomizer authentication value in Round 2

Implementation

Dealer — KK_Setup / ShardSetup

KK_Setup (flat variant) and ShardSetup (sharded variant) each run exactly once, during the initialization phase. ShardSetup additionally takes the CL, and repeats the KK_Setup process for each of the D KeyIDs of the tree, using only the corresponding coalition CL[keyID] at each iteration.

For each KeyID, the Dealer:

  1. Computes CHK[t] = PRF^AUTH_{K[t]}(KeyID, R, n) for each trustee in the coalition (original authentication values).
  2. Generates the shares of each component by invoking the PRF with the corresponding label.
  3. Masks each original component via XOR with all its shares: CRV.X = X ⊕ X_1 ⊕ ... ⊕ X_k.
  4. Publishes the resulting CRV (and, with sharding, the CL) on the PublicBulletinBoard.

After setup, the Dealer takes no further part in the protocol, and the keys K[t] must be distributed to each trustee over a secure channel.

Trustee — KK_Sign1 / KK_Auth / KK_Sign2 / ShardSign1 / ShardSign2

Each Trustee keeps minimal state between rounds: the active keyID and the message M currently in progress. This state is cleared when Round 2 completes, or on any error (including a failed authentication).

Protections implemented:

  • One-time enforcement: the usedKeyIDs set (flat variant) or the keylist built by TrusteeSetup (sharded variant) track/consume the KeyIDs that have been processed. Any reuse attempt returns ⊥.
  • Signing state: if current != null when a new KK_Sign1/ShardSign1 arrives, it is rejected (two signatures cannot overlap).
  • Round authentication (KK_Auth): before proceeding with Round 2, the Trustee recomputes PRF^AUTH_{K[t]}(KeyID, R, n) and compares it against the CHK[t] received from the Aggregator. This prevents a malicious Aggregator from forcing the Trustee to sign with an R different from the one committed to in Round 1.

Aggregator — KK_Aggregator_Sign / AggregatorSign

The Aggregator orchestrates the full protocol in a single method (KK_Aggregator_Sign(message, keyID) in the flat variant, AggregatorSign(message, keyID) with sharding):

  1. Round 1: invokes KK_Sign1/ShardSign1 on each Trustee in the coalition and collects (R_t, CHK_t). Reconstructs R and the CHK array via XOR with the CRV.
  2. Round 2: invokes KK_Sign2/ShardSign2(R, CHK[t]) on each Trustee and collects (Z_t, PATH_t). Reconstructs PATH via XOR with the CRV.
  3. Final assembly: computes the message hash h, applies the Winternitz chains over CRV.SK to obtain Z_CRV, and combines: Z = Z_CRV ⊕ Z_1 ⊕ ... ⊕ Z_k.
  4. Returns a ThresholdSignature(R, PATH, Z), a standard LMS/LM-OTS object verifiable with OpenSSL.

If any trustee returns ⊥ in either round, the Aggregator aborts and returns null.

Verification with OpenSSL

Signatures produced by the threshold scheme are indistinguishable from standard LMS signatures and directly verifiable with OpenSSL 4.

Verifying an LMS signature

# Verify signature
openssl pkeyutl -verify -in message.bin -sigfile sig.file -inkey lmspub.pem -pubin

# Inspect the X.509 certificate
openssl x509 -in cert.pem -text -noout

# Extract the public key from the certificate
openssl x509 -in cert.pem -pubkey -noout > public_key_from_cert.pem

# Check the public key format
openssl pkey -in lmspub.pem -text -noout -pubin

Expected output:

Signature Verified Successfully

Verifying a threshold signature

openssl pkeyutl -verify \
  -in ThresholdOpenSSL/messagethreshold.bin \
  -sigfile ThresholdOpenSSL/sigthreshold.file \
  -inkey ThresholdOpenSSL/lmspubthreshold.pem -pubin

Benchmarking

es.uma.nicslab.hbs.bench.Benchmark measures the cost of ShardSetup (per KeyID), of a full signature (AggregatorSign) and of its verification, for several values of w (Winternitz parameter) and k (coalition size), alongside a plain (non-threshold) LMS baseline. It has no JUnit dependency; it runs directly as a main.

# Compile and run the benchmark
mvn compile
java -cp target/classes es.uma.nicslab.hbs.bench.Benchmark

Methodology: 8 warm-up iterations and 15 repetitions per configuration, reporting mean ± standard deviation. Raw logs for each run (with a hardware/JDK/parameters header) are kept under bench/results/.

Testing

Three JUnit 5 test classes under src/test/java/es/uma/nicslab/hbs/roles/:

  • DealerTest — setup validation (CRV dimensions, errors from a malformed CL or out-of-range coalitions).
  • TrusteeTest — the protocol's state machine (rejecting an out-of-coalition KeyID, overlapping signatures, an invalid CHK, KeyID reuse) and an end-to-end case with a k=1 coalition.
  • AggregatorTest — the full signing flow across different coalitions, cryptographic verification against BouncyCastle's LMS verifier, and one-time protection at the coalition level.

Requirements

Component Minimum version
Java (JDK) 17
Maven 3.6
Bouncy Castle (bcprov-jdk18on / bcpkix-jdk18on) 1.84 (included in pom.xml)
OpenSSL 4.0

Build and Run

# Build and run tests
mvn clean test

# Run the benchmark
mvn compile
java -cp target/classes es.uma.nicslab.hbs.bench.Benchmark

About

No description, website, or topics provided.

Resources

Readme
Activity
Custom properties

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages