Skip to content
Crypto.world

Research

SILMARILS-MV: Information-Theoretically Secure Multi-Verifier Signatures with Dealer-Free Key Issuance and Linear Aggregation for Permissioned Blockchains

Dealer-free, linearly aggregatable signatures with unconditional unforgeability could replace heavy post-quantum quorum certificates in permissioned consensus, if the security proof holds.

SILMARILS-MV: Information-Theoretically Secure Multi-Verifier Signatures with Dealer-Free Key Issuance and Linear Aggregation for Permissioned Blockchains
arXiv
2610.31814
Published
2026-10-22
Authors
Khadijeh Bagheri, Hassan Khodaiemehr, Chen Feng

AI summary

Overview

  • Research area: Applied cryptography for permissioned blockchains — specifically unconditionally secure (information-theoretic) digital signatures, multi-party computation, and Byzantine fault-tolerant consensus certificates.
  • Technical level: Advanced. The paper is written for readers comfortable with finite-field algebra, secret sharing, MPC security definitions, and BFT protocol design; the constructions and proofs are stated in full algebraic notation.
  • Scope (one sentence): The paper constructs and evaluates SILMARILS-MV, a multi-verifier signature scheme whose unforgeability rests on information-theoretic security rather than computational hardness, with dealer-free key issuance by a BFT committee, unbounded transferability, and linear aggregation into constant-size finality certificates.

What This Paper Is About

Permissioned blockchains currently authenticate transactions, votes and quorum certificates with computationally secure signatures, which Shor's algorithm breaks and which post-quantum replacements make far larger. Information-theoretically secure signatures avoid computational assumptions entirely, but every prior approach has demanded a trusted authority that can forge, quantum or secret channels for every signature, per-signature interaction, or single-use keys with a bounded number of transfers. The paper's goal is a signature that is information-theoretically secure while also being non-interactive, multi-use, transferable without bound, aggregatable, and free of any single trusted authority — relying only on the honest-supermajority assumption (t < n/3) that a BFT committee already makes.

Key Contributions

  1. A multi-verifier construction with secret per-verifier functionals. A signature is the public vector α = A·e(m), and each verifier V_i holds a secret reconstruction functional c_i = Γ^T λ(x_i) derived from virtual anchors Γ that nobody ever learns. Signing costs (ω+1)(ψ+1) multiplications, verification costs ω+ψ+2, a signature is ω+1 field elements, and the scheme needs no interaction and no broadcast.

  2. An information-theoretic security proof against unbounded adversaries. Against an adversary that corrupts up to ω verifiers plus any signers and observes every honest decision, the probability that an honest verifier accepts a forged or invalid signature is at most Q/q + 1/(q−1), which the paper shows is tight in its leading term; the same single "Bad" event captures strong unforgeability, non-repudiation, transferability across unbounded hops, aggregate security, and sound arbitration, with simulation-based security in the Fitzi framework as a corollary.

  3. Dealer-free key issuance by the committee. A perfectly secure MPC protocol Π_DKI issues all keys for t < n/3 without a trusted dealer and without broadcast, with multiplications independent of the number of verifiers, because every verifier key is a public linear function of shared secrets; the point x_0 = 0 yields a committee arbiter whose key exists only in shared form.

  4. Threshold notarization and ledger integration at scale. The committee itself can hold the signing matrix in shares and sign "as one signer," producing finality certificates of constant size 32(ω+1) bytes in which honest shares are released only on decided values and per-validator issuance cost no longer depends on n; the paper adds arbiter-verified 32-byte signatures with batch arbitration, retroactive verifier enrollment, robust redistribution for membership change and share refresh, and three deployment modes (Table IV) plus information-theoretic equivocation evidence (Theorem 3).

Main Findings

  • Certificate verification is fast in practice: In a C implementation over F_{2^255−19}, a certificate verifies in 2.4 μs.
  • Threshold notarization cuts authentication traffic sharply at 1000 validators: In an analytic normal-case model at 1000 validators, threshold notarization needs 71 KiB of authentication traffic per validator per block — 22× less than ML-DSA-44, within the admitted-verifier setting the scheme considers.
  • Prototype throughput and CPU gains at 100 validators: In a Rust HotStuff prototype with 100 validators, SILMARILS-MV commits 2.8× more transactions per second than ML-DSA-44 with 67× less cryptographic CPU, and Monte-Carlo attacks are consistent with the proven bounds.
  • Concrete security margin at the chosen field: With q = 2^255−19, Q = 2^64 verification decisions over the system's lifetime, and at most E = 2^64 epochs with independently sampled anchors, Pr[Bad] ≤ 2^64/(2^255−19) + 2^64/(2^255−20) < 2^−189, holding against unbounded (including quantum) adversaries; the paper notes the MAC, decoder and redistribution terms are separate.
  • The cost that does not disappear: Dealer-free issuance in the individual-vote mode costs more total bandwidth than ML-DSA for committees larger than about ten validators; threshold notarization removes this growth (at n = 1000 it uses an estimated 71 KiB per validator per block versus 1.5 MiB for ML-DSA-44), but its certificates attest to the committee's decision rather than to individual votes unless an accountable variant is added.
  • Hashing margin is set by field size, not digest length: Because messages are reduced modulo q ≈ 2^255, generic collision attacks need about q^{1/2} ≈ 2^127.5 classical or q^{1/3} ≈ 2^85 quantum queries whatever the digest length; a larger margin requires splitting a SHA3-512 digest injectively into three field elements (254+254+4 bits) and signing with the vector encoding (L = 3, one message per index, encoding dimension 4), which reduces the assumption to collision resistance of SHA3-512 itself.
  • Storage is manageable at moderate committee sizes: At n = 31, ω = 10, ψ = 16 and a one-hour epoch of 3600 blocks, each validator stores 3.7 MiB of verifier keys and 1.3 MiB of signing keys.
  • Small signatures in the arbiter-verified mode: Arbiter-verified keys give clients 32-byte signatures that are checked in batches, with an exhaustive check of batch arbitration reported in the evaluation.
  • Security model makes trust explicit: The paper follows the Swanson–Stinson distinction between signatures produced by the signer and signatures that merely pass verification, and separates acceptance into validity, authenticity and acceptability so that dispute resolution and trust assumptions are stated rather than assumed away.
  • Stated costs and assumptions: Verification keys are secret and verifiers must be admitted by the committee; key material is consumed per signature and refreshed every epoch; issuance requires private channels and an honest committee supermajority within each epoch; t+1 colluding committee members of an epoch could forge for that epoch.

Methodology in Plain English

The design starts from an observation about the authors' earlier scheme, SILMARILS: there, the verifier reconstructs a Shamir sharing using public weights, so anyone who learns the per-message receipt can solve the public linear system and forge. SILMARILS-MV reverses this. The signature is a public vector built from a secret random matrix, but the weights each verifier uses to check it are secret and differ per verifier. A coalition of up to ω corrupted verifiers therefore learns only ω linear functionals of that matrix — which is never enough to predict what an honest verifier's functional will point at — while a dishonest signer who knows its own matrix does not know where the honest functionals point and so cannot craft a signature that some honest verifiers accept and others reject.

Everything else follows from one structural fact: signing and verification are linear in the verifier key, in the signature, and in the signing key. Linearity in the verifier key gives dealer-free issuance, because every verifier key becomes a public linear function of shared secrets held by the committee, so issuance needs only multiplications to form ΓA regardless of how many verifiers exist. Linearity in the signature gives aggregation, because signatures of different signers on the same message simply add. Linearity in the signing key gives threshold notarization, because the committee can hold the signing matrix in shares and release shares of A·e(m) only after deciding m, and any t+1 correct shares interpolate a certificate. Each of these components inherits the single core security theorem rather than requiring a new assumption, and the deployment modes differ only in who holds the signing matrix and who holds verifier keys.

The work is validated on several fronts: proofs of the core bound and its tightness, a C implementation of the core benchmarked against Ed25519, ML-DSA, Falcon and SLH-DSA on one host, an analytic ledger model up to n = 1000, a Rust HotStuff prototype up to n = 100, simulations with Byzantine members, Monte-Carlo checks of the security bounds, and an exhaustive check of batch arbitration.

Why This Matters

Impact on research. The paper shows that the usual trade-offs in information-theoretic signatures — a trusted authority, quantum links, per-signature interaction, or degrading transferability — are not intrinsic to unconditional security. It obtains unforgeability, unbounded transferability and linear aggregation simultaneously from the same honest-supermajority assumption a BFT committee already relies on, and it opens a research direction where consensus-level certificates are information-theoretic rather than computational, so evidence does not weaken retroactively as cryptanalysis advances.

Real-world applications.

  • Long-lived audit and slashing records: Because evidence signed today remains unforgeable for as long as the ledger is audited, dispute and slashing records do not decay if the underlying hardness assumption falls.
  • Post-quantum consensus certificates: Finality certificates of constant size 32(ω+1) bytes replace the 0.7 KB to 17 KB post-quantum signatures that would otherwise ride in every vote and certificate.
  • Cross-organizational permissioned ledgers: Hyperledger Fabric-style endorsement and Tendermint/HotStuff-style quorum certificates can carry compact, transferable, non-repudiable evidence to external auditors via arbiter-verified 32-byte signatures.
  • Committee hand-over and membership churn: Robust redistribution supports membership changes and share refresh without a trusted dealer, and verifiers can be enrolled retroactively.

Industry relevance. The evaluation is deliberately engineering-facing: a C core compared against deployed and standardized schemes on a single host, a Rust HotStuff prototype measured in transactions per second and CPU, and a traffic model at 1000 validators. The reported 2.8× throughput advantage and 67× cryptographic CPU reduction against ML-DSA-44 at 100 validators, and 22× less per-validator authentication traffic at 1000 validators, are the kind of numbers a ledger operator can act on — though the paper is upfront that verifiers must be admitted, keys must be refreshed per epoch, and issuance requires private channels.

Future Directions

  • An accountable threshold-notarization variant. The paper notes that threshold-notarization certificates attest to the committee's decision rather than to individual votes unless an accountable variant is added, which is the clearest open construction question.
  • Validating the malicious-case issuance cost. The semi-honest cost of Π_DKI is validated by simulation, while the malicious cost is estimated; a full malicious-case implementation and measurement would firm up the deployment numbers.
  • Instantiating private channels at scale. Issuance assumes synchronous, private, authenticated point-to-point channels; the paper points to Section X for how to instantiate them (including with QKD or pre-shared pads), but operational deployment of those channels across a wide-area validator set remains open.
  • Closing the individual-vote bandwidth gap. Dealer-free issuance in the individual-vote mode costs more total bandwidth than ML-DSA beyond roughly ten validators, so reducing that crossover — or extending the accountable variant to cover individual votes — would broaden applicability.
  • Widening the hashing margin beyond 2^85 quantum queries. Because the reduction-modulo-q hash caps generic collision resistance at about q^{1/2} classical and q^{1/3} quantum regardless of digest length, adopting the three-element SHA3-512 encoding as a default would remove that ceiling.

Target Audience

Cryptography and security researchers working on unconditionally secure signatures, secret sharing and MPC; blockchain protocol engineers designing BFT consensus, quorum certificates and post-quantum migration paths; and graduate students or advanced practitioners who need a rigorous, fully proved treatment of how information-theoretic authentication can be made practical inside a permissioned ledger. Readers seeking an accessible introduction to signatures should look elsewhere first — the paper assumes fluency in finite-field algebra and simulation-based security, and its value lies in the construction, the tight bound, and the measured systems performance.

Authors’ abstract

Permissioned blockchains authenticate transactions, votes and quorum certificates with computationally secure signatures, and post-quantum replacements inflate consensus traffic by orders of magnitude. Information-theoretic alternatives have required a trusted authority, quantum channels, per-signature interaction, or single-use keys with bounded transfer. We present SILMARILS-MV, a multi-verifier unconditionally secure signature in which a signature is the vector…

The full abstract on arXiv
Read the original paper