arXiv CSopen access

SILMARILS: Information-Theoretic and Quantum-Secure Designated-Verifier Signatures

SILMARILS: Information-Theoretic and Quantum-Secure Designated-Verifier Signatures Hassan Khodaiemehr1 , Khadijeh Bagheri1 , Chen Feng1 , and Dariia Porechna2

arXiv:2605.03230v1 [cs.CR] 4 May 2026

1

Faculty of Applied Science, School of Engineering, The University of British Columbia (UBC) Okanagan Campus, Kelowna, BC, Canada {hassan.khodaiemehr,khadijeh.bagheri,chen.feng}@ubc.ca 2 EternaX Labs [email protected]

Abstract. SILMARILS follows the principle of Secure Informationtheory-Leveraged Mechanism for Authentication and Receipt-Integrated Lightweight Signatures. It is built from a minimal algebraic core over Fp using true randomness and perfect 2-out-of-2 Shamir secret sharing. The framework supports both two-party and three-party modes. In the two-party setting, SILMARILS realizes a transferable designated-verifier (TDV) signature scheme. The designated verifier can simulate accepting transcripts indistinguishable from real ones, achieving Jakobsson–Sako– Impagliazzo DV security. The verifier may publish a receipt r enabling public verification, yet even with r, no external party can tell whether a transcript was signed or simulated. As DV signatures permit simulation, standard EUF-CMA cannot hold for the designated verifier; instead, we prove EUF-CMA¬DV security for all non-designated verifiers in both the random oracle model (ROM) and quantum random oracle model (QROM). In the three-party mode, adopting the broadcast model of Fitzi et al. [26, 27, 45], we obtain a statistically secure signature protocol with simulation-based security and error 1/p. We analyze security in the Pure IT model, the IT+ROM, and the QROM, extending the Fitzi et al. framework to quantum adversaries with classical I/O. Correctness, secrecy, transferability, and unforgeability for non-designated parties remain equivalent to simulation-based security. Thanks to its simple algebraic structure, SILMARILS achieves substantially smaller keys and signatures than standardized post-quantum schemes such as Dilithium, Falcon, and SPHINCS+ , while providing post-quantum security in a TDV setting well suited to blockchain applications.

Keywords: IT security · Digital signatures · MPC · QROM · Quantum-safe

1

Introduction

Digital signatures underpin authenticity and integrity in modern distributed systems. A broad spectrum of constructions exists, ranging from number-theoretic schemes such as RSA [33], DSS [1], ECDSA [32], and Schnorr [9], to postquantum alternatives including hash-based signatures [6, 37, 40], code-based

2

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

schemes [14, 39], lattice-based designs [19, 28], multivariate approaches [7, 8], and isogeny-based constructions [2]. Information-theoretic (IT) signatures offer unconditional security [3, 12, 29], but existing schemes often lack full simulationbased guarantees or incur significant inefficiencies. The study of digital signatures is deeply intertwined with the theory of broadcast and Byzantine agreement [45]. The foundational works of Pease, Shostak, and Lamport [36,42] introduced the broadcast and Byzantine agreement problems and established both feasibility and impossibility results under various adversarial models. The attack-coupling argument of Fischer, Lynch, and Merritt [22] has since become a standard tool for proving impossibility results in distributed computing [13, 24]. A comprehensive treatment of distributed algorithms can be found in [38]. Digital signatures play a crucial role in enabling authenticated broadcast. Dolev and Strong [18] showed that broadcast is possible for any number of dishonest parties if signatures are available along arbitrary transfer paths. Conversely, signatures can be constructed from broadcast via informationchecking protocols [15, 16, 45]. The minimal requirements for broadcast were further studied in [24]. Randomized and variable-round protocols were introduced to overcome deterministic lower bounds [5, 43], with optimal expected-round protocols developed in [21, 34]. In asynchronous networks, impossibility results such as [23] motivated randomized protocols for consensus [4]. 1.1

Motivation and Contribution

Although IT digital signatures are known to be possible, existing constructions do not provide efficient, reusable, and simulation-secure signatures in the multi-party, multi-use setting. The central challenge is achieving unconditional security while retaining efficiency, scalability, and practical deployability. Our work is motivated by the intersection of several research directions: IT security, secure multiparty computation (MPC), long-term quantum resilience, and the authentication requirements of modern distributed systems such as blockchains. In particular, SILMARILS addresses two complementary settings: a two-party TDV mode that yields efficient EUF-CMA¬DV signatures in the ROM and QROM, and a three-party broadcast-model construction that achieves full simulation-based security in the sense of Fitzi et al. notion. IT signatures are appealing in MPC settings, where using computational signatures would break end-to-end IT security. In practice, these guarantees are instantiated via hash functions, either as injective encodings in the Pure IT model or as random oracles in the IT+ROM and QROM settings, which requires analyzing the algebraic core in the ROM/QROM. Thus, unlike postquantum signatures that rely on hardness assumptions (e.g., LWE or hash-based security), our two-party construction achieves computational security in the ROM/QROM using IT tools, while the three-party construction achieves IT security in the Pure IT model (replacing hashes with IT authentication codes). In the three-party setting with at most one dishonest party, the classical lower bound shows that any ε-secure digital signature from scratch which uses only noiseless channels and no setup, must satisfy ε ≥ 1/3 [45, Corollary 18.7]. The

Title Suppressed Due to Excessive Length

3

Table 1: Comparison of major digital signature families. Family

Assumption

Key Sizes

Signature Sizes Quantum Security

Classical (RSA, ECDSA) Factoring, DL, ECDL Small–Medium Small Hash-Based (SPHINCS+ ) Hash functions Small Large Code-Based (CFS) Decoding random codes Large Medium Lattice-Based (Dilithium, Falcon) M-SIS/M-LWE, SIS over NTRU Lattices Medium Small–Medium Multivariate (UOV) MQ hardness Large Small Isogeny-Based (SQISign) Isogeny problems Small Small IT-Based (SILMARILS) Signer–Verifier shared randomness (TDV) Very Small Very small

No Yes Yes Yes Yes Yes (emerging) Yes

ε = 1/p construction of [45, Theorem 18.18] avoids this bound only by working in a richer setup with authenticated channels, pre-shared keys, or correlated randomness. This motivates our move to the TDV framework. Although TDV signatures superficially resemble MACs due to shared randomness, they are fundamentally different: MACs are symmetric, two-party, and non-transferable, whereas TDV schemes are publicly readable and verifiable only by a designated verifier who may choose to reveal validity evidences. In our two-party setting, the shared randomness is ephemeral rather than a long-term secret key, and is used solely to enable controlled transferability of signatures rather than to authenticate messages. This distinction ensures that our model and impossibility results remain fully consistent with the broader landscape of three-party signature constructions. Hence, our goal is to develop an information-theoretic signature framework that is efficient, reusable, and compatible with both classical and quantum settings. SILMARILS achieves this by combining a minimal algebraic core over Fp with perfect 2-out-of-2 Shamir secret sharing. The framework supports two complementary modes. Two-party mode: We obtain a transferable designated-verifier (TDV) signature scheme with computational designated-verifier simulatability in the sense of Jakobsson–Sako–Impagliazzo and EUF-CMA¬DV security for all non-designated verifiers in both the ROM and QROM. This mode provides lightweight authentication suitable for user–validator interactions and other two-party settings where public verifiability is not required. Three-party mode: Adopting the broadcast model of Fitzi et al., we construct a statistically secure signature protocol achieving full simulation-based security with error 1/p. Because practical instantiations rely on hash functions, we analyze security in the Pure IT, IT+ROM, and QROM models and extend the Fitzi simulation framework to a quantum setting with classical I/O. These two modes together capture the full range of practical and theoretical requirements: efficient two-party authentication, and a three-party informationchecking (IC) structure supporting correctness, unforgeability, transferability, and secrecy. Table 1 summarizes the comparison of SILMARILS and other signature families. 1.2

Applications to PQ Blockchain Architectures

The properties of SILMARILS align naturally with the needs of blockchain systems. Constant-time verification, compact receipts, and IT security allow PQ-safe architectures without the heavy onchain footprint of standardized PQ signatures. We developed a PQ-safe blockchain protocol where SILMARILS replaces both

4

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

validator signatures during consensus and user transaction message authentication, demonstrating that IT techniques can deliver practical, high-performance authentication in both classical and post-quantum distributed systems. The key achievements of our architecture include: 1) The TLS-derived per-pair secrets eliminate the need for large user-facing PQ signatures in high-frequency interactions, while designated-verifier receipts preserve public auditability. 2) Validator-tovalidator authentication becomes cheaper, consensus protocols simplify, and randomness generation can be implemented via lightweight commit–reveal mechanisms. The concrete ledger integration is outside the scope of this paper since we intend a companion publication. The rest of this paper is organized as follows. Section 2 presents the necessary preliminaries, including notation, ideal functionalities, and the security framework used throughout the paper. Section 3 introduces the quantum-information tools used in our analysis. Section 4 describes our digital signature scheme SILMARILS in its two-party and three-party modes, detailing the key generation, signing, and verification procedures. Section 5 and Section 6 provide a rigorous security analysis of the two-party mode of SILMARILS under both the Jakobsson–Sako– Impagliazzo designated-verifier framework and the EUF-CMA¬DV unforgeability notion, while Section 7 analyzes the security of the three-party mode. Section 8 evaluates the efficiency of our scheme. Finally, Section 9 concludes the paper.

2

Preliminaries

Let p be a prime and let Fp denote the finite field of order p. We write F∗p = Fp \{0} $

for its multiplicative group. Sampling uniformly from F∗p is denoted by x ← − F∗p . For a random variable X over a finite set X , we write PX for its distribution. For two distributions P and Q over X , the total variation distance is dvar (P, Q) =

1X |P (x) − Q(x)| = max |P (A) − Q(A)|. A⊆X 2

(1)

x∈X

A function µ : N → [0, 1] is negligible if for every polynomial q(·) there exists k0 ∈ N such that µ(k) ≤ 1/q(k) for all k ≥ k0 . We use boldface to denote vectors and tuples when needed, and we use Viewi to denote the view of party Pi in a protocol execution. We use the perfect 2-out-of-2 Shamir secret sharing scheme SSS2,2 over Fp [44]. Given a secret s ∈ Fp , the dealer chooses a random slope $

a← − Fp and defines the degree-1 polynomial f (x) = s + ax. Let w0 , w1 ∈ Fp be fixed, distinct, public interpolation points or weights. The shares are s0 = f (w0 ) and s1 = f (w1 ). Now, given the shares (s0 , s1 ) = SSS2,2 (s), and public weights w0 , w1 , reconstruction function SSS−1 2,2 is defined by Lagrange interpolation: s = SSS−1 2,2 (s0 , s1 ) =

w0 s1 − w1 s0 . w0 − w1

Each individual share is uniformly distributed over Fp and independent of the secret s, so SSS2,2 is a perfect secret-sharing scheme [44]. Since its security is

Title Suppressed Due to Excessive Length

5

purely information-theoretic, Shamir’s Secret Sharing enjoys a natural form of quantum resilience: its guarantees do not rely on computational assumptions that could be broken by quantum algorithms, and remain valid even in the presence of quantum adversaries [35]. 2.1

Ideal Functionality for Three-Party IT-Based Digital Signatures

We analyze our construction in the standard synchronous MPC model [45], the minimal setting supporting IT-based authentication [30]. The system consists of three parties: the signer P1 , the holder P2 , and the verifier P3 . Parties communicate over pairwise private and authenticated channels and have access to authenticated broadcast. Pairwise channels ensure confidentiality and integrity of point-to-point messages, while broadcast prevents equivocation. This matches the communication assumptions of the three-party SILMARILS protocol and the IC-based framework of [45, Protocol 18.7]. We consider a static, active adversary corrupting at most one party. Upon corruption, the adversary obtains full control of that party and may arbitrarily deviate from the protocol. The one-corruption threshold is the minimal requirement for IT-based authentication in the three-party setting [45]. Definition 1. For a protocol Π and adversary A corrupting party Pi , the view ViewΠ i consists of: 1) the input of Pi , 2) the private randomness of Pi , 3) all messages received by Pi , 4) all oracle answers observed by Pi . A three-party digital-signature scheme with transfer involves parties P1 (signer), P2 (holder), and P3 (verifier), communicating over pairwise private authenticated channels and an authenticated broadcast primitive [45]. Let x1 = M be the input to the scheme, which is defined by five polynomial-time algorithms: – KeyGen(1k ): run by P1 , outputs (pk, sk). – Signsk (M ): run by P1 , outputs a signature σ to P2 . – Extract(M, σ): run by P2 in the signing phase, outputs z2 ∈ X ∪ {⊥}, where z2 is the authenticated value associated with (M, σ). – Transfer(z2 , σ): run by P2 , outputs (M ′ , σ ′ ) to P3 . – ExtractTransfer(M ′ , σ ′ ): run by P3 , outputs z3 ∈ X ∪ {⊥}, representing the verifier’s recovered authenticated value. We formalize security using the three-party ideal functionality fDS = (fDS1 , fDS2 ), originally introduced by Fitzi et al. [25–27, 45] and illustrated in Fig. 1. The functionality captures the minimal guarantees required from an IT-DS scheme with transfer. Signing Phase (fDS1 ): The signer P1 provides an input x1 ∈ X ∪ {⊥} to the functionality. The value x1 represents the authenticated value associated with the P1 x1

P2 fDS1

x1

P3 z2

fDS2

z3

z3 =

 z2

if z2 = x1 ,

⊥

else.

x1

Fig. 1: Ideal three-party digital-signature functionality.

6

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

message. The functionality forwards x1 to the holder P2 and stores it internally for use in the transfer phase. No other party receives information at this stage. Transfer Phase (fDS2 ): To transfer a signature, P2 submits a value z2 ∈ X to ( z2 , if z2 = x1 , the functionality and P3 receives z3 = fDS2 (x1 , z2 ) = ⊥, otherwise. The ideal functionality enforces the three core guarantees of IT-DS: – Correctness: honest executions always yield the authenticated value x1 . – Unforgeability: neither the holder nor the verifier can cause the functionality to output any value other than x1 . – Transferability: any honest verifier must accept a value previously authenticated by an honest signer and forwarded by an honest holder. 2.2

Real-World Security Definition and Supporting Notions

We formalize security using the standard real or ideal paradigm. Let fDS denote the three-party ideal functionality for digital signatures introduced by Fitzi et al. [45]. A real protocol Π is said to ε-securely implement fDS if every realworld attack can be simulated in the ideal world with at most ε statistical distinguishability. For any adversary A corrupting at most one party, there must exist a simulator S such that the adversary’s real-world view when interacting with Π is statistically close to its ideal-world view when interacting with   S real ideal and the ideal functionality fDS , i.e., dvar ViewA (Π), ViewA (S ◦ fDS ) ≤ ε. This definition captures the strongest form of information-theoretic security: the adversary must not be able to distinguish whether it is interacting with the real protocol or with the ideal functionality, except with probability ε. Characterization via Local Properties: Fitzi et al. [45] established a fundamental equivalence that reduces simulation-based security to four concrete properties of a protocol. Theorem 1 ( [45], Lemma 18.15). A three-party protocol Π is a 2ε-secure implementation of fDS with error ε against one active adversary if the following conditions hold for any attack by the dishonest party: – εcorr −correctness: with honest P1 and P2 , Pr(z2 = x1 ) ≥ 1 − εcorr , – εuf −unforgeability: with honest P1 and P3 , Pr(z3 ̸= x1 , z3 ̸= ⊥) ≤ εuf , – εtrans −transferability: with honest P2 and P3 , Pr(z2 ̸= z3 , z2 ̸= ⊥) ≤ εtrans , – εsec −secrecy: with honest P1 and P2 , ViewΠ 3 (x1 ) of P3 in the signing phase is almost independent of P1 ’s input x1 , which implies the existence of QViewΠ 3 such that dvar (PViewΠ , QViewΠ ) ≤ εsec , for every x1 , 3 (x1 ) 3 where ε = max{εcorr , εuf , εtrans , εsec }. Thus, to prove that a protocol securely realizes fDS , it suffices to establish these four properties. This modular approach greatly simplifies the security analysis in Section 7.

Title Suppressed Due to Excessive Length

3

7

Quantum Generalization of Theorem 1

We analyze our constructions under three models for the hash function H: the Pure IT model, where H : X → Fp is a deterministic encoding; the IT+ROM, where H : {0, 1}∗ → Fp is a classical random oracle; and the IT+QROM, where H is accessible to quantum adversaries. In this section we lift Theorem 1 (cf. [45, Lemma 18.15]) to the quantum setting. This extension is necessary because many classical ROM techniques fail in the QROM—e.g., classical rewinding, inspecting superposition queries, classical oracle programming, and the forking lemma [10, 46, 47, 50]. In contrast, the proof of Theorem 1 never interacts with the adversary algorithmically; it reasons only about the joint distributions of (X1 , Z2 , Z3 , View1 , View2 , View3 ), where X1 is the signer’s input, Z2 , Z3 are outputs, and each Viewi is the corresponding party’s view. The simulators are defined at the level of distributions (or, in the quantum case, density operators), not as black-box procedures that manipulate a quantum adversary. The proof uses only standard IT tools—triangle inequality, conditioning/averaging, and coupling (including maximal couplings)—all of which lift directly to the quantum setting by replacing variational distance with trace distance and interpreting views as quantum states. No rewinding, forking, or oracle programming is required [47,48]. 3.1

Quantum Preliminaries

We briefly recall the quantum-information concepts required for our analysis. All Hilbert spaces are finite-dimensional. For a Hilbert space H, we write D(H) for the set of density operators on H, i.e., positive semidefinite operators of trace 1. Trace of an Operator and Partial Trace: Let T be a linear operator acting on a Pfinite-dimensional Hilbert space H. The trace of T is defined as Tr[T ] := i ⟨i | T | i⟩, where { |i⟩ } is any orthonormal basis of H. This quantity is basis independent and equals the sum of the eigenvalues of T . Now, let HA and HB be Hilbert spaces describing subsystems A and B, and let ρAB be a density operator on the composite system HA ⊗ HB . The partial trace over B, denoted TrB , is X

TrB [ρAB ] := IA ⊗ ⟨j|B ρAB IA ⊗ |j⟩B ≡ ρA , (2) j

where {|j⟩B } is any orthonormal basis of HB . The resulting operator ρA := TrB [ρAB ] is the reduced state of subsystem A. The partial trace over A is X

TrA [ρAB ] := ⟨i|A ⊗ IB ρAB |i⟩A ⊗ IB ≡ ρB . (3) i

Trace Distance: For density operators ρ, σ ∈ D(H), the trace distance is ∆(ρ, σ) := √ 1 † 2 ∥ρ − σ∥1 , where ∥A∥1 = Tr A A denotes the trace norm. Trace distance is the quantum analogue of variational distance and satisfies the triangle inequality. Definition 2 (Bipartite States, [41]). A bipartite quantum state over registers A and B is a density operator ρAB = ρA ⊗ ρB ∈ D(HA ⊗ HB ).

8

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

Classical–Quantum States: A classical–quantum (cq) Pstate over a classical register X and a quantum register Q has the form ρXQ = x px |x⟩⟨x| ⊗ ρxQ , where {px } is a probability distribution and ρxQ are density operators. The trace distance between two cq-states decomposes as follows. P Decomposition, [48]). Let ρXQ = x px |x⟩⟨x|⊗ Lemma 1 (Trace-Distance P x ρxQ and σXQ = x px |x⟩⟨x| ⊗ σQ , be classical–quantum states P with the xsame classical marginal distribution {px }. Then ∆(ρXQ , σXQ ) ≤ x px ∆(ρxQ , σQ ). CPTP Maps: A linear map Φ : D(H) → D(H′ ) is completely positive and trace-preserving (CPTP) if Φ ⊗ IK is positive for every auxiliary space K and Tr(Φ(ρ)) = 1 for all ρ [11]. CPTP maps model all physically admissible quantum operations, including unitary evolution, measurement, discarding registers, and interaction with an environment. Lemma 2 (Contractivity of CPTP Maps, [48]).
For any CPTP map Φ and any density operators ρ, σ, we have ∆ Φ(ρ), Φ(σ) ≤ ∆(ρ, σ). Quantum Coupling: The following lemma is the quantum analogue of the classical coupling argument used to relate the probability of “bad” events in two distributions. Lemma 3 (Quantum Coupling Lemma, [49]). Let ρAB and σAB be bipartite states. If an event E has probability 0 under σAB , then Prρ [E] ≤ ∆(ρAB , σAB ). These tools suffice to lift the classical characterization of digital-signature security to the quantum setting. Every step in the quantum generalization of Theorem 1 consists only of applying CPTP maps (e.g., tracing out registers, simulating views), conditioning on classical events, and using the triangle inequality for trace distance. Since CPTP maps are contractive, all classical arguments that bound variational distance extend directly by replacing it with trace distance and interpreting views as quantum states. No rewinding, forking, or oracle programming is used, so none of the classical ROM techniques that fail in the QROM arise here. 3.2

Quantum Security of fDS

We consider a three-party digital signature functionality fDS = (fDS,1 , fDS,2 ), P1 , P2 and P3 as before. A protocol Π implementing fDS is an interactive protocol among P1 , P2 , P3 (and possibly an environment and a quantum adversary) with classical inputs and outputs but potentially quantum internal computation and access to a quantum random oracle. In our setting, each party Pi has a classical output Zi and a quantum view Viewi consisting of all quantum registers and classical transcripts observed during the protocol. The joint state of all registers in the real execution is denoted by ρx1 Z2 Z3 View1 View2 View3 , with lowercase symbols (e.g., x1 ) representing fixed inputs and uppercase symbols (e.g., Z2 , Z3 ) representing random variables produced during the execution. All CPTP maps are contractive with respect to trace distance, and the triangle inequality holds. We adopt a standard simulation-based definition in the quantum setting (see, e.g., [11]).

Title Suppressed Due to Excessive Length

9

Definition 3 (ε-Security in Quantum). A protocol Π is ε-securely implementing fDS against one active quantum adversary if, for each corrupted party, there exists a quantum polynomial-time simulator such that the real and ideal executions are ε-close in trace distance (as joint states of the environment and honest parties). We now restate the four properties in the quantum setting. All probabilities are taken over the randomness of the protocol, the adversary, and any oracles. Correctness: With honest P1 and P2 , Pr[Z2 ̸= x1 ] ≤ ε, for all x1 ∈ X . Unforgeability: With honest P1 and P3 , Pr[Z3 ∈ / {x1 , ⊥}] ≤ ε, for all x1 ∈ X . Transferability: If P2 and P3 are honest, then Pr[Z2 ̸= Z3 ∧ Z2 ̸= ⊥] ≤ ε. Secrecy: If P1 and P2 are honest, then the view of P3 in the signing phase is almost independent
of x1 and there exists a state σView3 such that for all x1 , ∆ ρView3 (x1 ) , σView3 ≤ ε. Theorem 2 (Quantum Security of Digital Signatures). Let Π be a threeparty protocol for fDS against quantum adversaries. If Π satisfies correctness, unforgeability, transferability, and secrecy with error at most ε, then it is an O(ε)-secure implementation of fDS ; conversely, any ε-secure implementation of fDS satisfies these four properties with error O(ε). The hidden constants arise from a constant number of triangle-inequality applications. Proof. (⇐) If the four properties hold, then Π is secure. Case 1: P1 and P2 honest. When P1 and P2 behave honestly, the only potentially corrupted party is P3 . The simulator for P3 must therefore reproduce the joint distribution of (X1 , Z2 , View3 ) as seen in the real protocol. By secrecy, the adversary controlling P3 learns essentially nothing about the signer’s input x1 . Formally, there exists a
fixed state σView3 (independent of x1 ) such that ∆ ρView3 (x1 ) , σView3 ≤ ε. Thus, in the ideal world the simulator may simply output σView3 as the view of P3 . Correctness ensures that the honest verifier P2 outputs the signer’s input except with small probability: Pr[ Z2 ̸= x1 ] ≤ ε. Hence, the real joint state of (x1 , Z2 ) is ε-close to the ideal joint state in which Z2 is deterministically equal to x1 . We now compare the full real state ρx1 Z2 View3 with the ideal state σx1 Z2 View3 , where the ideal state is defined by: Z2 = x1 , and View3 ∼ σView3 . Applying Lemma 1 to decompose the trace distance over the classical registers (x1 , Z2 ), and then using the triangle inequality, we obtain
∆(ρx1 Z2 View3 , σx1 Z2 View3 ) ≤ Pr[Z2 ̸= x1 ] + ∆ ρView3 (x1 ) , σView3 ≤ 2ε. | {z } | {z } ≤ε

≤ε

Thus, the simulator for P3 can reproduce the ideal joint state up to trace distance at most 2ε, and therefore achieves simulation error O(ε) in this case. Case 2: P1 and P3 honest. Here P1 and P3 behave honestly, while P2 may be corrupted. In the ideal world, the functionality guarantees that the output of P3 is always either the correct message x1 or the distinguished symbol ⊥ indicating rejection. Thus, the ideal joint distribution of (x1 , Z3 ) is supported on the set

10

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

{(x1 , x1 ), (x1 , ⊥)}. In the real protocol, an honest P3 should never accept an incorrect message. Unforgeability therefore ensures that Pr[ Z3 ∈ / {x1 , ⊥} ] ≤ ε. Equivalently, the real distribution of (x1 , Z3 ) is ε-close to the ideal distribution in which Z3 is always either x1 or ⊥. Lemma 3 states that whenever two classical– quantum states differ only in a classical register with error probability at most ε, there exists a joint coupling whose trace distance is at most ε. Applying this lemma to the pair of states ρx1 Z3 (real) and σx1 Z3 (ideal), we obtain ∆(ρx1 Z3 , σx1 Z3 ) ≤ ε. The corrupted party P2 obtains its view by applying some CPTP map to the registers (x1 , Z3 ). Formally, there exists a CPTP map Φ such that ρx1 Z3 View2 = Φ(ρx1 Z3 ),

and

σx1 Z3 View2 = Φ(σx1 Z3 ).

By Lemma 2, CPTP maps cannot increase trace distance. Therefore, ∆(ρx1 Z3 View2 , σx1 Z3 View2 ) ≤ ∆(ρx1 Z3 , σx1 Z3 ) ≤ ε. Thus, the simulator for the corrupted party P2 can reproduce the ideal joint state of (x1 , Z3 , View2 ) up to trace distance at most ε, achieving simulation error O(ε) in this case. Case 3: P2 and P3 honest. Here P2 and P3 behave honestly, while P1 may be corrupted. In the ideal functionality, whenever the verifier outputs a valid message Z2 ̸= ⊥, the transfer recipient must output the same message. Thus, in the ideal world the joint distribution of (Z2 , Z3 ) satisfies Z2 ̸= ⊥ =⇒ Z3 = Z2 . In the real protocol, transferability guarantees that an honest P3 cannot be convinced to output a message different from the one accepted by the honest P2 . Formally, Pr[ Z2 ̸= Z3 ∧ Z2 = ̸ ⊥ ] ≤ ε. Equivalently, the real joint distribution of (Z2 , Z3 ) is ε-close to the ideal distribution in which Z3 always equals Z2 whenever Z2 ̸= ⊥. Lemma 3 states that if two classical–quantum states differ only in a classical register with error probability at most ε, then there exists a coupling whose trace distance is at most ε. Applying this lemma to the real and ideal states of the pair (Z2 , Z3 ) yields ∆(ρZ2 Z3 , σZ2 Z3 ) ≤ ε. The corrupted party P1 obtains its view by applying some CPTP map to the registers (x1 , Z2 , Z3 ). Thus, there exists a CPTP map Φ such that ρx1 Z2 Z3 View1 = Φ(ρx1 Z2 Z3 )

and

σx1 Z2 Z3 View1 = Φ(σx1 Z2 Z3 ).

By Lemma 2, CPTP maps cannot increase trace distance. Therefore, ∆(ρx1 Z2 Z3 View1 , σx1 Z2 Z3 View1 ) ≤ ∆(ρZ2 Z3 , σZ2 Z3 ) ≤ ε. Hence, the simulator for the corrupted signer P1 can reproduce the ideal joint state up to trace distance at most ε, achieving simulation error O(ε) in this case. (⇒) If Π is secure, then the four properties hold. Correctness: Assume that P1 and P2 behave honestly. In the ideal world, the functionality fDS always delivers the signer’s input to the honest verifier; that is, the ideal output satisfies Z2 = x1 with probability 1. Security of Π means that for every environment, the real execution of the protocol is ε-indistinguishable from the ideal execution. In particular, the joint real and ideal distributions

Title Suppressed Due to Excessive Length

11

of (x1 , Z2 ) are within trace distance at most ε. Since the ideal distribution assigns zero probability to the event {Z2 ̸= x1 }, indistinguishability implies that the real execution can assign at
most ε probability to this event. Formally, ideal Prreal [ Z2 ̸= x1 ] ≤ ∆ ρreal , ρ ≤ ε. Thus, an honest verifier outputs the x1 Z2 x1 Z 2 correct message except with probability at most ε, establishing correctness. Unforgeability: Assume that P1 and P3 behave honestly. In the ideal world, the functionality fDS guarantees that an honest P3 can never be made to accept an incorrect message: its output is always either the true message x1 or the rejection symbol ⊥. Thus, the ideal distribution of Z3 is supported entirely on the set {x1 , ⊥}. Security of Π means that the real execution must be ε-indistinguishable from the ideal execution. In particular, the real and ideal distributions of the classical register Z3 must be within trace distance at most ε. Since the ideal distribution assigns zero probability to the event {Z3 ∈ / {x1 , ⊥}}, any deviation from this event in the real world must be bounded by the distinguishing advantage. Formally, by Lemma 3, whenever two classical–quantum states differ only on a classical register with error probability at most ε, there exists a coupling whose trace distance is at most ε. Applying this lemma
to the real and ideal states of Z3 ideal yields Prreal [ Z3 ∈ / {x1 , ⊥} ] ≤ ∆ ρreal ≤ ε. Thus, an honest P3 outputs Z3 , ρZ3 an invalid message with probability at most ε, establishing unforgeability. Transferability: Assume that P2 and P3 behave honestly. In the ideal world, the functionality fDS enforces perfect transferability and whenever the verifier accepts a message, i.e., whenever Z2 ̸= ⊥, the transfer recipient must output the same message. Formally, the ideal distribution satisfies Z2 ̸= ⊥ =⇒ Z3 = Z2 . Security of Π means that the real execution must be ε-indistinguishable from the ideal execution. Since the ideal distribution assigns zero probability to the event { Z2 ̸= Z3 ∧ Z2 = ̸ ⊥ }, the real execution can assign at most ε probability to this event. Indeed, if the real protocol caused an honest P3 to output a value different from the one accepted by the honest P2 with probability greater than ε, then an environment could distinguish the real and ideal executions with advantage exceeding ε, contradicting security. Thus, indistinguishability immediately yields Prreal [ Z2 ̸= Z3 ∧ Z2 ̸= ⊥ ] ≤ ε. This establishes transferability. Secrecy. Assume that P1 and P2 behave honestly. In this setting, the only potentially corrupted party is P3 . In the ideal world, the functionality fDS reveals no information about the signer’s input x1 to P3 . Consequently, the ideal view of P3 is a fixed state, independent of x1 . Let us denote this state by σView3 . Security of Π means that for every environment, the real execution is ε-indistinguishable from the ideal execution. In particular, the real and ideal distributions of the adversary’s view must be within trace distance at most ε. Since the ideal view does not depend on x1 , this indistinguishability condition implies that the real view of P3 —which may in principle depend on x1 —cannot vary with x1 by more than ε in trace distance. Formally, letting ρView3 (x1 ) denote
the real view of P3 when the signer’s input is x1 , we obtain ∆ ρView3 (x1 ) , σView3 ≤ ε. Thus, an honest P3 learns at most ε information about the signer’s input, establishing secrecy. This completes the proof. □

12

3.3

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

Implications for QROM Analysis

Theorem 2 shows that Theorem 1 is robust to the quantum setting: once we establish correctness, unforgeability, transferability, and secrecy against quantum adversaries in the QROM (with respect to classical inputs/outputs and possibly quantum internal computation), we may soundly conclude simulation-based security of our implementation of fDS . The known issues that invalidate some classical ROM reductions in the QROM (e.g., forking-lemma based proofs) do not apply here, since the lemma and its proof are purely information-theoretic and metric in nature. When we prove that a scheme is unforgeable against quantum adversaries in the QROM, H : {0, 1}∗ → Fp is modeled as a uniformly random function, and the adversary may query H in superposition |x, y⟩ 7→ |x, y ⊕ H(x)⟩. Definition 4 (Forgery event in quantum). A forgery occurs if a (quantum) ∗ adversary A outputs a pair (M ∗ , σalg ) such that M ∗ was never submitted to ∗ the signing oracle, and the verification algorithm accepts (M ∗ , σalg ) as a valid signature. We denote this event by Forge. We can prove that a quantum adversary making qH queries to a random oracle H : {0, 1}∗ → Fp can cause a collision in the oracle outputs with probability at 2 most O(qH /p). The key technical tool is the recording (compressed-oracle) lemma, which says that the interaction of a quantum algorithm with a random oracle can be represented as a distribution over classical query–answer transcripts [51]. Definition 5 (Collision Event). Let H : {0, 1}∗ → Fp be a random function, and let A be a (possibly quantum) oracle algorithm. We say that a collision occurs if there exist distinct inputs x = ̸ x′ such that H(x) = H(x′ ) and both x and x′ appear in the (compressed) oracle transcript associated with A’s execution. We denote this event by Coll. Lemma 4 (Recording/Compressed-Oracle Lemma [51]). Let the hash function H : {0, 1}∗ → Fp be a uniformly random function, and let A be a quantum oracle algorithm making at most qH queries to H. Then, there exists a classical random variable T (the transcript) such that T is a finite sequence of
pairs T = (x1 , H(x1 )), . . . , (xt , H(xt )) with t ≤ qH , where the xi are (classical) inputs and H(xi ) are the corresponding oracle outputs. The distribution of T is identical to the distribution of the query–answer transcript in a classical lazysampling experiment where a classical algorithm makes at most qH (adaptive) queries to a random oracle H : {0, 1}∗ → Fp . In particular, any event that depends only on the multiset {(xi , H(xi ))}i (such as the existence of a collision among the values H(xi )) has the same probability in the quantum execution as in this classical transcript model. Using Lemma 4, the quantum birthday bound reduces to a purely classical probability calculation. Theorem 3 (Quantum Birthday Bound [50]). Let H : {0, 1}∗ → Fp be a uniformly random function, and let A be a quantum oracle algorithm making

Title Suppressed Due to Excessive Length

13

Algorithm 1 KeyGen(1k ) 1: Choose a prime p ≈ 2k and work over F∗p . 2: Select hash function H and SSS2,2 with public weights w0 , w1 . $

3: Sample K ← − F∗p and compute (K0 , K1 ) = SSS2,2 (K). 4: Output: private key sk = K, public key (w0 , w1 ).

Algorithm 2 Signsk (M ) Require: Secret key sk = K and ephemeral session key ksig . 1: n ← HMACksig (M ) and r ← H(M, n). $

2: Sample α, β, b, d ← − F∗p . 3: Compute ε = αβ and (ε0 , ε1 ) = SSS2,2 (ε). 4: Compute K ′ = HMACK (M ) and (K0′ , K1′ ) = SSS2,2 (K ′ ). 5: Compute the algebraic signature components: σ1 = b(K ′ − r), σ2 = db−1 , σ3 = K1′ d, −1 ′ −1 σ4 = d ε ε1 , σ5 = d(K0 − r ε ε0 ).

(4)

6: Output: σalg = (σ1 , . . . , σ5 ).

at most qH queries to H. Let Coll be the event that there exist distinct inputs x= ̸ x′ in the (compressed) transcript such that H(x) = H(x′ ). Then Pr[Coll] ≤ 2 qH qH (qH −1) 2 /p). ≤ 2p . In particular, Pr[Coll] = O(qH 2p

4

Construction of SILMARILS

We now give the full specification of our IT-secure signature scheme. The scheme operates over a prime field Fp and uses perfect 2-out-of-2 Shamir secret sharing SSS2,2 for all shared values. All randomness comes from a TRNG, and H is either a fixed injective encoding (pure IT model) or a random oracle (IT+ROM). Verification reconstructs a value that must equal 0 for valid signatures. Unforgeability Algorithm 3 Verify(M, σalg ) Require: Ephemeral session key ksig . 1: Parse σ = (σ1 , σ2 , σ3 , σ4 , σ5 ). 2: Compute n ← HMACksig (M ) and r ← H(M, n). 3: if σ4 = 0 then return 0 4: else 5: Compute V0 = σ1 σ2 − σ5 , and V1 = σ1 σ2 − σ3 + r σ4 . 6: Reconstruct V = SSS−1 2,2 (V0 , V1 ). 7: if V = 0 then return 1 8: else return 0 9: end if 10: end if

14

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

follows from the algebraic fact that any deviation from the honest equations introduces a nonzero term that is uniformly distributed in F∗p , since the verification constraints form a linear system satisfied by exactly one tuple—the honest signature—and any modification yields a uniformly random nonzero output. 4.1

Three-Party SILMARILS

In this section, we present SILMARILS construction in three-party mode. The goal is to enable a signer P1 to authenticate a message M so that a holder P2 can extract an authenticated value and subsequently transfer it to a verifier P3 , while ensuring correctness, unforgeability, and transferability with error at most ε = 1/p. Our construction implements an IC mechanism based on affine authentication over Fp [45, Protocol 18.7]. In our setting, the IC mechanism is applied not to the message itself but to the authenticated value x := H(M, σalg ) ∈ Fp , where σalg = (σ1 , . . . , σ5 ) is the algebraic part of SILMARILS signature produced by Algorithm 2. The IC layer ensures that P2 and P3 agree on a unique affine authentication pair (x, σ) satisfying σ = k1 x + k2 , for secret coefficients (k1 , k2 ) held by P3 . Any attempt by a malicious P1 to cause P2 and P3 to disagree on the authenticated value is detected with probability at least 1 − 1/p. Hence, the resulting three-party SILMARILS protocol consists of two phases: – Signing phase. The signer P1 computes σalg using Algorithm 2, derives x = H(M, σalg ), and initiates the IC protocol with P2 and P3 to authenticate x. The IC protocol consists of a challenge phase (run by P2 ) and a consistencycheck phase (run by P1 and P3 ). At the end of this phase, the holder P2 obtains an authenticated pair (x, σ) consistent with the verifier’s secret line σ = k1 x + k2 except with probability 1/p. – Transfer phase. The holder P2 sends (x, σ) to P3 , who checks whether the affine relation holds. If so, it outputs z3 = x; otherwise, it outputs ⊥. To interpret x as a signature on M , the verifier recomputes σalg from M , checks that H(M, σalg ) = x, and verifies the algebraic predicate V = SSS−1 2,2 (V0 , V1 ) = 0 from Algorithm 3; both conditions hold for all honest signatures, so the protocol realizes the ideal three-party functionality with error 1/p. Algorithms 1, 2, and 4 give key generation, signing, and three-party extraction. Each algebraic signature σalg = (σ1 , . . . , σ5 ) consists of masked encodings of K ′ , the randomness d, and Shamir shares of K ′ and ε = αβ, ensuring that V = 0 for honest executions. In the three-party setting, Algorithm 4 computes x = H(M, σalg ) and initiates the IC protocol with P2 and P3 , where the challenge and consistency checks (Algorithms 5–6) authenticate x by producing an affine pair (x, σ) satisfying σ = k1 x + k2 for verifier-held coefficients. The holder outputs z2 = x, which is consistent with the verifier’s line except with probability 1/p. Any malicious deviation violates an algebraic or affine relation, causing the reconstructed value at the verifier to be uniformly random in Fp , so a forgery is accepted with probability at most 1/p. Finally, the holder transfers (x, σ) to P3 (Algorithm 7), and the verifier applies Algorithm 8 to output z3 ∈ {x, ⊥} depending on whether the affine check holds.

Title Suppressed Due to Excessive Length

15

(3)

Algorithm 4 Signsk (M ) (run by P1 ) 1: Compute σalg using Algorithm 2. 2: Compute x := H(M, σalg ). $

3: Sample k1 , k2 , x′ , k2′ ← − Fp . 4: Compute σ = k1 x + k2 and σ ′ = k1 x′ + k2′ . 5: Send (x, x′ , σ, σ ′ ) to P2 and (k1 , k2 , k2′ ) to P3 . 6: Proceed to the IC challenge phase.

Algorithm 5 IC Challenge Phase (run by P2 ) $

1: Sample e ← − Fp . 2: Compute xe := x′ + ex and σe := σ ′ + eσ. 3: Broadcast (e, xe , σe ).

Upon receiving x, the verifier recomputes σalg from M and checks that H(M, σalg ) = x and V (P, M, σalg ) = 0. If both hold, the signature is accepted. 4.2

Two-Party SILMARILS

Let H : {0, 1}∗ → Fp with p ≈ 2k , be a hash function modeled as a random oracle, and let HMAC be a pseudorandom function keyed by the long-term signing key K. The two-party signature scheme SILMARILS = (KeyGen, Sign, Verify) between P1 and P3 is defined as follows. We have also provided an open-source reference implementation in Rust [20]. KeyGen(1k ): Choose a prime p ≈ 2k and work over F∗p . Fix H and SSS2,2 (with $

fresh internal randomness each use). Sample public weights w0 , w1 ← − F∗p $

and a long-term key K ← − F∗p . Signer and verifier share ksig for deriving n = HMACksig (M ). Output sk = K and pk = (w0 , w1 ). $

Signsk (M ): On input M and sk = K, sample α, β, b, d ← − F∗p and set ε = αβ, (ε0 , ε1 ) = SSS2,2 (ε). Compute the shared nonce n := HMACksig (M ), and compute r := H(M, n). Derive the per-message signing key K ′ := HMACK (M ), and compute its shares (K0′ , K1′ ) = SSS2,2 (K ′ ). Then compute the algebraic signature σalg = (σ1 , σ2 , σ3 , σ4 , σ5 ) using (4). Verifypk (M, σalg ): On input (M, σalg ) and public key (w0 , w1 ), parse σalg = (σ1 , σ2 , σ3 , σ4 , σ5 ). Compute n := HMACksig (M ), r := H(M, n). If σ4 = 0, output 0 (reject). Compute V0 = σ1 σ2 − σ5 ,

V1 = σ1 σ2 − σ3 + r σ4 .

(5)

Reconstruct V = SSS−1 2,2 (V0 , V1 ). If V = 0 output 1 (accept), otherwise output 0 (reject). Remark 1 (Relationship Between Modes). The two-party TDV mode and the three-party IC mode are distinct primitives with different assumptions, guarantees,

16

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

Algorithm 6 IC Consistency Checks (run by P1 and P3 ) Checks by P1 on P2 ’s broadcast: 1: Verify xe = x′ + ex and σe = σ ′ + eσ. 2: if either check fails then 3: Broadcast “P2 corrupt” and broadcast (x, σ). 4: P2 sets (x, σ) to the broadcasted pair. 5: P3 updates k2 so that σ = k1 x + k2 . 6: Terminate signing phase with z2 = x. 7: else 8: Broadcast “accept”. 9: end if Checks by P3 : ? 10: Verify σe = k1 xe + k2′ + ek2 . 11: Broadcast “accept” or “reject” accordingly. Checks by P1 on P3 ’s broadcast: 12: Using (k1 , k2 , k2′ ), verify whether P3 ’s broadcast (“accept” or “reject”) is consistent with the equation above. 13: if P3 ’s broadcast is inconsistent then 14: Broadcast “P3 corrupt”. 15: end if 16: if P3 says “accept” and P1 says “accept” then 17: Terminate signing phase with z2 = x. 18: else if P3 says “reject” and P1 says “accept” then 19: P1 broadcasts (x, σ). 20: P2 sets (x, σ) to the broadcasted pair. 21: P3 updates k2 so that σ = k1 x + k2 . 22: Terminate signing phase with z2 = x. 23: else if P1 says “P3 corrupt” then 24: P1 broadcasts (k1 , k2 ). 25: P3 sets (k1 , k2 ) to the broadcasted pair. 26: P2 updates σ so that σ = k1 x + k2 . 27: Terminate signing phase with z2 = x. 28: end if

and security models. We present them under a unified algebraic framework, but we do not claim a reduction or equivalence between them.

5

Designated-Verifier Security of Two-Party SILMARILS

In this section we formalize the DV security of the two-party SILMARILS mode and prove that it satisfies the Jakobsson–Sako–Impagliazzo (JSI) notion of DV proofs [31]. Intuitively, a designated-verifier signature (DVS) scheme is one in which the DV can always simulate accepting transcripts that are indistinguishable from real ones, so that no third party can be convinced that the signer actually produced a given transcript.

Title Suppressed Due to Excessive Length

17

Algorithm 7 Transfer(x, σ) (run by P2 ) 1: Send (x, σ) to P3 .

Algorithm 8 ExtractTransfer(x, σ) (run by P3 ) 1: if σ = k1 x + k2 then 2: Output z3 := x. 3: else 4: Output z3 := ⊥. 5: end if

Jakobsson et al. motivate designated verification as reconciling authenticity with privacy: “we designate a verifier when we ensure that nobody but this participant can be convinced by the proof.” Their core idea is that Alice proves the disjunction ”either φ is true, or I am Bob,” which convinces Bob but is useless to any third party, since Bob can always simulate being Bob. This captures the requirement that any transcript convincing to the designated verifier must be simulatable by that verifier alone, and therefore non-transferable. We adopt the JSI model with three parties: a prover P (the signer), a designated verifier V, and a third party C (Cindy). Let φ be the statement “σ is a valid SILMARILS signature on message M under the shared longterm key K and per-pair key ksig ”. A (possibly interactive) protocol (PP , PV ) is a designated-verifier proof of φ if the following two properties hold: 1) Correctness for the DV: If P is honest and φ is true, then an honest V accepts with overwhelming probability; 2) Simulatability for the DV: For any (possibly malicious) prover P ∗ , there exists a probabilistic polynomial-time (PPT) simulator SV that, given only V’s secret key and the public inputs, outputs transcripts that are computationally indistinguishable from those produced by an interaction between P ∗ and an honest V. Following JSI, we say that V is a designated verifier if for any protocol (PP , PV , PC ) in which V attempts to convince C of φ, there exists a protocol (PV′ , PC ) such that V alone can generate transcripts that C cannot distinguish from those of the original three-party protocol. In particular, a hidden verifier C cannot obtain transferable conviction, since any transcript she sees could have been generated entirely by V. In the sequel, we first analyze the algebraic structure of the verification equations, showing that any party who can compute the permessage value r = H(M, HMACksig (M )) can generate accepting transcripts and extract the hidden parameters a and s = K ′ . We then show that this capability is exactly the JSI designated-verifier simulation property and therefore a security feature, not a flaw. 5.1

Algebraic Structure and Simulator Construction

Using Shamir shares K0′ = K ′ + aK w0 , K1′ = K ′ + aK w1 , ε0 = ε + aε w0 , ε1 = ε + aε w1 , the verifier computes V0 = σ1 σ2 − σ5 = d(−aK w0 − r + rε−1 ε0 )

18

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

and V1 = σ1 σ2 − σ3 + rσ4 = d(−aK w1 − r + rε−1 ε1 ). Using ε−1 εi = 1 + aεεwi , we obtain V0 = dw0 C, V1 = dw1 C, and C := −aK + r aεε . Thus (V0 , V1 ) are evaluations of f (x) = dCx, and reconstruction yields f (0) = 0, guaranteeing acceptance. Simulator (DV Forgery): Any party knowing r can generate a valid transcript. Compute n = HMACksig (M ) and r = H(M, n), choose arbitrary K ′∗ , aK , aε ∈ Fp and d, ε, b ∈ F∗p , and form K0′∗ = K ′∗ + aK w0 , K1′∗ = K ′∗ + aK w1 , ε∗0 = ε + aε w0 , ε∗1 = ε + aε w1 . Substitute these values into the signature equations (4) and output the resulting σ ∗ = (σ1∗ , . . . , σ5∗ ). 5.2

Extraction of the Hidden Parameters

From the signature equations σ1 = b(s − r), σ2 = db−1 , σ3 = d(aw1 + s), σ4 = du1 , σ5 = d(aw0 + s − ru0 ), with ui = ε−1 εi , the verifier forms the ratio s−r R = σσ1 σ3 2 = aw , yielding s(R − 1) + aw1 R + r = 0. From reconstruction, 1 +s aCw = rCε , Cw = λ0 w0 + λ1 w1 , with Cε = λ0 (u0 − 1) + λ1 (u1 − 1) and d = σ3 /(aw1 + s),

u1 = σ4

aw1 + s , σ3

u0 =

aw0 + s − σ5 awσ13+s r

.

Thus Cε = αa a + αs s + α0 , giving the linear system (Cw − rαa )a − rαs s = rα0 ,

w1 R a + (R − 1)s = −r.

1 R−r Solving yields explicit closed forms for a and s. If R ̸= 1, then s = −aw . R−1 ′ ′ Once s is known, K0 = aw0 + s and K1 = aw1 + s.

Theorem 4 (DV Security of Two-Party SILMARILS). The two-party SILMARILS is a DV signature scheme in the sense of JSI notion. In particular, for every message M and every honestly generated transcript (M, σ, r), the designated verifier—and only the designated verifier—can (i) verify correctness and (ii) generate transcripts that are computationally indistinguishable from honestly generated ones. Consequently, no third party can obtain transferable conviction that the signer produced the transcript. Proof. Let P1 be the signer, P3 the DV, and C an arbitrary third party. The signer and DV share the per-pair key ksig , enabling P3 to compute n = HMACksig (M ) and r = H(M, n) for any M . Knowledge of r is the trapdoor enabling simulation, analogous to the trapdoor commitment key in JSI. Correctness: For an honestly generated signature σ = (σ1 , . . . , σ5 ), the verifier computes V0 = dw0 C, V1 = dw1 C, C = −aK + r aεε , which interpolate to the affine polynomial f (x) = dCx with f (0) = 0. Thus the verification algorithm always accepts honest signatures. Simulatability: Given any message M , the DV can generate an accepting transcript without interacting with the signer. It computes r = H(M, HMACksig (M )), chooses arbitrary K ′∗ , aK , aε ∈ Fp and d, ε, b ∈ F∗p , and forms K0′∗ = K ′∗ + aK w0 , K1′∗ = K ′∗ + aK w1 , ε∗0 = ε + aε w0 , ε∗1 = ε + aε w1 . Substituting into the signature

Title Suppressed Due to Excessive Length

19

equations (4) yields σ ∗ = (σ1∗ , . . . , σ5∗ ). Verification of σ ∗ produces the same (V0 , V1 ) structure as an honest signature and reconstructs f (0) = 0, so σ ∗ is always accepted. Indistinguishability: In honest signing, the parameters (K ′ , aK , aε , d, ε, b) are uniformly random in the same domains as in simulation. The only difference is that K ′ is derived as HMACK (M ), whereas K ′∗ is chosen uniformly. Since K is unknown to any external observer, the distributions of honest and simulated transcripts are identical. Hence no algorithm can distinguish them. Non-transferability: Let C receive (M, σ, r) from P3 . Because P3 can generate such transcripts without interacting with P1 , C cannot determine whether the transcript originated from the signer or from the DV. This matches the JSI definition: for any three-party protocol (PP , PV , PC ), there exists a two-party protocol (PV′ , PC ) producing indistinguishable transcripts. Hence, only the DV can be convinced by a transcript, and any transcript that convinces them is simulatable by them alone. Therefore, two-party SILMARILS satisfies the JSI designated-verifier definition. □

6

EUF-CMA Security of Two-Party SILMARILS Against Non-Designated Parties

In this section we prove that two-party SILMARILS is EUF-CMA secure in the ROM and QROM against non-designated parties. In the two-party mode of SILMARILS, the designated verifier holds the shared secret ksig and can therefore compute the per-message nonce n = HMACksig (M ) and the receipt r = H(M, n) for any message M . This enables the designated verifier to simulate accepting transcripts that are indistinguishable from honestly generated ones, as required by JSI notion. Consequently, standard EUF-CMA unforgeability cannot hold for the designated verifier. Instead, we prove unforgeability against all nondesignated parties, who do not know ksig and therefore cannot compute r for new messages. We emphasize that in the TDV setting the designated verifier may publish a receipt r enabling third-party verification, but verification is impossible without r, and even with r no external party can determine whether a valid transcript was produced by the signer or simulated by the designated verifier. Definition 6 (EUF-CMA Security for Non-Designated Verifiers). We write EUF-CMA¬DV to denote existential unforgeability under chosen-message attack for all parties except the designated verifier. An adversary A is given the public parameters (w0 , w1 ) and oracle access to Signsk (·). It outputs (M ⋆ , σ ⋆ ). We say that A wins if Verifypk (M ⋆ , σ ⋆ ) = 1 and M ⋆ was never queried to the signing oracle. The designated verifier is excluded from this game, as it must be able to simulate signatures. We isolate the algebraic core used to analyze unforgeability for non-designated verifiers. Here the only value depending on ksig is the receipt r = H(M, n), sampled uniformly per query; the adversary never learns n or ksig .

20

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

Definition 7 (Algebraic Core Experiment). In CoreForgeA (1k ), the chal$

lenger samples K ← − F∗p , gives (w0 , w1 ) to A, and for each signing query M sam$

$

ples α, β, b, d ← − F∗p , sets ε = αβ with (ε0 , ε1 ) = SSS2,2 (ε), samples r ← − Fp , com′ putes K = HMACK (M ) with (K0′ , K1′ ) = SSS2,2 (K ′ ), and returns (σ1 , . . . , σ5 ) $

as in (4). On output (M ⋆ , σ1⋆ , . . . , σ5⋆ ), the challenger samples r⋆ ← − Fp , computes ⋆ ⋆ V0⋆ and V1⋆ as in (5), and reconstructs V ⋆ = SSS−1 2,2 (V0 , V1 ), and outputs 1 iff M ⋆ was never queried and V ⋆ = 0. The advantage is Pr[CoreForgeA (1k ) = 1]. Lemma 5 (Algebraic Core Unforgeability). If r⋆ is sampled uniformly independent of the adversary’s view after the PPT adversary outputs its forgery, then Pr[CoreForgeA (1k ) = 1] ≤ p1 , which is negligible in k. Proof. Fix any view of A up to the moment it outputs (M ⋆ , σ1⋆ , . . . , σ5⋆ ). The value r⋆ used in verification is sampled after the forgery is output and is uniform in Fp , independent of A’s view. The verification equations define V0⋆ independently of ⋆ r⋆ and V1⋆ as an affine function of r⋆ . Since SSS−1 2,2 is linear, the predicate V = 0 ⋆ ⋆ holds for at most one value of r . Thus the probability that V = 0 is at most 1/p, even for an unbounded adversary. □ Remark 2. If the receipt were public, i.e. r = H(M ) without the hidden nonce n = HMACksig (M ), then the verification equations V0 = σ1 σ2 − σ5 and V1 = σ1 σ2 − σ3 + r σ4 become public linear constraints on (σ1 , . . . , σ5 ), making the algebraic core deterministically forgeable: for any new M ′ ̸= M , an adversary may choose arbitrary σ1′ , σ2′ , σ3′ , σ4′ ∈ Fp , compute V1′ = σ1′ σ2′ − σ3′ + r′ σ4′ with r′ = H(M ′ ), ′ ′ and set σ5′ = σ1′ σ2′ − (w0 /w1 )V1′ , which always yields V ′ = SSS−1 2,2 (V0 , V1 ) = 0 and thus a perfect forgery. To prevent this, SILMARILS derives a secret per-message nonce n = HMACksig (M ) and defines r = H(M, n), ensuring r is unpredictable for new messages and eliminating the algebraic forgery. Definition 8. Let Πcore = (KeyGen, Sign, Verify) denote the two-party algebraic core of SILMARILS. We say that Πcore is εcorr -correct if, for all messages M and all honestly generated key pairs (pk, sk) ← KeyGen,   Pr Verifypk (M, σalg ) = 1 σalg ← Signsk (M ) ≥ 1 − εcorr . If εcorr = 0, the algebraic core is said to be perfectly correct. Theorem 5 (1/p−Correctness). For any message M and every honestly generated key pair (pk, sk), an honestly generated signature σalg ← Signsk (M ) is rejected with probability at most 1/p. Proof. Let M be arbitrary and let σalg = (σ1 , σ2 , σ3 , σ4 , σ5 ) be the signature produced by Signsk (M ). Let n = HMACksig (M ), r = H(M, n), and let K ′ = $

HMACK (M ), (K0′ , K1′ ) = SSS2,2 (K ′ ). The signing algorithm samples α, β, b, d ← − F∗p , sets ε = αβ and (ε0 , ε1 ) = SSS2,2 (ε), and computes (σ1 , . . . , σ5 ) as in (4). The verifier computes V0 , V1 as in (5) and reconstructs V = SSS−1 2,2 (V0 , V1 ). We

Title Suppressed Due to Excessive Length

21

h i h i have V0 = d (K ′ − r) − (K0′ − r ε−1 ε0 ) and V1 = d (K ′ − r) − (K1′ − r ε−1 ε1 ) . w K ′ −w K ′

Since (K0′ , K1′ ) are the Shamir shares of K ′ at points (w0 , w1 ), K ′ = 0 w10 −w11 0 . 1 ε0 Similarly, since (ε0 , ε1 ) are the shares of ε, ε = w0wε10 −w −w1 . Reconstructing V 1 V0 gives V = w0wV10 −w −w1 . Substituting the expressions for V0 and V1 and simplifying using the identities above yields V = 0. Considering the case σ4 = 0, which causes the verification to reject, the verification predicate evaluates to zero with probability 1 − 1/p for honestly generated signatures. □ 6.1

EUF-CMA¬DV Security of Two-Party SILMARILS in the ROM

We now prove that the two-party mode of SILMARILS is EUF-CMA¬DV secure in the ROM, using Lemma 5. Recall that non-designated verifiers do not know the shared secret ksig and therefore cannot compute the per-message nonce n = HMACksig (M ) or the receipt r = H(M, n) for new messages. This prevents them from mounting the deterministic algebraic forgery described in the previous remark. Theorem 6. Assume H is modeled as a random oracle and is collision resistant, and HMAC is a PRF keyed by ksig . Then the two-party SILMARILS scheme is EUF-CMA¬DV secure. More precisely, for any PPT adversary A there exist PPT algorithms B1 , B2 , B3 such that ¬DV 1 core CR AdvEUF-CMA (B1 ) + AdvPRF SILMARILS (A) ≤ Adv HMAC (B2 ) + AdvH (B3 ) + . p

Proof. Let A be a PPT adversary in the EUF-CMA¬DV game. We proceed via a sequence of games. Game 0: This is the real EUF-CMA¬DV experiment for SILMARILS. The adversary receives (w0 , w1 ), has access to the signing oracle, and interacts with H as a random oracle. Let Succ0 denote the event that A outputs a valid forgery ⋆ (M ⋆ , σalg ) on a message M ⋆ not previously signed. Game 1: Replace HMACksig by a truly random function F : {0, 1}∗ → Fp . All other aspects remain unchanged. Let Succ1 be the forgery event in Game 1. By a standard PRF reduction, there exists a PPT distinguisher B2 such that Pr[Succ0 ] − Pr[Succ1 ] ≤ AdvPRF HMAC (B2 ). From now on we analyze Game 1, where n := F (M ) and r := H(M, n). Game 2: We now make explicit how the simulator programs the random oracle H. A simulator B maintains a table TH . On a signing query M , it: 1) samples $

$

n ← − Fp as F (M ); 2) samples r ← − Fp ; 3) programs H(M, n) := r in TH ; 4) $

samples α, β, b, d ← − F∗p , sets ε = αβ and (ε0 , ε1 ) = SSS2,2 (ε); 5) computes ′ K = HMACK (M ) and (K0′ , K1′ ) = SSS2,2 (K ′ ); 6) computes (σ1 , . . . , σ5 ) exactly as in Sign; 7) returns σalg to A. For any other H-query (x, y) not equal to (M, n) for a signed message, B returns a fresh uniform value in Fp , consistent with TH . This perfectly simulates Game 1, so Pr[Succ1 ] = Pr[Succ2 ].

22

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

⋆ Analysis of a forgery in Game 2: Suppose A outputs a forgery (M ⋆ , σalg ) with ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ σalg = (σ1 , . . . , σ5 ). Let n := F (M ) and r := H(M , n ). Since verification accepts, the algebraic predicate V0⋆ = σ1⋆ σ2⋆ − σ5⋆ ,, V1⋆ = σ1⋆ σ2⋆ − σ3⋆ + r⋆ σ4⋆ , satisfies ⋆ ⋆ SSS−1 2,2 (V0 , V1 ) = 0. We distinguish two cases. Case 1: A never queried H on (M ⋆ , n⋆ ). Then r⋆ is uniform and independent of A’s view. For any fixed (σ1⋆ , . . . , σ5⋆ ), the algebraic predicate holds for at most one value of r⋆ , so Pr[Succ2 ∧ Case 1] ≤ p1 . Case 2: A queried H on (M ⋆ , n⋆ ). Let this be the first such query. At that moment, the simulator chooses r⋆ uniformly. Conditioned on this choice, the distribution of (σ1⋆ , . . . , σ5⋆ ) is identical to that in the algebraic core experiment. Define B1 as the algebraic-core adversary that runs A and outputs the forgery in Case 2. Then Pr[Succ2 ∧ Case 2] ≤ Advcore (B1 ). If A ever forces H(x) = H(x′ ) for x = ̸ x′ , then we obtain a collision in H. Define B3 to output such a pair. Then Pr[A causes a collision in H] ≤ core AdvCR (B1 ) + p1 + AdvCR H (B3 ). Combining the two cases, Pr[Succ2 ] ≤ Adv H (B3 ). Together with the transition from Game 0 to Game 1, ¬DV 1 PRF core AdvEUF-CMA (B1 ) + AdvCR SILMARILS (A) ≤ AdvHMAC (B2 ) + Adv H (B3 ) + . p

By Lemma 5 and the assumed security of HMAC and H, the right-hand side is negligible. Hence SILMARILS is EUF-CMA¬DV secure. □ 6.2

EUF-CMA¬DV Security of Two-Party SILMARILS in the QROM

We now extend the EUF-CMA¬DV analysis of SILMARILS to the QROM. The classical ROM proof relies on lazy sampling and post-hoc programming of the random oracle at points (M, n), where n is the output of a PRF. In the QROM, the adversary may query the random oracle in superposition, and therefore the classical programming argument is no longer sound. To obtain a valid security proof, we rely on the measure-and-reprogram technique of Zhandry [50] and Unruh [47], which allows programming the random oracle at a single point while bounding the adversary’s distinguishing advantage. Lemma 6 (Quantum Measure-and-Reprogram [50], [47]). Let A be a quantum algorithm that makes at most qH queries to a random oracle H : X → Y, where Y is a finite set. On input public parameters PP, AH outputs a pair (x⋆ , z) ∈ X × Z. Let V(PP, x⋆ , z, H(x⋆ )) ∈ {0, 1} be a (classical) predicate. Consider the following two experiments: Real experiment (E1 ): Sample a random oracle H : X → Y, run (x⋆ , z) ← AH (PP), and output (x⋆ , z, H(x⋆ )). Measure-and-reprogram experiment (E2 ): Sample a random oracle H and run AH (PP), but let a simulator S do the following: at one adaptively chosen oracle query (among at most qH ), measure the query register to obtain x̃; choose any y ⋆ ∈ Y; define H ′ (x̃) = y ⋆ and H ′ (x) = H(x) for x = ̸ x̃; and let A continue with H ′ . If (x⋆ , z) is the final output, return (x⋆ , z, H ′ (x⋆ )).

Title Suppressed Due to Excessive Length

23

Then a simulator S exists making at most qH + O(1) oracle queries and  2      q Pr V(PP, x⋆ , z, H(x⋆ )) = 1 E1 − Pr V(PP, x⋆ , z, H ′ (x⋆ )) = 1 E2 ≤ O H . |Y| In particular, from the adversary’s point of view, programming the random oracle at a single point x̃ (chosen by measuring one of its queries) and assigning it an arbitrary value y ⋆ is indistinguishable from the original random-oracle experiment 2 up to statistical distance O(qH /|Y|). Theorem 7 (EUF-CMA¬DV Security in the QROM). Assume H is modeled as a quantum-accessible random oracle and is collision-resistant against quantum adversaries and HMAC is a quantum-secure PRF keyed by ksig . Then, SILMARILS is EUF-CMA¬DV secure in the QROM. More precisely, for any quantum polynomial time (QPT) adversary A making at most qH quantum queries to H, there exist QPT algorithms B1 , B2 , B3 such that  2  q EUF-CMA¬DV core PRF CR AdvSILMARILS (A) ≤ Adv (B1 ) + AdvHMAC (B2 ) + AdvH (B3 ) + O H . p Proof. Let A be a QPT adversary against SILMARILS in the EUF-CMA¬DV game, making at most qH quantum queries to the random oracle H. We show ¬DV how to bound AdvEUF-CMA SILMARILS (A) via a sequence of games and reductions. Game 0 (Real QROM EUF-CMA¬DV game): In Game 0, we run the standard EUF-CMA¬DV experiment for SILMARILS in the QROM: 1) A key pair (pk, sk) is generated honestly. 2) The adversary A has quantum oracle access to H and classical access to a signing oracle Signsk (·). 3) Eventually, A outputs a pair ⋆ ⋆ (M ⋆ , σalg ). 4) The experiment outputs 1 (success) if Verifypk (M ⋆ , σalg ) = 1 and ⋆ M was never queried to the signing oracle. Let Adv0 := Pr[Game 0 outputs 1] = ¬DV AdvEUF-CMA SILMARILS (A). Game 1 (Replace HMAC by a quantum-secure PRF): In the real scheme, the value n used to derive r is computed as n = HMACksig (M ). By assumption, HMAC is a quantum-secure PRF. We define Game 1 as follows: 1) Replace HMACksig by a truly random function F : {0, 1}∗ → Fp . 2) For each signing query M , set n := F (M ) and then derive r := H(M, n) as in the real scheme. By the quantum PRF security of HMAC, there exists a QPT distinguisher B2 such that |Adv1 − Adv0 | ≤ AdvPRF HMAC (B2 ), where Adv1 is the success probability of A in Game 1. Hence it suffices to bound Adv1 and consider the idealized setting where F is a truly random function, independent of H. Game 2 (Measure-and-reprogram H at signing points). In Game 1, for each signing query M , the scheme computes n := F (M ) and then sets r := H(M, n). In the QROM, A may have queried H on superpositions that include (M, n), so we cannot naively program H(M, n) after the fact. We now define Game 2, where a simulator S uses the measure-and-reprogram lemma (Lemma 6) to program H at points of the form (M, n) for signing queries M : 1) For each signing query M , the simulator samples n := F (M ) and a fresh

24

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna $

r← − Fp . 2) The simulator applies the measure-and-reprogram procedure to the quantum random oracle H at the point (M, n), reprogramming H(M, n) to r. 3) It then computes the algebraic signature components (σ1 , . . . , σ5 ) exactly as in the real signing algorithm, using this r, and returns σalg = (σ1 , . . . , σ5 ) to A. By Lemma 6, for each programmed point (M, n), the statistical distance between the real QROM experiment and the measure-and-reprogram experiment is at 2 most O(qH /|Y|), where Y is the output space of H. In our setting, H outputs elements of Fp , so |Y| = p. Since the number of signing queries is polynomial and qH bounds the total  number of quantum queries, a union bound yields 2 qH |Adv2 − Adv1 | ≤ O p , where Adv2 is the success probability of A in Game 2. In Game 2, the distribution of signatures seen by A is identical to the real scheme: for each signing query M , the value r = H(M, n) is uniform in Fp (from A’s point of view) and the signature is computed honestly from r. Game 3 (Explicit simulation of signatures): We now make explicit the fact $

that in Game 2, the simulator chooses r ← − Fp and then programs H(M, n) to r. Thus, we can equivalently define Game 3 as: 1) For each signing query M , sample $

n := F (M ) and r ← − Fp . 2) Program H(M, n) := r via measure-and-reprogram. 3) Compute (σ1 , . . . , σ5 ) exactly as in the real signing algorithm using this r. By construction, Adv3 = Adv2 . We emphasize that in Game 3, for each signed message M , the pair (n, r) is uniform and independent of A’s view, conditioned only on the fact that H(M, n) has been programmed to r. ⋆ ⋆ Let (M ⋆ , σalg ) be the forgery output by A in Game 3, where σalg = (σ1⋆ , . . . , σ5⋆ ) ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ and Verifypk (M , σalg ) = 1. Let n := F (M ) and r := H(M , n⋆ ). We distinguish two cases, depending on whether A has queried H on (M ⋆ , n⋆ ). Case 1: A never queried H on (M ⋆ , n⋆ ). In this case, from A’s point of view, r⋆ is uniform in Fp and independent of its entire view (including all signatures and oracle answers), because: 1) F is a truly random function, so n⋆ = F (M ⋆ ) is uniform and independent of all other values; 2) H is a random oracle, and (M ⋆ , n⋆ ) was never queried, so H(M ⋆ , n⋆ ) is uniform and independent. The algebraic verification predicate of SILMARILS is a system of equations over Fp that, for fixed (σ1⋆ , . . . , σ5⋆ ), is satisfied by at most one value of r⋆ . Therefore, Pr[verification accepts in Case 1] ≤ p1 . Case 2: A queried H on (M ⋆ , n⋆ ). Let (M ⋆ , n⋆ ) be the first such query. At the moment this query is made, the simulator in Game 3 chooses r⋆ as a fresh uniform element of Fp and programs H(M ⋆ , n⋆ ) to r⋆ via measure-and-reprogram. By Lemma 6, the joint state of A and the oracle after this programming step is statistically close to the state in the ideal 2 random-oracle experiment, with distinguishing advantage at most O(qH /p). Con⋆ ⋆ ⋆ ditioned on this, the distribution of (σ1 , . . . , σ5 , r ) in A’s view is identical to that in the algebraic core experiment, where r⋆ is uniform and independent of the adversary’s internal randomness. Hence, any non-negligible probability that A outputs a new tuple (M ⋆ , σ1⋆ , . . . , σ5⋆ ) such that the algebraic predicate holds for r⋆ yields a non-negligible advantage for a QPT adversary B1 in the algebraic core game. By Lemma 5, this probability is bounded by Advcore (B1 ) + 1/p.

Title Suppressed Due to Excessive Length

25

In both cases, we have implicitly assumed that A does not exploit collisions in H. If A can force H(x) = H(x′ ) for distinct x ̸= x′ with non-negligible probability, then we obtain a quantum collision-finder B3 against H, with advantage AdvCR H (B3 ). Now, let Adv3 be the success probability of A in Game 3. From  the  1 case analysis above, we obtain Adv3 ≤ Advcore (B1 ) + AdvCR H (B3 ) + p + O Combining the game transitions, we have

2 qH p

.

¬DV

PRF PRF AdvEUF-CMA SILMARILS (A) = Adv0 ≤ Adv1 + AdvHMAC (B2 ) ≤ Adv3 + AdvHMAC (B2 ) +  2   2  qH q core PRF CR O ≤ Adv (B1 ) + AdvHMAC (B2 ) + AdvH (B3 ) + O H . p p

By Lemma 5 and the assumed quantum security of HMAC and H, the right-hand side is negligible in the security parameter. □

7

Security Analysis of Three-Party SILMARILS

We now state the main security theorem for our three-party SILMARILS protocol. The theorem asserts that the protocol implements the ideal three-party digital signature functionality fDS with error ε = 1/p. Theorem 8 (Security of Three-Party SILMARILS). Let p be a prime and let all parties operate over Fp . Let H be any function (deterministic, classical random oracle, or quantum-accessible random oracle) with range Fp , and define x := H(M, σalg ). Consider the three-party SILMARILS protocol consisting of Algorithms 2–8. Then, for any (classical or quantum) adversary corrupting at most one party, the protocol realizes the ideal digital-signature functionality fDS with distinguishing advantage ε = p1 . In particular, the protocol satisfies the previously defined notions of correctness, unforgeability, transferability, and secrecy, each with error at most 1/p, uniformly across the ROM, QROM, and Pure-IT models. Proof. Fix a prime p and let all parties operate over Fp . Let H be any function with range Fp (deterministic, classical random oracle, or quantum-accessible random oracle). For a given message M and honestly generated algebraic signature σalg = (σ1 , . . . , σ5 ) produced by Algorithm 2, the signer P1 computes x := H(M, σalg ) ∈ Fp and then runs Algorithms 4–6 to authenticate x using an IC protocol of the same form as Protocol 18.7 in [45]. Reduction to the IC functionality: Condition on a fixed value of x ∈ Fp and on fixed secret coefficients (k1 , k2 ) ∈ F2p held by P3 . From the point of view of the IC layer, the three-party SILMARILS protocol is exactly an execution of Protocol 18.7 in [45] on the message x, where P1 plays the role of the sender, holding x and the affine authentication pair (x, σ) with σ = k1 x + k2 ; P2 plays the role of the receiver, who should obtain z2 = x; P3 plays the role of the verifier, who holds (k1 , k2 ) and outputs z3 ∈ {x, ⊥}. Algorithms 4–6 implement exactly the challenge, consistency checks, and resolution rules of Protocol 18.7 in [45], specialized to the affine line σ = k1 x + k2 over Fp . Crucially, the IC security

26

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

properties (correctness, unforgeability, transferability, secrecy) depend only on the algebraic structure of the protocol over Fp and on the randomness of the IC coins (k1 , k2 , x′ , k2′ , e), and not on how x was obtained. In particular, the adversary never interacts with H through the IC interface: x is simply a field element fixed by P1 before the IC protocol starts. Therefore, the analysis of [45, Protocol 18.7] applies verbatim in all three models (ROM, QROM, Pure-IT). Correctness: If P1 and P2 are honest, then by the correctness guarantee of Protocol 18.7, the IC protocol ensures that P2 and P3 both output x except with probability at most 1/p. In our instantiation, the resolution rules in Algorithm 6 guarantee that whenever the IC protocol accepts, we have z2 = x and z3 = x. Thus the previously defined correctness notion holds with error at most 1/p. Unforgeability: If P1 and P3 are honest, then a malicious P2 attempts to cause P3 to output some z3 ∈ / {x1 , ⊥}, where x1 is the value authenticated by P1 . In the IC abstraction, this corresponds to the receiver trying to change the authenticated message while still passing the verifier’s affine check. By the soundness (unforgeability) guarantee of Protocol 18.7 and Lemma 18.15 in [45], the probability that a cheating receiver can make the verifier accept a value different from the sender’s input is at most 1/p. Hence the previously defined unforgeability condition holds with error at most 1/p. Transferability: If P2 and P3 are honest, then a malicious P1 may try to make them disagree on the authenticated value. In the IC abstraction, this is exactly the cheating-sender case: the sender attempts to cause the receiver and verifier to output different values. Protocol 18.7 guarantees that this happens with probability at most 1/p. Therefore, the previously defined transferability notion holds with error at most 1/p. Secrecy: If P1 and P2 are honest, then the view of P3 during the IC protocol consists only of the affine authentication data and the challenge transcript, which, by the privacy guarantee of Protocol 18.7, is statistically independent of the authenticated value x1 . Thus the previously defined secrecy notion holds with error 0 (and hence at most 1/p). In all of the above arguments, the value x is treated as an arbitrary element of Fp fixed before the IC protocol begins. The correctness, unforgeability, transferability, and secrecy proofs for Protocol 18.7 and Lemma 18.15 in [45] rely only on the fact that H outputs elements of Fp ; they do not depend on any further structural property of H. As a result, the same bounds apply whether H is instantiated as a deterministic function, a classical random oracle, or a quantum-accessible random oracle. The distinguishing advantage between the real three-party SILMARILS protocol and the ideal digital-signature functionality fDS is therefore at most 1/p in all three models. This completes the proof. □

8

Performance Evaluation

We now evaluate the efficiency of two-party SILMARILS, covering key and signature sizes, computational costs of signing and verification, and overall communication overhead, and we compare these metrics to leading PQ signature schemes

Title Suppressed Due to Excessive Length

27

Table 2: Comparison of SILMARILS with other digital signature schemes. Scheme

Security Type

PK Size (B) SK Size (B) Sig Size (B) Who Can Verify and Cost

Key Assumptions

SILMARILS

Information-Theoretic

64

32

160

TDV, ≈ 5 − 6 field mults + 1 SSS recon

TRNG + SSS

sr25519

Classical, Like Schnorr

32

64

64

Public Verifier, 1 scalar mult + 1 hash

ECDLP over Curve2551

NIST Post-Quantum Candidates Dilithium-2 (L2) Computational PQ Dilithium-3 (L3) Computational PQ Falcon-512 (L1) Computational PQ SPHINCS+ (Gen.) Computational PQ SPHINCS+ -128s (L1) Computational PQ SPHINCS+ -128f (L1) Computational PQ SPHINCS+ -192s (L3) Computational PQ SPHINCS+ -192f (L3) Computational PQ SLH-DSA-(SHA2/SHAKE)-128-24** (L1, 224 sigs) Computational PQ SLH-DSA-(SHA2/SHAKE)-192-24** (L3, 224 sigs) Computational PQ SLH-DSA-(SHA2/SHAKE)-256-24** (L5, 224 sigs) Computational PQ

1312 1952 897 64 32 32 48 48 32 48 64

2528 4000* 1281 128 64* 64* 96 96 48 72 96

2420 3293 690 49 856 7856 17 088 16 224 35 664 3856 7752 14 944

Public Verifier, 1 matrix-vector mult + 1 hash Module-LWE Public Verifier, matrix–vector mult Module-LWE Public Verifier, FFT + lattice decoding SIS over NTRU lattices Public Verifier, Many hashing + tree traversal Hash-based (QROM) Public Verifier, hash tree traversal Hash-based Public Verifier, hash tree traversal Hash-based Public Verifier, hash tree traversal Hash-based Public Verifier, hash tree traversal Hash-based Public Verifier, hash-based tree traversal Hash-based (limited-signature) Public Verifier, hash-based tree traversal Hash-based (limited-signature) Public Verifier, hash-based tree traversal Hash-based (limited-signature)

*SK Size for Dilithium-3 assumed to scale with security level (not explicitly in original tables). SK Size for SPHINCS+ variants assumed to be 64B (seed size for 128-bit security level, not explicitly in original tables). See https://asecuritysite.com/pqc/pqc_sig for more details. **NIST SP 800-230 [17]: reduced-size SLH-DSA variants for 224 -signature use cases.

to contextualize practical performance. As SILMARILS in two-party TDV mode is not a public-verifier signature scheme, these comparisons to Dilithium, Falcon, and SPHINCS+ reflect size and efficiency only, not equivalent security or functionality. Let p ≈ 2k denote the prime defining the field Fp . All public, secret, and signature components are single field elements, and thus occupy log2 (p) ≈ k bits. This yields exceptionally compact keys. The secret key consists of a single field element, giving |sk| = k bits. The public key contains two field elements giving |pk| = 2k bits. A signature consists of five field elements giving |σ| = 5k bits. Over a 256-bit prime field, we have |sk| = 256 bits = 32B, |pk| = 512 bits = 64B and |σ| = 1280 bits = 160B. Thus, even at the 256-bit security level, the public and secret keys remain extremely compact, and the signature size remains close to that of ECDSA signature. In addition, all arithmetic is carried out in Fp with p ≈ 2256 , so a field multiplication costs roughly the same as a constant-time 256-bit modular multiply (e.g., via Montgomery reduction). Signing requires about 10–12 such multiplications, while verification needs only 5–6, making both operations far lighter than those in lattice or hash-based PQ schemes. Table 2 compares our concrete instantiation to standard PQ signatures at their 128-bit and 192-bit security levels. Although SILMARILS is a TDV and targets a different threat model (IT rather than computational), the comparison highlights its efficiency and potential in practical applications. Additional performance benchmarks for SILMARILS can be found in [20].

9

Conclusion

SILMARILS provides a unified, IT framework for constructing lightweight digital signatures from a minimal algebraic core over Fp using only true randomness and perfect 2-out-of-2 Shamir secret sharing. The two-party mode yields a TDV signature scheme. We prove DV simulatability in the sense of Jakobsson–Sako– Impagliazzo and establish EUF-CMA¬DV security for all non-designated verifiers in both the ROM and QROM. In the three-party setting, adopting the broadcast model of Fitzi et al., we obtain a statistically secure signature protocol with full simulation-based security and error 1/p. Practical instantiations rely on hash functions, motivating a unified analysis across the Pure IT, IT+ROM, and QROM models and a quantum extension of the Fitzi simulation framework. We show that correctness, secrecy, transferability, and non-designated unforgeability

28

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

remain equivalent to simulation-based security even against quantum adversaries. Thanks to its structural simplicity, SILMARILS achieves much smaller keys and signatures than standardized PQ schemes. Although TDV signatures such as SILMARILS are not publicly verifiable, their post-quantum security and low overhead make them particularly attractive for blockchain and other resourceconstrained environments.

References 1. Digital signature standard (DSS). Federal Information Processing Standard FIPS 186-1, National Institute of Standards and Technology, Gaithersburg, MD, USA (Dec 1998), https://csrc.nist.gov/pubs/fips/186-1/final, supersedes FIPS 186 (1996); Withdrawn January 27, 2000 2. Aardal, M.A., Adj, G., Aranha, D.F., Basso, A., Canales Martínez, I.A., ChávezSaab, J., Corte-Real Santos, M., Dartois, P., De Feo, L., Duparc, M., Eriksen, J.K., Fouotsa, T.B., Gazzoni Filho, D.L., Hess, B., Kohel, D., Leroux, A., Longa, P., Maino, L., Meyer, M., Nakagawa, K., Onuki, H., Panny, L., Patranabis, S., Petit, C., Pope, G., Reijnders, K., Robert, D., Rodríguez Henríquez, F., Schaeffler, S., Wesolowski, B.: SQIsign: Algorithm specifications and supporting documentation (round 2). Tech. rep., NIST Post-Quantum Cryptography Project (Feb 2025), https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/ round-2/spec-files/sqisign-spec-round2-web.pdf, accessed 2026-01-12 3. Amiri, R., Abidin, A., Wallden, P., Andersson, E.: Efficient unconditionally secure signatures using universal hashing. In: Applied Cryptography and Network Security. Lecture Notes in Computer Science, vol. 10892, pp. 143–162. Springer (2018) 4. Aspnes, J.: Randomized protocols for asynchronous consensus. Distributed Computing 16, 165–175 (2003) 5. Ben-Or, M.: Another advantage of free choice: Completely asynchronous protocols. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. pp. 27–30. ACM (1983) 6. Bernstein, D.J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P.: The SPHINCS+ signature framework. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. p. 2129–2146. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/ 3319535.3363229, https://doi.org/10.1145/3319535.3363229 7. Beullens, W.: Breaking Rainbow takes a weekend on a laptop. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022. pp. 464–479. Springer Nature Switzerland, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_ 16 8. Beullens, W., Chen, M.S., Ding, J., Gong, B., Kannwischer, M.J., Patarin, J., Peng, B.Y., Schmidt, D., Shih, C.J., Tao, C., Yang, B.Y.: UOV: Unbalanced oil and vinegar — algorithm specifications and supporting documentation (round 2). Tech. rep., NIST Post-Quantum Cryptography Project (Feb 2025), https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/ round-2/spec-files/uov-spec-round2-web.pdf, accessed 2026-01-12 9. Boneh, D.: Schnorr digital signature scheme. In: van Tilborg, H.C.A. (ed.) Encyclopedia of Cryptography and Security. Springer, Boston, MA (2005). https: //doi.org/10.1007/0-387-23483-7_369

Title Suppressed Due to Excessive Length

29

10. Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: CRYPTO 2013. Lecture Notes in Computer Science, vol. 8043, pp. 361–379. Springer (2013). https://doi.org/10.1007/ 978-3-642-40084-1_21 11. Cao, N., Fitzsimmons, M., Mann, Z., Pereira, R., Laflamme, R.: Quantum maps between CPTP and HPTP (2023), https://arxiv.org/abs/2308.01894 12. Chaum, D., Roijakkers, S.: Unconditionally-secure digital signatures. In: Advances in Cryptology – CRYPTO ’90. Lecture Notes in Computer Science, vol. 537, pp. 206–214. Springer (1990) 13. Considine, J., Fitzi, M., Franklin, M., Levin, L.A., Maurer, U., Metcalf, D.: Byzantine agreement given partial broadcast. Journal of Cryptology 18, 191–217 (2005) 14. Courtois, N., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Boyd, C. (ed.) Advances in Cryptology – ASIACRYPT 2001. Lecture Notes in Computer Science, vol. 2248, pp. 157–174. Springer (2001) 15. Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient multiparty computations secure against an adaptive adversary. In: Advances in Cryptology – EUROCRYPT ’99. Lecture Notes in Computer Science, vol. 1592, pp. 311–326. Springer (1999) 16. Cramer, R., Damgård, I., Nielsen, J.: Secure Multiparty Computation and Secret Sharing. Cambridge University Press (2015) 17. Dang, Q., Moody, D.: Additional SLH-DSA parameter sets for limited-signature use cases. NIST Special Publication 800-230 (Initial Public Draft), National Institute of Standards and Technology (Apr 2026). https://doi.org/10.6028/NIST. SP.800-230.ipd, https://doi.org/10.6028/NIST.SP.800-230.ipd, initial Public Draft 18. Dolev, D., Strong, R.: Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing 12(4), 656–666 (1983) 19. Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems 2018(1), 238–268 (Feb 2018). https://doi.org/10.13154/tches.v2018.i1.238-268 20. Eternax Labs: SILMARILS implementation repository. https://github.com/ eternax-ai/silmarils-paper (2026), accessed: 2026-04-24 21. Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM Journal on Computing 26(4), 873–933 (1997) 22. Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distributed Computing 1(1), 26–39 (1986) 23. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2), 374–382 (1985) 24. Fitzi, M., Garay, J.A., Maurer, U., Ostrovsky, R.: Minimal complete primitive for secure multi-party computation. Journal of Cryptology 18, 37–61 (2005) 25. Fitzi, M., Gisin, N., Maurer, U., Rotz, O.V.: Unconditional byzantine agreement and multi-party computation secure against dishonest minorities from scratch. In: Advances in Cryptology – EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332, pp. 482–501. Springer (2002) 26. Fitzi, M., Wolf, S., Wullschleger, J.: Pseudo-signatures, broadcast, and multiparty computation from correlated randomness. In: Advances in Cryptology – CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 562–578. Springer (2004) 27. Fitzi, M., Hirt, M., Maurer, U.: Trading correctness for privacy in unconditional multi-party computation. In: Krawczyk, H. (ed.) Advances in Cryptology — CRYPTO 1998. pp. 121–136. Springer Berlin Heidelberg, Berlin, Heidelberg (1998)

30

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng, and Dariia Porechna

28. Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: Falcon: Fast-fourier lattice-based compact signatures over NTRU. https://research.ibm.com/publications/ falcon-fast-fourier-lattice-based-compact-signatures-over-ntru (January 2020), iBM Research 29. Hanaoka, G., Shikata, J., Zheng, Y., Imai, H.: Unconditionally secure digital signature schemes admitting transferability. In: Advances in Cryptology – ASIACRYPT 2000. Lecture Notes in Computer Science, vol. 1976, pp. 130–142. Springer (2000) 30. Iwamura, K., Kamal, A.A.A.M.: Secure user authentication with information theoretic security using secret sharing-based secure computation. IEEE Access 13, 9015–9031 (2025). https://doi.org/10.1109/ACCESS.2025.3526632 31. Jakobsson, M., Sako, K., Impagliazzo, R.: Designated verifier proofs and their applications. In: Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science, vol. 1070, pp. 143–154. Springer (1996) 32. Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Secur. 1(1), 36–63 (Aug 2001). https://doi.org/10.1007/ s102070100002, https://doi.org/10.1007/s102070100002 33. Jonsson, J., Kaliski, B.: Public-key cryptography standards (pkcs) #1: Rsa cryptography specifications version 2.1. RFC 3447, Internet Engineering Task Force (IETF) (Feb 2003), https://datatracker.ietf.org/doc/html/rfc3447 34. Katz, J., Koo, C.Y.: On expected constant-round protocols for byzantine agreement. Journal of Computer and System Sciences 75(2), 91–112 (2009) 35. Krotou, A.: Shamir’s secret sharing (sss) for quantum-safe data storage (October 2025), https://vault12.com/learn/advanced-crypto-security/cryptography/ quantum-safe-data/, vault12 36. Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Transactions on Programming Languages and Systems 4(3), 382–401 (1982) 37. Lamport, L.: Constructing digital signatures from a one way function. Tech. Rep. CSL-98, SRI International, Computer Science Laboratory, Menlo Park, California (Oct 1979), https://lamport.azurewebsites.net/pubs/dig-sig.pdf 38. Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996) 39. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report 44, 114–116 (Jan 1978), https://ui. adsabs.harvard.edu/abs/1978DSNPR..44..114M, provided by the SAO/NASA Astrophysics Data System 40. Merkle, R.: A certified digital signature. In: CRYPTO. pp. 218–238. Springer (1989) 41. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition edn. (2010) 42. Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. Journal of the ACM 27(2), 228–234 (1980) 43. Rabin, M.O.: Randomized Byzantine generals. In: 24th Annual Symposium on Foundations of Computer Science (FOCS). pp. 403–409. IEEE Computer Society (1983) 44. Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (Nov 1979). https://doi.org/10.1145/359168.359176 45. Tyagi, H., Watanabe, S.: Information-theoretic Cryptography. Cambridge University Press (2023) 46. Unruh, D.: Universally composable quantum multi-party computation. In: EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 486–505. Springer (2010). https://doi.org/10.1007/978-3-642-13190-5_25

Title Suppressed Due to Excessive Length

31

47. Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Advances in Cryptology — EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer (2015) 48. Watrous, J.: The Theory of Quantum Information. Cambridge University Press (2018). https://doi.org/10.1017/9781316848142 49. Winter, A.: Tight uniform continuity bounds for quantum entropies. Communications in Mathematical Physics 347(1), 291–313 (2016). https://doi.org/10. 1007/s00220-016-2609-8 50. Zhandry, M.: How to construct quantum random functions. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 679–687 (2012). https://doi.org/10.1109/FOCS.2012.37 51. Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. In: Boldyreva, A., Micciancio, D. (eds.) Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science, vol. 11693, pp. 239–268. Springer (2019)