Track me if you can: Ephemeral coin tracing

Track me if you can: Ephemeral coin tracing Ignacio Amores-Sesar1[0000−0002−1751−1515] , Christian Cachin , Rohit Chatterjee3[0009−0004−1970−1779] , Luiza 1[0000−0002−4766−1506] Soezima , François-Xavier Wicht2[0009−0005−6090−7901] , and Michelle Yeo1,4[0009−0001−3676−4809] 2[0000−0001−8967−9213]

Aarhus University, Denmark {amores-sesar,lbrsoezima}@cs.au.dk 2 University of Bern, Switzerland {christian.cachin,francois-xavier.wicht}@unibe.ch 3 National University of Singapore, Singapore rochat@nus.edu.sg 4 Nanyang Technological University, Singapore michellexyeo@gmail.com

arXiv:2608.09249v1 [cs.CR] 10 Aug 2026

1

Abstract. Privacy-preserving payment systems are well understood, yet their adoption in regulated settings, such as central bank digital currencies (CBDCs), institutional stablecoins, and other compliant payment infrastructures, has been limited by concerns over their potential misuse for illicit activities. Regulators counter financial crime with a toolbox of complementary measures to identify, trace, and stop criminal actors. Tracing is one key tool: acting on outside evidence that a user is implicated in a crime such as money laundering, law enforcement follows the suspect’s funds through the ledger to uncover laundering routes and accomplices. The tracing schemes proposed in the literature, however, grant authorities unbounded capabilities: once initiated, tracing propagates through the transaction graph or persists across all future transactions of a user, and may eventually deanonymize the entire ledger. Only the goodwill of the authority, or the honesty of a committee, keeps surveillance targeted and temporary. We introduce ephemeral coin tracing (ECT), a primitive whose tracing capacity is bounded by construction, both in the number of simultaneously traced users and in the number of hops each trace survives. The authority issues tracing tags that degrade at each hop; after a protocoldefined number of hops, a tag collapses into a value indistinguishable from that of an untagged coin. Within a tracing period the bound is absolute: no authority, however motivated, can follow a tag past its budget. We formalize ECT, define its security and privacy guarantees, and give two constructions, one over exponential ElGamal and one over Damgård– Jurik encryption. Keywords: ephemeral tracing · coin tracing · transaction privacy · digital payment systems

Table of Contents

1

2 3

4

5

6 7 A

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Our contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Cryptographic notions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ephemeral tracing scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Approaches from first principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Nilpotent degradation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Exponential ElGamal instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Damgård–Jurik instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Efficiency and comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Discussion and applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Additional cryptographic notions and security definitions . . . . . . . . . . . . A.1 Public key encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Signature scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Non-interactive zero-knowledge (NIZK) proof system . . . . . . . . . .

3 4 5 6 9 10 10 11 12 13 16 16 16 17 22 26 27 30 34 34 35 36

1

Introduction

Central bank digital currencies (CBDCs) and digital payment systems are rapidly growing in popularity. These payment systems allow users to streamline and automate everyday payments, especially with the widespread adoption of secure digital identities. However, digital payment systems also make financial crimes such as money laundering, terrorist financing, and tax evasion easier to conduct at scale: transactions are fast, cross-border, and can be structured to obscure their origin. To address this, most regulated systems rely on a traditional third-party intermediary to monitor users and audit trails, even though privacy-preserving alternatives have been cryptographically achievable for decades, from Chaum’s ecash [9] to fully decentralized constructions such as Zcash [3]. This wholesale monitoring exposes a lot of unnecessary (and oftentimes private) user activity to regulatory bodies, who might go on to use this data to malicious ends, for instance, selling user data to data-hungry companies or exposing political dissidents and journalists in countries with weak democratic safeguards. A regulator tasked with fighting financial crime does not rely on a single mechanism, but on a toolbox of complementary measures to identify suspects, trace the flow of their funds, and prevent further criminal activity through account freezes, transaction limits, or mandatory disclosure. This work is concerned with one tool in this box: targeted tracing. In a typical investigation, law enforcement first obtains side-channel information implicating a specific user in crimes such as money laundering, for instance a report from a financial intelligence unit, a tip from an informant, or forensic evidence gathered off-ledger. Acting on this suspicion, the authority embeds a tracing tag into the suspect’s funds and follows the tagged funds through the payment system to map out laundering routes and accomplices. Crucially, tracing a suspect under investigation should not come at the price of deanonymizing law-abiding citizens: the overwhelming majority of users are not under investigation and should retain the full privacy guarantees of the underlying ledger. This need is not specific to CBDCs or blockchains. In a traditional banking network with interoperable authenticated payment states, existing monitoring and risk-scoring tools can supply the initial suspicion, while an encrypted tag can follow warranted funds across participating banks without exposing unrelated customers’ transaction histories. Targeted tracing is therefore a prospective investigative layer for payment networks generally, rather than a cryptocurrency-specific mechanism. The coin tracing schemes proposed in the literature [22,25] support such targeted investigations, but grant the authority tracing capabilities that are unbounded : once initiated, surveillance either propagates indefinitely through the transaction graph, affecting potentially all users [22], or continues through all future transactions of a targeted user [25]. Since traceability spreads with the flow of funds, an authority that keeps issuing tags accumulates tracing coverage across the user base and may eventually deanonymize the entire ledger. For ordinary users unlucky enough to be tracked, there is no cryptographic guarantee (apart from the goodwill of the tracing authority) that tracking remains targeted 3

and temporary, and unconstrained surveillance powers can be misused against political dissidents, journalists, or members of other vulnerable populations. A common mitigation is to distribute the tracing capability across a committee: in PEReDi [25] and UTT [34], tracing requires a threshold of committee members to cooperate, so that no single party can trace unilaterally. Distributing trust is valuable, but it bounds who may trace, not how much may be traced: a qualified majority of the committee wields the same unbounded capability as a single authority. The guarantee is thus only as strong as the independence of the committee, and in practice committee seats tend to concentrate in the hands of a few entities, so that the collusion of a couple of them restores unrestricted surveillance. Going further, one could replace the tracing authority altogether by a secure multiparty computation (MPC) [10] of a functionality that enforces the desired bounds. Trust in the authority is then replaced by the security model of the MPC protocol, but running an interactive multiparty computation on the critical path of every transaction imposes computational and communication overhead that is impractical at ledger scale. What is missing is a tracing mechanism whose capacity is bounded by construction: how many users may be traced simultaneously and how far each trace reaches should be fixed by public parameters, and no authority, however motivated, should be able to silently exceed either bound. In this work, we therefore ask the following question: Can we design a simple and efficient protocol that bounds the surveillance capacity of the tracing authority but still allows for targeted tracking of criminal activity? 1.1

Our contribution

We introduce ephemeral coin tracing (ECT), a primitive for targeted tracing with cryptographically enforced expiry. The authority initiates a trace by embedding an encrypted identifier in a suspect’s account. After exactly h hops, the tag collapses to zero and becomes indistinguishable from an untraced tag, even to the authority. Untargeted accounts carry encryptions of zero, so users learn neither whether they are traced nor how much of a tag’s budget remains. The public hop budget h is fixed at setup and cannot be exceeded by the authority. The ledger policy defines what constitutes a hop. It may advance a tag on every outgoing transfer, once per epoch or block-height interval, or only when a transfer satisfies a condition such as a minimum amount. The primitive therefore bounds tracing in policy-defined steps; the deployment determines how costly those steps are to trigger. ECT also bounds tracing breadth. Each target occupies one position in a public base-r encoding, whose capacity is limited by the plaintext modulus. Supporting more identifiers requires larger public parameters and hence larger tags. Fresh tags must be issued and recorded on the ledger, while subsequent tags must follow verified degradation and merge transitions. The hop and capacity 4

bounds are therefore public and auditable. A later warrant may start a new trace, but each issued contribution remains subject to its own hop budget. Transactions may combine tags issued at different times and therefore at different degradation depths. ECT merges them homomorphically while preserving each identifier at its current depth. A positional plaintext encoding separates both identifiers and depths, so an expired contribution vanishes without destroying live contributions. To the best of our knowledge, ECT is the first coin-tracing scheme to handle such merging efficiently. We develop ECT for anonymous account-based payment systems [25,38], where each account carries one encrypted tag. This model bounds tag duplication and requires only an additional encrypted account payload and validation constraints for its transitions. Making evasion costly. A user can clear a possible tag only by triggering enough hops before moving the funds of interest. A policy that counts every transfer would permit cheap “breadcrumb” payments, but minimum amounts, rate limits, or counterparty requirements can make exhaustion consume time, meaningful value, or identified counterparties. During that period the trace remains live, and the evasion pattern may itself justify stronger measures or a newly recorded tag. Acting immediately avoids this delay but risks conducting the incriminating transfer while the tag is active. Implications. ECT challenges the common assumption that an opaque ledger cannot be regulated: targeted, hop-bounded tracing coexists with full transaction privacy for every user not under investigation. Its public parameters make surveillance capacity explicit, allowing legislators and oversight bodies to prescribe and audit bounds that the authority cannot silently widen. The privacyregulation tradeoff thus becomes partly a matter of cryptographic design rather than institutional restraint alone. 1.2

Technical approach

Setup and group structure. Our first construction uses exponential ElGamal [21] in a cyclic group G = ⟨g⟩ of order q h , where q is prime and the public parameter h is the hop budget. The prime-power order is essential: multiplication by q in the exponent is non-invertible and erases all information after h applications. More generally, ECT requires an additively homomorphic encryption scheme with a plaintext ring containing a nilpotent element of index h. Section 5.2 gives this template, and Section 5.4 instantiates it with Damgård–Jurik encryption [15], trading larger tags for polynomial-time tracing and security under the standard decisional composite residuosity assumption. User identifiers and the base-r encoding. User idi receives the plaintext identifier mi = ri−1 , for a base r ≥ 2 satisfying rn < q. Thus each identifier occupies one base-r position and the complete encoding fits within one base-q digit. To trace idi , the authority encrypts mi ; a dummy tag encrypts zero. 5

Degradation via exponentiation. Each degradation raises the ciphertext components to the q-th power, changing an encryption of mq t into one of mq t+1 . The plaintext map m 7→ qm mod q h is nilpotent: after h applications, q h m ≡ 0 (mod q h ). Zero remains zero, so expiry is exact and permanent. Semantic security hides whether a tag contains zero or an identifier and also hides its current depth; the user therefore learns neither its tracing status nor the remaining budget. Merging across identifiers and depths. Multiplying ElGamal ciphertexts adds their plaintexts. Within a depth, the base-r representation separates identifiers: the coefficient at position i − 1 records the multiplicity of idi , and r is chosen to prevent carries. Across depths, the base-q representation provides a second layer of separation. A contribution q t mi occupies digit t, so contributions at different depths coexist without collision. The authority recovers the traced set by reading the base-q digits and then decoding each in base r. Authenticating degradation steps. ECT does not authenticate degradation and merging separately. Instead, the host ledger’s transaction proof asserts that every output tag is the prescribed degradation and merge of the tags bound to the consumed states. Sharing the account-state witnesses prevents tags from being detached, omitted, duplicated, or substituted. The authority signs fresh tags; thereafter, sound transaction proofs preserve their valid derivation. Rerandomization hides the algebraic link between successive tags, while zero knowledge hides the consumed states and transition witnesses. Organization. Section 2 surveys related work, and Section 3 introduces the model and notation. Section 4 defines ECT and its security properties. Section 5 presents the nilpotent template, both instantiations, and their security analysis. Section 6 discusses deployment choices and applications.

2

Related work

Privacy-preserving payment systems and their regulatory extensions have been studied along several lines; we survey the work most closely related to ours. Ecash and regulatory compliance. Building payment systems that are both privacy-preserving and regulatory-compliant has been studied since the origins of ecash, primarily through mechanisms that add auditability at the protocol level. Chaum [9] introduced blind signatures as a foundation for untraceable electronic payments. Sander and Ta-Shma [32] extend this model with auditable anonymous cash, enabling a regulator to verify the total amount in circulation without learning individual transactions. More recent systems operate in permissioned settings: Androulaki et al. [1] design privacy-preserving auditable token payments for permissioned blockchains, and Papadoulis et al. [29] augment the Quisquis [18] scheme with auditability, enabling selective disclosure to regulators without compromising user anonymity. 6

Privacy-preserving collaborative AML. Money-laundering routes frequently cross institutional boundaries, but banks cannot ordinarily pool complete customer and transaction records. Van Egmond et al. [17] address this problem with secure risk propagation: banks jointly propagate account-level risk scores over an interbank transaction network using secure multiparty computation, learning suspicious activity without revealing their underlying records. AMLChain [24] instead combines distributed identities, zero-knowledge proofs, and an auditable ledger to support privacy-preserving identification of suspicious interbank transactions. Effendi and Chattopadhyay [16] use fully homomorphic encryption for collaborative graph-based AML inference across institutional data silos. These approaches privately compute a risk score, classification, or compliance predicate over data already held by several institutions. ECT is complementary: once such an analysis, or conventional off-ledger evidence, identifies a target, ECT prospectively follows the associated funds across participating banks while cryptographically bounding the trace’s hop distance and breadth. It requires the payment rail to carry and validate tags, but avoids running a joint MPC or encrypted inference over the complete interbank graph on the critical path of each payment. Accountable decryption. Making an authority accountable for its tracing is related to the notion of accountable decryption. The concept was introduced by Ryan [31] and later formalized by Li et al. [28,27], who give security definitions and practical instantiations using on-chain logs to record each decryption event. More recent works extend the model to threshold settings, either by requiring collaboration among multiple regulators [41] or by equipping decryptors with self-incriminating proofs that expose rogue behavior [11]. Privacy budget. Rather than adding auditability at the protocol level, privacy budget mechanisms enforce compliance through value thresholds: users may transact anonymously below a set limit, beyond which disclosure to a regulator becomes mandatory. The budget is highly configurable: it can apply per transaction [37] or per period (e.g., weekly or monthly) [35], and it may constrain either outgoing or incoming values [38]. A major limitation is its “one size fits all” approach: a regulatory authority can potentially track all users whose activity exceeds the threshold indefinitely, exposing honest users with high transaction activity (e.g., currency exchanges) to undue surveillance, while requiring detailed knowledge of user behavior to set an accurate threshold. Furthermore, the authority can exploit monetary inflation to bring an ever-growing fraction of users above the threshold over time, effectively expanding surveillance coverage without any explicit policy change. Generalizations of this paradigm support broader conditional disclosure triggers beyond simple value thresholds, yet they follow the same pattern: a zero-knowledge proof certifies compliance with a predicate, and disclosure becomes mandatory upon violation. Coin tracing. Coin tracing schemes allow an authority to mark specific coins or users for surveillance and follow the resulting transaction flow. The idea of 7

endowing an authority with the ability to revoke the anonymity of otherwise untraceable payments goes back to fair e-cash, where one or more trustees can lift anonymity under defined conditions. Stadler et al. [33] introduce fair blind signatures, Brickell et al. [6] and Camenisch et al. [8] add trustee-based tracing to anonymous cash, and Frankel et al. [19] give an efficient off-line construction. These schemes bound who may revoke anonymity but, like the more recent designs below, place no bound on how much may be traced once revocation is triggered. Garman et al. [22] propose a coin tracing mechanism in the unspent transaction output (UTXO) model, where individual coins are explicitly marked for traceability. Each coin embeds a tracing key, and when a traced coin is spent the sender attaches an encrypted record from which the authority recovers the tracing keys of the outputs, so a trace follows the coins forward through the transaction graph. The design targets full-graph investigations, and its scope is correspondingly broad: traceability propagates to every descendant coin until a regulated entity clears it, so a trace has no horizon of its own; a user colluding with the authority can widen the trace, since the user produces the inner ciphertext and the authority the outer one; and the tracing payload grows linearly in the number of inputs. Accountability rests on regulated entities, such as exchanges, that reset the tracing status of coins. Kiayias et al. [25] and Tomescu et al. [34] propose a regulated tracing mechanism with better accountability guarantees based on threshold cryptography. Tracing is initiated by an audit committee and targets a specific user. Upon registration, users receive a secret tracing key, which remains hidden. For each transaction, users produce a pseudorandom tag derived from this key and a transaction counter. The tag is stored as part of the transaction metadata. During tracing, the committee reconstructs these tags incrementally using shares of the tracing secret and checks them against transaction identifiers stored in a distributed ledger. This allows the committee to locate all transactions of the user without revealing the key itself. Cryptographic watermarking. The tag embedding mechanism in ECT is somewhat related to cryptographic watermarking schemes, which embed hidden marks in digital objects that can later be detected by an authorized party, and more broadly to steganography [7], which studies the concealment of information within an innocent-looking carrier. The resemblance stops at the properties we require: a watermark is meant to persist, whereas our tags must merge with one another and expire at a fixed budget. Christ et al. [13] construct undetectable watermarks for language models, but their scheme embeds only a single bit and is single-user, and does not extend to the multi-user setting that merging requires. Of particular note is the work of Cohen et al. [14], which employs a similar scheme in spirit to watermark large language model outputs and extends to the multi-user setting. However, it does not address merging, which is fundamental to our purposes. Zhao et al. [40] survey the broader landscape of watermarking for AI-generated content. Other related cryptographic notions that are known include traitor tracing [12,5,4,39] and traceable signatures of various types [26,20,23]. While these set8

tings share some resemblance regarding the tracing of cryptographic objects, our setting has notable differences. For traitor tracing, the idea is to construct a means to track certain parties that perform some forbidden operation, like decrypting prohibited data. The notions of traceability in signatures are designed around tracing which user actually signed a message in a distributed setting. On the other hand, our setting concerns tracing regular behavior of selected users by default and not around tracing specific aberrant actions by any possible user.

3

Preliminaries $

Notation. For n ∈ N, we use [n] to denote the set {1, . . . , n}. We write x ← − S to denote sampling x uniformly at random from set S. For a function f : N → R, we write f (λ) = negl(λ) to denote that f is negligible in λ, i.e., f (λ) < 1/p(λ) for all polynomials p and sufficiently large λ. We use PPT as a shorthand for probabilistic polynomial time. Positional encoding of multisets. We encode multisets over an index set as integers in a fixed base, so that a multiset can be recovered from the sum of its per-element encodings. This device underlies the merging of tracing tags in our construction, where it is instantiated inside the plaintext ring of the encryption scheme. Definition 1 (Base-r encoding). Let n ∈ N and let r ≥ 2 be an integer. Assign index i ∈ [n] the value mi = ri−1 . For a multiset T overP[n] with multiplicity n function c : [n] → {0, . . . , r − 1}, its encoded sum is vT = i=1 c(i) ri−1 . Since each coefficient c(i) < r, the base-r digits of vT carry no overflow, so vT ≤ rn −1 and vT uniquely determines T . To apply this encoding to tracing tags, we must ensure that merging never makes a coefficient reach the base r, which would create a carry and conflate adjacent identifiers. This follows whenever the payment model bounds how many output states may inherit a contribution from one input state. Lemma 1 (Bounded-fan-out multiplicity). Suppose each transaction copies the contribution of any one input tag into at most d output tags. Then the multiplicity of any identifier at depth t is at most dt . In particular, a tag that remains live only for depths t < h has multiplicity at most dh−1 at any fixed depth. Proof. At depth 0, each identifier has multiplicity one. If its multiplicity is at most dt at depth t, and each occurrence is copied into at most d outputs by the next transition, its multiplicity at depth t + 1 is at most d · dt = dt+1 . The first claim follows by induction; maximizing over the live depths t < h gives the second. ⊓ ⊔ 9

In our two-state account model, d = 2: the sender’s input tag propagates to both the sender’s change state and the recipient’s new state. Hence, its multiplicity is at most 2h−1 . By contrast, an incoming payment carries the recipient’s existing contributions into only one successor state. Thus, only outgoing transfers increase their multiplicity (Section 4). Warrant renewal (Section 3.2) introduces a fresh contribution for an identifier while contributions from earlier issuances may remain live. At ingestion, the account tag is degraded before the fresh contribution is merged. The fresh contribution therefore remains at a strictly smaller depth than any earlier contribution carried by the account. Overlapping issuances consequently occupy distinct base-q digits and do not interfere when merged. Since Trace takes the union of the identifiers decoded at all depths, renewal preserves the tracing signal across successive warrants. 3.1

Cryptographic notions.

ECT relies on additively homomorphic encryption, signatures, and noninteractive zero-knowledge proofs (NIZKs). We use signatures only through correctness and existential unforgeability under chosen-message attacks (EUFCMA), and a NIZK for relation R only through completeness, soundness, and zero knowledge. Appendix A recalls these notions and the underlying encryption security definition. Since the algebraic properties of the encryption scheme drive both merging and degradation, we state them explicitly here. Homomorphic encryption. An additively homomorphic encryption scheme over a message group M consists of PPT algorithms (KeyGen, Enc, Dec, Rerand) satisfying correctness and IND-CPA security. Its ciphertext space is a group under an operation · such that, for ci = Enc(pk, mi ), Dec(sk, c1 · c2 ) = m1 + m2 . Moreover, Rerand(pk, c) returns a fresh encryption of the plaintext in c, realizable as c · Enc(pk, 0), whose distribution is computationally indistinguishable from a fresh encryption of the same message. Additive homomorphism implements tag merging, while rerandomization hides the link between a tag and its degraded successor. 3.2

System model

Ledger and accounts. We consider computationally bounded users, a tracing authority holding sktrace , and a permissioned ledger run by at least 3f + 1 validators tolerating f Byzantine faults. Users enroll with a real-world identity and receive a credential; the authority knows the enrolled identities but cannot link them to ledger states except at system boundaries. Following Platypus [38] and PayOff [2], an account state commits to a balance, an account secret, a tracing tag, and an epoch. A payment consumes the sender’s and recipient’s states and creates two new states, proving membership, correct nullifiers, balance conservation, enrollment, and the prescribed tag transition. Each tag is a ciphertext under the authority’s key, published with and bound to its state. 10

Tag lifecycle. Time is divided into epochs. In each epoch, the authority publishes a signed tag board with one ciphertext per enrolled identity: an encryption of a warrant identifier for an active target and an encryption of zero for everyone else. The board is the only source of fresh tags, and semantic security hides which entries are nonzero. On its first transition in an epoch, an account degrades its tag and merges the board entry bound to its credential. The proof hides which entry is used, and a per-identity, per-epoch nullifier prevents ingesting an entry twice or borrowing another identity’s entry. Degrading before merging keeps contributions from different epochs at distinct depths. Dormant accounts skip ingestion and consume no hop budget. A warrant is renewed by placing another nonzero entry in a later epoch, which the target’s next transition ingests: the warrant governs how long tracing is authorized, while the cryptography bounds how far each contribution propagates. Privacy and adversaries. We assume the host ledger provides confidentiality, unlinkability, and untraceability through hiding commitments and membership proofs over the full state set [25,36]. ECT reveals only what tracing requires: the authority can recognize live tags within their hop window, while dummy and expired tags decrypt to zero; identities are recovered only at system boundaries or through subsequent enforcement. Malicious users may submit malformed transitions, accelerate degradation, probe their status, or collude, but accepted transactions satisfy the ledger statement. A malicious authority cannot introduce tags outside the signed board, follow a contribution beyond h hops, or distinguish more than ⌊logr q⌋ identifier slots without enlarging the public parameters. We exclude out-of-band disclosure of tracing results. The two-state account model bounds tag duplication as required by Lemma 1; Figure 1 illustrates propagation. With this model in place, we are ready to define the ephemeral tracing scheme.

4

Ephemeral tracing scheme

An ephemeral tracing scheme enables controlled tracking of identifiers by embedding cryptographic tracing tags that degrade across hops. What constitutes a hop is not fixed by the primitive, but must be chosen as part of the ledger policy according to the actor being targeted and the desired cost of evasion. A hop may, for example, be triggered by every outgoing transfer, only by a transfer above a minimum amount, once per epoch or block-height interval, or by a transition involving an enrolled counterparty. This choice is consequential: if every transfer consumes a hop unconditionally, a target can cheaply exhaust the tracing budget by splitting funds into small “breadcrumb” payments across many accounts. Amount thresholds, rate limits, or counterparty requirements instead force such evasion to consume time, meaningful value, or identified counterparties (see Section 1.2). Each tag is created with a predefined hop budget, the number of policy-defined degradation steps after which it becomes untraceable, even to the authority. When coins from multiple senders flow to a single 11

Authority

{idA , idC }

{idA , idC , idD }

Tag

{idA , idC , idD } t=1 Degrade

A

A

(0) w A

(0) w C

···

B (2) w B

t=h Degrade

B

(h−1) w B

B (h) w B

C (1) w C Degrade

D

t = h−1

t=2 Degrade

(1) w A Degrade

C

B

{idD }

(0) w D

D

traceable (t < h) (1) w D

expired for A and C (t = h)

Fig. 1. Tag propagation, merging, and expiry, with t counting hops and h the budget. The authority issues tags with Tag, and every outgoing payment applies Degrade to the spent state. At t = 1, A and C pay B, and their degraded tags merge into B’s state; from then on B spends once per step, advancing every contribution it carries. D stays dormant until it pays B at t = 2, so its contribution joins one hop younger and a single tag then carries three identifiers at two depths. The gray boxes give the set returned by Trace. The contributions of A and C reach depth h at t = h and decrypt to zero, while that of D remains recoverable: expiry is per contribution and exact at the budget.

recipient, their tags are merged : the resulting tag encodes all traced identifiers across the inputs, preserving the tracing information of each sender at its current degradation depth. 4.1

Characterization

An ephemeral tracing scheme consists of the following five algorithms: Setup(1λ , n, h, r) → (pp, sktrace ) Takes as input the security parameter λ, the number of identifiers n, the maximum hop budget h, and the encoding base r. Outputs public parameters pp, which fix h publicly, and a tracing secret key sktrace . The public parameters pp are implicit input to the following algorithms. Tag(sktrace , id, b, h′ ) → (w, σ) Takes as input the tracing key, target identifier id, trace flag b ∈ {0, 1}, and a per-tag hop budget h′ ≤ h. Returns a tag w embedding id if b = 1 or zero if b = 0, together with an authority signature σ on w. The tag expires after exactly h′ degradation hops. Degrade(w) → w′ Takes as input a tag w. Returns the tag w′ obtained by applying one degradation step and rerandomizing. Merge(w1 , . . . , wm ) → Q w′ Takes as input a set of tags w1 , . . . , wm . Returns the ′ merged tag w = j wj , which contains the union of the traced identifiers across all inputs. Trace(sktrace , w) → S or ⊥ Takes as input the tracing key and a tag w. Outputs a set S of recovered identifiers, or ⊥ if the coin is untraced (dummy tag) or fully degraded. 12

Figure 2 illustrates how these algorithms are distributed across the three parties. Under the default hop policy, spending a state advances the spender’s tag by one

Authority Setup(1λ )

User

Validator

pp pp

Tag(sktrace , id, b, h′ ) (w, σ)

Degrade(w)

(w′ , π) Verify(w′ , π) → {0, 1}

Merge(w1 , . . . , wm ) w′ w′ (from ledger) Trace(sktrace , w′ ) → S

Fig. 2. Protocol overview: interactions between the authority, users, and validators. The authority runs Setup and Tag (producing (w, σ)) and Trace (requiring sktrace ). Users run Degrade and Merge as part of constructing a payment. Validators run the host ledger’s Verify algorithm on the transaction-validity proof, whose statement includes the tag transition.

hop, while receiving leaves the recipient’s contributions at their current depth. Thus, for input tags wS , wR , the user computes ŵS ← Degrade(wS ) ′ = Merge(ŵS , wR ) to the and assigns wS′ = ŵS to the sender’s change and wR

recipient. Because ŵS carries fresh randomness, the merged tag is itself reran′ is unlinkable to wR without a separate rerandomization step. domized, so wR Charging hops to the spender ties the budget to movements of the traced funds: third parties cannot consume it by sending payments to the target. The onceper-epoch ingestion transition is the single exception; it degrades the account tag before merging the due board entry, keeping contributions from successive epochs at distinct depths (Section 3.2). The ledger statement enforces these transitions and binds them to the hidden account states. This fan-out gives the bound of Lemma 1. 4.2

Security

We now state two correctness conditions and four computational security requirements. These definitions assume that the host transaction proof enforces the composition above with completeness, soundness, and zero knowledge. 13

Trace correctness captures the basic functionality of the scheme: a tag issued for an identifier and degraded within its hop budget must remain recoverable by the authority. Definition 2 (Trace correctness). An ECT scheme satisfies trace correctness if for every identifier id, every per-tag budget h′ ≤ h, and every k < h′ :   (pp, sktrace ) ← Setup(1λ );  (w(0) , σ) ← Tag(sktrace , id, 1, h′ );   ≥ 1 − negl(λ), Pr    w(k) ← Degradek (w(0) ); id ∈ Trace(sktrace , w(k) ) where Degradek (w(0) ) denotes k sequential applications of the Degrade operation. Merge correctness extends trace correctness to the multi-coin setting: after merging, the authority must recover exactly the identifiers whose contributions are still within budget. Expired and dummy contributions must act as neutral elements of merging, vanishing without disturbing live ones. Definition 3 (Merge correctness). An ECT scheme satisfies merge correctness if for every m ∈ N, identifiers id1 , . . . , idm , flags b1 , . . . , bm ∈ {0, 1}, per-tag budgets h′1 , . . . , h′m ≤ h, and degradation counts t1 , . . . , tm ≥ 0, writing L = {i : bi = 1 ∧ ti < h′i } for the live inputs and SL = {idi : i ∈ L} if L ̸= ∅ and SL = ⊥ otherwise:   (pp, sktrace ) ← Setup(1λ );  (w(0) , σi ) ← Tag(sktrace , idi , bi , h′ ), i ∈ [m];  i   i (0)  ≥ 1 − negl(λ), t Pr    wi ← Degrade i (wi ), i ∈ [m];   w′ ← Merge(w , . . . , w ); 1 m ′ Trace(sktrace , w ) = SL (0)

where Degradeti (wi ) denotes ti sequential applications of Degrade. Indistinguishability ensures that a user cannot determine whether their coin carries a traceable or a dummy tag, even given arbitrarily many other tags of its choice. Definition 4 (Indistinguishability). An ECT scheme satisfies indistinguishability if for every PPT adversary A:   (pp, sktrace ) ← Setup(1λ );  (id, h′ ) ← ATag(sktrace , ·, ·, ·) (pp);   $  b ←  1 − {0, 1};  ≤ + negl(λ). Pr   (w, σ) ← Tag(sk ′  2 trace , id, b, h );    b′ ← ATag(sktrace , ·, ·, ·) (w, σ);  b′ = b Ephemeral traceability is the central guarantee of the scheme: once a tag has been degraded beyond its hop budget, the authority irrevocably loses the ability to recover the traced identifier, even in possession of sktrace . 14

Definition 5 (Ephemeral traceability). An ECT scheme satisfies ephemeral traceability if for every identifier id, every per-tag budget h′ ≤ h, and every k ≥ h′ :   (pp, sktrace ) ← Setup(1λ );  (w(0) , σ) ← Tag(sktrace , id, 1, h′ );   ≤ negl(λ), Pr    w(k) ← Degradek (w(0) ); (k) Trace(sktrace , w ) ̸= ⊥ where Degradek (w(0) ) again denotes k sequential applications of Degrade. Unforgeability rules out framing: an adversary cannot derive a tag that traces to an identifier not tagged by the authority. This condition is necessary because public encryption allows anyone to encrypt arbitrary identifiers. A transition history for w∗ records a derivation in which each tag is either issued, with a valid signature under pksig , or produced by a prescribed transition. Under the default policy, these are the payment transition (wS , wR ) 7→ (ŵS , Merge(ŵS , wR )), where ŵS = Degrade(wS ), and the ingestion transition (w, we ) 7→ Merge(Degrade(w), we ) for an issued tag we . Each tag may be consumed at most once, and the final step outputs w∗ . The algorithm Verify(pp, w∗ , H) checks a claimed history given the step randomness: it verifies the signature on every issued tag, recomputes every transition, and confirms that no tag is consumed twice. Ledger-proof soundness and nullifiers ensure that every accepted tag admits a history that Verify accepts, built from entries on signed tag boards; the game below therefore captures the power of a ledger adversary. Definition 6 (Unforgeability). An ECT scheme satisfies unforgeability if for every PPT adversary A, letting Q denote the set of identifiers queried to the Tag oracle with flag b = 1:   (pp, sktrace ) ← Setup(1λ );   (w∗ , H) ← ATag(sktrace , ·, ·, ·) (pp);   ∗  ≤ negl(λ). Pr  Verify(pp, w , H) = 1 ∧     Trace(sktrace , w∗ ) ̸= ⊥ ∧ ∃ id ∈ Trace(sktrace , w∗ ) : id ∈ /Q Unlinkability prevents any party from correlating a tag before and after a degradation step. The game below isolates the protection supplied by rerandomization; in a deployment the host ledger’s zero-knowledge transaction proof additionally hides which committed state was consumed. Definition 7 (Unlinkability). An ECT scheme satisfies unlinkability if for every PPT adversary A:   (pp, sktrace ) ← Setup(1λ );  (w0 , w1 ) ← ATag(sktrace , ·, ·, ·) (pp);   $  b ←  1 − {0, 1};   ≤ + negl(λ). Pr  ′  2  w ← Degrade(wb );   b′ ← A(w , w , w′ );  0 1 ′ b =b 15

Having defined the interface and the security properties of ECT, we now give two constructions that satisfy all six when embedded in a ledger proof satisfying the requirement above.

5

Constructions

Most of the security properties from Section 4.2 can be instantiated with standard building blocks. Unforgeability is anchored by a signature scheme at issuance and propagated by soundness of the host ledger’s transaction proof. Indistinguishability follows from IND-CPA security of the encryption scheme: traced and dummy tags are encryptions of different plaintexts under the same key. Unlinkability of the algebraic operation follows from ciphertext rerandomization; the host ledger’s zero-knowledge proof additionally hides the consumed account states. The difficult property is ephemeral traceability: after exactly h steps, every tag must collapse to the same value as a dummy tag, yet an expired tag must not erase live tracing information when the two are merged. We first examine two natural approaches that each satisfy only one side of this requirement. 5.1

Approaches from first principles

One approach is noisy rerandomization. Each degradation step adds bounded noise δ ∈ [−∆, ∆] to the encoded identifier. Once enough noise has accumulated, decoding fails and Trace returns ⊥ with overwhelming probability. Decoding failure, however, is not the same as expiry. Even after h hops, the decryption of a traced tag remains concentrated around mi ·M , whereas a dummy tag decrypts to zero. The authority can therefore still distinguish expired traced tags from dummy tags, and the tracing window does not close at a sharp threshold. A second approach makes an expired tag look uniformly random. For example, pseudorandom-code constructions add noise from the ambient space until the codeword becomes computationally indistinguishable from uniform and its identifier can no longer be decoded, as in the construction of Cohen et al. [14]. This gives a stronger notion of expiry, but it is incompatible with merging. A uniformly random expired tag is not a neutral element: merging it with a live tag randomizes the result and destroys the live identifier as well. These approaches expose the two requirements that degradation must satisfy simultaneously. Expired tags must become indistinguishable from dummy tags, and they must behave neutrally when merged with tags that remain live. The nilpotent construction below achieves both by making every expired contribution equal to zero. 5.2

Nilpotent degradation

The key conceptual advance in our work is to replace a probabilistic notion of degradation (as in the previous approaches) with an algebraic one, which resolves both sticking points at once. 16

The mechanism is generic and does not depend on a particular encryption scheme. It requires an additively homomorphic encryption scheme whose plaintext ring R contains an element ν that is nilpotent of index h, that is, ν h = 0 but ν h−1 ̸= 0, and for which multiplication of a plaintext by ν is realizable as a public operation on ciphertexts (concretely, raising a ciphertext to a fixed public exponent). A tag is an encryption of an identifier, degradation multiplies the plaintext by ν and then rerandomizes for unlinkability, and merge is homomorphic addition of plaintexts. Two properties follow. First, degradation is nilpotent: the map m 7→ νm drives every plaintext to 0 after exactly h applications and keeps it there, since 0 is a fixed point, so a tag expires at a sharp, budget-defined hop and never revives. Second, merge commutes with degradation: both are homomorphic, so combining tags adds their plaintexts irrespective of degradation depth, and a positional encoding (Definition 1) keeps the contributions separable; the collapse to 0 occurs only once the full budget is consumed, so merging never destroys a live tag. Both properties hold irrespective of who applies the map. Degradation needs no key and no interaction with the authority, so the party that advances a tag is a deployment choice, which we discuss in Section 6. We instantiate this template twice. Over exponential ElGamal (Section 5.3) the plaintext ring is Zqh , the nilpotent element is the prime q (so that q h ≡ 0 in Zqh ), and degradation is the public map c 7→ cq ; this instantiation gives the most compact tags. Over Damgård–Jurik encryption [15] (Section 5.4) the plaintext ring is ZN s , the nilpotent element is the modulus N , of index s, and degradation is c 7→ cN ; setting s = h reproduces the same decay, with the practical advantage that decryption returns the plaintext integer directly, so tracing is polynomial rather than a bounded discrete-logarithm search, and with semantic security resting on DCR rather than on DDH in a prime-power-order group. 5.3

Exponential ElGamal instantiation

Exponential ElGamal gives compact tags and makes tracing expensive as the live traced set grows. It operates over a cyclic group G of order q h , for prime q, rather than the textbook prime-order group; the resulting small plaintext space publicly bounds identifier capacity, but requires a non-standard DDH assumption and fresh parameters for each hop budget. Definition 8 (Prime-power-order group). A cyclic group of prime-power h order q h is a group G = ⟨g⟩ of order q h , where g q = 1 and g k ̸= 1 for all 0 < k < qh . The structural property we use is that exponentiation by q is nilpotent: for any h x ∈ G, applying x 7→ xq exactly h times yields the identity, since xq = 1 for all x ∈ G. This supplies the nilpotent element ν = q of the template of Section 5.2. Definition 9 (DDH in prime-power-order groups). Let G be a cyclic group of order q h with generator g. The Decisional Diffie-Hellman (DDH) assumption holds in G if for all PPT distinguishers D: Pr[D(g, g a , g b , g ab ) = 1] − Pr[D(g, g a , g b , g c ) = 1] ≤ negl(λ) 17

$

where a, b, c ← − Zqh . h−1

This assumption is non-standard. Projection by x 7→ xq maps G onto its order-q subgroup, so prime-order DDH hardness is necessary but does not imply DDH in G; the remaining subgroup chain may expose additional structure. We therefore assume DDH directly in G. Concretely, G may be the order-q h subgroup √ of Z∗p for prime p with q h | p − 1. Pohlig–Hellman [30] costs O(h q), making q ≥ 22λ necessary, though not sufficient, for λ-bit security. Section 5.4 avoids this assumption using DCR. Setup (Alg. 1) generates two key pairs under pp: an ElGamal key pair (pkenc , skenc ) for tag encryption along with a signature key pair (pksig , sksig ) for authenticating freshly issued tags.

Algorithm 1. Setup, exponential ElGamal. Setup(1λ , n, h, r) → (pp, sktrace ) Let r be an integer with r > 2h−1 ; // encoding base, Lemma 1 3 Choose prime q with q > rn and q ≥ 22λ , q ̸= r; 4 Construct cyclic group G of order q h with generator g; 5 (pkenc , skenc ) ← KeyGen(G); 6 (pksig , sksig ) ← SigKeyGen(1λ ); 7 Assign mi ← ri−1 for each user idi , i ∈ [n]; 8 pp ← (G, q, h, n, r, pkenc , pksig ), sktrace ← (skenc , sksig ); 9 return (pp, sktrace );

1

2

The choices made by Setup also make both tracing bounds auditable. When h h−1 ̸= 1 G is realized as a subgroup of Z∗p , the checks q h | p − 1, g q = 1, and g q establish that g has order q h , fixing the hop budget. From the same public parameters, anyone computes the identifier capacity nmax = ⌊logr q⌋, because larger identifiers cross a base-q digit. Increasing either bound requires a larger public group and hence larger tags; assigning several identities to one slot only makes them indistinguishable under Trace. Tag (Alg. 2) realizes budget h′ ≤ h by issuing at depth h − h′ ; b = 0 encrypts zero. The authority signs the ciphertext to anchor its ledger history.

Algorithm 2. Tag issuance, exponential ElGamal. Tag(sktrace , idi , b, h′ ) → (w, σ) ′ 2 m ← q h−h · ri−1 · b ; 3 w ← Enc(pkenc , m); 4 σ ← Sign(sksig , w); 5 return (w, σ);

1

// h′ ≤ h

18

Degrade (Alg. 3) raises both components to q and rerandomizes, implementing m 7→ qm mod q h .

Algorithm 3. Degradation, exponential ElGamal. Degrade(w) → w′ 2 Parse w = (A, B);

1

3 4 5

$

r′ ← − Zq h ; ′ ′
′ w ← Aq · g r , B q · pkrenc ; return w′ ;

Merge (Alg. 4) multiplies ciphertexts component-wise, thereby adding their plaintexts. Its correctness is enforced by the transaction statement.

Algorithm 4. Merging, exponential ElGamal. Merge(w1 ,Q . . . , wm ) → w ′ ′ 2 w ← m j=1 wj ; 3 return w′ ;

1

Trace (Alg. 5) recovers the base-q digits of v ∈ Zqh from the decrypted group element g v : base q separates degradation depths, while base r separates identifiers within each depth. Let I ⊆ [n] be the set of issued identifier slots, let K = |I|, and P split I = I0 ⊔ I1 into two halves. For b ∈ {0, 1}, let Db contain the sums i∈Ib ci ri−1 with 0 ≤ ci ≤ 2h−1 , and let D = D0 + D1 ⊆ Zq . The coefficient bound follows from Lemma 1, and |D| ≤ (2h−1 + 1)K ≤ rK because r > 2h−1 . The digits are recovered one at a time as in Pohlig–Hellman [30]. Let γ = P h−1−t j q h−1 g generate the order-q subgroup and let yt = g j≥t dj q . Then ytq = γ dt t −dt q reveals the next digit, after which yt+1 = yt ·g removes it. Since dt lies in the structured set D, rather than all of Zq , it can be found with a meet-in-the-middle search. Concretely, write dt = e0 + e1 with eb ∈ Db , precompute a table of γ e0 for all choices from the first half, and search the second half for a matching value h−1−t ytq γ −e1 . Splitting the search in this way reduces its cost from enumerating roughly |D| candidates to enumerating roughly |D|1/2 candidates on each side. Overall, tracing costs O(h · rK/2 ) group operations and O(rK/2 ) memory: it is polynomial in h but exponential in K, so a polynomial-time authority requires K = O(log λ). Section 5.4 removes this restriction. On a tag outside the set of valid derivations, the digit search may find no element of D; Trace then returns ⊥. It remains to establish the six properties of Section 4.2 for this instantiation. The algebraic construction relies on DDH in G (Definition 9) and EUF-CMA 19

Algorithm 5. Tracing, exponential ElGamal. Trace(sktrace , w) → S or ⊥ Parse w = (A, B) and set y0 ← B/Askenc ; 3 if y0 = 1 then return ⊥;

1

2

// y0 = g v

h−1

4 5

γ ← gq ; for t = 0, . . . , h − 1 do h−1−t

6

if no d ∈ D satisfies γ d = ytq

7

dt ← the d ∈ D with γ d = ytq

h−1−t

then return ⊥; ;

t

8 9 10

yt+1 ← yt · g −dt q ; P Write dt = i∈I ct,i ri−1 for each t; return S ← {idi : ct,i > 0 for some t};

security of the issuance signature. Its ledger deployment additionally assumes completeness, soundness, and zero knowledge of the host transaction proof for the extended statement described above. Theorem 1 (Trace correctness). For any idi ∈ [n], any per-tag budget h′ ≤ h, and any t < h′ , let w ← Tag(sktrace , idi , 1, h′ ) and w′ be obtained by applying Degrade exactly t times. Then idi ∈ Trace(sktrace , w′ ) with probability 1 − negl(λ). Proof. By the ElGamal homomorphism, raising each ciphertext component to the q-th power multiplies the plaintext by q in Zqh . The tag Tag(sktrace , idi , 1, h′ ) ′ encrypts q h−h ri−1 (issuance depth h − h′ ); after t applications of Degrade it h−h′ +t encrypts q · ri−1 mod q h . Since ri−1 < q (by q > rn ) and h − h′ + t < h for ′ t < h , this value is nonzero. Writing it in base q, the digit at position h − h′ + t is ri−1 and all others are zero; decomposing ri−1 in base r gives a unit coefficient at position i − 1, so Trace returns idi . ⊔ ⊓ Theorem 2 (Merge correctness). For i ∈ [m], let wi ← Tag(sktrace , idi , bi , h′i ), and suppose each wi has been degraded ti ≥ 0 times before merging; write τi = (h − h′i ) + ti for its current depth and let L = {i : bi = 1 ∧ τi < h} be the live inputs. Let w′ ← Merge(w1 , . . . , wm ). Then the merged ciphertext encrypts P τi · mi , and Pr[Trace(sktrace , w′ ) = SL ] ≥ 1 − negl(λ), with SL as in i∈L q Definition 3. Proof. The tag Tag(sktrace , idi , bi , h′i ) is issued at depth h − h′i , so after ti applications of Degrade it encrypts q τi · mi mod q h by the ElGamal homomorphism. For τi ≥ h this value is q τi mi ≡ 0 (mod q h ), so expired inputs, like dummy inputs, contribute nothing. Merging via component-wise multiplication thereP τi fore encrypts v = q · mi (mod q h ). If L = ∅, then v = 0 and Trace i∈L returns ⊥ = SL . Otherwise, for the base-q decomposition P to be collision-free, i−1 it suffices that, at every depth τ , the partial sum dτ = is i∈L: τi =τ κi r less than q, where κi is the multiplicity of idi at depth τ . By Lemma 1 and the choice r > 2h−1 , each κi ≤ 2h−1 < r, so the depth-τ sum is at most 20

Pn

= rn − 1 < q by the constraint q > rn . Hence no base-q carry occurs across depths. Writing v in base q, the digit at position τ is exactly dτ ; since each coefficient κi < r, this is the base-r encoding of the identifiers at depth τ , which by Definition 1 uniquely determines {idi : i ∈ L, τi = τ }. Taking the union over all τ yields SL . ⊔ ⊓ i=1 (r − 1)r

i−1

Theorem 3 (Indistinguishability). Under DDH in G, the ECT scheme satisfies indistinguishability. ′

Proof. Let m1 = q h−h ri−1 and m0 = 0. On input b, Tag encrypts mb and signs the resulting ciphertext. Suppose D distinguishes the two cases with advantage ϵ. Construct an IND-CPA adversary B: on input pkenc , generate an independent signing key pair (pksig , sksig ), answer tagging queries by encrypting under pkenc and signing with sksig , and submit (m1 , m0 ) to the IND-CPA challenger. Upon receiving the challenge ciphertext w, compute σ ← Sign(sksig , w) and forward (w, σ) to D. Since sksig is independent of the IND-CPA challenge, (w, σ) has the same distribution as in the real game. Thus, B achieves advantage ϵ against IND-CPA. By IND-CPA security of ElGamal under DDH in G, ϵ ≤ negl(λ). ⊔ ⊓ Theorem 4 (Ephemeral traceability). The ECT scheme satisfies ephemeral traceability unconditionally. Specifically, for any idi ∈ [n] and any per-tag budget h′ ≤ h, if (w(0) , σ) ← Tag(sktrace , idi , 1, h′ ) and w(k) is obtained by applying Degrade at least h′ times, then Trace(sktrace , w(k) ) = ⊥. Proof. The tag is issued at depth h − h′ , so after h′ applications of Degrade it encrypts q h · mi ≡ 0 (mod q h ), since the group has order q h . As 0 is a fixed point of m 7→ qm mod q h , all further degradations leave the plaintext at 0. Decryption yields 0, so Trace returns ⊥. The argument is information-theoretic; no computational assumption is used. ⊔ ⊓ Theorem 5 (Unforgeability). Under EUF-CMA security of the signature scheme, the ECT scheme satisfies unforgeability. In a ledger deployment, soundness of the host transaction proof and the nullifier mechanism reduce acceptance of a tag to possession of a valid transition history. Proof. Let (w∗ , H) be the adversary’s output with Verify(pp, w∗ , H) = 1. A reduction B against EUF-CMA receives pksig and a signing oracle, generates the encryption key pair itself, and simulates the Tag oracle by encrypting the prescribed plaintext and querying the signing oracle. An issued tag in H that the oracle never produced is a valid forgery, so, except with negligible prob′ ability, every issued tag in H encrypts q h−h ri−1 with idi ∈ Q, or zero. We argue by induction along H that every derived tag encrypts a value of the form P tj ij −1 κ with idij ∈ Q and κj bounded as in Lemma 1: degradation mulj jq r tiplies the plaintext by q, the payment transition copies the degraded sender contribution into at most two outputs while passing the recipient tag through once, and the ingestion step merges one issued contribution at its issuance depth; since H consumes every tag at most once, the multiplicity of a contribution at depth t is at most 2t . By r > 2h−1 no base-r digit carries, and by q > rn no 21

base-q digit carries, so Trace(sktrace , w∗ ) decodes exactly these identifiers; hence every id ∈ Trace(sktrace , w∗ ) lies in Q. ⊔ ⊓ Theorem 6 (Unlinkability). Under the DDH assumption in G, the ECT scheme satisfies unlinkability. In a ledger deployment, zero knowledge of the host transaction proof additionally hides the consumed account states. Proof. Let A be a PPT adversary submitting (w0 , w1 ) and receiving w′ ← Degrade(wb ) for a uniformly random b. A tag parses as a pair of elements h of G, membership being publicly checkable via xq = 1, so we may assume w0 , w1 ∈ G × G. ′
′ Write wb = (Ab , Bb ). Degradation returns w′ = Aqb · g r , Bbq · pkrenc for uniform r′ ∈ Zqh , that is, wb raised componentwise to the q-th power and multiplied ′ ′ by the rerandomization factor (g r , pkrenc ). Construct a distinguisher B for DDH: on challenge (g, X, Y, Z), set pkenc ← X, answer tagging queries by encrypting under X and signing with a self-generated key, sample b, and give A the challenge w′ = (Aqb · Y, Bbq · Z); output 1 if A guesses b. If (g, X, Y, Z) is a Diffie–Hellman ′ ′ tuple, then Y = g r and Z = X r for uniform r′ , and w′ is distributed exactly as Degrade(wb ). If Z is instead uniform, then (Y, Z) is uniform on G × G, so w′ is uniform and independent of b, and A guesses b with probability exactly 1 2 . The advantage of A is therefore bounded by the DDH advantage of B, and Pr[b′ = b] ≤ 21 + negl(λ). ⊔ ⊓ 5.4

Damgård–Jurik instantiation

Damgård–Jurik trades larger tags for a larger plaintext space, polynomial-time tracing, and security under DCR. Its plaintext ring is ZN s , where N is nilpotent of index s, and exponentiating a ciphertext by N multiplies its plaintext by N . s For c = (1 + N )m ρN ,
s s cN = (1 + N )N m ρN ·N = (1 + N )N m (ρN )N = Enc N, N m mod N s ; ρN , so setting s = h gives exact expiry after h hops. Definition 10 (Decisional composite residuosity). Let N = p1 p2 be an RSA modulus and s ≥ 1. The decisional composite residuosity (DCR) assumption holds if for all PPT distinguishers D: s

Pr[D(N, z) = 1] − Pr[D(N, ρN mod N s+1 ) = 1] ≤ negl(λ) $

$

where z ← − Z∗N s+1 and ρ ← − Z∗N s+1 , that is, a uniform element of Z∗N s+1 cannot be distinguished from a uniform N s -th residue. Damgård–Jurik is IND-CPA secure under DCR for every s, with the assumption equivalent to the s = 1 case [15]. We again use mi = ri−1 , choose r > 2h−1 and N > rn , and let base N separate depths. Setup (Alg. 6) samples the modulus and fixes s = h. 22

Algorithm 6. Setup, Damgård–Jurik. Setup(1λ , n, h, r) → (pp, sktrace ) Let r be an integer with r > 2h−1 ; // encoding base, Lemma 1 3 Sample distinct primes p1 , p2 and set N ← p1 p2 , with N > rn and |N | sized for λ-bit factoring security; 4 s←h; // plaintext ring ZN h , ciphertext ring Z∗N h+1 5 pkenc ← N , skenc ← λN = lcm(p1 − 1, p2 − 1); 6 (pksig , sksig ) ← SigKeyGen(1λ ); 7 Assign mi ← ri−1 for each user idi , i ∈ [n]; 8 pp ← (N, h, n, r, pksig ), sktrace ← (skenc , sksig ); 9 return (pp, sktrace );

1

2

The public tag space ZN h+1 exposes the hop budget, while nmax = ⌊logr N ⌋ exposes identifier capacity. Enlarging either bound enlarges every tag. Tag (Alg. 7) issues at depth h − h′ , encrypts zero for a dummy, and signs the resulting ciphertext.

Algorithm 7. Tag issuance, Damgård–Jurik. Tag(sktrace , idi , b, h′ ) → (w, σ) ′ 2 m ← N h−h · ri−1 · b ;

1

3

// h′ ≤ h

$

− Z∗N h+1 ; ρ← h

4 5 6

w ← Enc(N, m) = (1 + N )m ρN mod N h+1 ; σ ← Sign(sksig , w); return (w, σ);

Degrade (Alg. 8) implements m 7→ N m mod N h and rerandomizes with a fresh N h -th residue. Algorithm 8. Degradation, Damgård–Jurik. 1

Degrade(w) → w′

2

ρ← − Z∗N h+1 ;

$

h

3 4

w′ ← wN · ρN mod N h+1 ; return w′ ;

h

In the ledger, the transaction statement enforces w′ = wN ρN mod N h+1 within the transaction composition of Section 4. Merge (Alg. 9) multiplies ciphertexts, adding their plaintexts modulo N h . Trace (Alg. 10) decrypts v directly, then reads base-N depths and base-r identifiers in O(nh) digit operations. The value v = 0 denotes either a dummy 23

Algorithm 9. Merging, Damgård–Jurik. Merge(w1 , . . . , wm ) → w′ Q h+1 ; w′ ← m j=1 wj mod N ′ 3 return w ;

1

2

or an expired tag. A digit dt ≥ rn cannot arise from a valid transition history, and Trace then returns ⊥. Algorithm 10. Tracing, Damgård–Jurik. Trace(sktrace , w) → S or ⊥ v ← Dec(skenc , w) ∈ ZN h ; 3 if v = 0 then return ⊥; P t 4 Write v = h−1 t=0 dt · N in base N ; 5 if dt ≥ rn for some t then return ⊥; 6 foreach t with dt ̸= 0Pdo i−1 7 Decompose dt = n in base r; i=1 ct,i · r 8 St ← {idi : i ∈ [n], ct,i > 0}; S 9 return t St ;

1

2

Security additionally uses EUF-CMA signatures and the completeness, soundness, and zero knowledge of the host transaction proof. Theorem 7 (Trace correctness, Damgård–Jurik). For any idi ∈ [n], any per-tag budget h′ ≤ h, and any t < h′ , let (w, σ) ← Tag(sktrace , idi , 1, h′ ) and let w′ be obtained by applying Degrade exactly t times. Then idi ∈ Trace(sktrace , w′ ) with probability 1 − negl(λ). Proof. Raising a ciphertext to N multiplies the plaintext by N in ZN h , so the tag, ′ ′ which encrypts N h−h ri−1 , encrypts N h−h +t ri−1 mod N h after t degradations. Since ri−1 ≤ rn−1 < N by the constraint N > rn , and h − h′ + t < h, the integer ′ ′ N h−h +t ri−1 is positive and strictly below N h−h +t+1 ≤ N h , hence nonzero in ZN h . Its base-N digit at position h − h′ + t is ri−1 and all other digits vanish; decomposing that digit in base r gives a unit coefficient at position i − 1, so Trace returns idi . ⊓ ⊔ Theorem 8 (Merge correctness, Damgård–Jurik). For i ∈ [m], let wi ← Tag(sktrace , idi , bi , h′i ), and suppose each wi has been degraded ti ≥ 0 times before merging; write τi = (h − h′i ) + ti for its current depth and let L = {i : bi = 1 ∧ τi < h} be the live inputs. Let w′ ← Merge(w1 , . . . , wm ). Then w′ encrypts P τi h i∈L N mi mod N , and Pr[Trace(sktrace , w′ ) = SL ] ≥ 1 − negl(λ), with SL as in Definition 3. 24

Proof. Componentwise multiplication adds plaintexts modulo N h . An input with τi ≥ h contributes N τi mi ≡ 0 (mod N h ), so expired inputs, like dummy inputs, vanish, which gives the statedPvalue v. If L = ∅, then v = 0 and Trace returns ⊥ = SL . Otherwise, let dτ = i∈L: τi =τ κi ri−1 be the contribution at depth τ , where κi is the multiplicity of idi at that Pndepth. By Lemma 1 and the choice r > 2h−1 , each κi ≤ 2h−1 < r, so dτ ≤ i=1 (r − 1)ri−1 = rn − 1 < N by the constraint N > rn . Every depth therefore occupies one base-N digit of v with no carry, and each digit is the base-r encoding of the identifiers at that depth, which by Definition 1 determines them uniquely. Taking the union over τ yields SL . ⊓ ⊔ Theorem 9 (Indistinguishability, Damgård–Jurik). Under DCR (Definition 10), the Damgård–Jurik instantiation satisfies indistinguishability. ′

Proof. A tag issued with b = 1 is Enc(N, N h−h ri−1 ) and a tag issued with b = 0 is Enc(N, 0), so a distinguisher between them yields an IND-CPA adversary. On input the public key N , the adversary B generates an independent signing key pair, answers tagging queries by encrypting under N and signing with sksig , sub′ mits the challenge messages (N h−h ri−1 , 0), signs the challenge ciphertext w with sksig , and forwards (w, σ) to the distinguisher. The signing key is independent of the challenge, so the simulated pair is distributed as in the real game and B inherits the distinguisher’s advantage. Damgård–Jurik is IND-CPA secure under DCR [15], so that advantage is negligible. ⊔ ⊓ Theorem 10 (Ephemeral traceability, Damgård–Jurik). For any idi ∈ [n] and any per-tag budget h′ ≤ h, if (w(0) , σ) ← Tag(sktrace , idi , 1, h′ ) and w(k) is obtained by applying Degrade at least h′ times, then Trace(sktrace , w(k) ) = ⊥. The statement holds unconditionally and for every modulus N . Proof. The tag is issued at depth h − h′ , so after h′ degradations it encrypts N h mi ≡ 0 (mod N h ), and 0 is a fixed point of m 7→ N m mod N h , so every further degradation leaves the plaintext at 0 and Trace returns ⊥. The identity N h ≡ 0 (mod N h ) holds for every integer N , so the argument is informationtheoretic and uses no property of the public parameters beyond the value of h fixed by the ciphertext ring. ⊔ ⊓ Theorem 11 (Unforgeability, Damgård–Jurik). Under EUF-CMA security of the signature scheme, the Damgård–Jurik instantiation satisfies unforgeability. In a ledger deployment, soundness of the host transaction proof and the nullifier mechanism reduce acceptance of a tag to possession of a valid transition history. Proof. As in Theorem 5, a reduction against EUF-CMA simulates the Tag oracle with the signing oracle and its own encryption keys, so every issued tag in a history H accepted by Verify was, except with negligible probability, produced ′ i−1 with idi ∈ Q, or zero. Induction along H by the oracle and encrypts N h−h Pr ∗ shows that w encrypts a sum j κj N tj rij −1 with every idij ∈ Q: degradation 25

multiplies the plaintext by N , the payment transition copies the degraded sender contribution into at most two outputs while passing the recipient tag through once, the ingestion step merges one issued contribution at its issuance depth, and H consumes every tag at most once, so the multiplicities κj obey Lemma 1. With r > 2h−1 and N > rn , no digit carries, so tracing returns only identifiers in Q. ⊓ ⊔ Theorem 12 (Unlinkability, Damgård–Jurik). Under DCR (Definition 10), the Damgård–Jurik instantiation satisfies unlinkability. In a ledger deployment, zero knowledge of the host transaction proof additionally hides the consumed account states. Proof. The adversary submits (w0 , w1 ) and receives w′ ← Degrade(wb ) for a uniform bit b. A tag parses as an element of Z∗N h+1 , membership being publicly checkable via a gcd with N , so we may assume w0 , w1 ∈ Z∗N h+1 . h Degradation returns w′ = wbN ρN mod N h+1 for uniform ρ ∈ Z∗N h+1 . Construct a distinguisher B for DCR with s = h: on challenge (N, z), answer tagging queries by encrypting under N and signing with a self-generated key, sample b, give A the challenge w′ = wbN · z mod N h+1 , and output 1 if A guesses b. If h z = ρN is a random N h -th residue, w′ is distributed exactly as Degrade(wb ). If z is uniform in Z∗N h+1 , then w′ = wbN · z is uniform in Z∗N h+1 and independent of b, since multiplication by the fixed unit wbN permutes the group; A then guesses b with probability exactly 21 . The advantage of A is therefore bounded by the DCR advantage of B, and Pr[b′ = b] ≤ 21 + negl(λ). ⊓ ⊔ 5.5

Efficiency and comparison

Both instantiations implement the same interface; their principal trade-off is between compact tags and scalable tracing. We compare them at 128-bit security and choose the smallest admissible encoding base, r > 2h−1 . Independently of the instantiation, nilpotency index h yields a strict chain M ⊋ νM ⊋ · · · ⊋ ν h M = {0}. Each inclusion reduces the size of the plaintext space by at least a factor of two, so representing all h degradation depths requires at least h bits. Linear growth in the hop budget is therefore inherent to this template, although the constants depend strongly on the underlying ring. An exponential ElGamal tag contains two elements of G ⊆ Z∗p and therefore occupies 2⌈log2 p⌉ bits. Two constraints size it: a base-q digit must hold the base-r encoding of an entire traced set, so q > rn , and G must embed in Z∗p , so q h | p − 1. With h = 10 and a 256-bit q, this gives a 0.75 KB tag and an identifier capacity of nmax = 28. Capacity becomes expensive beyond this point because enlarging q also enlarges p by a factor of h: supporting 341 identifiers requires a roughly 3072-bit q, a prime p of at least 30720 bits, and hence a 7.5 KB tag. Moreover, tracing uses a meet-in-the-middle search costing O(h rK/2 ) group operations for the K identifiers the authority holds live at once (Section 5.3). ElGamal is thus compact only when the traced set is small; its dependence on K, rather than on the capacity nmax , is the limiting factor. Because q h is built 26

into the group order, changing the maximum budget h also requires new public parameters. A Damgård–Jurik tag is a single element modulo N h+1 and occupies (h + 1)⌈log2 N ⌉ bits. For h = 10 and a 3072-bit modulus this is 4.1 KB, about five and a half times the size of the minimal ElGamal tag. In return, the same modulus gives nmax = 341, since capacity depends only on rn < N , and tracing takes O(nh) digit operations regardless of how many identifiers occur in a merged tag. Damgård–Jurik therefore avoids both the exponential search in K and the sharp tag-size increase that ElGamal incurs at larger capacities. The same key also serves different values of h: raising s enlarges the plaintext ring but requires neither a fresh modulus nor a stronger assumption, since DCR for parameter s is equivalent to the case s = 1. This scalability comes with more expensive online arithmetic. Damgård– Jurik operates on (h + 1)⌈log2 N ⌉-bit values, and the direct rerandomization h h ρN uses an h⌈log2 N ⌉-bit exponent. Precomputing ζ = ζ0N and using ζ ρ with $

ρ ← − [0, N ) shortens the online exponent, but restricts the randomness to ⟨ζ⟩ and consequently requires a subgroup variant of DCR. We retain the direct construction so that Theorems 9 and 12 rely on standard DCR as stated. Table 1 collects these trade-offs. Exponential ElGamal is the compact choice for modest hop budgets and few simultaneous traces. Damgård–Jurik is better suited to larger identifier sets and heavily merged tags, and offers polynomialtime tracing under a standard assumption, at the cost of larger tags and more expensive arithmetic. Table 1. The two instantiations of nilpotent degradation, at 128-bit security and r > 2h−1 . Exponential ElGamal Damgård–Jurik Plaintext ring Zqh ZN h Nilpotent element prime q modulus N Degradation c 7→ cq c 7→ cN Digit size (bits) max(2λ, n log2 r) log2 N Tag size (bits) 2 max(3072, h · digit) (h + 1) log2 N Tag size at h = 10 0.75 KB 4.1 KB Capacity nmax 28 341 Trace O(h · rK/2 ) O(nh) Assumption DDH in G (Def. 9) DCR (Def. 10) Changing h fresh parameters same key

6

Discussion and applications

We first discuss how ECT interacts with disclosure and ledger policy, and then outline applications in permissioned payment systems such as central bank digital currencies and regulated stablecoins. These applications combine ECT with 27

institutional measures; the tracing primitive alone neither identifies the current account holder nor authorizes an enforcement action. On disclosure by the authority. Disclosure necessarily removes uncertainty for the identifiers that the authority names. It does not, however, help distinguish the status of an undisclosed challenge identifier, provided that the tracing key is not revealed. Tags are independently randomized encryptions, so auxiliary tagged or dummy samples are exactly what the tagging oracle of Definition 4 provides; a standard hybrid argument then reduces any remaining advantage to Theorem 3 or 9. The same reasoning permits the disclosed list to contain false entries. This observation concerns the cryptographic view only: side information about an investigation may reveal tracing status independently of the tags. Delegating degradation. Degradation uses no secret: it raises a ciphertext to a public exponent and rerandomizes, and both operations are available to any party holding pp. Which party advances a tag is therefore a deployment choice, subject to two conditions. That party must be able to update the structure binding tags to account states, and the ledger must enforce exactly the degradation schedule prescribed by its hop policy. Three deployments illustrate this flexibility. Coin holders degrade their own tags inside the transactions they submit. This is the deployment of Section 3.2, in which a hop is an outgoing transfer. Custodial intermediaries, such as payment service providers or exchanges holding accounts on behalf of their customers, can degrade instead. They already assemble the transactions of those accounts, so the construction is unchanged, and clients with limited resources are relieved of producing the proof. Custody grants no tracing information: the intermediary manipulates ciphertexts under the authority’s key and learns neither whether a tag is real nor how much of its budget remains. Validators can instead degrade every published tag at a fixed block height or once per epoch. If tags and their updates are public, all parties can recompute c 7→ cν , so no zero-knowledge proof of degradation is needed. This changes the budget from transaction hops to ledger epochs and ages dormant accounts as well. It also changes the evasion trade-off: waiting consumes the budget, whereas holder-driven degradation preserves a dormant tag but requires transactions to exhaust it (Section 1.2). Ledger-driven degradation requires a publicly updatable tag structure, unlike the owner-controlled account states of Section 3.2; it is therefore a different ledger model, not merely a parameter choice. Beyond coin tracing. ECT records that a ledger state descends from a tagged identifier; turning that signal into action requires the ledger or operator to associate the state with an account and apply an external policy. Possible responses include freezing the current account, imposing transaction limits, restricting counterparties, or requesting additional records under the applicable legal process. ECT can also support the investigation of structuring by preserving the tagged contribution across splits and merges, but it does not itself classify a transaction pattern as suspicious. These measures are complementary 28

and may be applied only while the tag is traceable, or later on the basis of evidence recorded during that window. Prospective versus retrospective tracing. A central limitation is that ECT is prospective: Trace can recover an identifier only if the authority previously encoded it with b = 1. An untagged contribution may later share a state with tagged funds, but its own origin cannot be recovered retroactively, even with sktrace . This separation limits retrospective mass surveillance. Deployments requiring retrospective tracing need an additional mechanism, for example a distinct account type whose transactions carry an opening trapdoor. Distributing that trapdoor among a threshold committee can prevent unilateral tracing, as in PEReDi [25] and UTT [34]; such a mechanism is complementary to, rather than an extension of, ECT. User-requested protective tracing. A user facing kidnapping, extortion, or account-compromise risk may voluntarily request traceable tags for their holdings. For example, a merchant could request b = 1 with budget h′ = 5 and either announce the protection as a deterrent or keep it hidden using indistinguishability. If the funds are transferred under duress, the authority can inspect subsequent ledger tags and use Trace to recognize descendants of the merchant’s tagged state. Where the ledger links those states to enforceable accounts, an authorized party may then freeze or investigate them. After h′ transaction hops, ECT no longer supplies that tracing signal. Time-bounded regulatory investigation. A court order may authorize prospective tracing of a suspicious account for at most h′ transaction hops. The authority issues tags with h′ ≤ h, after which degradation removes the encoded identifier without requiring the authority to revoke it. This enforces a transactiondistance bound, not a wall-clock deadline; a time-based warrant instead requires the epoch-driven variant above or an additional ledger rule. Privacy budget integration. ECT can be combined with a ledger-enforced privacy budget, such as a zero-knowledge proof that a user’s monthly volume remains below a threshold. Crossing the threshold would trigger a separate policy that obtains an authority-issued traceable tag for the resulting state; implementing this trigger without revealing compliant users requires additional protocol machinery. The budget determines when monitoring begins, while ECT bounds how far the resulting signal propagates. Because tags survive splits and merges, the combination can support investigations of structuring, although detection of the pattern remains outside the ECT primitive. Temporary institutional transparency. Exchanges and custodians may ask the authority to issue traceable tags for designated deposits or withdrawals. The authority’s signature authenticates each initial tag, while indistinguishability hides whether it encodes an identifier. Auditors can then follow the propagation of tagged funds for a bounded number of hops, provided they receive the relevant 29

tracing result and ledger view. This offers bounded transaction-flow accountability; it does not by itself prove solvency or correct custody, which require separate accounting commitments and proofs.

7

Conclusion

We have introduced ephemeral coin tracing (ECT), a cryptographic primitive that provides bounded and accountable surveillance in anonymous payment systems. ECT tags degrade algebraically and expire exactly at a predetermined hop budget h, giving the authority no tracing capability beyond this bound. The mechanism is a nilpotent map on the plaintext ring of an additively homomorphic encryption scheme, applied publicly on ciphertexts; the host ledger’s zero-knowledge transaction statement enforces the complete degrade-and-merge transition while binding tags to hidden account states. We instantiate the algebraic mechanism twice, over a cyclic group of order q h , where multiplication by q in the exponent is nilpotent and tags are most compact, and over Damgård– Jurik encryption, where the modulus plays that role and tracing becomes polynomial under a standard assumption. The public parameters h and n render the authority’s surveillance capacity explicit and auditable, and the indistinguishability property prevents users from determining whether they are being traced. We have demonstrated multiple concrete applications in permissioned payment systems. Our work is an important first step that balances targeted tracing with accountability and privacy guarantees.

References 1. Androulaki, E., Camenisch, J., Caro, A.D., Dubovitskaya, M., Elkhiyaoui, K., Tackmann, B.: Privacy-preserving auditable token payments in a permissioned blockchain system. In: AFT ’20: 2nd ACM Conference on Advances in Financial Technologies, New York, NY, USA, October 21-23, 2020. pp. 255–267. ACM, New York, NY, USA (2020). https://doi.org/10.1145/3419614.3423259, https: //doi.org/10.1145/3419614.3423259 2. Beer, C., Zingg, S., Kostiainen, K., Wüst, K., Capkun, V., Capkun, S.: Payoff: A regulated central bank digital currency with private offline payments. CoRR abs/2408.06956 (2024). https://doi.org/10.48550/ARXIV.2408.06956, https:// doi.org/10.48550/arXiv.2408.06956 3. Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: Decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014. pp. 459–474. IEEE Computer Society, Berkeley, CA, USA (2014). https: //doi.org/10.1109/SP.2014.36, https://doi.org/10.1109/SP.2014.36 4. Boneh, D., Partap, A., Rotem, L.: Accountability for misbehavior in threshold decryption via threshold traitor tracing. In: Reyzin, L., Stebila, D. (eds.) Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII. pp. 317–351. Lecture Notes in Computer Science, Springer, Santa Barbara, CA, USA

30

(2024). https://doi.org/10.1007/978-3-031-68394-7_11, https://doi.org/10.1007/ 978-3-031-68394-7_11 5. Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: EUROCRYPT. pp. 573–592 (2006). https: //doi.org/10.1007/11761679_34, https://doi.org/10.1007/11761679_34 6. Brickell, E.F., Gemmell, P., Kravitz, D.W.: Trustee-based tracing extensions to anonymous cash and the making of anonymous change. In: SODA. pp. 457–466 (1995), http://dl.acm.org/citation.cfm?id=313651.313790 7. Cachin, C.: An information-theoretic model for steganography. In: Aucsmith, D. (ed.) Information Hiding, Second International Workshop, Portland, Oregon, USA, April 14-17, 1998, Proceedings. pp. 306–318. Lecture Notes in Computer Science, Springer, Portland, OR, USA (1998). https://doi.org/10.1007/3-540-49380-8_21, https://doi.org/10.1007/3-540-49380-8_21 8. Camenisch, J., Maurer, U.M., Stadler, M.: Digital payment systems with passive anonymity-revoking trustees. In: ESORICS. pp. 33–43 (1996). https://doi.org/10. 1007/3-540-61770-1_26, https://doi.org/10.1007/3-540-61770-1_26 9. Chaum, D.: Blind signatures for untraceable payments. In: CRYPTO. pp. 199–203 (1982). https://doi.org/10.1007/978-1-4757-0602-4_18, https://doi.org/10.1007/ 978-1-4757-0602-4_18 10. Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC. pp. 11–19 (1988). https://doi.org/10.1145/62212. 62214, https://doi.org/10.1145/62212.62214 11. yu Chiang, J.H., David, B., Frederiksen, T.K., Mondal, A., Yeniaras, E.: Detecting rogue decryption in (threshold) encryption via self-incriminating proofs. Cryptology ePrint Archive, Paper 2024/794 (2024), https://eprint.iacr.org/2024/794 12. Chor, B., Fiat, A., Naor, M., Pinkas, B.: Tracing traitors. IEEE Trans. Inf. Theory 46(3), 893–910 (2000). https://doi.org/10.1109/18.841169, https://doi.org/10. 1109/18.841169 13. Christ, M., Gunn, S., Zamir, O.: Undetectable watermarks for language models. In: Agrawal, S., Roth, A. (eds.) The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada. Proceedings of Machine Learning Research, vol. 247, pp. 1125–1139. PMLR, Edmonton, Canada (2024), https://proceedings.mlr.press/v247/christ24a.html 14. Cohen, A., Hoover, A., Schoenbach, G.: Watermarking language models for many adaptive users. In: Blanton, M., Enck, W., Nita-Rotaru, C. (eds.) IEEE Symposium on Security and Privacy, SP 2025, San Francisco, CA, USA, May 12-15, 2025. pp. 2583–2601. IEEE, San Francisco, CA, USA (2025). https://doi.org/10.1109/ SP61157.2025.00084, https://doi.org/10.1109/SP61157.2025.00084 15. Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In: Public Key Cryptography. pp. 119–136 (2001). https://doi.org/10.1007/3-540-44586-2_9, https://doi.org/10. 1007/3-540-44586-2_9 16. Effendi, F., Chattopadhyay, A.: Privacy-preserving graph-based machine learning with fully homomorphic encryption for collaborative anti-money laundering. In: SPACE. pp. 80–105 (2024). https://doi.org/10.1007/978-3-031-80408-3_6, https: //doi.org/10.1007/978-3-031-80408-3_6 17. van Egmond, M.B., Dunning, V., van den Berg, S., Rooijakkers, T., Sangers, A., Poppe, T., Veldsink, J.: Privacy-preserving anti-money laundering using secure multi-party computation. In: FC (2). pp. 331–349 (2024). https://doi.org/10.1007/ 978-3-031-78679-2_18, https://doi.org/10.1007/978-3-031-78679-2_18

31

18. Fauzi, P., Meiklejohn, S., Mercer, R., Orlandi, C.: Quisquis: A new design for anonymous cryptocurrencies. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I. pp. 649–678. Lecture Notes in Computer Science, Springer, Kobe, Japan (2019). https://doi.org/10.1007/978-3-030-34578-5_ 23, https://doi.org/10.1007/978-3-030-34578-5_23 19. Frankel, Y., Tsiounis, Y., Yung, M.: "indirect discourse proof": Achieving efficient fair off-line e-cash. In: ASIACRYPT. pp. 286–300 (1996). https://doi.org/10.1007/ BFb0034855, https://doi.org/10.1007/BFb0034855 20. Fujisaki, E.: Sub-linear size traceable ring signatures without random oracles. In: Kiayias, A. (ed.) Topics in Cryptology - CT-RSA 2011 - The Cryptographers’ Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6558, pp. 393–415. Springer, San Francisco, CA, USA (2011). https://doi.org/10.1007/978-3-642-19074-2_25 21. Gamal, T.E.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985). https://doi.org/10. 1109/TIT.1985.1057074, https://doi.org/10.1109/TIT.1985.1057074 22. Garman, C., Green, M., Miers, I.: Accountable privacy for decentralized anonymous payments. In: Grossklags, J., Preneel, B. (eds.) Financial Cryptography and Data Security - 20th International Conference, FC 2016, Christ Church, Barbados, February 22-26, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9603, pp. 81–98. Springer, Christ Church, Barbados (2016). https://doi. org/10.1007/978-3-662-54970-4_5, https://doi.org/10.1007/978-3-662-54970-4_5 23. Ghadafi, E.: Efficient distributed tag-based encryption and its application to group signatures with efficient distributed traceability. In: Progress in Cryptology - LATINCRYPT 2014 - Third International Conference on Cryptology and Information Security in Latin America, Florianópolis, Brazil, September 17-19, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8895, pp. 327–347. Springer, Florianópolis, Brazil (2015). https://doi.org/10. 1007/978-3-319-16295-9_18 24. He, Y., Chen, J.: AMLChain: Supporting anti-money laundering, privacypreserving, auditable distributed ledger. In: EISA. pp. 50–67 (2021). https://doi. org/10.1007/978-3-030-93956-4_4, https://doi.org/10.1007/978-3-030-93956-4_4 25. Kiayias, A., Kohlweiss, M., Sarencheh, A.: Peredi: Privacy-enhanced, regulated and distributed central bank digital currencies. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 711, 2022. pp. 1739–1752. ACM, Los Angeles, CA, USA (2022). https://doi.org/10. 1145/3548606.3560707, https://doi.org/10.1145/3548606.3560707 26. Kiayias, A., Tsiounis, Y., Yung, M.: Traceable signatures. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3027, pp. 571–589. Springer, Interlaken, Switzerland (2004). https: //doi.org/10.1007/978-3-540-24676-3_34 27. Li, R., Li, Y., Wang, Q., Duan, S., Wang, Q., Ryan, M.: Accountable decryption made formal and practical. IACR Cryptol. ePrint Arch. p. 1519 (2023), https: //eprint.iacr.org/2023/1519

32

28. Li, R., Wang, Q., Liu, F., Wang, Q., Galindo, D.: An accountable decryption system based on privacy-preserving smart contracts. In: Susilo, W., Deng, R.H., Guo, F., Li, Y., Intan, R. (eds.) Information Security - 23rd International Conference, ISC 2020, Bali, Indonesia, December 16-18, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12472, pp. 372–390. Springer, Bali, Indonesia (2020). https://doi.org/10.1007/978-3-030-62974-8_21, https://doi.org/10.1007/ 978-3-030-62974-8_21 29. Papadoulis, G., Balla, D., Grontas, P., Pagourtzis, A.: AQQUA: Augmenting quisquis with auditability. Cryptology ePrint Archive, Paper 2024/1181 (2024). https://doi.org/10.1007/978-3-031-95764-2, https://eprint.iacr.org/2024/1181 30. Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over gf(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978). https://doi.org/10.1109/TIT.1978.1055817, https:// doi.org/10.1109/TIT.1978.1055817 31. Ryan, M.D.: Making decryption accountable. In: Stajano, F., Anderson, J., Christianson, B., Matyás, V. (eds.) Security Protocols XXV - 25th International Workshop, Cambridge, UK, March 20-22, 2017, Revised Selected Papers. pp. 93–98. Lecture Notes in Computer Science, Springer, Cambridge, UK (2017). https://doi.org/ 10.1007/978-3-319-71075-4_11, https://doi.org/10.1007/978-3-319-71075-4_11 32. Sander, T., Ta-Shma, A.: Auditable, anonymous electronic cash extended abstract. In: Wiener, M.J. (ed.) Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1666, pp. 555–572. Springer, Santa Barbara, CA, USA (1999). https://doi.org/10.1007/ 3-540-48405-1_35, https://doi.org/10.1007/3-540-48405-1_35 33. Stadler, M., Piveteau, J.M., Camenisch, J.: Fair blind signatures. In: EUROCRYPT. pp. 209–219 (1995). https://doi.org/10.1007/3-540-49264-X_17, https: //doi.org/10.1007/3-540-49264-X_17 34. Tomescu, A., Bhat, A., Applebaum, B., Abraham, I., Gueta, G., Pinkas, B., Yanai, A.: UTT: Decentralized ecash with accountable privacy. Cryptology ePrint Archive, Paper 2022/452 (2022), https://eprint.iacr.org/2022/452 35. Tomescu, A., Bhat, A., Applebaum, B., Abraham, I., Gueta, G., Pinkas, B., Yanai, A.: UTT: Decentralized ecash with accountable privacy. Cryptology ePrint Archive, Paper 2022/452 (2022), https://eprint.iacr.org/2022/452 36. Wicht, F., Wang, Z., Le, D.V., Cachin, C.: A transaction-level model for blockchain privacy. In: Clark, J., Shi, E. (eds.) Financial Cryptography and Data Security - 28th International Conference, FC 2024, Willemstad, Curaçao, March 48, 2024, Revised Selected Papers, Part II. pp. 293–310. Lecture Notes in Computer Science, Springer, Willemstad, Curaçao (2024). https://doi.org/10.1007/ 978-3-031-78679-2_16, https://doi.org/10.1007/978-3-031-78679-2_16 37. Wüst, K., Kostiainen, K., Capkun, V., Capkun, S.: Prcash: Fast, private and regulated transactions for digital currencies. In: Goldberg, I., Moore, T. (eds.) Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers. Lecture Notes in Computer Science, vol. 11598, pp. 158–178. Springer, Frigate Bay, St. Kitts and Nevis (2019). https://doi.org/10.1007/978-3-030-32101-7_11, https://doi.org/10.1007/978-3-030-32101-7_11 38. Wüst, K., Kostiainen, K., Delius, N., Capkun, S.: Platypus: A central bank digital currency with unlinkable transactions and privacy-preserving regulation. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) Proceedings of the 2022 ACM

33

SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022. pp. 2947–2960. ACM, Los Angeles, CA, USA (2022). https://doi.org/10.1145/3548606.3560617, https://doi.org/10.1145/ 3548606.3560617 39. Zhandry, M.: Optimal traitor tracing from pairings. In: Fehr, S., Fouque, P. (eds.) Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part III. pp. 305–335. Lecture Notes in Computer Science, Springer, Madrid, Spain (2025). https://doi.org/10.1007/ 978-3-031-91131-6_11, https://doi.org/10.1007/978-3-031-91131-6_11 40. Zhao, X., Gunn, S., Christ, M., Fairoze, J., Fábrega, A., Carlini, N., Garg, S., Hong, S., Nasr, M., Tramèr, F., Jha, S., Li, L., Wang, Y., Song, D.: Sok: Watermarking for ai-generated content. In: Blanton, M., Enck, W., Nita-Rotaru, C. (eds.) IEEE Symposium on Security and Privacy, SP 2025, San Francisco, CA, USA, May 1215, 2025. pp. 2621–2639. IEEE, San Francisco, CA, USA (2025). https://doi.org/ 10.1109/SP61157.2025.00178, https://doi.org/10.1109/SP61157.2025.00178 41. Zhaolu, T., Wan, Z., Wang, H.: Division of regulatory power: Collaborative regulation for privacy-preserving blockchains. IEEE Trans. Inf. Forensics Secur. 19, 2533–2548 (2024). https://doi.org/10.1109/TIFS.2023.3348268, https://doi.org/ 10.1109/TIFS.2023.3348268

A

Additional cryptographic notions and security definitions

A.1

Public key encryption

Here, we recall public key encryption and IND-CPA security. Definition 11 (Public key encryption scheme). A public key encryption scheme over a message space M with security parameter 1λ is a tuple of 3 PPT algorithms (KeyGen, Enc, Dec) such that – KeyGen(1λ ) → (pk, sk) generates a public/secret key pair. – Enc(pk, m) → c encrypts message m ∈ M to ciphertext c. – Dec(sk, c) → m decrypts ciphertext c to message m or ⊥. We require correctness, i.e., for all λ ∈ N, (pk, sk) ← KeyGen(1λ ) and m ∈ M, Pr[Dec(sk, Enc(pk, m)) = m] = 1. We further require that our public-key encryption scheme is IND-CPA secure against computationally bounded adversaries. IND-CPA security is defined by the following indistinguishability game between an adversary A and challenger C. IND-CPA indistinguishability game PubKcpa A,Π (λ). 1. C samples (pk, sk) ← KeyGen(1λ ). 2. A gets oracle access to Enc(pk, ·). It outputs a pair of messages (m0 , m1 ) of the same length and sends them to C. 34

3. C samples a uniform random bit b ∈ {0, 1}, and computes the challenge ciphertext c∗ = Enc(pk, mb ). C sends the challenge ciphertext c∗ to A. 4. A outputs a guess bit b′ . The output of the game is 1 if b′ = b and 0 otherwise. Definition 12 (IND-CPA security). A public key encryption scheme Π = (KeyGen, Enc, Dec) is IND-CPA secure if for every PPT adversary A, there exists a negligible function negl such that Pr[PubKcpa A,Π (λ) = 1] ≤ A.2

1 + negl(λ). 2

Signature scheme

Here, we recall signature schemes and EUF-CMA security. Definition 13 (Signature scheme). A (digital) signature scheme over a message space M with security parameter 1λ is a tuple of 3 PPT algorithms (KeyGen, Sign, Ver) such that – KeyGen(1λ ) → (pk, sk) generates a public/secret key pair. – Sign(sk, m) → σ signs a message m ∈ M to output a signature σ. – Ver(pk, m, σ) → b takes as input a public key pk, a message m, and a signature σ and outputs a bit b representing if the σ is a valid signature on m or not. We require correctness, i.e., for all λ ∈ N, (pk, sk) ← KeyGen(1λ ) and m ∈ M, Pr[Ver(pk, m, Sign(sk, m)) = 1] = 1. We further require that our signature scheme is EUF-CMA secure against computationally bounded adversaries. EUF-CMA security is defined by the following indistinguishability game between an adversary A and challenger C. EUF-CMA indistinguishability game SigForgeEUF−CMA (λ). A,Σ 1. C samples (pk, sk) ← KeyGen(1λ ). 2. A receives pk and gets oracle access to Sign(sk, ·). A can repeatedly query the signing oracle Sign(sk, ·) with messages (m1 , . . . , mQ ) of its choosing to get signatures (σ1 , . . . , σQ ). 3. A now outputs a new message and signature pair (m∗ , σ ∗ ) such that m∗ ∈ / (m1 , . . . , mQ ), and sends (m∗ , σ ∗ ) to C. 4. The output of the game is 1 if Ver(pk, m∗ , σ ∗ ) = 1 and m∗ ∈ / (m1 , . . . , mQ ), and 0 otherwise. Definition 14 (EUF-CMA security). A signature scheme Σ = (KeyGen, Sign, Ver) is EUF-CMA secure if for every PPT adversary A, there exists a negligible function negl such that Pr[SigForgeEUF−CMA (λ) = 1] ≤ negl(λ). A,Σ 35

A.3

Non-interactive zero-knowledge (NIZK) proof system

We recall NIZK proof systems and their security. Definition 15 (NIZK proof system). A pair of PPT algorithms (P, V) with security parameter λ is a NIZK proof system for an NP relation R if there exists some polynomial poly such that 1. (Completeness.) For x ∈ R ∩ {0, 1}λ , and all witnesses w for x, Pr[r ← {0, 1}poly(λ) ; π ← P(r, x, w); V(r, x, π) = 1] ≥ 1 − negl(λ). 2. (Soundness.) For all x ∈ {0, 1}λ \ R, and for all algorithms P ∗ : Pr[r ← {0, 1}poly(λ) ; π ← P ∗ (r, x); V(r, x, π) = 1] ≤ negl(λ). 3. (Zero-knowledge.) There exists a PPT algorithm Sim such that for any x ∈ R ∩ {0, 1}λ and any witness w for x, the following ensembles of random variables are computationally indistinguishable: (1) {r ← {0, 1}poly(λ) ; π ← P(r, x, w)}λ (2) {(r, π) ← Sim(x)}λ

36

Related documents

• Octadrachm (Coin) Portraying Arsinoe II#667613
• Presenting power to the people: a quantitative analysis of the late Roman base-metal coinage and its political messages (284-450)#474145
• The Clue of the Gold Coin#57296
• Scaling Verification of Cryptographic Software with Aeneas, Rust, and Lean#1109628
• Tetradrachm (Coin) Depicting the God Apollo Gryneios#632663