D EANONYMIZABLE S COPED L INKABLE R ING S IGNATURES
Montassar Naghmouchi
arXiv:2605.11715v1 [cs.CR] 12 May 2026
1
1
and Maryline Laurent
1
SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, 91120 Palaiseau, France
A BSTRACT Although ring signatures offer highly desirable privacy requirements like anonymity and ad-hoc group formation with signer autonomy, they partially lack trust requirements like linkability and accountability that are required for strict use-cases, such as consent management in healthcare. Existing signature schemes fail to natively integrate scoped linkability with decentralized accountability (on-demand deanonymization) in a single scheme without relying on separate commitments or a centralized opener. We therefore introduce Deanonymizable Scoped Linkable Ring Signatures (DSLRS). The originality of the DSLRS is manifold. DSLRS uses ”scopes” (context identifiers) and dynamic key images to provide scoped linkability and unlinkability across different scopes. Decentralized accountability is provided thanks to two ELGamal components deeply embedded in the signature, and a decentralized deanonymization network of k-of-N nodes that can collaboratively extract the signer’s public key. DSLRS scheme is defined and proved under the ECDLP and DDH hardness assumptions in the Random Oracle Model (ROM). Formal security definitions and formal reduction proofs are provided before introducing a blockchain-based instantiation for a consent management application using DSLRS. Keywords: Ring Signatures, Linkability, Accountability, Decentralization, Consent Management, Blockchain
1
Introduction
Ring signatures enable ad-hoc group (ring) formation and allow signers to remain anonymous within a given ring. Intended to be used by whistle-blowers [1], the first ring signatures did not account for the need to link two signatures together, or for the need of accountability, where the identity of the signer needs to be revealed. The absence of a group manager made it even harder to implement such features. Linkable ring signatures provide linkability that extended the use-cases of ring signatures into domains that require detecting double signing, such as e-voting [2], preventing double-spending in blockchains [3], etc. Later on, accountable variants [5] provided revocation of anonymity either on-demand [7] or upon signer misbehavior [6]. This presented further application possibilities for ring signatures, like online anonymous forums and anonymous auctions, or simply introducing accountability to previous use-cases - like holding dishonest whistle-blowers accountable. While previous applications focus on isolated transactions and communications, healthcare applications require strict data governance. Consequently, consent management in healthcare and clinical trials requires high privacy standards combined with accountability. For medical and legal purposes, an anonymous consent giver can be traced back and deanonymized on demand if needed and under specific conditions like the need to re-identify the patient. For such use-case, a signature scheme is required to provide signer indistinguishability to provide anonymity for signers, scoped linkability in order to allow patients to be traced within the same scope (context, like a given research project), cross-scope unlinkability so they remain unlinkable in different contexts and accountability which is ondemand deanonymization to satisfy re-identification needs. Furthermore, to avoid reliance on centralized authorities, decentralized deanonymization is desired. Existing schemes fail to satisfy all criteria simultaneously. We therefore introduce Deanonymizable Scoped Linkable Ring Signatures (DSLRS).
Our contributions are: (1) A new ring signature construction and algorithms that satisfies indistinguishability, scoped linkability, cross-scope unlinkability and embedded decentralized accountability; (2) Formal security definitions and proofs under ECDLP and DDH assumptions in the Random Oracle Model (ROM); (3) A consent management use-case and an effective blockchain instantiation of the proposed scheme. The rest of the paper is structured as follows: Section 2 provides a related work comparison, Section 3 provides an overview and threat model in 3.1, preliminaries and security assumptions in 3.2, scheme definition of DSLRS and the full DSLRS algorithms in Section 3.3. In Section 4 we provide formal definitions of our signature scheme properties using cryptographic game sets. Full reduction proofs are provided in appendix A. In section 5 we present our effective instantiation and use-case: blockchain-based consent management for clinical trials. Finally in Section 6 we conclude the paper.
2
Related works
Ring signatures (RS) originally provided unconditional anonymity for ad-hoc groups without requiring a group manager nor group coordination [1]. LSAG [2] addressed the inability to detect double-signing, extending the use of ring signatures to e-voting applications. LSAG linkability was global and depend on the ring, so the two signatures from the same signer were always linkable within the same ring. MLSAG [4] advanced this scheme by using scopes to break the global linkability and the ring dependence, yielding signatures that are only linkable in a specific scope and that were used for anonymous transactions on blockchain [3]. These linkable RS variants do not provide any accountability for the signers. Fujisaki and Suzuki [6] introduced Traceable RS (TRS). TRS is linkable and uses a ’tag’ (referred to as scope in this paper) that allows the signer’s identity to be revealed mathematically if they sign twice within the same tag and ring. This effectively provides a form of conditional accountability with scoped linkability. Xu and Yung [5] proposed Accountable RS (ARS) that enabled revocation of anonymity via designated trusted opener - or a threshold of openers - but lacked linkability and relies on a trusted dealer to generate and distribute keys. Bootle et al.[7] introduced Short Accountable RS (SARS), in which the signer must encrypt their index within the ring using the public key of an opener and generate a non-interactive zero-knowledge (NIZK) proof to demonstrate it. The NIZK proof is a separate commitment from the signature, and SARS offered no linkability. RS in principle removed the centralization and the need for a group manager traditionally present in group signatures, so introducing a centralized accountability authority would be counter-productive. A clear literature gap in RS schemes is identified: no existing scheme natively integrates scoped linkability and on-demand decentralized accountability. Table 1 summarizes the limitations of existing RS schemes. Table 1: Comparison of linkable ring signatures Schemes Linkability RS [1] None LSAG [2] Global MLSAG [4] Scoped ARS [5] None TRS [6] Scoped SARS [7] None DSLRS (Ours) Scoped N/A for ’Not Applicable’.
3
Ring-Independence N/A No Yes N/A No N/A Yes
Accountability None None None On-Demand Conditional On-Demand On-Demand
Opener N/A N/A N/A Designated / Dealer Mathematical Extraction Centralized Authority Decentralized (Threshold)
Separate Commitment N/A N/A N/A N/A No (Embedded) Yes (External NIZK) No (Embedded)
Defining DSLRS signature scheme
This section formalizes the DSLRS scheme. It specifies the used cryptographic primitives, the threat model, the security assumptions and details the DSLRS algorithms. A comprehensive notation reference table is provided in Table 2.
3.1
Overview
The DSLRS scheme constructs a circular challenge loop denoted as (chi ) using Fiat-Shamir heuristic for each user of R the ring L. Challenges for non-signers use the uniformly random responses (xi , zi ) ← − Zq while the signer computes
2
Table 2: Notations Notations G, G, q (Si , Pi )
L = {P1 , P2 , . . . , PK } L = {P1 , P2 , . . . , Pn } (Snet , Pnet ), {Snet−j }N j=1 N {ωj }N j=1 , {λj }j=1
SID ← − Zq Iscope ∈ G m = {0, 1}∗ σ R
− Zq a← H : {0, 1}∗ − → Zq ∗ Hp : {0, 1}∗ − →G Os (m, Pi , L, SID, P P ) → − σ
Description The EC group G generated from G and of prime order q. A key pair of user i, i ∈ {1, . . . , K}, where Si ∈ Zq ∗ is user i’s secret key (scalar) and Pi ∈ L is the public key computed as Pi = Si · G. Let s be the index of the signer and (Ps , Ss ) their key pair. Global public key registry of K users, K ≥ nmin where nmin is a fixed number representing the smallest possible ring. A ring of n public keys which are sampled by the signer from L, Ps ∈ L, and nmin ≤ n ≤ K. (Snet , Pnet ) is the key pair of the deanonymization network of N nodes. Each participating node j has: a public index ωj , a coefficient λj and a Shamir Q P i secret key share Snet−j , where λj = ki=1,i̸=j ωiω−ω (mod q), Snet = kj=1 λj · j Snet−j (mod q) and Pnet = Snet · G. Identifier of a scope. Key image of the key pair (Ss , Ps ) of the signer for a given scope SID, computed as Iscope = Ss · Hp (Ps ||SID). The message to be signed. The digital signature issued by the signer. a is the uniform random draw of a value from Zq A hash function that maps an arbitrary-length binary input string to a random scalar in Z∗q (in the Random Oracle Model). A hash-to-point function that maps an arbitrary-length binary input string to a random valid point on the subgroup G (in the Random Oracle Model). A signing Oracle that receives a message m, a public key Pi ∈ L, a ring L, a scope identifier SID, and P P , returns a valid signature σ generated using the secret key Si .
their response (xs , zs ) using their secret key to mathematically close the loop. Verification requires a single challenge (provided in the signature, by default ch1 ) and the responses {xi , zi }ni=1 to independently compute challenges and verify the signature. Linkability uses a ”scope” to separate signatures into different contexts, effectively providing scoped linkability and cross-scope unlinkability. This linkability feature is independent from the used ring, as it is based on the scope and the signer’s public key. Accountability is achieved by embedding an ElGamal-encrypted deanonymization tuple (C1 , C2 ) directly into the challenges. Moreover, the extraction of the signer’s identity requires a threshold from a decentralized deanonymization network, and it extracts the public key instead of their index in the ring, making DSLRS ring-independent for accountability too. The deanonymization network runs a Distributed Key Generation (DKG) protocol [8, 9] to generate necessary parameters to achieve decentralized accountability. The security of this scheme and its properties are formally proven under the threat model described below and the security assumptions in Section 3.2. Threat model: We assume a Probabilistic Polynomial-Time (PPT) adversary A that has access to public parameters P P (cf. Section 3.3). We assume A cannot alter the established P P . A is capable of making up to a polynomial number of queries (qH ) to the random hash oracles H and Hp and (qOs ) queries the signing oracle Os . We assume an honest majority in the decentralized deanonymization network composed of N independent nodes. The maximum number of corruptible nodes is c < (k − 1) where k is the network’s secret key reconstruction threshold (cf. N etKeyGen in Section 3.3). 3.2
Preliminaries and assumptions
Let p be a large prime number, Fp the finite field of order p, and E an elliptic curve over Fp denoted as E(Fp ). E(Fp ) is defined by the simplified Weierstrass equation as y 2 = x3 + ax + b (mod p) where a, b ∈ Fp and 4a3 + 27b2 ̸= 0
3
(mod p) [12]. Let G be an element of a large prime order q of E(Fp ). G generates a cyclic subgroup G of E(Fp ), such that G = {k · G | k ∈ Zq } and q · G = O, where O is the identity element of G. The Elliptic Curve Discrete Logarithm Problem (ECDLP) assumption holds relative to G if for any PPT adversary A, the probability of finding x ∈ Zq that satisfies Y = x · G for Y ∈ G is negligible. We note the advantage of A in solving the ECDLP as R ECDLP AdvA = P r[A(G, x · G) = x|x ← − Zq] ≈ 0. The Decisional Diffie-Hellman (DDH) assumption also holds relative to G if for any PPT adversary A, the probability of distinguishing a Diffie-Hellman tuple TDH = (G, a · G, b · G, ab · G) from a random tuple Trandom = (G, a · G, b · R G, c · G) for uniform scalars a, b, c ← − Zq is negligible. We note the advantage of A in solving DDH as R DDH AdvA = |P r[a, b, c ← − Zq, β ← − {0, 1} : A(G, a · G, b · G, ((1 − β)ab + βc) · G) = β] − 21 | ≈ 0. The two hash functions H and Hp are modeled in the Random Oracle Model (ROM). 3.3
DSLRS scheme definition
A DSLRS scheme over a PPT setup Setup is a (Setup, Sign, V erif y, Link, Deanonymize) defined as follows:
tuple
of
polynomial-time
algorithms
• Setup(1λ , N, K, P ) → − N K K N (P P = (G, G, q, H, Hp , {SIDi }P i=1 , Pnet , {ωj }j=1 , L = {Pi }i=1 , nmin ), {Si }i=1 , {Snet−j }j=1 ): Given the security parameter λ, N deanonymization network (opener) nodes, K users, and P contexts, the K full system generates public parameters P P , users’ public keys L = {Pi }K i=1 and private keys {Si }i=1 and N N the network’s public key Pnet and secret key shares {Snet−j }j=1 and public indices {ωj }j=1 , as follows: 1. Generate base parameters {G, G, q, H, Hp , {SIDi }P i=1 , nmin } where authorized in the system. N 2. Execute [N etKeyGen(P P ) → − ({Snet−j }j=1 , Pnet )]. The DKG issues the deanonymization network’s public key Pnet and securely distributes individual secret key shares Snet−j to each node j in the network. Each node j has a public index ωj ∈ P P assigned by N etKeyGen. Based on the Lagrange interpolation and the Shamir Secret Sharing [10], the secret key of the deanonymization netPk work is reconstructed as Snet = j=1 λj · Snet−j (mod q) using k shares (k-of-N threshold), where Qk i (mod q) for node j of the k nodes that respond. The public key is computed as λj = i=1,i̸=j ωiω−ω j Pnet = Snet · G. 3. Execute K times [Gen(P P ) → − (Si , Pi )] for K users. Given P P , Gen(P P ) issues a valid pair of public key (verification key) Pi ∈ G and secret key (signing key) Si ∈ Z∗q for user i, where Pi = Si · G. This initializes the global public key registry L = {P1 , · · · , PK } 1 and associated secret keys {Sj }K j=1 . • Sign(m, Ss , L, SID, P P ) → − σ = (Iscope , L, SID, Pnet , C1 , C2 , ch1 , {xi , zi }ni=1 ): Given a message m, a ring L = {P1 , · · · , Pn } of n ≥ nmin public keys sampled by the signer from L ∈ P P , the secret key Ss of the signer associated with his public key Ps ∈ L, a scope SID and P P , returns either a computed signature σ or ⊥ if the inputs are malformed or Ps ∈ / L. This algorithm computes commitments, responses {xi , zi }ni=1 and challenges {chi }ni=1 for all users in the ring L. • V erif y(m, σ, P P ) → − 1/0: Given a message m, a signature σ and public parameters P P , returns 1 if the signature is valid and 0 otherwise. V erif y uses the input signature containing responses {xi , zi }ni=1 to independently rebuild all challenges {chi }ni=1 . Since challenges are a circular loop that can be verified at any point, this algorithm by default verifies at the index i = 1. • Link(σ1 , m1 , σ2 , m2 , P P ) − → 1/0: Given two signatures σ1 and σ2 , two messages m1 and m2 , and P P , returns 1 if the signatures share the same signer in the same scope and 0 otherwise. After running V erif y on both signatures, this algorithm uses the key images Iscope of both signatures to verify if the signatures were made by the same signer in this scope or not. • Deanonymize(σ, {Dj }kj=1 , P P ) → − Ps : Given a signature σ, the calculated transient decryption shares Dj = Snet−j · C1 from k of N deanonymization network’s nodes and their public indices {ωj }kj=1 ∈ P P , returns the public key of the signer Ps . Deanonymize allows the extraction of Ps from the committed (C1 , C2 ) in the signature σ using P P and the decryption shares of k nodes. 1
This registry can be dynamically updated with a Decentralized Key Registration mechanism as presented in section 5.
4
Algorithm 1 Sign
Algorithm 2 Verify
1: Inputs: m, Ss , L, SID, P P 2: if (Ps ̸∈ L) ∨ (L ̸⊂ L) ∨ (SID ̸∈ {SID}P i=1 ) ∨ (length(L) < nmin ) then 3: return ⊥ 4: end if 5: Iscope = Ss · Hp (Ps ||SID)
1: Inputs: m, σ = (Iscope , L, SID, Pnet , C1 , C2 , ch1 , {xi , zi }n i=1 ), P P 2: if (L ̸⊂ L) ∨ (SID ̸∈ {SID}P i=1 )) ∨ (Pnet ̸∈ P P ) ∨ (length(L) < nmin ∈ P P ) then 3: return 0 4: end if 5: if ((Iscope ∈ / G) ∨ (C1 ∈ / G) ∨ (C2 ∈ / G) then 6: return 0. 7: end if 8: L′1 = x1 · G + ch1 · P1 9: R1′ = x1 · Hp (P1 ||SID) + ch1 · Iscope 10: A′1 = z1 · G − ch1 · C1 11: B1′ = z1 · Pnet − ch1 · (C2 − P1 ) 12: ch′2 = H(m, L, Iscope , SID, C1 , C2 , L′1 , R1′ , A′1 , B1′ ) 13: for i = 2 to n do 14: L′i = xi · G + ch′i · Pi 15: Ri′ = xi · Hp (Pi ||SID) + ch′i · Iscope 16: A′i = zi · G − ch′i · C1 17: Bi′ = zi · Pnet − ch′i · (C2 − Pi ) = 18: ch′(i mod n)+1 H(m, L, Iscope , SID, C1 , C2 , L′i , Ri′ , A′i , Bi′ ) 19: end for 20: if ch′1 == ch1 then 21: return 1 22: end if 23: return 0
R
− Zq 6: r, rdean , rz ← 7: C1 = rdean · G ; C2 = Ps + rdean · Pnet 8: Ls = r · G ; Rs = r · Hp (Ps ||SID) 9: As = rz · G ; Bs = rz · Pnet 10: ch(s (mod n))+1 = H(m, L, Iscope , SID, C1 , C2 , Ls , Rs , As , Bs ) 11: for j = 1 to n − 1, i ← ((s + j − 1) (mod n)) + 1) do R
− Zq xi , zi ← Li = xi · G + chi · Pi Ri = xi · Hp (Pi ||SID) + chi · Iscope Ai = zi · G − chi · C1 Bi = zi · Pnet − chi · (C2 − Pi ) ch(i (mod n))+1 H(m, L, Iscope , SID, C1 , C2 , Li , Ri , Ai , Bi ) 18: end for 19: xs = r − chs · Ss (mod q) 20: zs = rz + chs · rdean (mod q) 21: σ ← (Iscope , L, SID, Pnet , C1 , C2 , ch1 , 22: {xi , zi }n i=1 ) 23: return σ
12: 13: 14: 15: 16: 17:
=
Algorithm 3 Link
Algorithm 4 Deanonymize
1: Inputs: σ1 , m1 , σ2 , m2 , P P 2: if (SIDσ1 ̸= SIDσ2 ) then 3: return 0 4: end if 5: if (V erif y(m1 , σ1 , P P ) ∧ V erif y(m2 , σ2 , P P )) then σ1 σ2 6: if (Iscope == Iscope ) then 7: return 1 8: end if 9: end if 10: return 0
1: Inputs: σ = (Iscope , L, SID, Pnet , C1 , C2 , ch1 , {xi , zi }n i=1 ), {Dj = Snet−j · C1 }kj=1 , P P 2: for j = 1 Q to k do i 3: λj = ki=1,i̸=j ωiω−ω (mod q) j 4: end for P 5: V = kj=1 λj · Dj 6: Ps = C2 − V 7: return Ps
3.4
DSLRS signature evaluation
Let |G| be the size of a point in G and |Zq | the size of a scalar. A DSLRS signature σ = (Iscope , L, SID, Pnet , C1 , C2 , ch1 , {xi , zi }ni=1 ) evaluates in size as: |σ| = (n + 4) · |G| + (2n + 2) · |Zq | Although the ring L can be transmitted to the verifier outside of the signature itself, including it creates faster verification at the cost of signature size. In all cases, the spatial evaluation is |σ| = O(n) linear which is consistent with similar related works even though DSLRS has a bigger signature footprint due to the dual responses {xi , zi }ni=1 . However, avoiding the need for separate commitments and their overhead makes DSLRS more efficient on the long run if we exclude secondary steps like retrieving the public keys of the ring during verification and verifying separate commitments that other works tend to overlook or omit from their complexity evaluation. DSLRS is built to be self-sufficient and self-contained. Assuming a 256-bit curve, the compressed EC point size is |G| = 33 bytes and |Zq | = 32 bytes. The signature size will be |σ| = 97n + 196 bytes, which translates to |σ| ≈ 0.97 KB for a ring of size n = 8, |σ| ≈ 1.74 KB for n = 16 and |σ| ≈ 3.3 KB for n = 32 as examples. The algorithms {Sign, V erif y, Link} have an O(n) computational complexity since they all include construction or reconstruction of challenges for all ring members. Compared to related works like RS[1], LSAG [2], MLAG [4], ARS
5
[5] and TRS [6], DSLRS complexity aligns with this baseline of linear complexity O(n) for standard ring signatures. While SARS [7] has a sub-linear complexity O(log2 n) making DSLRS less efficient in both spatial and computational complexity if compared to it, SARS requires the verification of a separate NIZK proof for accountability, which might also have a sub-linear complexity. Nevertheless, in DSLRS Deanonymize is ring-independent and only depends on the number of the threshold nodes k, making its complexity an O(k) which is an O(1) relative to n. In terms of accountability, the computational complexity and self-sufficient nature of DSLRS is more practical than SARS.
4
Security analysis and proofs
Theorem 1: The DSLRS scheme is perfectly correct, satisfies signer indistinguishability, EUF-CMA unforgeability, scoped linkability, cross-scope unlinkability and accountability under the ECDLP and DDH hardness assumptions in the Random Oracle Model (ROM) (cf. Section 3.2) and the threat model presented in Section 3.1. The full proofs are provided in appendix A. Lemma 1 (Perfect correctness): DSLRS scheme satisfies perfect correctness if:
N λ (P P, {Si }K i=1 , {Snet−j }j=1 ) ← Setup(1 , N, K, P ); σ ← Sign(m, Ss , L, SID, P P ); =1 Pr (∀m ∈ {0, 1}∗ ) ∧ (∀SID ∈ {SIDi }P ) ∧ (∀L ⊆ L) ∧ (∀(S , P )) ∧ (P ∈ L) s s s i=1 V erif y(m, σ, P P ) = 1 ∧ Deanonymize(σ, {Dj }kj=1 , P P ) = Ps Lemma 2 (Signer indistinguishability): The DSLRS scheme satisfies signer indistinguishability if for any PPT adversary A: R N λ (P P, {Si }K − {0, 1}; i=1 , {Snet−j }j=1 ) ← Setup(1 , N, K, P ); b ← (m∗ , SID∗ , L∗ , Pj∗0 , Pj∗1 ) ← AOs (P P ); 1 indist σ ∗ ← Sign(m∗ , Sjb , L∗ , SID∗ , P P ); − AdvA = Pr ′ ∗ 2 ≈0 b ← − A(σ ) = b ∧(L∗ ⊆ L) ∧ ({Pj∗0 , Pj∗1 } ⊆ L∗ ) ∗ ∗ ∗ ∗ ∧((Pj0 , SID ), (Pj1 , SID ) not queried to Os ) Lemma 3 (Unforgeability – EUF-CMA): The DSLRS scheme is existentially unforgeable under chosen-message attacks (EUF-CMA) if for any PPT adversary A: N λ P P, {Si }K i=1 , {Snet−j }j=1 ← Setup(1 , N, K, P ); (m∗ , SID∗ , L∗ , σ ∗ ) ← AOs ,H,Hp (P P ); ! EU F −CM A AdvA = Pr ≈0 (L∗ ⊆ L) ∧ (∀Pi ∈ L∗ , Si is unkown to A) ∧V erif y(m∗ , σ ∗ , P P ) = 1 ∗ ∗ ∗ ∧((m , SID , L ) not queried to Os ) Corollary 1 (Key image attack resistance): The DSLRS unforgeability property holds even if A obtains a valid key image Iscope generated by an honest signer s. Corollary 2 (Key image integrity): The DSLRS scheme guarantees that if a signature σ is valid, the embedded key image Iscope is strictly formed as Ss · Hp (Ps ||SID). Lemma 4 (Scoped-linkability): The DSLRS scheme satisfies scoped-linkability if for any PPT adversary A: N λ P P, {Si }K i=1 , {Snet−j }j=1 ← Setup(1 , N, K, P ); ∗ Os ,H,Hp ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ (P P ); (σ1 , σ2 , m1 , m2 , SID∗ , L1 ,∗L2 , Ps1∗, Ps2 )∗← A ) ∈ L ) ∧ (P ∈ L (P s2 2 s1 1 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∧((m∗1 , Ps1 , P , L , SID ) not queried to O ) , L , SID ), (m SL s 2 1 2 s2 AdvA = Pr ≈0 1) ∧(V erif y(m∗1 , σ1∗ , P P ) = 1) ∧ (V erif y(m∗2 , σ2∗ , P P ) = ! ∗ ∗ ∗ ∗ ∗ ∗ (Ps1 = Ps2 ) ∧ Link(σ1 , m1 , σ2 , m2 , P P ) = 0) ∨ ∧ ∗ ∗ ∗ ∗ ∗ ∗ (Ps1 ̸= Ps2 ) ∧ Link(σ1 , m1 , σ2 , m2 , P P ) = 1) Lemma 5 (Cross-scope unlinkability): The DSLRS scheme provides cross-scope unlinkability if for any PPT adversary A:
6
R λ N ← Setup(1 , N, K, P ); b ← − {0, 1}; , {S } P P, {Si }K net−j j=1 i=1 (m∗ , SID0∗ , SID1∗ , L∗ , Pj∗0 , Pj∗1 ) ← AOs ,H,Hp (P P ); ∗ ∗ ∗ σ1 ← Sign(m , Sj0 , L , SID0 , P P ); 1 ∗ ∗ ∗ σ ← Sign(m , S , L , SID , P P ); CSU 2 j − 1 b AdvA = Pr ′ 2 ≈0 b ← − A(σ , σ ) = b 1 2 ∗ ∗ (SID0 ̸= SID1 ) ∧(L∗ ⊆ L) ∧ ({Pj∗0 , Pj∗1 } ⊆ L) ∧((Pj∗0 , SID1∗ ), (Pj∗1 , SID1∗ ) not queried to Os )
Lemma 6 (Accountability): The DSLRS scheme satisfies accountability if for any PPT adversary A: N λ P P, {Si }K i=1 , {Snet−j }j=1 ← Setup(1 , N, K, P ); (m∗ , SID∗ , L∗ , σ ∗ ) ← AOs (P P, Ss ); ACC ≈0 AdvA = Pr ∗ ∗ ∗ k ∗ (V erif y(m , σ , P P ) = 1) ∧ (Deanonymize(σ , {Dj }j−1 ) = Pf ake ) ∗ ∧(Pf ake ̸= Ps )
Corollary 3 (Non-frameability): The DSLRS scheme satisfies non-frameability if for any PPT adversary A: N λ P P, {Si }K i=1 , {Snet−j }j=1 ← Setup(1 , N, K, P ); (m∗ , SID∗ , L∗ , σ ∗ , Pv∗ ) ← AOs ,H,Hp (P P, Ss ); F RAM E ∗ ∗ ∗ ∗ ∗ ∗ ≈0 AdvA = Pr ) ∧ (V erif y(m , σ , P P ) = 1) ∈ L ) ∧ (P ∈ L ) ∧ (P = ̸ P (P s s v v ∧(Deanonymize(σ ∗ , {Dj }kj−1 ) = Pv∗ ) ∧(m∗ , Pv∗ , SID∗ ) not queried to Os
5
Blockchain-based Consent Management using DSLRS signatures
We leverage a consortium blockchain B (Hyperledger Fabric) maintained by N research organizations (ROs) hereby referred to as ”decentralized deanonymization network”. Application of DKG on a blockchain [11] facilitates the instantiation of the DSLRS signature scheme. We suppose that there is an honest majority of ROs where fewer than k nodes are corrupted, k being the DSLRS deanonymization threshold. 5.1
DSLRS blockchain instantiation
The initialization of the signature system proceeds as follows: 1. Parameter Agreement: The network nodes agree upon and immutably publish on the ledger the public parameters P P = {G, G, q, H, Hp , {SIDi }P i=1 , nmin }. Each SIDi uniquely identifies a research project. SID1 is reserved for key registration. 2. Network Key Generation: the N nodes run N etKeyGen. Pnet and public indices of the nodes {ωj }N j=1 are published on the ledger and appended to P P . Each one of the N nodes securely retains an individual secret key share Snet−j . 3. Smart Contracts Deployment: Network nodes agree on publishing the smart contract ”consent management contract” that uses DSLRS scheme to provide consent management functions as described in 5.2. An additional smart contract is deployed to enable user registration which permits users to publish their public keys. 4. Decentralized Public Key Registration and Proof of Possession (PoP): Users (patients/participants) generate key pairs (Si , Pi ) off-chain. To register Pi to the global registry L, they submit a Schnorr-based Non-Interactive Zero-Knowledge (NIZK) Proof of possession πi = SchnorrSign(Si , mi ) made over mi = H(Pi ||SID1 ) to the user registration contract. The contract verifies that Pi ∈ G ∧ Pi ̸= O ∧ Pi ∈ /L and that SchnorrV erif y(Pi , mi , πi ) = 1 before publishing Pi on the blockchain. Lemma 7: Rogue Key Resistance: A PPT adversary A has a negligible probability in registering a rogue key Progue . Proof in A.7. This instantiation allows users to dynamically update and add public keys to L global registry. Once K ≥ nmin , we can start our decentralized consent management system.
7
5.2
Dynamic Consent Management
We assume consent agreements are negotiated off-chain. Participants generate consent proofs mi , defined as hashes of the concluded consent agreements. These consent proofs are modeled as messages in our system. The Consent Management Contract provides a set of functions {P ublish, Revoke, Deanonymize} for participants. A consent proof on-chain has three states: V ALID, REV OKED and REV EALED. A registered participant samples L a ring of n − 1 public keys from L and appends their registered public Ps to it before executing Sign(m, Ss , L, SID, P P ) to generate a DSLRS signature σ. The participant submits (m, σ) to the P ublish function. The P ublish function executes V erif y(m, σ, P P ) and if it passes, it writes (m, σ) with the status V ALID. To revoke m, a participant executes Sign(′ REV ′ , Ss , L, SID, P P ) to get σ ′ . They later submit (′ REV ′ , σ ′ ) to the Revoke function. Revoke runs Link(σ, m, σ ′ ,′ REV ′ ) and if it passes, it changes the status of (m, σ) to REV OKED and writes the new (′ REV ′ , σ ′ ) as V ALID. If a user wishes to instead update their consent with a new consent agreement and proof m′ , they submit (m′ , σ ′ ) to Revoke which effectively revokes and replaces the old consent. Upon legal or clinical demand, k nodes submit their computed transient decryption shares {Dj = Snet−j · C1 }kj=1 to the consent management contract. It invokes Deanonymize on the published (m, σ), transitions the consent state to REV EALED and publishes the extracted signer’s identity Ps . Coupling this system with an external certification authority, Ps is easily linkable to the true identity of the patient.
6
Conclusions
The DSLRS scheme solves a literature gap by providing a signature scheme with scoped linkability and accountability features. By embedding cryptographic commitments computed using ElGamal encrypted components alongside elements like dynamic key images that change from scope to scope and a network public key resulting from a DKG, the DSLRS signature challenges natively provide decentralized accountability without needing a separate commitment or relying on a trusted opener. Formal security reductions prove that under the ECDLP and DDH assumptions in the ROM model, DSLRS scheme satisfies perfect correctness, signer indistinguishability, EUF-CMA, scoped-linkability, cross-scope unlinkability and accountability. The proposed blockchain instantiation confirms practical use of our proposed system, especially within the proposed use-case which is consent management in clinical trials.
References [1] Rivest, R.L., Shamir, A., Tauman, Y. (2001). How to Leak a Secret. In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_32 [2] Liu, J.K., Wei, V.K., Wong, D.S. (2004). Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds) Information Security and Privacy. ACISP 2004. Lecture Notes in Computer Science, vol 3108. Springer, Berlin, Heidelberg. https://doi.org/10.1007/ 978-3-540-27800-9_28 [3] Monero blockchain https://www.getmonero.org/ [last accessed: 24/02/2026] [4] Shen Noether (2015). Ring Signature Confidential Transactions for Monero. In Cryptology ePrint Archive. https://eprint.iacr.org/2015/1098 [5] Xu, S., Yung, M. (2004). Accountable Ring Signatures: A Smart Card Approach. In: Quisquater, JJ., Paradinas, P., Deswarte, Y., El Kalam, A.A. (eds) Smart Card Research and Advanced Applications VI. IFIP International Federation for Information Processing, vol 153. Springer, Boston, MA. https://doi.org/10.1007/ 1-4020-8147-2_18 [6] Fujisaki, E., Suzuki, K. (2007). Traceable Ring Signature. In: Okamoto, T., Wang, X. (eds) Public Key Cryptography – PKC 2007. PKC 2007. Lecture Notes in Computer Science, vol 4450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71677-8_13 [7] Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., Petit, C. (2015). Short Accountable Ring Signatures Based on DDH. In: Pernul, G., Y A Ryan, P., Weippl, E. (eds) Computer Security – ESORICS 2015. ESORICS 2015. Lecture Notes in Computer Science(), vol 9326. Springer, Cham. https://doi.org/10.1007/ 978-3-319-24174-6_13
8
[8] Gennaro, R., Jarecki, S., Krawczyk, H. et al. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. J Cryptology 20, 51–83 (2007). https://doi.org/10.1007/s00145-006-0347-3 [9] Pedersen, T. P. (1991). A threshold cryptosystem without a trusted party (pp. 522–526). Springer-Verlag. https: //doi.org/10.1007/3-540-46416-6_47 [10] Adi Shamir. (1979). How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. https://doi.org/ 10.1145/359168.359176 [11] Aniket Kate and Pratyay Mukherjee and Pratik Sarkar and Hamza Saleem and Nibesh Shrestha and David Yang. (2026) Scalable Distributed Key Generation for Blockchains. In Cryptology ePrint Archive. https://eprint. iacr.org/2026/072 [12] Daniel R. L. Brown, SEC 1: Elliptic Curve Cryptography (2009). Section 2.2.1 page 6 of 138 https://www. secg.org/sec1-v2.pdf [13] Schnorr Non-interactive Zero-Knowledge Proof https://datatracker.ietf.org/doc/html/rfc8235 [14] Herranz, J., Sáez, G. (2003). Forking Lemmas for Ring Signature Schemes. In: Johansson, T., Maitra, S. (eds) Progress in Cryptology - INDOCRYPT 2003. INDOCRYPT 2003. Lecture Notes in Computer Science, vol 2904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24582-7_20
A
Formal proofs
A.1
Proof of Lemma 1 (Perfect correctness)
Proof for Verify: An honest signer with index s in ring L produces xs , zs ∈ Zq such that the initial commitments can be successfully reconstructed during verification. xs , zz are computed by the signer as xs = r − chs · Ss (mod q) and zs = rz + chs · rdean (mod q). The signer commitments during verification are: • L′s = xs · G + ch′s · Ps = (r − chs · Ss ) · G + ch′s · (Ss · G) = r · G = Ls • Rs′ = xs · Hp (Ps ||SID) + ch′s · Iscope = (r − chs · Ss ) · Hp (Ps ||SID) + ch′s · (Ss · Hp (Ps ||SID)) = r · Hp (Ps ||SID) = Rs • A′s = zs · G − ch′s · C1 = (rz + chs · rdean ) · G − chs · (rdean · G) = rz · G = As • Bs′ = zs · Pnet − ch′s · (C2 − Ps ) = (rz + chs · rdean ) · Pnet − chs · (Ps + rdean · Pnet − Ps ) = rz · Pnet = Bs Reconstructing these four points guarantees that ch′s+1 == chs+1 . This successfully closes the circular challenge loop, ensuring that, at any point, ch′i = chi and ch′1 = ch1 . Proof for Deanonymize: Before the Deanonymize algorithm is executed, k of N deanonymization nodes have to provide their transient decryption share, {Dj = Snet−j · C1 }kj=1 , over C1 using their secret key shares. The Deanonymize algorithm then computes λj (cf. Algorithm 4) based on the public indices {ωj }kj=1 of the k respondent nodes and the following values: Pk Pk Pk V = j=1 λj · Dj = j=1 λj · (Snet−j · C1 ) = j=1 (λj · Snet−j ) · C1 = Snet · C1 C1 = rdean · G ⇒ V = Snet · (rdean · G) = rdean · (Snet · G) = rdean · Pnet C2 = Ps + rdean · Pnet ⇒ C2 − V = Ps + rdean · Pnet − rdean · Pnet = Ps Furthermore, Lemma 6 proves that the output of Deanonymize if a signature is valid can only be Ps . This satisfies the correctness of the Deanonymize algorithm.
A.2
Proof of Lemma 2 (Signer indistinguishability)
{xi , zi }ni=1,i̸=s the non-signer scalars are uniformly chosen randoms from Zq. Their associated commitments (Li , Ri , Ai , Bi ) are all computed using the (xi , zi ) scalars, so they are uniformly distributed points of G. (Ls , Rs , As , Bs ) the signer’s initial commitments are computed directly using the nonces r, rz that are uniformly and randomly chosen from Zq , so they and their corresponding (equal) reconstructed commitments during verification (L′s , Rs′ , A′s , Bs′ ) are all uniformly distributed points of G. As for (xs , zs ), they are generated as xs = r − chs · Ss (mod q) and zs = rz + chs · rdean (mod q). Since the nonces r, rz and rdean are uniformly distributed in Zq, the resulting signer responses are statistically indistinguishable from the rest of the responses.
9
⇒ {xi , zi }ni=1 are uniformly distributed scalars of Zq , and {(Li , Ri , Ai , Bi )}ni=1 are uniformly distributed points of G. ⇒ A has no advantage from the analysis of responses and commitments. The deanonymization components (C1 , C2 ) are standard ElGamal encryption components. They are generated from the nonce rdean uniformly and randomly chosen from Zq as: C1 = rdean · G and C2 = Ps + rdean · Pnet . Since Pnet = Snet · G and C2 contains the signer’s public key masked with rdean · Pnet , for A to determine if b = 0 or ∗ b = 1 in C2 = Pjb + (rdean · Pnet ), they need to tell (G, Snet · G, rdean · G, rdean · Snet · G) from a uniformly random tuple (G, Snet · G, rdean · G, c · G). A has a negligible advantage in this decision under the DDH assumption. Consequently, the mask rdean · Pnet is indistinguishable from a uniformly random point in G. ⇒ A has no advantage from the analysis of (C1 , C2 ). Finally, A was restricted from querying Os for (Pj∗0 , SID∗ ) and (P j1 ∗ , SID∗ ) so the element Iscope in σ ∗ offers no advantage to guessing the signer. indist ⇒ AdvA ≈0
A.3
Proof of Lemma 3 (Unforgeability - EUF-CMA)
EU F −CM A We prove using the Forking Lemma for ring signatures [14] that if A has a non-negligible advantage AdvA ,a simulator B can construct an algorithm utilizing A to solve an instance of the ECDLP with an advantage AdvBECDLP .
Simulator setup: B is presented with an ECDLP challenge. A random point (public key) P ∈ G and the generator G are provided to B that aims to compute S ∈ Z∗q such that P = S · G. B initializes the DSLRS system environment for A: • B selects v ∈ {1, · · · , K} uniformly at random. • B embeds the ECDLP challenge into the global registry L by setting the public key at the chosen index v to the challenge point: Pv = P . The rest of the (K − 1) public keys are generated normally as (Si , Pi ). • B provides A with P P which includes L. • B simulates the hash functions H and Hp as Random Oracles and in a consistent way. B also simulates a signing oracle Os and generates a valid-looking signature for every query (m, L, Pi , SID). Application of the Forking Lemma: B executes A twice on a specific random tape. A is allowed to choose the message m∗ , the scope SID∗ and the ring L∗ ⊂ L. Suppose that Pv ∈ L∗ . A executes in a time t and makes qH queries to the random hash oracle H and qOS queries to the signing oracle Os . B runs A twice: 1. First execution: A outputs a valid forgery σ ∗ for the signer index s and B records all the challenges {chi }ni=1 outputted by the random oracle H. B also records all the internal generated randoms {xi , zi }ni=1 . 2. Second execution (the fork): B restarts A with the same random tape numbers but rewinds and forks (stops) the simulation at a uniformly random query to the random oracle H. Let i∗ ∈ {1, · · · , qH } denote the index of the hash query to the random hash oracle H that determines the signer’s index challenge chs in the forged signature. At this index, B provides a new randomly selected and different challenge ch′s ̸= chs . A outputs a second valid forgery σ ′∗ using the same signer index s. The probability of B forking at i∗ = s is at least q1H . Both signatures σ ∗ and σ ′∗ are valid DSLRS signatures and share the same challenges and randoms (commitments ∗ xi , zi ) up to the fork - all known to B. Using V erif y, B reconstructs at the fork i∗ = s: Lσs = xs · G + chs · Ps ′∗ and Lσs = x′s · G + ch′s · Ps . Equating these: (xs − x′s ) · G = (ch′s − chs ) · Ps and since at the fork ch′s ̸= chs we x −x′ x −x′ have: Ps = ch′s −chs s · G. Since Ps = Ss · G, Ss = chs′ −chs s (mod q) is extracted. The probability that the embedded s s ECDLP challenge index v matches the signer index s chosen by A for the forgery is n1 . According to the General Forking Lemma, the simplified probability that B successfully forces A to produce two EU F CM A 2 related forgeries and extracts the secret key S = Sv is: AdvBECDLP ≥ n1 · q1H · (AdvA ) . 1 1 EU F CM A 2 Under the ECDLP hardness assumption AdvBECDLP ≈ 0 ⇒ n · qH · (AdvA ) ≈ 0. Since both qH and n EU F CM A are bounded integers ⇒ AdvA ≈0
Proof of corollary 1: A submits a forged signature σ ∗ containing an Iscope = Ss · Hp (Ps ||SID) that belongs to a signer s. During verification of σ ∗ using V erif y, the commitment Rs′ = xs · Hp (Ps ||SID) + chs · Iscope must match
10
the initial commitment made during Sign which is Rs = r · Hp (Ps ||SID) (from Lemma 1). This requires A to input the response xs = r − chs · Ss (mod q). Knowledge of Iscope is not enough to compute a valid xs , therefore A cannot produce a valid signature without extracting Ss from Iscope , which is negligible under the ECDLP assumption. ′ Proof of corollary 2: A forges a signature σ ∗ for a scope SID∗ containing a malformed key image Iscope ̸= Ss ·B ·G ∗ ′ ∗ ∗ with B · G = Hp (Ps ||SID ). Let Iscope = A · G. A, B ∈ Zq . During V erif y and since σ is valid, the reconstructed ′ commitment Rs′ = xs · Hp (Ps ||SID∗ ) + chs · Iscope = xs · B · G + chs · A · G must match the initial Rs = ∗ r · Hp (Ps ||SID ) = r · B · G. A must compute xs to satisfy xs · B · G + chs · A · G = r · B · G. Simultaneously, the commitment L′s = xs · G + chs · Ps must match the initial commitment Ls = r · G. A must compute xs to satisfy A xs · G + chs · Ps = r · G. Extracting xs from both expressions: xs = r − chs · Ss = r − chs · B . ⇒ A = Ss · B which ′ ′ means Iscope = A · G = Ss · B · G. This contradicts Iscope ̸= Ss · B · G so we prove that a valid DSLRS signature σ must have a key image formed as Ss · Hp (Ps ||SID).
A.4
Proof of Lemma 4 (Scoped-linkability)
∗ ∗ Case A. Ps1 = Ps2 and Link(σ1∗ , m∗1 , σ2∗ , m∗2 , P P ) = 0: V erif y(m∗1 , σ1∗ , P P ) = 1 and V erif y(m∗2 , σ2∗ , P P ) = 1 σ1∗ σ2∗ ∗ ∗ and Link(σ1 , m1 , σ2∗ , m∗2 , P P ) = 0 so Iscope ̸= Iscope . Since Ps1 = Ps2 and the scope SID∗ is the same for both σ1∗ σ2∗ signatures, Iscope ̸= Iscope holds true only if one of the signatures contains a malformed key image, which contradicts SL Corollary 2. ⇒ AdvA [Case A] ≈ 0 . ∗ ∗ Case B. Ps1 ̸= Ps2 and Link(σ1∗ , m∗1 , σ2∗ , m∗2 , P P ) = 1: Link(σ1∗ , m∗1 , σ2∗ , m∗2 , P P ) = 1, it follows that σ1∗ σ2∗ ∗ ∗ ∗ ∗ Iscope = Iscope . From Corollary 2: Ss1 · Hp (Ps1 ||SID∗ ) = Ss2 · Hp (Ps2 ||SID∗ ). Since Ps1 ̸= Ps2 and Hp ∗ ∗ is modeled as ROM, Hp (Ps1 ||SID∗ ) and Hp (Ps2 ||SID∗ ) are two distinct points in G. Finding a collision so that ∗ ∗ Ss1 · Hp (Ps1 ||SID∗ ) = Ss2 · Hp (Ps2 ||SID∗ ) requires A to find a relationship between two independent points in G, SL which is strictly equivalent to solving ECDLP, which is negligible. ⇒ AdvA [Case B] ≈ 0 SL Finally ⇒ AdvA ≈0
A.5
Proof of Lemma 5 (Cross-scope unlinkability)
We prove that if A has a non-negligible ADVACSU , a simulator B can use A to solve the DDH problem with a nonnegligible advantage. Simulator setup: B is a presented with a DDH challenge tuple (G, a · G, b · G, Z) and must decide if Z = ab · G or Z = c · G (valid tuple or random tuple). Let Pj∗0 = A = a · G and B = b · G. B initializes the DSLRS system environment for A: • B selects two indices u, v ∈ {1, · · · , K} • B sets Pu = A = a · G; a ← − Zq is unknown to B (a is Su ) • B sets Pv = x · G; x ← − Zq is known to B (x is Sv ) • B generates the remaining K − 2 keys normally in L • B provides P P to A. During the learning phase, A chooses Pj∗0 , Pj∗1 and if (Pj∗0 ̸= Pu ) ∨ (Pj∗1 ̸= Pv ); B 2 aborts the simulation. The probability of A picking the right key combination is K·(K−1) ; Suppose A picked ∗ ∗ 2 Pj0 = Pu , Pj1 = Pv . The simulation continues . • B simulates the random oracles H, Hp and programs the following responses: R
– Hp (Pu ||SID0∗ ) = r · G; r ← − Zq known to B ∗ – Hp (Pu ||SID1 ) = B – Hp (Pv ||SID1∗ ) = x−1 · Z; σ1 Signature generation: B generates σ1 for Pu in scope SID0∗ . Iscope is computed as Su · Hp (Pu ||SID0∗ ) = a · r · G = r · A. Since B knows r, A it can successfully compute this without knowing a. The remaining signature items ({Li , Ri , Ai , Bi , xi , zi }ni=1 , C1 , C2 ) are faked by back-patching the random oracle H to correctly close the loop. The 2
B can reduce the number of keys in L to nmin to maximize the chances of A picking the needed keys.
11
simulated components are uniformly distributed and indistinguishable from an honest signer output, as proven in Lemma 2. σ2 B generates σ2 for Pu or Pv in scope SID1∗ . B embeds the DDH challenge in the key image Iscope = Z and simulates the rest of the signature components as it did for σ1 . B provides A with (σ1 , σ2 ) for it to guess b′ = 0 same signer or b′ = 1 different signers. σ2 1. b′ = 0 ⇒ σ2 is evaluated as a valid signature from Pu , the key image is Iscope = Su · Hp (Pu ||SID1∗ ) = ′ a · B = ab · G. If A outputs b = 0, B outputs 1 indicating it is a valid tuple. σ2 2. b′ = 1 ⇒ σ2 is evaluated as a valid signature from Pv , the key image is Iscope = Sv · Hp (Pv ||SID1∗ ) = −1 ′ x · x · Z = Z. If A outputs b = 1, B outputs 0 indicating it is a random tuple. CSU 2 CSU · AdvA . Since AdvBDDH ≈ 0 ⇒ AdvA ≈0 We note AdvBDDH ≥ K(K−1)
A.6
Proof of Lemma 6 (Accountability)
Assume that A generated a valid signature σ ∗ with (C1 , C2 ) using a false identity Pf∗ake where C1 = rdean · G and C2 = Pf∗ake + rdean · Pnet . During V erif y, Bs′ is constructed as Bs′ = zs · Pnet − chs · (C2 − Ps ) ⇒ Bs′ = zs · Pnet − chs · (Pf∗ake + rdean · Pnet − Ps ). Since zs = rz + chs · rdean (mod q) ⇒ Bs′ = (rz + chs · rdean ) · Pnet − chs · (Pf∗ake + rdean · Pnet − Ps ) = rz · Pnet + chs · rdean · Pnet − chs · Pf∗ake − chs · rdean · Pnet + chs · Ps = rz · Pnet − chs · (Pf∗ake − Ps ). Since σ ∗ is valid, the reconstructed commitment Bs′ matches Bs = rz · Pnet . ⇒ rz · Pnet − chs · (Pf∗ake − Ps ) = rz · Pnet ⇒ chs (Pf∗ake − Ps ) = 0. chs ̸= 0 ⇒ (Pf∗ake − Ps ) = 0. A is strictly ACC forced to encapsulate their Ps in C2 ⇒ AdvA ≈0
Proof of corollary 3: Assume A outputs a forged signature σ ∗ to frame a victim Pv∗ ∈ L∗ . Let Pv∗ be set as Pf∗ake defined in Lemma 6. According to lemma 6, A cannot generate a valid signature where Pf∗ake ̸= Ps . A cannot frame a victim without violating the accountability proven in lemma 6. F RAM E ⇒ AdvA ≈0
A.7
Proof of Lemma 7 (Rogue key resistance)
To register a rogue key Progue = P1 − P2 , A is required to submit a valid Schnorr PoP πrogue on mrogue = H(Progue ||SID1 ). This requires A to know Srogue since Schnorr signatures are EUF-CMA. By definition, Progue = P1 − P2 = S1 · G − S2 · G = (S1 − S2 ) · G. Let Srogue = S1 − S2 , it is computationally infeasible for A to compute S1 − S2 under the ECDLP hardness assumption.
12