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

PREPRINT

1

SILMARILS-MV: Information-Theoretically Secure Multi-Verifier Signatures with Dealer-Free Key Issuance and Linear Aggregation for Permissioned Blockchains arXiv:2610.31814v1 [cs.CR] 22 Oct 2026

Khadijeh Bagheri, Hassan Khodaiemehr, and Chen Feng

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 α = A e(m) and each verifier holds a secret functional ci = ΓT λ(xi ) derived from virtual anchors Γ that nobody learns. Against unbounded adversaries corrupting up to ω verifiers and any signers, and observing every decision, an honest verifier accepts a forged or invalid signature with probability at most Q/q + 1/(q − 1), a bound that is tight in its leading term. The scheme is strongly unforgeable, non-repudiable, transferable across unboundedly many hops, and linearly aggregatable. Keys are issued by the validators through perfectly secure MPC for t < n/3, without broadcast. To scale, we let the committee itself sign: in threshold notarization, finality certificates have constant size 32(ω + 1) bytes, honest shares are released only on decided values, and per-validator issuance cost no longer depends on n. Arbiterverified keys give clients 32-byte signatures checked in batches, robust redistribution supports membership changes and share refresh, and verifiers can be enrolled retroactively. In C over F2255 −19 , a certificate verifies in 2.4 µs. In an analytic normalcase 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 considered by SILMARILS-MV. 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 bounds. Index Terms—Unconditionally secure signatures, informationtheoretic security, quantum-safe blockchain, Byzantine fault tolerance, threshold signatures, multi-party computation, aggregate signatures, quorum certificates.

I. I NTRODUCTION

D

IGITAL signatures are the authentication backbone of permissioned blockchains. In Byzantine fault-tolerant (BFT) protocols such as PBFT [1], HotStuff [2], [3] and Tendermint [4], as well as in endorsement-based platforms such as Hyperledger Fabric [5], signatures serve three roles at K. Bagheri, H. Khodaiemehr and C. Feng are with the School of Engineering, Faculty of Applied Science, The University of British Columbia (Okanagan Campus), Kelowna, BC, Canada (e-mail: khadijeh.bagheri@ubc.ca; hassan.khodaiemehr@ubc.ca; chen.feng@ubc.ca). Preprint, October 2026. This is the full version of the paper, with all proofs and the complete evaluation.

once. They authenticate client transactions as these are relayed through gossip and mempools. They let a leader convince every replica that a quorum of 2t + 1 validators voted for a block, through a quorum certificate (QC). And they provide transferable, non-repudiable evidence that is later used for accountability and slashing [6]–[8]. The third role is the most demanding: evidence must stay convincing to third parties long after it was produced. All signatures deployed today are computationally secure. Elliptic-curve schemes fall to Shor’s algorithm [9], [10]. The NIST post-quantum standards, ML-DSA [11], [12], Falcon [13] and SLH-DSA [14], [15], replace the hardness assumption but keep the computational nature. They also inflate signatures from 64 B to between 0.7 KB and 17 KB, and BFT protocols carry these signatures in every vote and certificate. Post-quantum migration efforts for ledgers [16]–[18] report precisely this overhead. A structural problem remains that no computational scheme removes: evidence signed today must remain unforgeable for as long as the ledger is audited; consequently, any future cryptanalytic progress against the underlying assumption retroactively weakens slashing and dispute records [19]. Information-theoretically (unconditionally) secure signatures (USS) remove computational assumptions entirely [20]– [23]. Unlike public-key signatures, a USS must give each verifier a different secret verification key, and it must explicitly handle disagreement between verifiers [23]. Every known approach pays a price that is hard to reconcile with a production ledger: polynomial constructions [21], [22], [24] require a trusted authority that generates all keys and can therefore forge; the universal-hashing scheme of Amiri et al. [25] and quantum digital signatures (QDS) [26]–[30] remove the authority but consume key material per message, need secret or quantum channels for every signature, and support only a bounded number of transfers through decreasing verification levels; pseudo-signatures [31]–[33] and information-checking (IC) signatures [34], [35] are tailored to broadcast inside MPC and support few transfers or require interaction. Our own earlier framework, SILMARILS [36], combines a compact algebraic designated-verifier (DV) mode with a three-party IC mode. The DV mode lets the verifier simulate signatures and is therefore not transferable. The three-party mode needs an interactive consistency phase with authenticated broadcast for every signature, and it supports exactly one transfer.

PREPRINT

2

A. Our Approach This paper asks whether a signature can be informationtheoretically secure and at the same time non-interactive, multi-use, transferable without bound, aggregatable, and free of any single trusted authority, using only an assumption a BFT committee already makes: an honest supermajority t < n/3. We answer affirmatively with SILMARILS-MV. The design starts from one observation about our earlier construction. In SILMARILS the verifier reconstructs a Shamir sharing with public weights; hence anyone who learns the per-message receipt can solve the public linear system and forge [36]. SILMARILS-MV reverses this. The signature is a public vector α = A e(m), where e(m) = (1, m, . . . , mψ )T . The reconstruction weights are secret and differ per verifier: verifier Vi accepts iff cTi α = bTi e(m) with bi = AT ci . A coalition of ω verifiers learns ω linear functionals of A, which is never enough to predict the functional of an honest verifier. Conversely, a dishonest signer who knows A does not know where the honest functionals point and therefore cannot craft a signature that some honest verifiers accept and others reject. One property, three uses. Everything else in this paper follows from a single structural fact: signing and verification are linear in the verifier key, in the signature and in the signing key. Each linearity yields one component, and each component inherits the security theorem of the core scheme (Theorem 1) instead of needing a new assumption. (i) Linear in the verifier key: dealer-free issuance. We set ci = ΓT λ(xi ), where λ(x) = (1, x, . . . , xω )T , xi is a public identifier and the virtual anchors Γ are held in shares by the committee and never reconstructed. Every verifier key is then a public linear function of shared secrets, issuance needs multiplications only to form ΓA, independently of the number of verifiers, and the point x0 = 0 supplies a committee arbiter whose key exists only in shared form. (ii) Linear in the signature: aggregation. Signatures of different signers on one message add up, and a quorum certificate (QC) is a single (ω + 1)-vector. (iii) Linear in the signing key: threshold notarization. The committee can hold A in shares and sign as one signer: each member releases its share of Ae(m) once it has decided m, and any t+1 correct shares interpolate a certificate. The committee is then a single signer and its verifiers are external; hence neither the issuance cost nor the collusion bound ω grows with the committee. The deployment modes of Sections VII and VIII are therefore not separate schemes. They differ only in who holds the signing matrix (a validator, a client, or the committee in shares) and who holds verifier keys (all validators, external auditors, or the arbiter alone), and every unforgeability claim reduces to Theorem 1. The paper follows this line: the core scheme and its proof (Sections IV and V), issuance (Section VI), deployment and scaling (Sections VII and VIII), and evaluation up to 1000 validators (Section IX). B. Contributions Table I summarizes our contributions. We are explicit about the costs (Section X). Verification keys are secret and verifiers must be admitted by the committee; key material is consumed per signature and refreshed every epoch;

TABLE I C ONTRIBUTIONS OF THIS PAPER . Contribution

Result

Construction (Section IV)

Signing, verification, linear aggregation and dispute resolution; a signature is ω + 1 field elements, signing costs (ω + 1)(ψ + 1) and verification ω + ψ + 2 multiplications; no interaction, no broadcast.

IT security (Section V)

Pr[Bad] ≤ Q/q + 1/(q − 1) against unbounded adversaries that corrupt ω verifiers and any signers and observe every decision (Theorem 1). Strong unforgeability, non-repudiation, unbounded-hop transferability, aggregate security, arbitration; the leading term of the bound, ω and ψ are tight (Proposition 2); simulation-based security in the Fitzi framework (Corollary 4).

Dealer-free issuance (Section VI)

Perfectly secure MPC ΠDKI for t < n/3 without broadcast; multiplications independent of the number of verifiers; semi-honest cost validated by simulation, malicious cost estimated.

Ledger integration (Section VII)

Votes, aggregated QCs, transaction relays, information-theoretic equivocation evidence (Theorem 3), epochs; three deployment modes (Table IV).

Scaling (Section VIII)

Threshold notarization with soundness, uniqueness and robustness (Theorem 4) and per-validator issuance independent of n; 32-byte arbiter-verified keys with batch arbitration (Lemma 4); retroactive enrollment (Proposition 3); robust redistribution (Lemma 5); comparison with threshold signatures (Table V).

Evaluation (Section IX) C core versus Ed25519, ML-DSA, Falcon and SLH-DSA on one host; ledger model up to n = 1000; Rust HotStuff prototype up to n = 100; simulations with Byzantine members; Monte-Carlo checks of the bounds and an exhaustive check of batch arbitration.

issuance needs private channels and an honest committee supermajority within each epoch. In the individual-vote mode, dealer-free issuance costs more total bandwidth than ML-DSA for committees larger than about ten validators. Threshold notarization removes this growth: at n = 1000 it needs an estimated 71 KiB per validator per block in the normal case, against 1.5 MiB for ML-DSA-44, but its certificates attest to the committee’s decision rather than to individual votes unless the accountable variant is added. II. R ELATED W ORK Table II summarizes prior work by area, and Table III compares the resulting signature families property by property. Two lines of work matter most. Information-theoretic signatures either rely on a trusted authority that can impersonate any signer [21]–[23], or consume keys per message and degrade with every transfer [25], [26]. Scalable certificates for BFT rely on computational threshold signatures [37]–[40], which Table V compares with threshold notarization. Kniep et al. [41] avoid post-quantum aggregation altogether: their distributed quorum signatures turn a certificate into a local event of a Bracha-style approval broadcast over ordinary postquantum signatures, with constant-size messages and public verification, but a certificate convinces a party outside the protocol only through the O(n) underlying signatures. Threshold notarization instead gives a constant-size, informationtheoretic certificate that verifiers can forward, at the price of secret verifier keys. We follow the security model of Swanson and Stinson [23], which distinguishes signatures produced by

PREPRINT

3

the signer from signatures that merely pass verification and makes dispute resolution and trust assumptions explicit. III. P RELIMINARIES AND S YSTEM M ODEL A. Notation and Algebraic Tools Let q be a prime and Fq the field with q elements. Vectors are columns and T denotes transposition. For integers ω, ψ ≥ 1 and x, m ∈ Fq we write λ(x) = (1, x, x2 , . . . , xω )T ∈ Fω+1 , q e(m) = (1, m, . . . , mψ )T ∈ Fψ+1 . q For a matrix K, row(K) is its row space. Pr[·] is taken over $ all coins of the experiment, and x ← − S denotes uniform sampling. We use two elementary facts throughout. Lemma 1 (Vandermonde independence). If x0 , . . . , xω ∈ Fq are pairwise distinct, then λ(x0 ), . . . , λ(xω ) form a basis of Fω+1 . Likewise, any j ≤ ψ +1 vectors e(m1 ), . . . , e(mj ) with q distinct mℓ are linearly independent. Lemma 2 (Affine uniformity). Let S ⊆ Fdq be a non-empty affine subspace with linear part L, let X be uniform on S, and let f : Fdq → Fq be affine. If there is ∆ ∈ L with f (X + ∆) ̸= f (X), then f (X) is uniform on Fq ; in particular Pr[f (X) = y] = 1/q for every fixed y. Proof. Write f (z) = ℓ(z) + f0 with ℓ linear; then ℓ(∆) = f (X + ∆) − f (X) ̸= 0. The sets X0 + {s∆ : s ∈ Fq } partition S into lines of equal size. Along each line f takes the values f (X0 ) + s ℓ(∆), which is every element of Fq exactly once. Averaging over the lines gives the claim.

phases), broadcast is emulated perfectly for t < n/3 by Byzantine agreement over point-to-point channels [81], which the committee runs anyway as part of consensus. This contrasts with the three-party mode of SILMARILS and with information checking [34], [60], where every signature requires an authenticated broadcast of the holder’s challenge and of the consistency verdicts. Adversary. The adversary A is computationally unbounded, malicious and static. It corrupts a set T ⊆ P with |T | ≤ t, a set of verifiers C ⊆ V with |C| ≤ ω and T ∩ V ⊆ C, and an arbitrary subset UC ⊆ U of signers. When V = P we choose ω ≥ t. Because security is information-theoretic and all honest messages are classical, the guarantees hold verbatim against quantum adversaries (Remark 6). C. Syntax Definition 1 (Multi-verifier USS). A multi-verifier unconditionally secure signature (MV-USS) scheme with parameters (q, ω, ψ, N ) consists of: KeyIssue, an interactive protocol run by P (or, in the trusted-dealer variant, a dealer). It gives each signer U ∈ U a stateful signing key with N indices k ∈ [N ] := {0, . . . , N − 1}, each usable for ψ distinct messages, and gives each Vi a secret verification key. Sign(U, k, m) → σ, which signs m ∈ Fq under index k ∈ [N ], or returns ⊥ if index k has already signed ψ distinct messages. Verifyi (σ) → {0, 1}, run by Vi . Aggregate and AggVerifyi , which combine and verify signatures of distinct signers on a common message. Resolve(σ) → {0, 1}, the committee arbiter’s verdict. Arbitrary messages M ∈ {0, 1}∗ are mapped to m = H(M ) ∈ Fq by a collision-resistant hash (Remark 1).

B. Participants, Channels and Adversary Participants. A committee P = {P1 , . . . , Pn }, the validators of a permissioned ledger, tolerates t < n/3 Byzantine members. A set of verifiers V = {V1 , . . . , Vν }, normally V = P, is indexed by public, pairwise distinct, non-zero identifiers x1 , . . . , xν ∈ Fq ; hence ν ≤ q −1. Committee share points (Sections VIII-B and VIII-E) are likewise distinct and non-zero, which requires n, n′ ≤ q −1, and we assume ψ < q. These conditions hold trivially for the field q = 2255 −19 used throughout. A set of signers U contains validators and clients. The committee arbiter V0 is a virtual verifier at point x0 = 0: its key exists only in shared form inside the committee. Channels. Key issuance (Section VI) assumes synchronous, private, authenticated point-to-point channels between committee members and from the committee to each signer and verifier. This is the standard model of information-theoretic MPC [35], [67]; Section X discusses how to instantiate it. Signatures themselves travel over arbitrary public channels, and their verification is non-interactive. No broadcast channel. We do not assume a broadcast channel. Signing, aggregation and verification involve no broadcast at all: a signature is a single message that may be forwarded point-to-point, or through untrusted relays, any number of times. Key issuance and resolution use point-to-point channels only. Where the underlying MPC sub-protocols are stated with a broadcast channel (in their complaint and fault-detection

D. Security Model We follow the philosophy of Swanson and Stinson [23] and distinguish signatures that the signer produced from signatures that merely pass a verification algorithm. To quantify over adaptive behavior, the adversary observes every decision of every honest verifier. Definition 2 (Validity, authenticity, acceptability). Each signer U and index k determine a secret signing matrix AU,k (Section IV). An individual signature σ = (U, k, m, α) is valid if α = AU,k e(m). It is authentic if it was output by the signing oracle of an honest U . An P aggregate σS = (m, (U, kU )U ∈S , αS ) is valid if αS = U ∈S AU,kU e(m), and authentic if it is valid and every honest U ∈ S has signed (kU , m). A signature or aggregate is acceptable if it is authentic whenever it involves an honest signer, and valid otherwise. Definition 3 (Experiment Expmv-uss ). (i) A fixes T, C, UC . A Keys are issued, and A receives the keys of all corrupted signers and verifiers together with the view of T during issuance. (ii) A adaptively queries: S IGN(U, k, m) for honest U ; V ER(i, σ) and AGG V ER(i, σS ) for honest Vi , i ∈ {0, . . . , ν} \ C; and R ES(σ). Each query returns the honest decision bit. Every decision honest parties take in a higherlevel protocol is modeled as such a query. (iii) Bad is the event

PREPRINT

4

TABLE II R ELATED WORK BY AREA , AND HOW SILMARILS-MV RELATES TO IT. Area

Representative work

Gap, and relation to SILMARILS-MV

What it achieves 2

IT authentication and Wegman–Carter [42], [43]; A /multi-receiver arbitration codes [44]–[47]

Unconditional authentication, also No transferable, non-repudiable evidence to third parties; when sender and receivers SILMARILS-MV adds secret per-verifier functionals with a distrust each other global validity predicate.

USS with trusted authority

Chaum–Roijakkers [20]; Hanaoka et al. [21], [24]; Shikata et al. [22], [48]; Swanson–Stinson [23]; group variants [49]

Polynomial USS with transferability; formal models with dispute resolution

The authority generates all keys and can forge; in SILMARILS-MV, keys are issued by MPC with virtual anchors, and the signer does not learn the key polynomial.

USS without authority

Amiri et al. [25], [50]

Universal-hash keys exchanged over secret channels

One message per key distribution; transfer bounded by degrading thresholds. SILMARILS-MV is multi-use per index, with unbounded transfer.

Quantum digital signatures and quantum-secured ledgers

QDS [26], [51]–[54]; one-time universal hashing [27], [28]; multi-user [29], [30]; ledgers [55]–[57]

IT security through quantum key distribution

Quantum links, per-message keys, bounded transfer. SILMARILS-MV needs no quantum hardware and can use QKD keys for its issuance channels.

Information checking IC [34], [35]; pseudo-signatures [31]–[33], [58]; Fitzi and framework [59], [60] pseudo-signatures

Broadcast and MPC from correlated randomness

Interactive or bounded transfers; the three-party mode of SILMARILS [36] needs broadcast and allows one transfer. SILMARILS-MV meets the same framework non-interactively (Corollary 4).

Designated-verifier signatures

DVS [61]; strong and universal DVS [62], [63]; two-party SILMARILS [36]

Deniability: the verifier can simulate signatures

Non-transferable by design; SILMARILS-MV targets the opposite goal, transferable evidence.

Post-quantum signatures in ledgers

Surveys and systems [10], [16], [17]; NIST PQ replacements and aggregation standards [11], [14], [64]; Falcon SNARGs [18]; BLS for consensus; accountability and Fabric multi-signatures [65], [66]; forensics [6], [7] needs transferable evidence

Large signatures, costly aggregation, computational security; BLS is not PQ. SILMARILS-MV gives small, linearly aggregatable IT evidence.

Threshold certificates BLS threshold [37], [38]; lattice threshold [39], [40]; and MAC-based BFT PBFT with MACs [1]

Compact committee certificates; signature-free consensus

Computational and publicly verifiable, or non-transferable (MACs). TN combines MAC-authenticated agreement with IT certificates (Section VIII-B and Table V).

Post-quantum quorum certificates

Distributed quorum signatures (DQS) [41]

Constant-size messages from ordinary post-quantum (e.g., hash-based one-time) signatures and a Bracha-style approval broadcast; certificates become local events

Computational. A certificate convinces a party outside the protocol only through the O(n) underlying signed votes and approvals, and only some correct node can attribute the signers. TN gives a constant-size, transferable, IT certificate, at the price of secret verifier keys (Table V).

Honest-majority MPC and resharing

BGW/CCD [67]–[69]; linear MPC [70]–[73]; packing [74]; composition [75], [76]; OEC [77]; proactive sharing and redistribution [78], [79]

Perfect security for t < n/3; robust reconstruction; committee hand-over

General-purpose tools. ΠDKI instantiates them for a depth-one circuit; Lemma 5 gives a perfectly private batch redistribution.

TABLE III Q UALITATIVE COMPARISON OF SIGNATURE FAMILIES RELEVANT TO PERMISSIONED LEDGERS . “IT” = INFORMATION - THEORETIC ; “TA” = TRUSTED AUTHORITY; “H OPS ” = NUMBER OF TRANSFERS BETWEEN VERIFIERS THAT PRESERVE VALIDITY. Family

Security basis

Setup / trust

Key reuse

Hops

Verifier forges? Per-sig. interaction

Aggregation

Special hardware

ML-DSA, Falcon, SLH-DSA [11], [13], [14] XMSS/LMS [64] Ed25519 / BLS [65], [80] DVS / SDVS [61], [63] SILMARILS 2-party [36] SILMARILS 3-party [36] IC / pseudo-signatures [32], [34], [58] USS with TA [21]–[24] Amiri et al. [25] QDS [26]–[29] BLS / lattice threshold [37], [39], [40] DQS [41] SILMARILS-MV (this work)

computational (PQ) computational (hash) computational (not PQ) computational comp. (PRF, ROM/QROM) IT (IC) IT IT IT IT (quantum) comp. (BLS: not PQ) computational (PQ) IT∗

PKI PKI, stateful PKI PKI session channel auth. channels + broadcast correlated randomness trusted authority secret channels, no TA quantum links / QKD DKG, PKI PKI committee, t < n/3, point-to-point only

unlimited bounded unlimited unlimited unlimited per signature bounded bounded per message per message unlimited one-time keys (WOTS-TS) ψN per epoch

unbounded unbounded unbounded none (by design) none (DV) 1 bounded supported bounded (levels) bounded (levels) unbounded unbounded, O(n) proof unbounded

no no no yes (simulates) yes (simulates) no no no no no no no no

SNARG-based [18] no BLS: yes no no no no not studied no no threshold none (local events) linear and threshold

none none none none none none none none none quantum none none none‡

∗

none none none none none IC challenge phase IC: yes none key distribution quantum distribution lattice: signing rounds approval broadcast none

For messages in Fq ; hash-then-sign for long messages adds only collision resistance. ‡ Issuance needs private channels, which are information-theoretic with QKD or pre-shared pads; t + 1 colluding committee members of an epoch could forge for that epoch.

that some query to an honest verifier (or to R ES) returns 1 on a signature or aggregate that is not acceptable. Definition 4 ((Q, ε)-security). An MV-USS scheme is perfectly correct if every valid signature and aggregate is accepted by every honest verifier and by Resolve with probability 1. It is (Q, ε)-secure if, for every adversary making at most Q verification, aggregate-verification and resolution queries in total, Pr[Bad] ≤ ε. The single event Bad captures every requirement of [23] at once: strong unforgeability: an honest verifier never accepts a non-authentic signature of an honest signer, even one that

modifies a genuine signature; non-repudiation: a dishonest signer cannot get an invalid signature accepted by an honest verifier; hence any accepted signature is valid and will also be upheld by the arbiter; transferability: validity is a global predicate; if one honest verifier accepts, all honest verifiers accept (Corollary 2); sound dispute resolution: Resolve is an honest verifier. IV. T HE SILMARILS-MV C ONSTRUCTION A. Design Rationale Three failure modes guided the design. We observed each of them in earlier algebraic attempts, including ours [36].

PREPRINT

5

Functionality FKI (q, ω, ψ, N ; x0 = 0, x1 , . . . , xν ) $

(ω+1)×(ω+1)

1) Epoch anchors. Sample Γ ← − Fq . For i ∈ [ν], send ci := ΓT λ(xi ) to Vi . Keep c0 := ΓT λ(0) internally (the arbiter key). 2) Signer indices. For every U ∈ U and k ∈ [N ] sample $ (ω+1)×(ψ+1) AU,k ← − Fq and send it to U . For i ∈ [ν], send bi,U,k := ATU,k ci ∈ Fψ+1 to Vi , and keep b0,U,k internally. q 3) Arbitration. On input σ = (U, k, m, α) from the committee, return 1 iff cT0 α = bT0,U,k e(m); aggregates are handled analogously. Fig. 1. Ideal key-issuance functionality. Γ (the virtual anchors) and the arbiter key are never output to anyone.

(i) Public reconstruction is forgeable. If acceptance is a public linear predicate of the signature, as in the Shamir reconstruction of the SILMARILS core once its receipt is known, then anyone can solve the predicate for a fresh message. Acceptance must therefore depend on verifier-specific secret coefficients. (ii) Shared verification secrets collapse to a MAC. If a verifier’s secret determines the signer’s secret, the verifier can forge, and evidence is not transferable. A coalition of up to ω verifiers must learn too little to predict the signer’s response to a new message. (iii) Signer-dealt keys break agreement. If the signer generates the verifiers’ keys, it can give them inconsistent keys, and its signatures are accepted by some honest verifiers and rejected by others. Verification keys must be generated consistently by a party the signer does not control. SILMARILS-MV meets the three requirements with secret per-verifier linear functionals, uniformly random signing matrices, and committee-generated keys. No rank condition on the signing matrix is needed: the security proof uses only its uniform distribution. B. Ideal Key Issuance We first describe key issuance as an ideal functionality FKI . It can be realized by a trusted dealer or, without any trusted party, by the committee protocol ΠDKI of Section VI. Write MU,k := ΓAU,k . Then bTi,U,k = cTi AU,k = λ(xi )T ΓAU,k = λ(xi )T MU,k .

(1)

Verifier keys are therefore evaluations, at the public identifiers xi , of the bivariate polynomial FU,k (x, z) = λ(x)T MU,k e(z), of degree ω in x and ψ in z. The key of Vi is z 7→ FU,k (xi , z). What distinguishes this from simply emulating the trusted authority of a polynomial USS [21], [22] by MPC is that the signer does not know FU,k . If the signer’s key determined the bivariate polynomial at public verifier identifiers, a dishonest signer could tailor signatures that pass at chosen identifiers and fail at others. It knows only AU,k , which is related to MU,k = ΓAU,k through the secret anchors (when Γ is invertible, AU,k = Γ−1 MU,k is a version of MU,k rotated by them). This is what prevents a dishonest signer from tailoring signatures to the public identifiers.

Algorithm 1 SILMARILS-MV algorithms State of signer U : (AU,k )k∈[N ] and sets Mk ⊆ Fq of messages signed under index k, initially empty. 1: procedure S IGN (U, k, m) 2: if m ∈ / Mk and |Mk | = ψ then return ⊥ 3: end if 4: Mk ← Mk ∪ {m}; α ← AU,k e(m) ▷ (ω + 1)(ψ + 1) mult. 5: return σ = (U, k, m, α) 6: end procedure 7: procedure V ERIFY i (σ = (U, k, m, α)) ▷ ω + ψ + 2 mult. 8: return [ cTi α = bTi,U,k e(m) ] 9: end procedure 10: procedure AGGREGATE(m, (σU )U ∈S ) ▷ all σU on m P 11: return σS = (m, (U, kU )U ∈S , U ∈S αU ) 12: end procedure 13: procedure AGG V ERIFY i (σS = (m, (U, kU )U ∈S , αS )) P 14: return [ cTi αS = U ∈S bTi,U,kU e(m) ] 15: end procedure 16: procedure R ESOLVE(σ) ▷ committee MPC, Section VI 17: compute [[δ]] = [[c0 ]]T α − [[b0,U,k ]]T e(m); take a fresh preprocessed [[ρ]], ρ ∈ F∗q 18: open δρ; return [ δρ = 0 ] 19: end procedure

C. Signing, Verification, Aggregation and Resolution Algorithm 1 lists the algorithms. Correctness is immediate: for a valid α = AU,k e(m), cTi α = cTi AU,k e(m) = bTi,U,k e(m), and the aggregate check follows by linearity. In Resolve, a sharing of a uniform non-zero mask ρ is obtained in the standard way: generate random sharings [[ρ]], [[s]], open ρs, and retry if it is 0 [35]. Each attempt costs two Rand outputs, one multiplication and one opening, and succeeds with probability (1−1/q)2 . Masks are preprocessed in batches, and every mask is used for exactly one test: reusing ρ on two non-zero residuals would reveal their ratio δ1 /δ2 . Then δρ is 0 iff δ = 0, and otherwise it is uniform on F∗q ; consequently, the arbiter key is never exposed. The online cost of a resolution is one multiplication and one opening; preprocessing the mask costs one more of each, plus two Rand outputs. Input validation. The security analysis quantifies over well-formed objects, and implementations must enforce the same domain. Verifyi , AggVerifyi and Resolve reject an object whose field elements are not canonically encoded in {0, . . . , q − 1}, whose index lies outside [N ] or was not issued to the stated signer for the object’s declared signing epoch, or whose message is not bound to that epoch and to the protocol domain. Keys are selected by the declared epoch. Whether an object from an earlier epoch is admissible is a separate policy of the operation: consensus messages must carry the current epoch, whereas historical verification and dispute resolution accept any epoch whose keys are retained. AggVerifyi additionally rejects aggregates whose signer identities are not pairwise distinct; otherwise a repeated identity could inflate a quorum. Proposition 1 (Correctness). SILMARILS-MV is perfectly

PREPRINT

correct: every valid, well-formed signature or aggregate that is admissible for the operation (see the input validation above) is accepted by every verifier holding keys output by FKI for its declared epoch, and by Resolve. D. Parameters and Costs Typical choices are q = 2255 − 19, ω = t (the committee’s fault bound), ψ ∈ {1, 16, 64} messages per index, and N indices per epoch. Per signer-index the signing key holds (ω + 1)(ψ + 1) field elements and each verifier stores ψ + 1. A verifier additionally stores ci once per epoch. A signature carries its index (we budget 4 bytes) and ω + 1 field elements; an aggregate carries a signer bitmap, the list (kU )U ∈S of signer indices and ω + 1 field elements. Signing costs (ω + 1)(ψ + 1) multiplications plus ψ − 1 to compute e(m), and verification costs ω +1 plus ψ +1 multiplications. With ψ = 1, a signature is one matrix–vector product with a 2-column matrix. Parameter selection. Field. With q = 2255 − 19 and, generously, Q = 264 verification decisions over the system’s lifetime, spread over at most E = 264 epochs with independently sampled anchors, Theorem 1 and Remark 4 give Pr[Bad] ≤ 264 /(2255 − 19) + 264 /(2255 − 20) < 2−189 for the core authentication budget; the MAC, decoder and redistribution terms of Remark 9 are separate. This bound holds against unbounded, including quantum, adversaries. Hashing. For hashed long messages, the relevant assumption is collision resistance of the composite map M 7→ int(H(M )) mod q, including distinct digests with the same residue. Because its range has q ≈ 2255 elements, generic attacks find collisions with about q 1/2 ≈ 2127.5 classical or q 1/3 ≈ 285 quantum queries [82], whatever the digest length of H; SHA3-512 improves the uniformity of m but not this margin. A larger margin requires a larger range: splitting a SHA3-512 digest injectively into three field elements (e.g., 254 + 254 + 4 bits, each chunk below q) and signing them with the vector encoding of Remark 1 (L = 3, one message per index, encoding dimension 4) reduces the assumption to collision resistance of SHA3-512 itself. Collusion bound. ω equals the number of verifiers that may be corrupted, i.e., t for a BFT committee of n = 3t + 1. Capacity. ψ ∈ [1, 64] balances signing time, which is linear in ψ, against verifier storage of (ψ + 1)/ψ elements per signature. Epochs. N indices per signer cover the epoch’s expected signatures; for consensus, N ≈ (blocks per epoch)/ψ. For example, 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. Remark 1 (Message space). Messages are elements of Fq . Longer messages are hashed, m = H(M ), with a collisionresistant H such as SHA3-256 reduced modulo q. A forger then either breaks collision resistance or triggers Bad; hence security degrades additively by AdvCR H , and only collision resistance is used, never a random oracle. This term is a computational caveat: an unbounded adversary that chooses the hashed messages can find collisions, and the guarantee is then information-theoretic only for the injective encoding below. In BFT protocols, votes already sign a block digest, and this adds no new assumption. A purely information-theoretic

6

alternative for messages in a fixed finite domain M ∈ FL q replaces e(m) by e(M ) = (1, M1 , . . . , ML )T and allows one distinct message per index: any second signature under the same index is refused. The security proof of Theorem 1 applies with ψ = 1 messages per index, because (1, M )T and (1, M ′ )T are independent for M ̸= M ′ . The encoding dimension, however, is L + 1 rather than ψ + 1 = 2: then (ω+1)×(L+1) AU,k ∈ Fq and bi,U,k ∈ FL+1 , and signing, q verification, storage and issuance costs scale with L + 1. The encoding must bind the protocol domain, epoch, slot and value within the declared message space; arbitrarily long messages cannot be encoded injectively into a fixed dimension. Remark 2 (State). As in XMSS/LMS [64], the signer keeps a counter. In a BFT ledger, each validator keeps one counter per message type and uses index k = ⌊j/ψ⌋ for its j-th signature; signing two different messages for the same consensus slot is equivocation (Section VII). Proposition 2 shows that exceeding ψ messages on one index reveals that index’s key. The damage is confined to that index and to the misbehaving signer. V. S ECURITY A NALYSIS We analyze SILMARILS-MV in the FKI -hybrid model. Section VI replaces FKI by the committee protocol ΠDKI with no loss. Throughout, C is the set of corrupted verifiers (ω+1)×|C| (|C| ≤ ω), and we write ΛC = [λ(xs )]s∈C ∈ Fq T and K = ΛC Γ. The rows of K are exactly the corrupted functionals cTs , s ∈ C. Since the arbiter point x0 = 0 differs from every xs , Lemma 1 gives λ(xi ) ∈ / span{λ(xs ) : s ∈ C},

∀ i ∈ {0, . . . , ν} \ C. (2)

A. Main Theorem Theorem 1 (Security of SILMARILS-MV). Let A be any computationally unbounded adversary that corrupts at most ω verifiers, an arbitrary set of signers, and makes at most Q queries to honest verifiers (individual, aggregate and resolution queries together). In the experiment of Definition 3, in the FKI -hybrid model, 1 Q + . Pr[Bad] ≤ q q−1 Hence SILMARILS-MV is (Q, Q/q + 1/(q − 1))-secure and perfectly correct. The additive term 1/(q − 1) bounds the probability that the uniformly sampled anchor matrix Γ is singular. It is paid once per anchor matrix, not per query (Remark 4); Remark 5 explains how it could be removed. The proof has three steps. (i) We replace every verification answer by an ideal answer that the adversary could compute itself; this does not change Pr[Bad]. (ii) In the resulting game, the posterior distribution of all secrets is uniform on a product of affine subspaces. (iii) Every individual query triggers Bad with probability at most 1/q, by Lemma 2 applied along an explicit direction in either the anchor matrix Γ or a signing matrix AU,k . Proof. Step 1 (ideal answers). Let G0 be the real experiment. In G1 , every query j to an honest verifier is answered with

PREPRINT

7

Idealj := 1 iff the queried object is acceptable (Definition 2) at the time of the query, instead of the real decision Realj . Both games use the same coins. Acceptable objects are valid, and by Proposition 1 valid objects are accepted; hence Idealj = 1 ⇒ Realj = 1. Therefore Realj ̸= Idealj iff badj := (Realj = 1 ∧ Idealj = 0). The games proceed identically until the first j with badj , and that event is precisely Bad in G0 . By the S fundamental lemma of game playing, PrG0 [Bad] = PrG1 [ j badj ], where in G1 each badj is evaluated on the actual keys but never influences the adversary. Step 2 (posterior). Let τj be the adversary’s view in G1 just before query j. It consists of its random tape; K; the corrupted key polynomials BU,k := KAU,k for every (U, k); the matrices AU,k of corrupted signers; and the answers to earlier queries. In G1 , a signing answer equals AU,k e(m). A verification answer Ideal is a deterministic function of earlier answers (for honest signers, acceptability depends only on the signing log) and of the corrupted signers’ matrices, both of which are part of τj . The matrices of corrupted signers are sampled independently of those of honest signers. Hence the likelihood of τj , given the honest secrets s = (Γ, (AU,k )U ∈U / C ), equals a factor independent of s times the indicator 1[s ∈ S(τj )], where S(τj ) = {Γ : ΛTC Γ = K} × Y {A : KA = BU,k , A EU,k = RU,k }. U ∈U / C, k

Here EU,k = [e(m)]m∈Mk and RU,k is the matrix of returned signatures. The fixed matrix K read from τj appears in the second factor; therefore S(τj ) is a product of affine subspaces. With a uniform prior, the posterior of s given τj is uniform on S(τj ), and the factors are independent. Step 3 (per-query bound). Fix τj and let query j go to an honest verifier Vi (with i = 0 for Resolve; there the mask ρ ̸= 0 makes the decision exact). We use two kinds of shifts. (A) Γ-shift. Suppose the real decision is [λ(xi )T ΓD = 0] for some non-zero D determined by τj . By (2) there is u with ΛTC u = 0 and λ(xi )T u = 1. Choose v with vT D = 1. The direction ∆ = uvT preserves ΛTC Γ = K and leaves every A-factor unchanged; hence it lies in the linear part of S(τj ). The affine function f (Γ) = λ(xi )T ΓD satisfies f (Γ + ∆) = f (Γ) + 1. By Lemma 2, Pr[badj | τj ] = 1/q. (B) A-shift. Suppose the real decision is [cTi AU ⋆ ,k⋆ e(m) = y], where U ⋆ is honest, m ∈ / Mk⋆ , and y is determined by τj , Γ and the other signing matrices. Condition additionally on Γ and on all AU,k ̸= AU ⋆ ,k⋆ . By Step 2, AU ⋆ ,k⋆ remains uniform on its affine factor. If Γ is invertible, then (2) gives ci = ΓT λ(xi ) ∈ / row(K); hence some g satisfies Kg = 0 and cTi g = 1. Since |Mk⋆ | ≤ ψ and m ∈ / Mk⋆ , Lemma 1 gives e(m) ∈ / span(EU ⋆ ,k⋆ ); hence some h satisfies ETU ⋆ ,k⋆ h = 0 and hT e(m) = 1. The direction ghT preserves both KA = B and AE = R, and changes cTi Ae(m) by 1. By Lemma 2, Pr[badj | τj , Γ] = 1/q whenever Γ is invertible. Case analysis. Let query j be non-acceptable, since otherwise badj cannot occur. Malformed objects are rejected in both games. (i) Individual, corrupted signer. The object is invalid; hence D = α − AU,k e(m) ̸= 0 is known from τj ,

and the real decision is [λ(xi )T ΓD = 0]. Shift (A) applies. (ii) Individual, honest signer, m ∈ Mk , α differs from the returned signature αk,m . Set D = α − αk,m ̸= 0. Shift (A) applies. (iii) Individual, honest signer, m ∈ / Mk . Shift in which every (B) applies with y = cTi α. (iv) Aggregate P honest U ∈ S has signed (kU , m). Then U ∈S AU,kU e(m) is known from τj , and non-acceptability means D := αS − P U AU,kU e(m) ̸= 0. Shift (A) applies. (v) Aggregate in which some honest U ⋆ ∈ S P has not signed (kU ⋆ , m). Shift T (B) applies with y = ci αS − U ̸=U ⋆ cTi AU,kU e(m). In every case Pr[badj ∧Γ invertible] ≤ 1/q. A uniform (ω+1)×(ω+1) Qω+1 matrix is singular with probability 1 − ℓ=1 (1 − q −ℓ ) ≤ P −ℓ = 1/(q − 1). A union bound gives ℓ≥1 q PQ Pr[Bad] ≤ Pr[Γ singular] + j=1 Pr[badj ∧ Γ invertible] Q 1 + . ≤ q−1 q Posterior uniformity in detail. We make Step 2 of the proof of Theorem 1 explicit. Fix the adversary’s random tape ρ and the corrupted signers’ matrices a = (AU,k )U ∈UC . The honest secrets are s = (Γ, (AU,k )U ∈U / C ), uniform and independent of (ρ, a). In G1 , the adversary’s next query is a deterministic function Qj (ρ, τj ) of its tape and the transcript up to that point. Each answer is either a signature AU,k e(m) or an ideal bit Idealj , which is a function of (τj , a) alone. By induction on j, the transcript τj is a deterministic function Tj (ρ, a, s). Moreover, for every value τ̂ , {s : Tj (ρ, a, s) = τ̂ } = S(τ̂ ), the product of affine subspaces of Step 2, provided τ̂ is consistent with (ρ, a). Indeed, τ̂ fixes the sequence of queries. The initial keys contribute the constraints ΛTC Γ = K and KAU,k = BU,k . Signing answers contribute AU,k e(m) = α. Ideal answers contribute no constraint on s. Hence Pr[s = ŝ | τj = τ̂ , ρ, a] = 1[ŝ ∈ S(τ̂ )]/|S(τ̂ )|. Averaging over (ρ, a) consistent with τ̂ preserves uniformity on S(τ̂ ), since S(τ̂ ) does not depend on them. Remark 3 (What the proof does not need). The proof uses no computational assumption, no random oracle, and no rewinding. It holds even if the adversary chooses its queries with unbounded computation. It is also robust to how cs is distributed among corrupted verifiers: Step 3 only needs λ(xi ) ∈ / span{λ(xs )}, which holds deterministically. For the variant in which each verifier samples a uniformly random ci itself (no anchors), the same proof goes through with a different singular event, ci ∈ row(K), which has probability at most 1/q per query, giving Pr[Bad] ≤ 2Q/q. Remark 4 (Several epochs). Theorem 1 concerns one anchor matrix. Over E epochs with independently sampled anchors, where epoch e answers Qe queries, the same proof P applied per epoch and a union bound give Pr[Bad] ≤ e Qe /q + P p ≤ Q /q + E/(q − 1), where p = 1− sing total sing e Qω+1 −ℓ (1 − q ). Only epochs in which a decision is taken ℓ=1 need to be counted. Further independent components, such as the scalar anchors of arbiter-verified keys (Section VIII-C), redistribution (Lemma 5), MAC forgeries and probabilistic

PREPRINT

decoding (Theorem 4), contribute their own terms to a systemlevel bound. Remark 5 (Invertible anchors). If Γ is sampled uniformly from the invertible matrices, the bound becomes Pr[Bad] ≤ Q/q, but the proof changes, because {Γ : ΛTC Γ = K, det Γ ̸= 0} is not an affine subspace and shift (A) may leave it. In the ideal game, fix K with row space W of dimension c = |C| (it has full rank, since Γ is invertible). By (2), the honest functional cTi = λ(xi )T Γ is then uniform on Fω+1 \ W . For q a transcript-determined D ̸= 0, Pr[cTi D = 0 | K] = (q ω − |W ∩ D⊥ |)/(q ω+1 − q c ) ≤ 1/q, because |W ∩ D⊥ | ≥ q c−1 . The fresh-message case keeps shift (B), conditional on Γ. The distributed protocol ΠDKI of Fig. 2 does not implement this key distribution: doing so needs a secure invertibility test (e.g., opening ΓR for a random shared R and checking its rank, which reveals nothing when both are invertible), with its own multiplications, retries and leakage analysis. We therefore keep uniform anchors and the 1/(q − 1) term. B. Consequences Corollary 1 (Strong unforgeability and non-repudiation). Except with probability Q/q + 1/(q − 1): no honest verifier, and not the arbiter, accepts a signature of an honest signer that the signer did not output, including modified versions of genuine signatures; no honest verifier accepts an invalid signature of a dishonest signer. Consequently, a signer cannot repudiate a signature that any honest verifier has accepted: Resolve upholds it.

8

Corollary 4 (Simulation-based security in the Fitzi framework). Let ω ≥ 1, and let P1 ∈ U , P2 = Vi and P3 = Vj , with keys issued by FKI independently of the input x1 ∈ Fq . Consider the following non-interactive protocol. In the signing phase, P1 sends σ ← Sign(P1 , k, x1 ) to P2 over a private authenticated channel, which outputs z2 = x1 if Verifyi (σ) = 1 and ⊥ otherwise. In the transfer phase, P2 forwards σ to P3 , which outputs z3 analogously. This protocol satisfies the correctness, unforgeability, transferability and secrecy conditions of the characterization in [60, Lemma 18.15] with error ε ≤ 1/q + 1/(q − 1). Under the hypotheses of that lemma (three parties, one static active corruption, pairwise private authenticated channels, classical inputs), it 2ε-securely implements the three-party signature functionality fDS of Fitzi et al. [32], [59], [60]. The four game-based properties also hold against quantum adversaries that interact classically (Remark 6). A simulation-based statement against quantum adversaries additionally relies on the quantum version of the characterization in [36], whose hypotheses must be matched to this protocol; we state it only in that conditional form, and we make no claim for adversaries with entangled auxiliary inputs or for a particular composable quantum framework.

Corollary 2 (Unbounded-hop transferability). Let a fixed signature or aggregate be forwarded through honest verifiers Vi1 , Vi2 , . . . , ViL , for any L. If some Viℓ rejects it although Vi1 accepted it, then the acceptance by Vi1 was a Bad event. Hence the probability of such a disagreement is at most Q/q + 1/(q − 1), where Q counts the verification decisions taken up to and including that first acceptance; the L−1 later verifications of the same object add nothing.

Proof. Correctness is perfect (Proposition 1). Unforgeability (P1 , P3 honest, P2 corrupt, whence |C| = 1 ≤ ω): z3 ∈ / {x1 , ⊥ } requires P3 to accept a non-authentic signature. Since Q = 1, this has probability at most 1/q + 1/(q − 1). Transferability (P2 , P3 honest, P1 corrupt): z2 ̸=⊥ and z3 ̸= z2 require that P2 accept an invalid signature, because a valid one is accepted by P3 . By shift (A), this has probability at most 1/q. Secrecy (P3 corrupt): the signing message travels over the private channel from P1 to P2 , and P3 therefore receives nothing during signing; its view consists of its keys, which are independent of x1 , and εsec = 0. Without a private signing channel, a corrupt P3 could read x1 from σ, and this condition would fail. The classical implication then follows from [60, Lemma 18.15]; the quantum implication is conditional on the quantum version of that lemma in [36].

Proof. If Vi1 accepts a non-acceptable object, then Bad occurs, which Theorem 1 bounds with the queries made so far. Otherwise the object is valid and, by perfect correctness, every honest verifier accepts it deterministically.

Corollary 4 recovers, non-interactively, without broadcast, and for an unbounded number of transfers, what the threeparty mode of SILMARILS achieves with an interactive IC phase and a single transfer.

Transferability is thus a structural property: once an object is valid, every honest verifier accepts it, at every hop. It is not a guarantee against unboundedly many fresh verification attempts, which Theorem 1 charges 1/q each. In threshold-based USS and QDS [25], [26], each hop lowers the acceptance level, which bounds the number of transfers. In SILMARILS-MV, validity is a single global predicate, and there is nothing to degrade.

Remark 6 (Quantum adversaries). All keys and all messages exchanged with honest parties are classical. In the game of Definition 3, any quantum adversary therefore induces a (possibly inefficiently computable) randomized strategy for choosing its classical queries, and the proof of Theorem 1 holds for every such strategy. This is a statement about the game-based bound; simulation-based or composable quantum security needs the separate argument discussed after Corollary 4. The proof does not rely on any computational restriction on the adversary. Consequently, the information-theoretic component of the security analysis remains unchanged even if the adversary possesses quantum computational capabilities, and SILMARILS-MV has no computational assumption for a quantum computer to break. The only exception is collision resistance when long messages are hashed (Remark 1). Because

Corollary 3 (Information-theoretic aggregate signatures). Except with probability Q/q + 1/(q − 1), an honest verifier accepts an aggregate σS on m only if every honest signer in S actually signed m under the stated index, and αS equals the sum of the corresponding valid signatures. Rogue-key attacks do not apply, because no participant chooses its own key.

PREPRINT

hashed messages are reduced into Fq , the generic quantum collision attack [82] needs about q 1/3 ≈ 285 queries whatever the digest length; a larger margin uses the vector encoding of Remark 1 (Section IV, parameter selection). C. Tightness Proposition 2 (Tightness). (a) The bound of Theorem 1 is tight up to lower-order terms. An adversary without any corruption makes Q ≤ q queries on a fixed unsigned message m, using αℓ = α1 +(ℓ−1)w for a uniform w. It succeeds with probability at least (Q/q)(1 − 1/q)(1 − 1/(q − 1)). (b) The collusion threshold is tight. If ω + 1 verifiers collude, they recover Γ and can compute every honest verifier’s response to every message, i.e., they forge universally with probability 1. (c) The capacity is tight. Given ψ + 1 signatures on distinct messages under one index, anyone recovers AU,k and forges on that index with probability 1. (d) The non-repudiation term is exact. For a first query with an invalid α, each individual honest verifier accepts with probability exactly 1/q. Proof. (a) Let Γ be invertible; then ci ̸= 0. Let θ = cTi Ae(m), which is uniform by shift (B). If cTi w ̸= 0, which happens with probability 1 − 1/q, the Q values cTi αℓ are distinct. Each rejection excludes one candidate value of θ; hence some αℓ hits θ with probability Q/q. (b) By Lemma 1, ΛC is T invertible; hence Γ = Λ−T C K and every ci = Γ λ(xi ) = T −1 K ΛC λ(xi ) is a known combination of the rows of K. Write ci = KT µi with µi = Λ−1 C λ(xi ) public. For any m, the coalition picks any solution α of Kα = BU,k e(m). The system is consistent because AU,k e(m) solves it. Then cTi α = µTi Kα = µTi BU,k e(m) = bTi,U,k e(m) for every i, and the forgery is accepted by everyone. (c) EU,k is an invertible −1 Vandermonde matrix; hence AU,k = RU,k EU,k . (d) This is shift (A) with equality. Part (a) establishes that the leading term Q/q is tight; it does not claim that the whole bound Q/q + 1/(q − 1) is attained for every parameter set. Our Monte-Carlo experiments (Section IX-F) are consistent with (a) for Q ∈ {1, 4, 16}, where success grows as Q/q, and with (b), (c) and (d); they support the analysis but do not replace it. VI. D EALER -F REE D ISTRIBUTED K EY I SSUANCE We now realize FKI without a trusted dealer. The committee P evaluates the arithmetic circuit of Fig. 1 using perfectly secure honest-majority MPC. Our contribution is to exhibit a circuit, enabled by virtual anchors, whose multiplicative work is independent of the number ν of verifiers, and to count its cost: exact circuit counts, a semi-honest communication cost validated by simulation, and an estimate for the malicious setting. A. Building Blocks We use degree-t Shamir sharings [[s]] over Fq among n ≥ 3t + 1 parties [83], and the following standard sub-protocols, each perfectly secure against t < n/3 malicious parties [35], [67], [68], [71]: Rand, which outputs [[r]] for a uniform r,

9

Protocol ΠDKI (committee P, t < n/3) Epoch set-up. 2 1) [[Γ]] ← Rand(ω+1) . 2) For each verifier Vi : locally compute [[ci ]] = [[Γ]]T λ(xi ) and run Open→Vi on its ω + 1 entries. Keep [[c0 ]] = [[Γ]]T λ(0), i.e., the first row of [[Γ]], as the arbiter key. Per signer-index (U, k) (batched and pipelined): 3) [[A]] ← Rand(ω+1)(ψ+1) . 4) [[M ]] ← [[Γ]][[A]], using (ω + 1)(ψ + 1) calls to IP of length ω + 1. 5) Open→U on every entry of [[A]]. 6) For each Vi : locally compute [[bi ]] = [[M ]]T λ(xi ), by (1), and run Open→Vi on its ψ + 1 entries. Keep [[b0 ]] = [[M ]]T λ(0). Resolution. On σ: [[δ]] = [[c0 ]]T α − [[b0,U,k ]]T e(m) (local). Take a fresh preprocessed uniform non-zero [[ρ]] (Section IV), compute [[δρ]] with one multiplication, send it to all parties point-to-point, decode it robustly, and output [δρ = 0]. Robust decoding gives every honest party the same verdict; hence no broadcast is needed. Fig. 2. Distributed key issuance with virtual anchors. Only step 4 and resolution use multiplications; verifier keys (steps 2 and 6) are local linear maps followed by private openings.

generated in batches by Vandermonde (hyper-invertible) extraction [70], [71]; IP, which on input [[a]], [[b]] outputs [[aT b]]. Each party multiplies and sums its local shares, obtaining a degree-2t sharing, and one degree reduction follows. An inner product therefore costs one degree reduction, i.e., the communication of one multiplication; the local coordinate products cost no communication [70], [71]; Open→P , which reconstructs a shared value towards a single party. All n shares are sent, and the receiver decodes the degree-t Reed–Solomon codeword with up to t errors (e.g., Berlekamp–Welch [84]). Linear combinations with public coefficients are computed locally. These sub-protocols use broadcast only for complaints and for short fault-detection messages, amortized over large batches; for t < n/3 we realize it by Byzantine agreement over point-to-point channels [81]. Signing, aggregation and verification never use it. B. The Protocol Figure 2 gives ΠDKI . It computes exactly the outputs of T FKI : ci = ΓT λ(xi ), AU,k , and bi,U,k = MU,k λ(xi ) = T T T AU,k Γ λ(xi ) = AU,k ci . Γ, MU,k and the arbiter’s key are never opened. Theorem 2 (Security of ΠDKI ). Let ΠDKI be instantiated with perfectly secure malicious sub-protocols for Rand, IP and Open (e.g., BGW [67], [68], or the linear-communication protocols of [71] with fault detection and player elimination). Then ΠDKI securely computes FKI with perfect security and guaranteed output delivery against a static malicious adversary that corrupts at most t < n/3 committee members, together with any set of signers and verifiers, given synchronous private channels. Consequently, Theorem 1 and its corollaries hold in the real world, with ΠDKI in place of FKI , with the same bounds. Proof sketch. FKI is a randomized arithmetic circuit of multiplicative depth one, with outputs to designated parties. Cor-

PREPRINT

10

rupted verifiers and signers have no inputs. By the BGW theorem with its full proof [67], [68], every such circuit has a perfectly secure protocol for t < n/3 with guaranteed output. The sub-protocols above are standard perfectly secure instantiations whose composition is perfectly secure [35], [71]. Robust opening succeeds because a degree-t codeword of length n ≥ 3t + 1 corrects t errors. Privacy of the unopened values follows from the simulator. Corrupted parties hold at most t shares of each degree-t sharing; hence their view of Γ, MU,k , c0 and b0,· is simulatable from their outputs alone. The opened value δρ is 0 or uniform on F∗q , hence simulatable from the verdict. Perfectly secure protocols with straight-line black-box simulators remain secure under composition [75], [76]. The joint distribution of the adversary’s view and all honest outputs is therefore identical in the real and ideal executions, and any event, Bad in particular, has the same probability in both. C. Communication Cost Let d be the number of random sharings extracted from n dealt sharings: d = n − t with plain Vandermonde extraction (semi-honest dealers), and d = n − 2t with hyper-invertible extraction, which also verifies the dealt sharings against malicious dealers [71]. Let rc = n(n − 1)/d be the amortized cost, in field elements sent in total, of one Rand output. Let µc = 2(n−1)+2n(n−1)/d be the cost of one degree reduction with double sharings and a king [70], and let n (an upper bound) be the cost of one Open. With E = (ω + 1)(ψ + 1), the communication per signer-index is Cidx = E rc + E µc + |{z} E n + ν(ψ + 1) n |{z} |{z} | {z } random A

ΓA

A→U

(3)

bi →Vi

field elements. The epoch set-up costs a further (ω + 1)2 rc + ν(ω + 1)n. Our simulator implements the semi-honest instantiation (d = n − t, king-based degree reduction), with Berlekamp–Welch decoding of all outputs against t parties that send corrupted shares. It agrees with (3) to within 0.4%, e.g., exactly 908 elements per index for n = 7, ω = 2, ψ = 4, and it confirms that all issued keys satisfy bi = AT ci . It does not model malicious dealers or a malicious king. We therefore separate four statements. (i) The circuit counts ((ω + 1)(ψ + 1) multiplications per index, none per verifier) are exact. (ii) Equation (3) with d = n − t is the semi-honest amortized communication, validated by simulation. (iii) Equation (3) with d = n − 2t is an estimate of the malicious communication: perfect malicious security requires the fault detection, complaints and player elimination of [71] and the emulation of their broadcasts, which keep the communication linear but add terms that (3) omits, as do batch rounding, setup and failure paths. (iv) Theorem 2 establishes that a perfectly secure malicious realization exists. Section IX reports (ii) and (iii) and labels (iii) as an estimate. Derivation. Rand is batched: every party deals one degree-t sharing, sending n − 1 elements, and the n dealt sharings are multiplied by a d × n extraction matrix. With d = n − t and a Vandermonde matrix, this yields n − t uniformly random sharings if dealers follow the protocol [70]. With d = n − 2t

and a hyper-invertible matrix, the remaining t outputs are opened to verify consistency against malicious dealers [71]. Hence rc = n(n − 1)/d. A degree reduction consumes one double sharing ([[r]]t , [[r]]2t ), generated the same way at 2n(n−1)/(n−t) elements, and one masked opening to a king and back, at 2(n − 1) elements. Open→P costs n elements. Summing over steps 3–6 of Fig. 2 gives (3). The residual between simulation and (3) comes from rounding up partially consumed batches. Remark 7 (Why virtual anchors matter). The naive alternative lets each verifier input a secret random ci and computes cTi A by MPC. This costs ν(ψ +1) multiplications per index instead of (ω + 1)(ψ + 1), a factor ν/(ω + 1) = (3t + 1)/(t + 1) more multiplications when ν = n = 3t + 1 and ω = t, which approaches 3 for large committees. Our simulators measure a total per-index cost 1.5×, 1.65× and 1.72× higher for n = 4, 7, 10 (ψ = 4); the gap widens with n because the multiplication term dominates. Remark 8 (Further optimizations). The workload is a large SIMD batch of identical depth-one circuits, the ideal case for packed secret sharing [74] and for constant-onlinecommunication honest-majority protocols [73]. If the committee accepts a slightly lower corruption threshold, e.g. n ≥ 4t + 1, packing reduces the dominant opening term ν(ψ + 1)n by a factor of Θ(n/t). We leave engineering these variants to future work. VII. I NTEGRATION INTO P ERMISSIONED BFT L EDGERS Figure 3 shows the deployment. We consider a leaderbased BFT protocol in the style of PBFT/HotStuff [1]–[3]: n = 3t + 1 validators, a leader per view, and QCs formed from 2t + 1 votes. We first describe the individual-vote (IV) mode, in which all validators are verifiers (V = P) and ω = t; Section VII-G compares it with the modes of Section VIII. A. Epochs and Key Refresh Time is divided into epochs, delimited by validator-set reconfiguration or by key exhaustion. During epoch e − 1, the committee runs ΠDKI for epoch e in the background, sized for the expected number of votes and transactions plus headroom. Signing keys and verifier keys of past epochs can be erased once their epoch is final. The arbiter’s shares [[c0 ]], [[b0,· ]] are kept for a dispute window and handed over to new committees by redistribution (Section VIII-E). Since every epoch uses fresh Γ and A, a verifier compromised in one epoch learns nothing about the next. Within an epoch, however, the collusion bound ω counts every verifier credential for that epoch’s Γ that is ever corrupted, also at different times (Proposition 3). The per-epoch cost is quantified in Section IX. B. Message Format, Slots and Index Streams Every consensus message has an explicit slot s = (e, h, r, ϕ): epoch, height, round and phase (e.g., prepare, commit, proposal). A vote is the structured message M = (VOTE, s, digest(B)),

m = H(M ).

PREPRINT

11

ate) (priv k

Committee P = {P1 , . . . , Pn }, t < n/3 shares [[Γ]], [[AU,k ]], [[MU,k ]] ΠDKI (offline, per epoch)

Signer U (validator / client) AU,k , counters Mk

σ(

A U, ci ,

bi

,U, k (p

rivat e)

Verifier Vi (validator) ci = ΓT λ(xi ), bi,U,k

y verif

pub lic)

te rega / agg

[[c0 ]], [[b0,· ]] never opened

Consensus round h: votesP αU = AU,k e(mh ) QC = U ∈S αU (ω+1 elts) evidence

Committee arbiter V0 (x0 = 0) Resolve: slashing / disputes

Fig. 3. SILMARILS-MV in a permissioned BFT ledger. Key issuance is offline and private; signing, aggregation and verification are online, non-interactive and public; dispute resolution reuses the shared state.

Every honest validator signs at most one message per slot. Each validator keeps a separate index stream per message type. Its j-th signature in a stream uses index k = ⌊j/ψ⌋; hence an honest validator never exceeds ψ distinct messages per index. Extra rounds caused by view changes consume more capacity. Epochs are therefore provisioned with headroom, and the committee runs a small top-up issuance if a stream nears exhaustion. Exhaustion can only delay a validator (liveness); it never affects safety. C. Votes and Aggregated Quorum Certificates The leader verifies each incoming vote individually, at a cost of ω + ψ + 2 multiplications, and then forms
P QC = M, bitmap(S), (kU )U ∈S , U ∈S αU with |S| = 2t + 1. The leader includes this QC in the next proposal. Each replica runs AggVerify in ω + 1 + |S|(ψ + 1) multiplications. By Corollary 3, an accepted QC certifies that every honest member of S voted for M , except with probability Q/q + 1/(q − 1) (plus collision resistance of H). Quorum intersection therefore carries over unchanged, as do safety and liveness, which in such protocols rely only on unforgeability and transferability of votes [1], [2]. Since the QC is forwarded and re-verified by every replica, unbounded transferability (Corollary 2) is exactly the property consensus requires. The explicit index list (kU ) is needed because stream counters advance independently at each validator, e.g., across view changes. We encode each index in 4 bytes; all QC sizes and wire sizes reported in Section IX, and those of the prototype, include this list (4|S| bytes per QC). AggVerify rejects a QC whose signer identities are not distinct (Section IV). D. Transactions and Relays In IV mode, a client U obtains N indices per epoch. It signs a transaction once, and the transaction is gossiped through any number of untrusted relays or mempools, which need no keys. Every validator verifies it with its own key. This resolves the relay problem that motivated the three-party mode of SILMARILS [36], without interaction and without bounding the number of hops. For large committees, clients use arbiterverified keys instead (Section VIII-C): their signatures are 32 bytes and are checked once per block by the committee.

E. Accountability and Slashing Forensics [6], [7] and slashing [8] punish a validator that signs two conflicting messages for the same slot. Definition 5 (Equivocation evidence). Evidence against U consists of two individual signatures σ = (U, k, m, α) and σ ′ = (U, k ′ , m′ , α′ ) together with preimages M ̸= M ′ such that m = H(M ), m′ = H(M ′ ), M and M ′ carry the same slot, and Resolve(σ) = Resolve(σ ′ ) = 1. Theorem 3 (Accountability). (i) If U equivocates, its evidence is accepted with probability 1. (ii) For an honest U , the probability that any evidence against U is accepted is at most Q/q+1/(q−1)+AdvCR H . With the purely information-theoretic encoding of Remark 1, the last term vanishes. Proof. (i) follows from perfect correctness of Resolve. For (ii), an honest U signs at most one message per slot. Unless H(M ) or H(M ′ ) collides with a message that U signed, at least one of σ, σ ′ is non-authentic, and its acceptance by the arbiter is the event Bad of Theorem 1. If the two conflicting messages are signed under the same index and push it beyond ψ messages (e.g., ψ = 1), equivocation reveals AU,k (Proposition 2(c)), and anyone can then forge on that index. Evidence nevertheless stays sound: an honest signer never produces the two signatures that reveal its key, and the leak is confined to the guilty signer’s single index. Aggregated QCs certify the honest members of S. For per-validator attribution of corrupted members, which forensics needs, replicas retain the individual votes, or the leader forwards them on demand. F. Light Clients and External Auditors In IV mode, external parties do not hold verifier keys. They can query Resolve, rely on a QC after enrolling as verifiers (Proposition 3), in which case they count towards ω = t, or use the TN certificates of Section VIII-B, which are designed for them: constant size, a few microseconds to verify, and a collusion bound ω chosen independently of n. G. Choosing a Mode Table IV summarizes the three modes. They share the construction, the issuance protocol and Theorem 1, and they can be combined. A consortium of a few dozen validators can

PREPRINT

12

TABLE IV D EPLOYMENT MODES OF SILMARILS-MV (n = 3t + 1). IV (§VII)

TN (§VIII-B)

AV (§VIII-C)

Signer / verifiers validator / validators committee / external client / arbiter Collusion bound ω t independent of n 0 Object size 32(t+1)+4|S| B† 32(ω+1) B 32 B Signer state counter slot number counter Attribution per validator committee per signer 2 Issuance / val. / block Θ(n ) O(ω + ν) O(1) per sig. Consensus auth. signatures pairwise MACs – Suited for n ≲ 30 to n = 1000 clients, slashing †

Plus an n-bit signer bitmap; |S| signer indices of 4 B.

run IV mode and obtain individually attributable, aggregatable votes. A large committee runs consensus over pairwise MACs [1], information-theoretic with Wegman–Carter pads, issues TN certificates to external verifiers, gives clients arbiterverified keys, and, if slashing is required, adds arbiter-verified commit votes (accountable TN, Section VIII-C). VIII. S CALING TO L ARGE C OMMITTEES A. Where the Quadratic Cost Comes From In the deployment of Section VII, three choices interact. Every validator is a signer, every validator is a verifier, and ω = t because corrupted validators hold verifier keys. Consequently, per block, n signer-indices are consumed, each needs a key for each of the n verifiers, and every key is opened by all n committee members. The resulting Θ(n2 ) field elements per validator per block, together with signatures of ω + 1 = t + 1 elements, are what limit the individual-vote mode to committees of a few dozen validators (Section IX). None of the three choices is forced by the scheme. This section removes them with three mechanisms that reuse the construction and the proofs unchanged: (i) Threshold notarization (TN, Section VIII-B). The committee itself is the signer. Its signing matrices are never opened, a certificate is a single (ω + 1)-vector, and the verifiers are external parties (auditors, light clients, bridges, other committees) whose collusion bound ω is independent of n. (ii) Arbiter-verified keys (Section VIII-C). With ω = 0, the only verifier is the committee arbiter. Signatures are a single field element, issuance needs no verifier keys, and the committee checks a whole block of signatures with one online multiplication. This serves clients and, optionally, validator accountability. (iii) Open verifier sets and evolving committees (Sections VIII-D and VIII-E). Verifiers can be enrolled at any time, also retroactively, by local linear maps, and the shared state can be handed over to a new committee of a different size, which yields membership changes and proactive refresh. B. Threshold Notarization Setting. Committee members P1 , . . . , Pn , n ≥ 3t + 1, have public, pairwise distinct, non-zero share points η1 , . . . , ηn . External verifiers V1 , . . . , Vν have identifiers xi as in Section III, and at most ω of them are corrupted. Validators do not hold verifier keys. A validator that wants to check certificates can be enrolled as a verifier, and it then counts towards ω. The committee runs any BFT protocol ΠBFT over

authenticated point-to-point channels that decides one value per certified slot s = 0, 1, 2, . . . (e.g., per height) and satisfies agreement: no two honest members decide different values for the same slot. We do not construct a new agreement protocol: Theorem 4 is conditional on agreement of ΠBFT . A protocol whose safety with MAC authenticators is proved for t < n/3, without signatures, is PBFT in the version of Castro and Liskov [1], including its view change. We instantiate its MACs information-theoretically in the Wegman–Carter style [42], [43], with a polynomial hash so that no digest is needed: a message is encoded injectively, with a length prefix, as a vector µ = (µ1 , . . . , µℓ ) ∈ Fℓq , ℓ ≤ Lmax , that binds (sender, receiver, epoch, counter, message type, full message), and its Pℓ tag is τ = κ2 + i=1 κ1i µi . Here κ1 is a pre-shared key of the ordered pair (sender, receiver) for the epoch, and κ2 is a fresh pre-shared 32-byte pad for each message, indexed by a per-pair message counter that covers every message type, including view-change, new-view and checkpoint messages. Each pad authenticates at most one message, and a receiver accepts at most one message per counter. A failed check does not consume the pad; hence injected candidates cannot prevent a genuine, delivered message from being accepted. Because every honest tag is masked by a fresh pad, κ1 is uniform given the honest tags alone; rejections then exclude candidate values. A check of a message other than the one authenticated under that counter succeeds only if κ1 is a root of a non-zero polynomial of degree at most Lmax (or, for a counter not yet used, if the adversary hits the uniform pad), and each failed check excludes at most Lmax candidates. Hence, if honest members perform at most Nchk tag checks in the epoch, the probability that some check accepts a forged message is n Nchk Lmax o (Nchk Lmax < q), εMAC ≤ min 1, q − Nchk Lmax and εMAC ≤ 1 otherwise. Nchk is finite because a receiver processes at most its link capacity during an epoch; with q ≈ 2255 the bound is negligible for any physical traffic. Fixing Nchk at the link capacity makes rekeying unnecessary within an epoch; κ1 is fresh in every epoch, and a lifetime budget sums εMAC over pairs and epochs. Agreement may still rely on hashing elsewhere: PBFT agrees on request digests [1], which adds the collision advantage AdvCR HBFT unless replicas agree on full values or on an injective encoding. We write εagr ≤ εMAC +AdvCR HBFT +εBFT , where εBFT is the failure probability of the agreement protocol itself with ideal authenticated channels (0 for PBFT). In the normal case, each receiver needs only its own entry of a PBFT authenticator, which is the one-tagper-delivered-message traffic we count in Section IX-D; viewchange and checkpoint traffic are outside that count. Slot s uses the committee index k(s) = ⌊s/ψ⌋, a fixed public map that crashes, recoveries and view changes do not alter. The value v decided in slot s is certified on the message ms (v) = H(CERT, e, s, v), which separates certificates from all other message types. Figure 4 gives the protocol. A certificate is an ordinary SILMARILS-MV signature of the committee, viewed as a single signer whose signing matrices exist only in shared form. Its validity is the same global predicate as before; certificates

PREPRINT

13

Protocol ΠTN (committee P, t < n/3) Issuance (offline, as in ΠDKI without the opening to a signer). 2

1) [[Γ]] ← Rand(ω+1) ; open ci = ΓT λ(xi ) to each Vi . 2) Per committee index k: [[Ak ]] ← RandE , [[Mk ]] ← [[Γ]][[Ak ]], and open bi,k = MkT λ(xi ) to each Vi . Ak and Mk are never opened. Member Pj holds Ak (ηj ), where Ak (y) is the degree-t sharing polynomial with Ak (0) = Ak . Release rule. When Pj decides v in slot s, and only then, it sends the share α(j) = Ak(s) (ηj ) e(ms (v)) to the combiners. It releases at most once per slot. Combine. Given shares for (s, v): (i) optimistic: interpolate α at 0 from t + 1 shares of non-suspected members and, if the combiner is an enrolled verifier, check α with its own key; (ii) otherwise, or if the check fails: decode the degree-t Reed–Solomon codeword. The fast decoder freezes the set of shares received, then draws a fresh uniform ρ, decodes the scalar word (ρT α(j) )j (Gao or Berlekamp–Welch), marks members whose scalars disagree as suspects, and interpolates every coordinate from t+1 non-suspects. A retry with additional shares freezes a new set and draws a new ρ. The exact decoder decodes each coordinate separately. Output the certificate (s, v, α). Verify. Vi accepts iff cTi α = bTi,k(s) e(ms (v)). Fig. 4. Threshold notarization. A certificate is ω + 1 field elements for every n; each member sends one share per certified slot.

are therefore transferable without bound and can be resolved by the arbiter. Shares are linear in the shared signing matrix: each member’s work is one matrix–vector product, exactly the cost of a signature. Lemma 3 (Share simulation). Let T be a set of t members, let A(y) be a uniformly random degree-t matrix polynomial with A(0) = A, and let m1 , . . . , mL ∈ Fq . Then (A(ηj ))j∈T is uniform and independent of A, and for every ℓ the honest shares (A(ηj )e(mℓ ))j ∈T / are a fixed linear function of αℓ = Ae(mℓ ) and of (A(ηj )e(mℓ ))j∈T . Proof. The first claim is the perfect privacy of Shamir sharing, applied entrywise. For the second, y 7→ A(y)e(mℓ ) is a vector polynomial of degree at most t whose values at the t + 1 distinct points {0} ∪ {ηj : j ∈ T } are αℓ and the corrupted shares. Lagrange interpolation at these points determines its value at every ηj . Theorem 4 (Security of threshold notarization). Let ΠBFT satisfy agreement, and let ΠTN be instantiated with the subprotocols of Theorem 2. Consider any computationally unbounded adversary that corrupts at most t members and at most ω verifiers, and makes at most Q verification and resolution queries. (i) Soundness. The probability that some honest verifier, or the arbiter, accepts a certificate (s, v, α) although no honest member decided v in slot s is at most Q/q + 1/(q − 1) + εagr + AdvCR H . The last term is the collision advantage of the adversary’s strategy against the certificate hash H; it vanishes with the injective encoding of Remark 1, which here means one distinct encoded message per index, one index per slot, and encoding dimension L + 1. Hashing used inside agreement is accounted separately, in εagr . (ii) Uniqueness. Except with the same probability, no two certificates for the same slot and different values are

accepted by honest verifiers. (iii) Robustness. If all honest members decide v in slot s, then every combiner that receives the shares of the honest members outputs α = Ak(s) e(ms (v)), whatever the corrupted members send: with probability 1 if it runs the exact decoder directly, and with probability at least 1 − t/q for each invocation of the fast decoder on a frozen set of shares (1 − Rt/q over R invocations). The optimistic path of Fig. 4 returns early when the combiner’s own check accepts an interpolated vector; it can return a wrong vector only if that check accepts an invalid object, which is a Bad event of Theorem 1 for the combiner’s checks (probability εopt ). The optimistic protocol is therefore correct except with probability εopt with exact fallback, and εopt + Rt/q with R fast-decoder calls. In a synchronous round, missing shares are erasures, and decoding succeeds from the at most n shares received. Asynchronously, the combiner uses online error correction [77]: with r ≥ 2t + 1 shares received, it decodes up to ⌊(r − t − 1)/2⌋ errors and outputs only if the decoded polynomial agrees with at least 2t + 1 received shares, and otherwise waits for another share; it terminates once 2t + 1 + e shares have arrived, where e ≤ t is the number of incorrect shares among them. The optimistic checks count towards Q. A combiner that is not an enrolled verifier may output a wrong vector with the probability above; honest verifiers then reject it unless Bad occurs. (iv) Capacity and transfer. Conditioned on agreement, honest members release shares on at most ψ distinct messages per index; hence the attack of Proposition 2(c) cannot be mounted from honest releases. Shares released by corrupted members are functions of their own shares and add nothing (Lemma 3). Agreement fails with probability at most εagr , which (i) already accounts for. Accepted certificates are accepted by every honest verifier, after any number of hops (Corollary 2). Proof. (iv), capacity: by agreement, all honest members that release in slot s release on the same value; each index serves ψ slots; hence the honest members release shares on at most ψ distinct messages per index, unless agreement fails, which has probability εagr . (i). Let FTN be the reactive functionality that samples Γ and the Ak , keeps them, outputs the verifier keys of FKI (also on later enrollment requests, Proposition 3), and, when an honest member Pj releases on (k, m), hands Ak (ηj )e(m) to the adversary. Throughout ΠTN , all state is kept as degreet sharings, and every step is Rand, IP, a local linear map, a robust opening, or the release of a local linear map of a member’s own shares. The perfectly secure reactive composition used for Theorem 2 [67], [68], [75] therefore shows that ΠTN securely realizes FTN ; in the ideal world, the corrupted members’ shares of each Ak are uniform and independent of all secrets. Given an adversary B against ΠTN , we build an adversary A against the experiment of Definition 3 with a single honest signer U ⋆ (the committee) whose index-k signing matrix is Ak . Giving B the shares of further honest members only increases its information; we therefore assume |T | = t. A corrupts the same verifiers as B, samples the corrupted members’ shares uniformly, and runs B together with all honest members of ΠBFT ; consensus uses no secret

PREPRINT

14

of SILMARILS-MV, and A can execute it in full. Whenever a simulated honest member decides v in slot s for the first time, A queries S IGN(U ⋆ , k(s), ms (v)) and computes all honest shares from the answer by Lemma 3. By capacity, these queries respect the bound of ψ messages per index. A forwards verification and resolution queries unchanged. The view of B is distributed exactly as in the real protocol. A certificate on (s, v) that no honest member decided is non-authentic unless ms (v) collides with a signed message, which happens with probability AdvCR H . Its acceptance is therefore the event Bad, which Theorem 1 bounds by Q/q + 1/(q − 1). (ii) follows from (i) and agreement: two accepted certificates on different values for one slot would require an honest decision on each of them. (iii). Honest shares are evaluations of the degree-t vector polynomial y 7→ A(y)e(m), and at most t shares are wrong or missing. With r received shares, e of them wrong, and s′ missing, decoding succeeds when r ≥ t + 1 + 2e. Since r = n − s′ and e + s′ ≤ t, this holds for n ≥ 3t + 1; the exact decoder applies it to each coordinate. In the fast decoder, a wrong share with error dj ̸= 0 escapes detection only if ρT dj = 0, which has probability 1/q because ρ is drawn after the set of shares is frozen. A share that arrives later is not part of this decoding; a retry draws a new ρ and is accounted separately. Unless one of the at most t wrong shares escapes, every non-suspect share is correct, and interpolation from t+1 of them returns α. The stopping rule of online error correction is the standard one [77]: an output that agrees with 2t + 1 received shares agrees with at least t + 1 honest shares and is therefore the honest polynomial. Remark 9 (System-level error budget). The components fail on separate events, which a deployment must add up. Over the lifetime of a system with E anchor matrices (including those of arbiter-verified keys), E εsys ≤ Qtotal + q−1 +εMAC + AdvCR H q | {z }

USS, incl. batches tLRS Rt + AdvCR HBFT + εBFT + q + q ,

where Qtotal counts all verification, resolution and optimisticcombiner checks and charges each tested batch by its size (Lemma 4), AdvCR H covers the hashes of signed and certified messages (zero with the injective encoding), AdvCR HBFT the digests used inside agreement, Rt/q the fast-decoder calls, and tLRS /q the redistributions (Lemma 5), with LRS summed over all of them; εMAC is likewise summed over pairs and epochs. With ideal private channels, the issuance protocols are perfectly secure and add no term; if those channels are built from pads and the same MAC, their checks are counted in εMAC . Each term is counted once; in particular, εagr in Theorem 4 stands for the agreement terms of this sum, not for additional events. A fully information-theoretic deployment needs the injective encoding for certificates, the polynomial MAC above, agreement on full values, and private channels from pads (Section X). Remark 10 (What TN changes and what it does not). TN removes signer-side state: indices follow the slot number fixed

by consensus, and an honest committee cannot equivocate. The signing key is never in one place, and certificates have constant size. What TN does not provide is per-validator attribution: a certificate shows that the committee decided, not who voted. Section VIII-C restores attribution at extra cost. Remark 11 (Linear communication for t < n/5). The following observation is specific to SILMARILS-MV. If the committee accepts n ≥ 5t + 1, the certificate can itself be the quorum certificate of a HotStuff-style protocol, without allto-all authenticated voting. Members share Ak with degree d = n − 2t − 1 and release a share as their vote; the vote message includes the view and the phase. A certificate needs d + 1 = n − 2t shares, and three counts make this work. All n − t honest members suffice for a certificate (liveness). Each certificate contains at least n − 3t honest votes, and two certificates for one view and phase would need 2(n − 3t) > n − t distinct honest voters, i.e., an honest member that voted twice in one view and phase (uniqueness). Decoding a degree-d codeword from n shares with t errors needs n ≥ d + 1 + 2t (robustness); a leader that waits only for n − t shares corrects fewer errors and must wait for more on failure. Two conditions differ from TN. First, capacity must be budgeted per (view, phase) message, because honest members may vote in many views. Second, in the soundness argument, shift (B) becomes ghT L(y), where L has degree at most d, L(0) = 1, and vanishes at the at most d points whose shares on the target message the adversary has seen. The vector h must be orthogonal to e(m′ ) for every message m′ on which some honest share was released; therefore all such messages, not only certified ones, count towards ψ. We leave a full treatment of this variant to future work. Comparison with threshold signatures. TN is structurally close to a threshold signature: the committee holds a degree-t sharing of a linear signing map, and any t + 1 correct shares interpolate a certificate. Table V compares it with BLS [37], [38] and lattice [39], [40] threshold signatures. TN rests on no hardness assumption, and certificates issued today cannot be forged by future cryptanalysis. The price is verification with secret keys of admitted verifiers, which is unavoidable because no publicly verifiable signature is information-theoretically unforgeable; transferability is preserved because validity is a global predicate (Corollary 2). A TN share is one matrix– vector product released after the consensus decision, with no signing rounds among the signers and no per-share verification: wrong shares are removed by Reed–Solomon decoding. The new ingredient is that the virtual anchors make a secretshared linear map transferable and non-repudiable; without them, a secret-shared MAC would let every verifier forge. C. Arbiter-Verified Keys and Batch Arbitration Setting ω = 0 gives a key whose only verifier is the arbiter. The anchor matrix becomes a scalar γ, a signer-index is a row 1×(ψ+1) vector aU,k ∈ Fq , and a signature is the single element α = aU,k e(m). The committee keeps [[γ]] and [[b0,U,k ]] = [[γ]][[aU,k ]] and opens aU,k to the signer. No verifier key is issued. Theorem 1 holds verbatim with C = ∅: shift (A) uses u = 1, and shift (B) needs only γ ̸= 0.

PREPRINT

15

TABLE V T HRESHOLD NOTARIZATION VERSUS THRESHOLD SIGNATURES AND DISTRIBUTED QUORUM SIGNATURES (DQS).

Security basis Verification Signing rounds Faulty shares Size Key lifetime Individual signers

BLS thr. [37], [38] Lattice thr. [39], [40] DQS [41]

SILMARILS-MV TN

pairings (not PQ) public key 1 + checks verified 96 B unlimited no

none (IT) secret keys 0 (decided) RS decoding 32(ω+1) B ψ msgs / index yes (IV, AV)

lattices public key 2–3 by protocol several KB unlimited no

PQ sig. public key approvals n/a O(n) sigs per scheme some node

Checking each signature with Resolve costs one multiplication and one opening online, plus a preprocessed non-zero mask (Section IV). A block of signatures can instead be checked at once. Note that γ is uniform on Fq and is therefore zero with probability 1/q; this is the singular-anchor term of Theorem 1 for ω = 0, and it is shared by all checks on the same γ. Lemma 4 (Batch arbitration). Let σ1 , . . . , σL be arbiterverified signatures, fixed before a uniform r ∈ Fq is opened. Let [[δj ]] = [[γ]]αj − [[b0,Uj ,kj ]]e(mj ) (local), [[D]] = PL j−1 [[δj ]], and output [ρD = 0] after one multiplication j=1 r by a fresh uniform non-zero [[ρ]] and one opening. The output reveals only the verdict. If some σj is not acceptable, then on any transcript of the ideal game of the proof of Theorem 1 (in particular, for a first query), the verdict is 1 with probability at most (L + 1)/q: at most 1/q for the event γ = 0, and at most L/q otherwise. Proof. ρD is 0 iff D = 0, and otherwise it is uniform on F∗q ; the verdict therefore determines the distribution of the opened value, which can be simulated from the verdict. Suppose σj0 is not acceptable. The event γ = 0 has probability P 1/q; assume γ ̸= 0. Case 1: some δj ̸= 0. Then D(r) = j rj−1 δj is a non-zero polynomial in r of degree at most L − 1. The batch and all keys are fixed before r is opened; hence r is uniform and independent of the δj , and D(r) = 0 with probability at most (L − 1)/q. Case 2: all δj = 0. In particular, the arbiter’s check accepts the non-acceptable σj0 . With ω = 0 there are no corrupted functionals. If σj0 deviates by a known non-zero amount ∆ from a valid or returned signature (a corrupted signer, or a modified signature of an honest one), then δj0 = γ∆ ̸= 0, which is impossible. If σj0 is a fresh message of an honest signer, then δj0 = γ(αj0 − ae(mj0 )) vanishes iff ae(mj0 ) = αj0 , which has probability 1/q by shift (B), because on such a transcript a is uniform on its affine posterior. Altogether, 1/q + (L − 1)/q + 1/q = (L + 1)/q. Weights starting at r1 , i.e., rj for j = 1, . . . , L, do not give this bound: for L = 1 and a fresh unsigned message submitted with α = 0, the verdict is [rγae(m) = 0], which holds with probability 3/q−3/q 2 +1/q 3 > 2/q. An exhaustive check over F3 , F5 , F7 (batch_check.py in [85]) confirms the counterexample, and the corrected bound for batches of L ∈ {1, 2} unsigned honest items and every choice of submitted values. Batches within a run. As in the proof of Theorem 1, we answer every batch in the ideal game with the bit “every item

is acceptable”, which the adversary can compute itself. Each batch draws its own r after it is fixed and its own fresh ρ; r is public and independent of all secrets; hence it does not change the posterior. With Qind individual resolution queries and B batches of sizes L1 , . . . , LB on the same γ, the proof above gives PB 1 + Qind + b=1 Lb : Pr[Bad] ≤ q the event γ = 0 is counted once, each individual query contributes 1/q, and each non-acceptable batch contributes (Lb − 1)/q for cancellation and 1/q for one non-acceptable item. A rejected batch is bisected to locate the offenders. Bisection identifies the items that fail the algebraic check; it identifies every non-acceptable item only outside the event Bad, since a sub-batch can pass by cancellation and an unsigned item can pass by a lucky guess. Locating β offenders takes O(β log L) further tests, but the error accounting charges the sizes P of all tested sub-batches: the bound above holds with b Lb taken over every tested batch, which can reach Θ(L log L) item appearances when most items are bad. Each test uses fresh r and ρ. Clients. A client receives arbiter-verified indices. Its transaction carries a 32-byte signature, validators verify the transactions of a block collectively with Lemma 4, and the block’s TN certificate attests to the outcome for external parties. Nonrepudiation holds through Resolve. One signer-index costs (ψ+1)(rc +µc +n) field elements in total, i.e., a constant number per validator and transaction. The client receives (ψ + 1)n elements per index, about 32n bytes per transaction, which is the only client-side cost that grows with n (Section IX-D). Accountable TN. Validators may additionally attach an arbiter-verified signature to their commit votes. The committee batch-checks the votes of each block. Two accepted signatures of one validator on conflicting votes for the same slot are equivocation evidence in the sense of Theorem 3, whose proof applies unchanged with ω = 0. This restores pervalidator accountability on top of TN, at the cost quantified in Section IX-D. D. Open Verifier Sets Proposition 3 (Dynamic and retroactive enrollment). A verifier with a fresh identifier xnew ∈ / {0, x1 , . . . , xν } can be enrolled at any time by opening cnew = ΓT λ(xnew ) and bnew,k = MkT λ(xnew ) for any set of indices k, including indices whose slots are long past. This uses only local linear maps and robust openings, costs (ω + 1)n field elements once per epoch for cnew and (ψ +1)n per index, and needs no multiplication. Consider the following extension of Definition 3: the committee corruption remains static, but the adversary may adaptively request enrollments of fresh identifiers of its choice and adaptively corrupt enrolled verifiers, receiving all keys the corrupted verifier holds, for past and future indices. Theorems 1 and 4 continue to hold as long as the cumulative number of verifiers ever corrupted for the same anchor matrix Γ, including verifiers whose credentials were later revoked, is at most ω.

PREPRINT

Proof. The keys are exactly those FKI would have issued to xnew . The bound of Theorem 1 does not depend on ν, only on |C| ≤ ω and on the distinctness of identifiers used in (2). For the adaptive extension, we follow the proof of Theorem 1 with Cj , the set of verifiers corrupted before query j. Step 1 is unchanged, because the ideal answers do not depend on keys. For Step 2, we argue by induction over the transcript: a corruption of Vs reveals cTs = λ(xs )T Γ and bTs,U,k = cTs AU,k for all (U, k), i.e., it appends one row to K and the corresponding row to every BU,k . These are linear constraints of the same form; hence the posterior remains uniform on a product of affine subspaces. Step 3 applies with ΛCj , which has at most ω columns; (2) holds for every honest xi because identifiers are distinct, whatever order they were chosen in. Revoking a credential does not remove its row from K, which is why the bound is cumulative. Enrollment must be admission-controlled, e.g., by the committee’s membership rules. Since ω + 1 colluding verifiers forge (Proposition 2(b)), Sybil verifiers must not be admitted. With a fresh Γ per epoch, ω bounds the verifiers corrupted per epoch, cumulatively over the epoch and over any period in which that epoch’s state is retained. This adaptive statement concerns verifiers only; the committee corruption stays static, as in Theorem 2. E. Evolving Committees and Proactive Refresh Let the shared state, i.e., [[Γ]], the live [[Ak ]] and the retained [[Mk ]], be held by a committee P (n ≥ 3t + 1) and be handed over to a committee P ′ (n′ ≥ 3t′ + 1), which may overlap with P or differ from it in size. Protocol ΠRS . (i) Every old member Pj shares each of its shares with P ′ by a perfect VSS of degree t′ [67], [71]. The VSS guarantees that each dealing is a consistent degreet′ sharing, but a corrupted dealer may share a wrong value. (ii) P ′ opens a uniform r after all dealings are complete, and PL (ℓ) forms, for each dealer j, the sharing [[wj ]] = ℓ=1 rℓ [[sj ]] of (ℓ) the combination of the values sj it dealt for the L secrets. (iii) With a parity-check matrix H of the degree-t Reed– Solomon code on the old points, P ′ computes [[Hw]] locally and opens it. (iv) The syndrome Hw is decoded to the support D of the error vector, i.e., the dealers that deviated. Silent dealers are erasures. (v) The new share of every secret is P G (ℓ) j∈G λj [[sj ]] for a fixed set G of t + 1 dealers outside D, with Lagrange coefficients λG j at 0. Old members erase their shares. Lemma 5 (Robust redistribution). Against a static adversary that corrupts at most t members of P and at most t′ members of P ′ , ΠRS outputs degree-t′ sharings of the same secrets except with probability at most tL/q, where L is the number of secrets. Privacy is perfect, also on that event: the adversary’s complete view of one transition, i.e., the old shares of corrupted old members, all messages that corrupted parties receive in the dealings, the public r, the opened syndrome polynomials and the new shares of corrupted new members, has the same distribution for all values of the secrets, and a simulator that knows none of the secrets generates it exactly.

16

Proof. Write w = c + ϵ, where c is the combination of the P (ℓ) correct shares, a codeword, and ϵj = ℓ rℓ ∆j collects the (ℓ) deviations ∆j of dealer j. Then Hw = Hϵ depends only on deviations that the adversary chose; opening it reveals nothing about the secrets. Since at most t dealers deviate and the code has minimum distance n − t ≥ 2t + 1, syndrome decoding recovers ϵ, and with it every dealer with ϵj ̸= 0. A deviating (ℓ) dealer escapes only if ϵj = 0 although some ∆j ̸= 0; this is a non-zero polynomial of degree at most L in r, which has probability at most L/q, and at most t dealers deviate. All dealers in G then shared their correct shares, and the Lagrange combination of t + 1 correct shares is the secret. Privacy. Giving the adversary more corrupted new members only enlarges its view; we therefore assume (ℓ) |T ′ | = t′ . An honest dealer h shares sh with Pt′ (ℓ) (ℓ) (ℓ) κ (ℓ) Ph (z) = sh + κ=1 ah,κ z , whose coefficients ah ′κ are fresh and uniform. Let V = [ηi ]i∈T ′ ,κ∈[t′ ] , which is invertible because the new points are distinct and nonzero. The values that corrupted new members receive ′ (ℓ) (ℓ) (ℓ) are eh = sh 1 + V ah , which are uniform on Ftq and independent of the secrets, of the old shares and of everything (ℓ) else, because ah is fresh. By the privacy of perfect VSS, the other dealing messages that corrupted parties receive are simulatable from these values [67]. Consider the opened P P ℓ (ℓ) syndrome polynomial Si (z) = j Hij ℓ r Pj (z). Its constant term is (Hϵ)i , because the correct old shares form a codeword, and the adversary knows it. Its other P P (ℓ) coefficients have the honest part Hih ℓ rℓ ah = hP
P P P ℓ (ℓ) ℓ (ℓ) V −1 H r e − 1 H , and r s ih ih h ℓ h ℓ h P h P P P (ℓ) ℓ (ℓ) = − j∈T Hij ℓ rℓ sj , again because h Hih ℓ r sh correct old shares form a codeword. The adversary knows the right-hand side, since it holds the corrupted old shares. Hence the syndrome polynomials are a fixed function of the (ℓ) eh , of r and of the adversary’s own data. The same holds for the set G, which syndrome decoding derives from the P G (ℓ) ′ constant terms, and for the new shares j∈G λj Pj (ηi ) of corrupted new members. The corrupted old shares are uniform and independent of the secrets, because there are at most t of them. The complete view is therefore a fixed function of independent variables whose distribution does not depend on the secrets, and the simulator samples them and runs the adversary. The lemma does not claim that the adversary’s old and new views are independent given the secrets. A corrupted dealer may reshare its own old share Z with the constant polynomial Z; both views then contain Z. That correlation consists only of information the adversary already holds, and the joint view is still simulatable. Consequences. (a) Membership changes at epoch boundaries need no resharing of signing state: the new committee runs issuance for the next epoch with a fresh Γ, and only the retained state of (c) is reshared. Mid-epoch changes use ΠRS . (b) Proactive refresh [78]: refreshing with P ′ = P at every epoch, and erasing old shares, is designed to ensure that forging requires t + 1 members corrupted within one epoch, rather than t + 1 members corrupted at any time.

PREPRINT

17

Lemma 5 covers a single transition against a static adversary; it does not by itself give security against a mobile adversary, and a formal treatment of that model is future work. Two limits apply even then. Refreshing the sharings of a retained Γ does not change the verifier functionals ci already issued; hence ω bounds the verifiers corrupted cumulatively for that Γ (Proposition 3), not those corrupted at one time. Erasure by honest members does not remove copies that a corrupted member kept. (c) Retained state: verifying history needs no retained secrets when later certificates cover hashes of earlier blocks. This relies on collision resistance of the block hash and on an authenticated current checkpoint, and is therefore computational; it does not replace the information-theoretic verification of the old certificates. Only the dispute window and the indices that the committee chooses to keep open for retroactive enrollment are reshared. F. Cost of Threshold Notarization With E = (ω+1)(ψ+1) and rc , µc as in (3), one committee index costs TN Cidx = E rc + E µc + ν(ψ + 1) n

(4)

TABLE VI SILMARILS-MV CORE OVER F2255 −19 (µS , EXCLUDING HASHING ; SHA3-256 OF A 128 B MESSAGE ADDS 0.52 µS )

ω

|σ| (B)

1 3 10 20 33 66

64 128 352 672 1088 2144

ψ=1 sign verify

ψ = 16 sign verify

ψ = 64 sign verify

0.06 0.12 0.29 0.60 0.87 1.74

0.59 1.02 2.48 4.57 7.81 13.67

2.41 4.00 8.91 17.43 27.43 52.47

0.08 0.10 0.18 0.32 0.47 0.77

0.45 0.47 0.55 0.63 0.83 1.13

2.13 1.70 1.57 1.81 1.82 2.30

TABLE VII S AME - HOST COMPARISON . F OR SILMARILS-MV: ω = 10 (n = 31), ψ = 16, TIMES INCLUDING SHA3-256. “V ERIFIER KEY ” IS PER SIGNER - INDEX (ψ SIGNATURES ). Scheme∗ SILMARILS-MV Ed25519 ML-DSA-44 ML-DSA-65 Falcon-512 SLH-DSA-128f SLH-DSA-128s †

|σ| (B)

Ver. key (B)

Sign (µs)

Verify (µs)

352 64 2420 3309 666 17088 7856

544†

3.0 13.8 64.9 104 160 6609 146158

1.1 31.3 23.2 37.4 29.2 568 224

32 1312 1952 897 32 32

Basis IT ECDLP MLWE/MSIS MLWE/MSIS NTRU-SIS hash hash

Secret, per signer-index; 34 B per signature, plus 352 B ci per epoch.

∗

field elements, and each certified slot adds n(ω + 1) elements of shares per combiner. Per member and slot, this is i h

c + 1 + ν 1 + ψ1 = O(ω + ν), (ω + 1) 1 + ψ1 rc +µ n because rc /n and µc /n are constants for d = Θ(n). It is bounded independently of n. The only per-member term that grows with n is the authentication of consensus messages themselves, O(n) MAC tags per slot, which any all-to-all BFT protocol pays. Our simulator, which runs ΠTN with garbage, silent and equivocating members, matches (4), instantiated with the semi-honest extraction rate d = n − t, to within 0.8% (Section IX-D). IX. I MPLEMENTATION AND E VALUATION A. Setup We implemented the SILMARILS-MV core in C: field arithmetic over F2255 −19 in radix 251 , signing with a log-depth power ladder for e(m) and lazily reduced inner products, and verification. Long messages are mapped to Fq with OpenSSL SHA3-256. We also wrote three Python components: a reference implementation for arbitrary primes q; a simulator of ΠDKI that counts every field element sent and decodes outputs with Berlekamp–Welch against t parties sending corrupted shares; a Monte-Carlo attack suite. All timings in this section were measured on the same host, an Intel Core i9-13900HX under WSL2 (Ubuntu, GCC 15.2 -O3 -march=native, Rust 1.99), single-threaded. Baselines use the fastest available implementations: Ed25519 from ed25519-dalek, and ML-DSA-44/65, Falcon-512 and SLH-DSA from the AVX2optimized PQClean code through the Rust pqcrypto crates. For SLH-DSA we measure SPHINCS+ -SHA2-128f/s-simple, which uses the same parameter sets. All code, simulators and raw data are publicly available at https://github.com/ hassankhodaiemehr/silmarils-mv [85] (Section A).

The schemes compared in this table operate under different verification models. SILMARILS-MV requires secret verifier credentials and authorization-controlled verification, whereas standardized signature schemes provide public verification.

B. Microbenchmarks Table VI reports signing and verification times. Verification costs ω + ψ + 2 multiplications (about 12.5 ns each on this host). For ψ ≤ 16 it stays near or below one microsecond up to ω = 33, i.e., committees of 100 validators. Signing costs (ω + 1)(ψ + 1) multiplications. With ψ = 1 it is a few hundred nanoseconds; larger ψ trades signing time for fewer indices and smaller verifier storage per signature. Table VII compares SILMARILS-MV with standardized schemes on the same host. Against AVX2-optimized implementations, verification is 22× faster than ML-DSA-44 and 27× faster than Falcon-512, and signing is 22× and 53× faster, respectively. The price is secret, per-signature verifier key material: 34 B per future signature, issued offline. The compared schemes address different deployment models. Standardized digital signatures provide unrestricted public verification, whereas SILMARILS-MV assumes admissioncontrolled verification using verifier credentials. Accordingly, the comparison should be interpreted as a resource comparison rather than a claim of functional equivalence. C. Ledger-Level Evaluation We model the leader-based protocol of Section VII with n = 3t + 1, ω = t and ψ = 16. Per block, n votes go to the leader, which broadcasts a QC of 2t+1 votes plus its proposal signature to n − 1 replicas. Each replica verifies the QC and the proposal. We count authentication bytes only and use the measured times of Tables VI and VII. For SILMARILSMV we report both individual-vote QCs and aggregated QCs (Corollary 3). Offline issuance cost follows (3), with n + 1 signatures per block (happy path: one vote per validator and

PREPRINT

one proposal; protocols with several voting phases scale this term proportionally). QC size. Figure 5(a) shows QC size against committee size. Individual-vote QCs grow as (2t + 1)(t + 1) field elements; they beat ML-DSA-44 by 7× at n = 31 and match Falcon-512 at n ≈ 60. Aggregated QCs grow only linearly. At n = 31 an aggregated QC is 440 B (352 B for the vector, 4 B of bitmap and 84 B for the 21 signer indices), against 49.6 KiB for MLDSA-44, 13.7 KiB for Falcon-512 and 1.3 KiB for Ed25519 without aggregation. Leader bottleneck. Figure 5(b) plots online authentication bytes sent by the leader per block. Note that this compares aggregated SILMARILS-MV QCs with the non-aggregated QCs that standardized post-quantum schemes support natively; SNARG-based aggregation of Falcon [18] shrinks QCs at a large proving cost and is not modelled. With aggregation, the leader sends 23.3 KiB per block at n = 31, against 1.52 MiB for ML-DSA-44 (67× less) and 429 KiB for Falcon-512 (18× less). It even undercuts non-aggregated Ed25519 at every committee size we consider. Verification time. Figure 5(c) shows the per-replica cost of verifying one QC and one proposal signature. At n = 31 it is 6.2 µs for aggregated SILMARILS-MV, against 0.51 ms for ML-DSA-44, 0.64 ms for Falcon-512 and 0.69 ms for Ed25519, an improvement of 82× over ML-DSA-44. Total cost including issuance. Figure 5(d) adds the offline key material to the online traffic. With a dealer or HSM (e.g., the membership service of Fabric [5]), the total is 2.5 KiB per validator per block at n = 31, 21× less than ML-DSA-44. With dealer-free issuance by ΠDKI , costed with the malicious estimate d = n − 2t of Section VI, the average total per validator is lower than ML-DSA-44 for n ≤ 10 and higher for larger committees: 164 KiB versus 53 KiB at n = 31 (118 KiB under the semi-honest cost model that our simulator validates). The malicious figure omits the fault-detection and broadcast-emulation terms listed in Section VI. This is the price of removing every trusted party and every computational assumption. The extra traffic is offline, evenly spread over validators, and does not touch the leader bottleneck. At one block per second and n = 31 it amounts to 1.3 Mbit/s per validator, and to 573 MiB of issuance traffic and 3.7 MiB of verifier key storage per validator per one-hour epoch. Any USS consumes key material per signature [23], [25], and QDS consume it through quantum channels [27], [28]. For SILMARILS-MV the cost of producing that key material without any trusted party or quantum link is given in closed form by (3). D. Scalability to 1000 Validators We now evaluate the modes of Section VIII for n = 3t + 1 from 4 to 1000. TN uses ω = 16, ψ = 64 and ν = 64 external verifiers, which receive every certificate, and issuance is costed with the malicious model d = n − 2t. Consensus in TN mode runs two all-to-all voting rounds authenticated by 32-byte information-theoretic MAC tags, with one tag per delivered message: each receiver gets only its own entry of the PBFT authenticator. The model is an analytic normalcase estimate under declared exclusions: it omits pre-prepare,

18

TABLE VIII S CALABILITY (n = 3t + 1), ANALYTIC NORMAL - CASE MODEL . P ER - VALIDATOR AVERAGE AND MAXIMUM ( LEADER OR COMBINER ) BYTES PER BLOCK , CERTIFICATE SIZE , AND TIME FOR AN EXTERNAL PARTY TO VERIFY ONE CERTIFICATE . TN: ω = 16, ψ = 64, ν = 64. n = 31 n = 100 n = 301 n = 1000 52.7 144 14.5 164 11.0 25.2

161 470 44.4 1 675 14.9 61.8

478 1 420 132 15 085 27.4 170

1 579 4 724 435 166 160 71.0 545

max. party ML-DSA-44 star Falcon-512 star (KiB) SILMARILS-MV TN

1 633 449 59.9

16 146 4 443 101

143 926 39 609 221

1 579 456 434 677 636

certificate (KiB)

ML-DSA-44 Falcon-512 SILMARILS-MV TN

49.6 13.7 0.53

158 43.6 0.53

475 131 0.53

1 576 434 0.53

cert. verify

ML-DSA-44 Falcon-512 SILMARILS-MV TN

0.49 ms 0.61 ms 2.4 µs

1.55 ms 1.96 ms 2.4 µs

4.66 ms 5.87 ms 2.5 µs

15.5 ms 19.5 ms 2.4 µs

avg. per validator (KiB)

ML-DSA-44 star ML-DSA-44 all-to-all Falcon-512 star SILMARILS-MV IV SILMARILS-MV TN SILMARILS-MV TN+acc.

client, checkpoint and view-change traffic, and its issuance term uses the malicious estimate of Section VI, which omits fault-detection and broadcast-emulation terms. It is not the measured cost of a fully implemented malicious-secure ledger. The baselines are post-quantum signatures in a HotStuffstyle star topology (one vote to the leader, a QC of 2t + 1 signatures to everyone) and in a PBFT/Tendermint-style all-toall topology (two voting rounds), plus Ed25519 and BLS [65] (analytic, 96-byte aggregate plus bitmap) as non-post-quantum references. As before, we count authentication bytes only. Bandwidth. Figure 6 and Table VIII show the effect of the three mechanisms. IV mode grows as n2 and is the right choice only for small consortia. TN grows only through the MAC tags of consensus, which any all-to-all protocol pays: at n = 1000, TN costs 71 KiB per validator per block, of which 62.5 KiB are MAC tags and about 8 KiB are issuance. This is 22× less than ML-DSA-44 in a star topology, 67× less than ML-DSA-44 all-to-all, and 6× less than Falcon-512. With information-theoretic MACs, consensus also consumes a pre-shared 32-byte pad per tag and endpoint, 125 KiB per validator per block at n = 1000. If this pad material is counted as traffic, TN totals 196 KiB, still 8× below ML-DSA-44; with computational post-quantum MACs, it is not consumed at all (Section X). The busiest party is where the difference is largest. An ML-DSA-44 leader must send a 1.5 MiB QC to every replica, i.e., 1.5 GiB per block at n = 1000, whereas the busiest TN party (the combiner) handles 636 KiB. For n = 4, TN is more expensive than ML-DSA-44 in a star topology, because issuing keys to 64 external verifiers dominates; IV mode is cheaper there. Adding accountability (TN+acc.) costs 545 KiB per validator per block at n = 1000, still 2.9× below ML-DSA-44 in a star topology, with attributable votes and 32-byte vote signatures. Certificates. A TN certificate is 544 B at every committee size, and an external verifier checks it in 2.4 µs including hashing. An ML-DSA-44 QC at n = 1000 is 1.5 MiB and takes 15.5 ms to verify. Only BLS aggregates are smaller (96 B plus a bitmap), and they are not post-quantum.

PREPRINT

19

(b) leader egress / block (KiB)

(a) QC size (KiB) 103

(c) QC + proposal verification (µs)

(d) total per validator / block (KiB)

105 104 102

103

101

102

20

40

60

80

100

100

101

100

10−1

20

40

60

80

100

committee size n

committee size n

SLH-DSA-128s Ed25519 (not PQ) agg. + ΠDKI , malicious (d)

20

40

60

80

100

committee size n

ML-DSA-44

Falcon-512

SILMARILS-MV indiv. (a–c) agg. + ΠDKI , semi-honest (d)

SILMARILS-MV agg. (a–c) agg. + dealer (d)

20

40

60

80

100

committee size n

avg. bytes per validator per block (KiB)

Fig. 5. Ledger-level model of a leader-based BFT committee (n = 3t + 1, ω = t, ψ = 16): (a) quorum-certificate size; (b) online authentication bytes sent by the leader per block; (c) per-replica time to verify one QC and one proposal signature; (d) average total bytes per validator per block, including offline key issuance by the committee (ΠDKI , both cost models of (3)) or by a dealer/HSM. Aggregated SILMARILS-MV QCs contain ω + 1 field elements, an n-bit bitmap and a 4-byte index per signer; individual votes also carry their 4-byte index.

Clients. An arbiter-verified client signature is 32 B. Its issuance costs each validator 0.38 KiB per transaction, independent of n, whereas a ML-DSA-44 signature delivers 2.4 KiB to every validator and costs each of them 23 µs to verify. The client receives about 32n bytes of key material per transaction: 3.2 KiB at n = 100 and 31.7 KiB at n = 1000.

104

102

100 4

10

31

100

301

1000

committee size n SILMARILS-MV IV, dealer-free ML-DSA-44, star

ML-DSA-44, all-to-all Falcon-512, star

SILMARILS-MV TN + accountability MAC-only BFT (no certificate) BLS aggregate (not PQ)

SILMARILS-MV TN Ed25519, star (not PQ)

Fig. 6. Average authentication bytes per validator per block, including all offline key issuance, up to n = 1000. One-time MAC key material for TN consensus is not counted as traffic (see text). TN costs an amount bounded independently of n on top of MAC-authenticated consensus.

Computation. Measured in C over F2255 −19 (ω = 16, ψ = 64), producing a share costs about 15 µs per member and slot. Combining is dominated by computing t + 1 Lagrange coefficients: 12 µs at n = 31, 0.20 ms at n = 301 and 2.1 ms at n = 1000, including the check with the combiner’s own key. The fast decoder of Fig. 4, Gao decoding of one random combination followed by interpolation from non-suspects, takes 0.17 ms, 8.7 ms and 99 ms at the same sizes. It runs only when a share is wrong, and suspects are excluded from the optimistic path afterwards. We estimate that a TN validator spends about 1.5 ms per block at n = 1000: 0.4 ms on MAC tags, assuming 0.2 µs per tag, and the rest on local issuance arithmetic. ML-DSA-44 verification alone takes 15.5 ms (star) or 46 ms (all-to-all).

Simulation of the protocols. The simulator (tn_sim.py in [85]) executes ΠTN end to end for n ∈ {4, 7, 10, 13, 16}, with 8 committee indices, ψ = 4 and 4 external verifiers. The t corrupted members are assigned, in turn, three behaviors: random shares, silence, and shares on a conflicting value (all three occur for n ≥ 10). All 32 certificates per run were valid and accepted by every verifier. Combining used the optimistic path, with at most one coordinate-wise Berlekamp–Welch decoding per run, after which the combiner excluded the suspects it identified. The measured issuance cost matches (4) to within 0.8%. A verifier enrolled after all slots had passed verified every historical certificate (Proposition 3). Redistribution to a committee of n + 3 members (Lemma 5), with corrupted old dealers sharing wrong values and silent dealers, identified exactly the deviating dealers in every run. The new committee then issued and certified on a new index, and all old certificates still verified. For arbiter-verified keys, with the weights rj−1 of Lemma 4, batches of 24 valid signatures were always accepted, and batches with one modified signature were always rejected. Separately, an exhaustive enumeration over F3 , F5 and F7 (batch_check.py) reproduces the counterexample to the weights rj given after Lemma 4 (acceptance 19/27, 61/125 and 127/343 for L = 1) and confirms the bound (L + 1)/q of the corrected lemma for batches of L ∈ {1, 2} unsigned honest items and every choice of the submitted values. Finally, in the TN forgery experiment (n = 7, ω = 2, ψ = 2), t corrupted members and ω corrupted verifiers see ψ−1 released certificates on an index and try to certify a value that the committee did not decide. The adversary samples the signing matrix from its exact posterior given the corrupted keys and the certificates; by Lemma 3, the member shares add nothing. Over 2 × 104 trials it succeeded with probability 0.0079 at

PREPRINT

20

throughput (ktx/s)

q = 257 (bound 0.0078, standard error 0.0006, i.e., within one standard error of the bound) and 0.0189 at q = 101 (bound 0.0199). These runs support Theorem 4(i) but do not prove it. E. HotStuff Prototype

10 5 0

crypto CPU / replica / block (ms)

To complement the analytic model, we implemented chained HotStuff [2] in Rust (tokio). It has a three-chain commit rule, round-robin leaders and a timeout-based view change, with pluggable vote authentication and real cryptography throughout: Ed25519 (ed25519-dalek); ML-DSA44 (PQClean, AVX2); SILMARILS-MV in IV mode, with aggregated QCs; MACs over F2255 −19 with fixed per-pair keys (a timing model of the analyzed polynomial MAC); MACs plus TN certificates (ω = 16, ψ = 64), sent to 4 external auditors. Star-topology variants send votes to the next leader. All-to-all variants (“a2a”) broadcast votes, and every replica forms the QC locally. In the MAC variants a QC is not transferable: a replica accepts a QC, whether it arrives in a proposal or in a new-view message, only after it has itself received 2t + 1 valid MAC-authenticated votes for that block and view, and it holds the proposal until then. Since every honest replica votes once per view and sends the same vote to everyone, two locally formed QCs for conflicting blocks in one view would need an honest replica that voted twice; hence the quorum-intersection step of the HotStuff safety argument [2] carries over to locally formed QCs, provided the MACs are unforgeable, i.e., use pads as in Section VIII-B, which the timing prototype does not. Liveness under Byzantine voters that withhold votes from some replicas is not addressed by this rule; a deployment would use a MAC-based protocol with a proved view change, such as PBFT [1] (Section VIII-B). For timing, the prototype derives the MAC keys from a fixed per-pair key instead of consuming pads; the pad material is accounted analytically in Section IX-D. SILMARILS-MV votes and QCs carry their 4-byte indices, which the wire sizes include. All replicas run on one host and communicate over an emulated network. The network applies a per-link one-way delay and a per-node egress bandwidth cap, charges every message its exact wire size, and delivers through one delay queue per node. Blocks carry 400 transactions of 128 B. Keys are issued before the measured window; issuance traffic is either omitted or injected as background traffic following (3) and (4). Unless stated otherwise, the one-way delay is 10 ms and the egress cap is 1 Gbit/s. All experiments ran on the host of Section IX (24 cores, 32 threads). Each configuration was run three times for 15 s after a 4 s warm-up, and we report medians. In all 354 runs, every honest replica committed the same chain. These runs involve honest and crashed replicas only; they are a performance evaluation and do not test Byzantine safety under equivocation, selective delivery or fabricated QCs. Figure 7 and Table IX summarize the results. Scaling. At n = 100, SILMARILS-MV IV commits 7.97 ktx/s, against 2.88 ktx/s for ML-DSA-44 in the same star topology (2.77×). Its latency is 162 ms instead of 429 ms, and each replica sends 52 KiB per block instead of 209 KiB. ML-DSA-44 recovers most of the throughput with all-to-all voting (7.55 ktx/s), but

15

4

10

4

10

31

100

31

100

100

10−2

committee size n SILMARILS-MV IV (star) ML-DSA-44 (star) Ed25519 (not PQ)

SILMARILS-MV TN (a2a) ML-DSA-44 (a2a)

Fig. 7. HotStuff prototype, 10 ms one-way delay and 1 Gbit/s per node: throughput and cryptographic CPU time per replica per block versus committee size (medians of 3 runs, i9-13900HX).

TABLE IX H OT S TUFF PROTOTYPE ( MEDIANS OF 3 RUNS , I 9-13900HX). T HROUGHPUT ( KTX / S ), COMMIT LATENCY ( MS ), K I B SENT PER REPLICA PER BLOCK ( INCLUDING THE 50 K I B PAYLOAD ), AND CRYPTOGRAPHIC CPU TIME PER REPLICA PER BLOCK (µS , n = 31).

Scheme

n=31, 1 ms n=31, 100 Mb/s n=100, 10 ms, 1 Gb/s tput lat tput lat tput lat KiB crypto

ML-DSA-44 ML-DSA-44 a2a Ed25519 (not PQ) SILMARILS-MV IV MAC a2a SILMARILS-MV TN

18.4 30.8 28.6 32.1 32.5 32.6

68.7 38.7 45.3 39.7 37.0 36.9

2.08 3.57 3.60 3.68 3.71 3.68

602 331 349 342 324 325

2.88 7.55 6.77 7.97 8.08 8.08

429 158 193 162 148 148

209 288 54.0 52.0 56.8 57.4

576 737 772 11 10 26

it then sends 288 KiB per replica per block, 5.5× more than SILMARILS-MV IV. Cryptographic CPU. Per replica and block, SILMARILS-MV IV spends 24 µs at n = 100 and TN spends 57 µs, including share computation and combining. ML-DSA-44 spends 1.61 ms in the star topology, 67× more than SILMARILS-MV IV. The values for Ed25519 and for ML-DSA-44 a2a at n ≥ 64 are inflated by contention among colocated replicas. Bandwidth-bound regime. At n = 31, SILMARILS-MV IV sustains 1.85×, 1.77× and 1.62× the throughput of ML-DSA-44 at 50, 100 and 250 Mbit/s, because an ML-DSA-44 QC adds 50 KiB to every copy of the proposal. CPU-bound regime (1 ms delay, n = 31). SILMARILS-MV IV reaches 1.75× the throughput of ML-DSA-44. Threshold notarization costs less than 1% throughput relative to MAConly consensus at every committee size. External auditors hold verified certificates 22.4–23.0 ms after commit, independent of n from 4 to 100, i.e., two message delays plus processing. Issuance traffic (background, following (3) and (4)). In TN

success probability

PREPRINT

21

TABLE X L IMITATIONS REMOVED BY THE SCALING MECHANISMS , AND LIMITATIONS THAT REMAIN .

10−1

10−2

11

31

101

Limitation

Status

Issuance cost

Removed Bounded per validator independently of n in TN mode (4); only consensus authentication grows with n.

Signature size

32(ω + 1) B, with ω chosen for external verifiers, not tied to t.

Signer state

TN indices follow consensus slots; an honest committee cannot reuse one.

257

field size q bound 1/q + 1/(q−1)

posterior forger

Closed verifier set

Retroactive enrollment (Proposition 3).

bound 1/q

repudiator (one honest Vi )

Membership changes

Robust redistribution with perfect privacy (Lemma 5); fresh anchors in every epoch.

Clients

32-byte arbiter-verified signatures, constant cost per validator and transaction.

Fig. 8. Monte-Carlo success of the best attacks against the bounds of Theorem 1 (Q = 1). Each q has three points, for (ω, ψ) ∈ {(1, 1), (2, 2), (3, 4)}.

mode it adds 6 KiB per replica per block at n = 100 and leaves throughput unchanged. In IV mode it reaches 1.7 MiB per replica per block at n = 100 and lowers throughput by 35%, which confirms that IV mode is meant for small committees. Crashes. With t crashed replicas, recovery is dominated by the timeout policy of our simple pacemaker, and all authentication schemes behave alike (within 10%). Sensitivity to colocation. Varying the runtime from 8 to 32 threads at n = 100 changes the throughput of SILMARILS-MV IV, TN and star ML-DSA44 by less than 0.4%, and that of all-to-all ML-DSA-44 by 7%. The emulation shares one machine among all replicas and does not model packet loss or jitter. The per-replica cryptographic CPU time is the metric least affected by colocation. F. Empirical Validation of the Bounds We implemented the adversaries of Proposition 2 over small primes q ∈ {11, 31, 101, 257} with (ω, ψ) ∈ {(1, 1), (2, 2), (3, 4)}, using 4 × 104 trials per point: the posterior forger corrupts ω verifiers, obtains ψ signatures on the target index, samples a signing matrix from the exact posterior given its view, and signs a fresh message; the repudiator, a corrupted signer colluding with ω verifiers, submits α = Ae(m) + D with D ̸= 0 orthogonal to all corrupted functionals; the tightness attacks (b) and (c) use ω+1 colluders and ψ + 1 signatures, respectively. Figure 8 plots the results against the bounds of Theorem 1 for Q = 1. Forgery success is close to the bound 1/q + 1/(q − 1) and exceeds it by at most one standard error (the largest excess, 0.0206 against 0.0199 at q = 101, is 0.95 standard errors); at q = 257, for example, we measure 0.0068– 0.0072 (standard error about 0.0004) against a bound of 0.0078. The second term is not vacuous: a singular Γ can place an honest functional in the corrupted row space (conditional on rank K = r, this happens with probability q r−ω−1 , not always), and the posterior forger then succeeds. Repudiation success equals 1/q within sampling error, matching Proposition 2(d). The independent-functional variant (no anchors) behaves the same, with forgery success at 2/q, matching its 2Q/q bound. In that variant, ω + 1 colluders forged with probability 0.89–0.997 (2 000 trials per point), which is

Verification not public

Remaining Secret keys and admission control, since ω + 1 colluders forge (Proposition 2(b)); rare external checkpoints can use ML-DSA or SLH-DSA.

Attribution in TN

Certificates attest the decision, not votes; accountable TN costs 545 KiB per validator per block at n = 1000, below ML-DSA-44 but 7.7× TN.

Key consumption

About one element per certified slot and signer; one-time MAC pads cost 125 KiB per validator per block at n = 1000. Computational PQ MACs avoid this, but agreement then holds only against adversaries that cannot break the MAC during the run; a failed agreement can exceed ψ messages on one index and expose it (Proposition 2(c)).

Client key delivery

About 32n bytes per transaction.

Private channels

Needed for issuance (below).

Consensus integration Theorem 4 assumes agreement of ΠBFT (e.g., PBFT with MAC authenticators); its digests add a collision term unless replicas agree on full values (Remark 9). The MAC variant of our HotStuff prototype is a performance prototype, and its Byzantine liveness is not established. The traffic figures are an analytic normal-case model, not the cost of a complete deployment. Long-term trust

Each refresh is covered by Lemma 5, but security against a mobile adversary is not proved; ω bounds verifiers corrupted cumulatively per anchor matrix; historical evidence via later certificates relies on hashing and a trusted checkpoint.

Maturity

Malicious dealing checks of [71] are costed (as an estimate), not implemented; n = 1000 results are analytic; the prototype runs on one host over an emulated network without loss or jitter, and only crash faults were tested.

the probability that their independent random functionals are linearly independent. In the anchored scheme, the attack of Proposition 2(b) succeeded in every one of 4 000 trials per field size, as predicted. With ψ + 1 signatures, forgery succeeded in every trial (Proposition 2(c)). Finally, the Q-query attack of Proposition 2(a) without corruptions succeeded with probability 0.0045, 0.016 and 0.066 at q = 257 for Q = 1, 4, 16, against bounds of 0.0078, 0.019 and 0.066, consistent with Proposition 2(a), which shows that the leading term Q/q is tight. Small-field experiments support the analysis; they do not prove the bounds or their tightness. X. D ISCUSSION AND L IMITATIONS Limitations. Table X lists the limitations that Section VIII removes and those that remain. Private channels for issuance. Information-theoretic security of ΠDKI and ΠTN needs private channels. They can be

PREPRINT

22

realized in three ways: (i) one-time pads from QKD links, as already deployed in quantum-secured ledger testbeds [55], consumed offline at the rate given by (3) or (4); (ii) predistributed pad material, e.g., by courier or HSM bootstrapping; (iii) post-quantum TLS with forward secrecy as a pragmatic compromise. With option (iii), signatures produced in an epoch are information-theoretically unforgeable against anyone who has not broken that epoch’s issuance channels by then. An attacker who records issuance traffic and later breaks the key exchange could learn old keys and forge signatures for old epochs. Evidence that must remain valid indefinitely should therefore be anchored in later certificates, which in turn relies on collision resistance and on an authenticated checkpoint (Section VIII-E). Options (i) and (ii) avoid the issue entirely, which is the sense of “everlasting” security in [86]. Signing and verification never need confidential channels. Threshold trust. The committee acts as a distributed authority: t + 1 members who pool their shares of an epoch can forge for that epoch. Within an epoch this is the BFT assumption t < n/3. Proactive refresh and erasure (Section VIII-E) are designed so that it suffices that no t + 1 members are corrupted within the same epoch, so that members who leave cannot later pool erased shares; we prove each refresh step (Lemma 5) but not security against a mobile adversary, and erasure cannot remove copies that corrupted members kept. This is the trust model of threshold-signature-based ledgers [37], [38], and it is strictly weaker than trusting one authority. A malicious threshold of validators may refuse to issue new verifier credentials or selectively admit verifiers, but such behavior constitutes a denial of service at the governance layer rather than a forgery attack against SILMARILS-MV authentications. Liveness. ΠDKI and ΠTN have guaranteed output for t < n/3 in synchronous issuance rounds. Certificate release inherits the liveness of the consensus protocol, and combining is robust also under asynchrony (Theorem 4(iii)). Asynchronous issuance and variants for t < n/2 with statistical security [34] are outside our scope. Relation to threshold signatures. Section VIII-B and Table V compare TN with BLS and lattice threshold signatures. Relation to SILMARILS. SILMARILS-MV complements [36]. The two-party mode of SILMARILS remains the right tool when deniability is wanted, such as private user– validator sessions. SILMARILS-MV is the right tool when evidence is wanted. Its secret reconstruction weights ci are precisely what turns SILMARILS’s publicly reconstructed, simulatable algebraic core into a transferable, non-repudiable signature. XI. C ONCLUSION We introduced SILMARILS-MV, a multi-verifier unconditionally secure signature in which verifiers hold secret linear functionals derived from virtual anchors that nobody knows. The scheme is strongly unforgeable, non-repudiable and transferable without bound, with a bound of Q/q+1/(q−1) against unbounded adversaries whose leading term is tight. It admits linear aggregation, and its keys are issued by the validator

committee itself with perfect security. Letting the committee itself sign, through threshold notarization, makes certificates constant-size and per-validator issuance independent of the committee size. Together with arbiter-verified keys for clients, retroactive enrollment and robust redistribution, this brings information-theoretic authentication to committees of 1000 validators at an estimated 71 KiB per validator per block in the normal case, 22× below ML-DSA-44 within the admittedverifier setting considered by SILMARILS-MV. Open directions include: a full treatment of the linearcommunication variant of Remark 11 and of asynchronous issuance; a malicious-secure implementation of issuance integrated with a production BFT engine; packed secret sharing to reduce client key delivery; lower bounds on key and signature length for multi-verifier USS with aggregation; integration with QKD networks for fully everlasting deployments; a proof of security against mobile adversaries across refreshes; and a MAC-based consensus engine integrated with TN, with Byzantine safety and liveness proved and tested in the deployed configuration. R EFERENCES [1] M. Castro and B. Liskov, “Practical Byzantine fault tolerance and proactive recovery,” ACM Trans. Computer Systems, vol. 20, no. 4, pp. 398–461, 2002. [2] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus with linearity and responsiveness,” in Proc. ACM PODC, 2019, pp. 347–356. [3] M. M. Jalalzai, J. Niu, C. Feng, and F. Gai, “Fast-HotStuff: A fast and robust BFT protocol for blockchains,” IEEE Trans. Dependable Secure Comput., vol. 21, no. 4, pp. 2478–2493, 2024. [4] E. Buchman, J. Kwon, and Z. Milosevic, “The latest gossip on BFT consensus,” arXiv:1807.04938, 2018. [5] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis et al., “Hyperledger Fabric: A distributed operating system for permissioned blockchains,” in Proc. EuroSys, 2018, pp. 30:1–30:15. [6] P. Sheng, G. Wang, K. Nayak, S. Kannan, and P. Viswanath, “BFT protocol forensics,” in Proc. ACM CCS, 2021, pp. 1722–1743. [7] P. Civit, S. Gilbert, and V. Gramoli, “Polygraph: Accountable Byzantine agreement,” in Proc. IEEE ICDCS, 2021, pp. 403–413. [8] V. Buterin and V. Griffith, “Casper the friendly finality gadget,” arXiv:1710.09437, 2017. [9] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, 1997. [10] D. Aggarwal, G. Brennen, T. Lee, M. Santha, and M. Tomamichel, “Quantum attacks on Bitcoin, and how to protect against them,” Ledger, vol. 3, 2018. [11] National Institute of Standards and Technology, “Module-lattice-based digital signature standard,” NIST, FIPS 204, 2024. [12] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, “CRYSTALS-Dilithium: A lattice-based digital signature scheme,” IACR Trans. Cryptogr. Hardw. Embed. Syst., vol. 2018, no. 1, pp. 238–268, 2018. [13] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “Falcon: FastFourier lattice-based compact signatures over NTRU,” NIST PQC Round 3 Submission, 2020. [14] National Institute of Standards and Technology, “Stateless hash-based digital signature standard,” NIST, FIPS 205, 2024. [15] D. J. Bernstein, A. Hülsing, S. Kölbl, R. Niederhagen, J. Rijneveld, and P. Schwabe, “The SPHINCS+ signature framework,” in Proc. ACM CCS, 2019, pp. 2129–2146. [16] T. M. Fernandez-Carames and P. Fraga-Lamas, “Towards post-quantum blockchain: A review on blockchain cryptography resistant to quantum computing attacks,” IEEE Access, vol. 8, pp. 21 091–21 116, 2020. [17] A. Holcomb, G. Pereira, B. Das, and M. Mosca, “PQFabric: A permissioned blockchain secure from both classical and quantum attacks,” in Proc. IEEE ICBC, 2021, pp. 1–9.

PREPRINT

[18] T. Zhaolu, Z. Wan, and H. Wang, “Post-quantum rollup: Falcon signature aggregation based on SNARG with enhanced gates,” IEEE Trans. Inf. Forensics Security, vol. 20, pp. 2899–2914, 2025. [19] M. Mosca, “Cybersecurity in an era with quantum computers: Will we be ready?” IEEE Security & Privacy, vol. 16, no. 5, pp. 38–41, 2018. [20] D. Chaum and S. Roijakkers, “Unconditionally-secure digital signatures,” in Advances in Cryptology – CRYPTO ’90, ser. LNCS, vol. 537. Springer, 1991, pp. 206–214. [21] G. Hanaoka, J. Shikata, Y. Zheng, and H. Imai, “Unconditionally secure digital signature schemes admitting transferability,” in Advances in Cryptology – ASIACRYPT 2000, ser. LNCS, vol. 1976. Springer, 2000, pp. 130–142. [22] J. Shikata, G. Hanaoka, Y. Zheng, and H. Imai, “Security notions for unconditionally secure signature schemes,” in Advances in Cryptology – EUROCRYPT 2002, ser. LNCS, vol. 2332. Springer, 2002, pp. 434– 449. [23] C. M. Swanson and D. R. Stinson, “Unconditionally secure signature schemes revisited,” Journal of Mathematical Cryptology, vol. 10, no. 1, pp. 35–67, 2016. [24] G. Hanaoka, J. Shikata, Y. Zheng, and H. Imai, “Efficient and unconditionally secure digital signatures and a security analysis of a multireceiver authentication code,” in Public Key Cryptography (PKC 2002), ser. LNCS, vol. 2274. Springer, 2002, pp. 64–79. [25] R. Amiri, A. Abidin, P. Wallden, and E. Andersson, “Efficient unconditionally secure signatures using universal hashing,” in Applied Cryptography and Network Security (ACNS 2018), ser. LNCS, vol. 10892. Springer, 2018, pp. 143–162. [26] P. Wallden, V. Dunjko, A. Kent, and E. Andersson, “Quantum digital signatures with quantum-key-distribution components,” Physical Review A, vol. 91, p. 042304, 2015. [27] H.-L. Yin, Y. Fu, C.-L. Li, C.-X. Weng, B.-H. Li, J. Gu, Y.-S. Lu, S. Huang, and Z.-B. Chen, “Experimental quantum secure network with digital signatures and encryption,” National Science Review, vol. 10, no. 4, p. nwac228, 2023. [28] B.-H. Li, Y.-M. Xie, X.-Y. Cao, C.-L. Li, Y. Fu, H.-L. Yin, and Z.-B. Chen, “One-time universal hashing quantum digital signatures without perfect keys,” Physical Review Applied, vol. 20, p. 044011, 2023. [29] E. O. Kiktenko, A. S. Zelenetsky, and A. K. Fedorov, “Practical quantum multiparty signatures using quantum-key-distribution networks,” Physical Review A, vol. 105, p. 012408, 2022. [30] Y. Pelet, I. V. Puthoor, N. Venkatachalam, S. Wengerowsky, M. Lončarić et al., “Unconditionally secure digital signatures implemented in an eight-user quantum network,” New Journal of Physics, vol. 24, p. 093038, 2022. [31] B. Pfitzmann and M. Waidner, “Unconditional Byzantine agreement for any number of faulty processors,” in STACS 92, ser. LNCS, vol. 577. Springer, 1992, pp. 337–350. [32] M. Fitzi, S. Wolf, and J. Wullschleger, “Pseudo-signatures, broadcast, and multi-party computation from correlated randomness,” in Advances in Cryptology – CRYPTO 2004, ser. LNCS, vol. 3152. Springer, 2004, pp. 562–578. [33] V. Narayanan, V. M. Prabhakaran, N. Sangwan, and S. Watanabe, “Complete characterization of broadcast and pseudo-signatures from correlations,” in Advances in Cryptology – EUROCRYPT 2023, ser. LNCS. Springer, 2023, pp. 563–593. [34] T. Rabin and M. Ben-Or, “Verifiable secret sharing and multiparty protocols with honest majority,” in Proc. 21st ACM STOC, 1989, pp. 73–85. [35] R. Cramer, I. B. Damgård, and J. B. Nielsen, Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. [36] H. Khodaiemehr, K. Bagheri, C. Feng, and D. Porechna, “SILMARILS: A unified algebraic framework for designated-verifier and three-party information-theoretic signatures,” arXiv:2605.03230 [cs.CR], 2026. [37] C. Cachin, K. Kursawe, and V. Shoup, “Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography,” J. Cryptology, vol. 18, no. 3, pp. 219–246, 2005. [38] G. G. Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D.-A. Seredinschi, O. Tamir, and A. Tomescu, “SBFT: A scalable and decentralized trust infrastructure,” in Proc. 49th IEEE/IFIP Int. Conf. Dependable Syst. Netw. (DSN), 2019, pp. 568–580. [39] R. del Pino, S. Katsumata, M. Maller, F. Mouhartem, T. Prest, and M.-J. Saarinen, “Threshold Raccoon: Practical threshold signatures from standard lattice assumptions,” in Advances in Cryptology – EUROCRYPT 2024, ser. LNCS, 2024, pp. 219–248. [40] C. Boschini, D. Kaviani, R. W. F. Lai, G. Malavolta, A. Takahashi, and M. Tibouchi, “Ringtail: Practical two-round threshold signatures from

23

learning with errors,” in Proc. IEEE Symp. Security Privacy (SP), 2025, pp. 149–164. [41] Q. Kniep, J. Sliwinski, and R. Wattenhofer, “Byzantine faulttolerant post-quantum distributed quorum signatures,” arXiv preprint arXiv:2607.17700, 2026. [42] M. N. Wegman and J. L. Carter, “New hash functions and their use in authentication and set equality,” Journal of Computer and System Sciences, vol. 22, no. 3, pp. 265–279, 1981. [43] D. R. Stinson, “Universal hashing and authentication codes,” Designs, Codes and Cryptography, vol. 4, no. 3, pp. 369–380, 1994. [44] G. J. Simmons, “A Cartesian product construction for unconditionally secure authentication codes that permit arbitration,” Journal of Cryptology, vol. 2, no. 2, pp. 77–104, 1990. [45] Y. Desmedt and M. Yung, “Arbitrated unconditionally secure authentication can be unconditionally protected against arbiter’s attacks,” in Advances in Cryptology – CRYPTO ’90, ser. LNCS, vol. 537. Springer, 1991, pp. 177–188. [46] Y. Desmedt, Y. Frankel, and M. Yung, “Multi-receiver/multi-sender network security: Efficient authenticated multicast/feedback,” in Proc. IEEE INFOCOM, 1992, pp. 2045–2054. [47] R. Safavi-Naini and H. Wang, “Multireceiver authentication codes: Models, bounds, constructions, and extensions,” Information and Computation, vol. 151, no. 1–2, pp. 148–172, 1999. [48] J. Shikata, “Construction methodology of unconditionally secure signature schemes,” in Information Theoretic Security, Y. Desmedt, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 113–114. [49] T. Seito, Y. Hara, J. Shikata, and T. Matsumoto, “Unconditionally secure group signatures,” IEICE Trans. Fundamentals, vol. E92-A, no. 8, pp. 2067–2085, 2009. [50] R. Amiri, A. Abidin, P. Wallden, and E. Andersson, “Unconditionally secure signatures,” Cryptology ePrint Archive, Paper 2016/739, 2016. [51] D. Gottesman and I. Chuang, “Quantum digital signatures,” arXiv:quantph/0105032, 2001. [52] V. Dunjko, P. Wallden, and E. Andersson, “Quantum digital signatures without quantum memory,” Physical Review Letters, vol. 112, p. 040502, 2014. [53] R. Amiri, P. Wallden, A. Kent, and E. Andersson, “Secure quantum signatures using insecure quantum channels,” Physical Review A, vol. 93, p. 032325, 2016. [54] J. M. Arrazola, P. Wallden, and E. Andersson, “Multiparty quantum signature schemes,” Quantum Information & Computation, vol. 16, no. 5–6, pp. 435–464, 2016. [55] E. O. Kiktenko, N. O. Pozhar, M. N. Anufriev, A. S. Trushechkin, R. R. Yunusov et al., “Quantum-secured blockchain,” Quantum Science and Technology, vol. 3, no. 3, p. 035004, 2018. [56] X. Sun, M. Sopek, Q. Wang, and P. Kulicki, “Towards quantum-secured permissioned blockchain: Signature, consensus, and logic,” Entropy, vol. 21, no. 9, p. 887, 2019. [57] Q. Li, J. Wu, J. Quan, J. Shi, and S. Zhang, “Efficient quantum blockchain with a consensus mechanism QDPoS,” IEEE Trans. Inf. Forensics Security, vol. 17, pp. 3264–3276, 2022. [58] B. Pfitzmann and M. Waidner, “Information-theoretic pseudosignatures and Byzantine agreement for t ≥ n/3,” IBM Research, Tech. Rep. RZ 2882, 1996. [59] M. Fitzi, N. Gisin, U. Maurer, and O. von Rotz, “Unconditional Byzantine agreement and multi-party computation secure against dishonest minorities from scratch,” in Advances in Cryptology – EUROCRYPT 2002, ser. LNCS, vol. 2332. Springer, 2002, pp. 482–501. [60] H. Tyagi and S. Watanabe, Information-Theoretic Cryptography. Cambridge University Press, 2023, chapter 18: Broadcast, Byzantine Agreement, and Digital Signature. [61] M. Jakobsson, K. Sako, and R. Impagliazzo, “Designated verifier proofs and their applications,” in Advances in Cryptology – EUROCRYPT ’96, ser. LNCS, vol. 1070. Springer, 1996, pp. 143–154. [62] R. Steinfeld, L. Bull, H. Wang, and J. Pieprzyk, “Universal designatedverifier signatures,” in Advances in Cryptology – ASIACRYPT 2003, ser. LNCS, vol. 2894. Springer, 2003, pp. 523–542. [63] Y. Zhang, W. Susilo, and F. Guo, “Lattice-based strong designated verifier signature with non-delegatability,” Computer Standards & Interfaces, vol. 92, p. 103904, 2025. [64] D. A. Cooper, D. C. Apon, Q. H. Dang, M. S. Davidson, M. J. Dworkin, and C. A. Miller, “Recommendation for stateful hash-based signature schemes,” NIST, Special Publication 800-208, 2020. [65] D. Boneh, M. Drijvers, and G. Neven, “Compact multi-signatures for smaller blockchains,” in Advances in Cryptology – ASIACRYPT 2018, ser. LNCS, vol. 11273. Springer, 2018, pp. 435–464.

PREPRINT

24

[66] Y. Xiao, P. Zhang, and Y. Liu, “Secure and efficient multi-signature schemes for Fabric: An enterprise blockchain platform,” IEEE Trans. Inf. Forensics Security, vol. 16, pp. 1782–1794, 2021. [67] M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proc. 20th ACM STOC, 1988, pp. 1–10. [68] G. Asharov and Y. Lindell, “A full proof of the BGW protocol for perfectly secure multiparty computation,” Journal of Cryptology, vol. 30, no. 1, pp. 58–151, 2017. [69] D. Chaum, C. Crépeau, and I. Damgård, “Multiparty unconditionally secure protocols,” in Proc. 20th ACM STOC, 1988, pp. 11–19. [70] I. Damgård and J. B. Nielsen, “Scalable and unconditionally secure multiparty computation,” in Advances in Cryptology – CRYPTO 2007, ser. LNCS, vol. 4622. Springer, 2007, pp. 572–590. [71] Z. Beerliová-Trubı́niová and M. Hirt, “Perfectly-secure MPC with linear communication complexity,” in Theory of Cryptography (TCC 2008), ser. LNCS, vol. 4948. Springer, 2008, pp. 213–230. [72] V. Goyal, H. Li, R. Ostrovsky, A. Polychroniadou, and Y. Song, “ATLAS: Efficient and scalable MPC in the honest majority setting,” in Advances in Cryptology – CRYPTO 2021, ser. LNCS, vol. 12826. Springer, 2021, pp. 244–274. [73] D. Escudero, V. Goyal, A. Polychroniadou, and Y. Song, “TurboPack: Honest majority MPC with constant online communication,” in Proc. ACM CCS, 2022, pp. 951–964. [74] M. Franklin and M. Yung, “Communication complexity of secure computation,” in Proc. 24th ACM STOC, 1992, pp. 699–710. [75] E. Kushilevitz, Y. Lindell, and T. Rabin, “Information-theoretically secure protocols and security under composition,” SIAM Journal on Computing, vol. 39, no. 5, pp. 2090–2112, 2010. [76] R. Canetti, “Security and composition of multiparty cryptographic protocols,” Journal of Cryptology, vol. 13, no. 1, pp. 143–202, 2000. [77] M. Ben-Or, R. Canetti, and O. Goldreich, “Asynchronous secure computation,” in Proc. 25th Annu. ACM Symp. Theory Comput. (STOC), 1993, pp. 52–61. [78] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung, “Proactive secret sharing or: How to cope with perpetual leakage,” in Advances in Cryptology – CRYPTO’95, ser. LNCS, vol. 963, 1995, pp. 339–352. [79] T. M. Wong, C. Wang, and J. M. Wing, “Verifiable secret redistribution for archive systems,” in Proc. 1st Int. IEEE Security in Storage Workshop, 2002. [80] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe, and B.-Y. Yang, “Highspeed high-security signatures,” Journal of Cryptographic Engineering, vol. 2, no. 2, pp. 77–89, 2012. [81] M. Pease, R. Shostak, and L. Lamport, “Reaching agreement in the presence of faults,” Journal of the ACM, vol. 27, no. 2, pp. 228–234, 1980. [82] G. Brassard, P. Høyer, and A. Tapp, “Quantum cryptanalysis of hash and claw-free functions,” in LATIN’98, ser. LNCS, vol. 1380. Springer, 1998, pp. 163–169. [83] A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979. [84] L. R. Welch and E. R. Berlekamp, “Error correction for algebraic block codes,” in U.S. Patent 4,633,470, 1986. [85] K. Bagheri, H. Khodaiemehr, and C. Feng, “SILMARILS-MV: Code, simulators and data,” https://github.com/hassankhodaiemehr/ silmarils-mv, 2026. [86] D. Unruh, “Everlasting multi-party computation,” in Advances in Cryptology – CRYPTO 2013, ser. LNCS, vol. 8043. Springer, 2013, pp. 380–397.

A PPENDIX A R EPRODUCIBILITY The artifact is publicly available at https://github.com/ hassankhodaiemehr/silmarils-mv [85]. The files below are in its silmarils-mv/ directory (subdirectories code/, hsbench/ and results/). It contains: fe25519.h and silmv_bench.c: the C core and its benchmark; silmv.py: the reference implementation; dki_va.py and dki_sim.py: the issuance simulators, with and without anchors; attacks.py, attacks_va.py and attacks_va_tight.py: the Monte-Carlo validation; batch_check.py: the exhaustive check of batch

arbitration (Lemma 4); hsbench/run_baselines.sh and make_baselines.py: the same-host AVX2 baselines, converted into results/baselines.json; ledger_model.py: the ledger model, which generates every table and figure from the raw measurements. tn_bench.c: threshold-notarization share, combine, fastdecoder and certificate-verification benchmark; tn_sim.py: end-to-end simulation of ΠTN with Byzantine members, retroactive enrollment, robust redistribution, batch arbitration of arbiter-verified keys, and the TN forgery experiment (TNQ=257); scale_model.py: the scalability model up to n = 1000 (Fig. 6 and Table VIII). hsbench/: the Rust HotStuff prototype of Section IX-E, with run_matrix.py (experiment matrix) and summarize.py (medians and tables).

Related documents

• SILMARILS-MV: Information-Theoretically Secure Multi-Verifier Signatures with Dealer-Free Key Issuance and Linear Aggregation for Permissioned Blockchains#1446859
• The Immutability Conundrum: Reconciling GDPR Data Subject Rights with Blockchain Architecture in a Borderless and Decentralized Digital Economy#1177639
• CBOR Object Signing and Encryption (COSE): Hash Algorithms#502494
• SoK: Cryptographic Key Recovery for Cryptoasset Custody and Financial Technologies#440295
• The doctrine of signatures#1193592