Defining Purpose-Limited Secrets

arXiv:2610.10010v1 [cs.CR] 7 Oct 2026

Defining Purpose-Limited Secrets★ Bhumika Mittal

Aalok Thakkar

School of Computer Science Georgia Institute of Technology

Vachani School of Advanced Computing Ashoka University

Abstract. A cryptographic secret is issued for a purpose but grants a capability, and the capability is usually larger: a decryption key meant for computing aggregates can read every record, and a token meant to pay one invoice can drain the account. Deployed systems state the purpose in policy and enforce only the capability. We make the purpose a property of the secret. A mechanism sees operations, not reasons, so a scheme enforces an admissible set 𝐴(𝑃) of operations that stands in for a declared intended use 𝐼; whether 𝐼 captures the human purpose is a modeling obligation that marks where policy takes over. Against the same 𝐼 we define three regimes: under confinement an operation outside the intended use is infeasible, under mediation a trusted component refuses it, and under accountability use beyond a stated bound is possible but attributed to the holder. The confinement games, for unpredictability and indistinguishability, coincide with the key-query forms of functional-signature unforgeability and constrained-PRF pseudorandomness and correspond to simulation-secure functional encryption within its feasibility boundary; stated against 𝐼, they also register a predicate that permits too much. A payment token uses all three regimes on one secret: it pays one capped charge at one merchant, can be narrowed but not widened, is checked by the merchant, and identifies the withdrawing account if spent twice. Attenuation unforgeability reduces to unforgeable signatures and a collision-resistant hash without random oracles; traceability and non-frameability hold under discrete log and unforgeable signatures in the random-oracle model. We claim no new primitive, hardness assumption, or general composition theorem; the framework is a common specification against which such primitives are stated and compared. Keywords: Purpose limitation · Confinement · Functional cryptography · E-cash · Capabilities · Data protection.

1

Introduction

A person who asks an assistant to pay one invoice must hand over a payment credential, and the credential can empty the account. The same gap appears wherever a secret is shared for a task. A hospital gives an analytics firm a decryption key to compute infection rates, and the key decrypts every patient record. A team gives its build server a signing key for releases of one product, and the key signs anything, malware included. Each secret is given for a purpose but grants a capability, and the capability is larger. Deployed systems write the purpose down and enforce it outside the key. An X.509 certificate lists the uses its key is meant for [36], and a PKCS#11 token tags each key ★ Full version of a paper accepted at the 22nd International Conference on Information Systems

Security (ICISS 2026), to appear in Springer LNCS.

2

B. Mittal and A. Thakkar

with the operations it may perform [58]. In both cases the key can perform any operation, and only a trusted component that reads the tag stands in the way; bypassing it restores the full capability [35,21]. This paper asks whether “this key works only for purpose 𝑃” can be proved of the key itself, as one proves that a signature is unforgeable, so that the limit holds when no monitor is present. Where that is out of reach, it asks what a trusted checker or an audit log can guarantee instead. Such a proof can concern only what a mechanism observes. The same $50 paid to the same merchant may settle the invoice or pay a bribe, and a decryption may serve analytics or re-identification depending on what happens to the plaintext afterwards. A scheme therefore limits operations, not reasons. Each purpose 𝑃 comes with an admissible set 𝐴(𝑃) of operations that the mechanism permits, and the issuer declares an intended use 𝐼, which says which operations each purpose is meant to cover. “Usable only for purpose 𝑃” is shorthand for “usable only for the operations in 𝐴(𝑃)”. Whether 𝐴 and 𝐼 capture the human purpose is a modeling obligation, not a theorem, and it marks where cryptography hands off to policy (Sections 2 and 5.2). Three regimes. Against one intended use we define three regimes, which give different kinds of guarantee. Under confinement an operation outside 𝐼 (𝑃) is computationally infeasible, a hardness property. Under mediation a trusted monitor or verifier refuses it, a trust assumption. Under accountability use beyond a stated bound is possible, and a trace attributes it to the holder after the fact. Functional encryption and constrained pseudorandom functions (PRFs) confine, hardware key stores and certificate flags mediate, traitor tracing holds to account, and electronic cash confines and holds to account. A payment token. For the invoice task we build a token whose single secret uses all three regimes. It authorizes one charge, up to a cap, at one merchant, within a time window. A holder can narrow it but not widen it (confinement), the merchant checks each charge (mediation), and a second spend reveals the account that withdrew it (accountability). What is new. We claim no new primitive or hardness assumption: the confinement games coincide with existing notions in key-query form, and the token is built from known parts (Section 4). The paper contributes a common specification, in which every guarantee, in every regime, is stated against the declared intended use 𝐼 and not against the predicate a primitive enforces. A predicate that permits too much can therefore fail the specification while it satisfies the primitive’s own game (Section 3.4), and the regimes can be related to one another (Section 3.5). The token’s results are proved one regime at a time; a joint security statement and a general composition theorem are open (Section 5.1). Contributions. The paper contributes the following. – A specification of purpose limitation (Section 3): syntax, the intended use and its proxy, and games for the three regimes. The confinement games coincide with key-query unforgeability of functional signatures and with constrained-PRF pseudorandomness against constrained-key queries, cover policy-based signatures, and correspond to functional encryption within its feasibility boundary.

Defining Purpose-Limited Secrets

3

– The payment token (Section 4), with proofs of attenuation unforgeability, traceability, and non-frameability, a comparison with macaroons, SPKI/SDSI, e-cash, and delegatable credentials by the properties each achieves, and an anonymous variant. – A discussion of what the common specification adds and of where cryptographic purpose limitation hands off to policy (Section 5). Section 2 derives the requirements from the payment task, and Section 6 discusses related work.

2

Requirements for a Purpose-Limited Secret

The invoice task of Section 1 is the running example of the paper. A user wants an assistant, human or software, to pay one invoice of at most $50 to one named merchant within the current week. The user’s payment credential can do far more, and the aim is a smaller secret that performs this task and nothing else. Section 4 constructs a token for it. Requirements. The secret must not authorize a payment the task excludes: a different merchant, a larger amount, or a later date. Delegation must only shrink authority: if the assistant sub-contracts part of the task, it derives and passes on a narrower secret (an operation we call attenuation), say at most $20 to the same merchant, and the recipient cannot enlarge it back to $50 or extend it to a second merchant. Finally, the secret should work once. Enforcement. The first two can rest on hardness: producing a valid payment outside the granted terms, or a delegation chain that widens them, is infeasible, and validity is a public check (confinement). The merchant’s check of amount, identity, and date at redemption is mediation, as strong as the trust placed in the checker [21]. The third requirement needs accountability. A merchant that keeps no record cannot tell a second presentation of the token from the first, but a scheme can make the second use reveal the holder, as in electronic cash [33]. Scope of the guarantee. The token limits the merchant, the amount, and the date, which are visible when it is used; it cannot limit the reason for the payment (Section 1). Purpose in the legal sense, as in Article 5(1)(b) of the EU General Data Protection Regulation (GDPR) [59,41,5], concerns why data is used and what happens downstream, which a mechanism cannot see. The guarantee is therefore stated for the observable operation “pay amount 𝑎 to merchant 𝑀 ′ at time 𝑡”, the position that formal treatments of purpose in audit and contextual integrity also take (Section 6). Further examples. The analytics and build-key examples of Section 1, and a dataset licensed to train one model, motivate the definition but are not instances of the token. An analytics key that computes aggregates but cannot read a record is confinement of the indistinguishability kind, realized by functional encryption within its known limits (Section 3.3). A build key that signs one project’s artifacts is confinement of the unpredictability kind, realized by policy-based signatures (Section 3.4). A dataset licensed to train one model reaches the release of plaintext, which no confinement game governs (Section 5.2).

4

B. Mittal and A. Thakkar human purpose (unobservable) 𝐼 (𝑃) false deny 𝐼\𝐴

𝐴(𝑃)

𝐴∩𝐼

false permit 𝐴\𝐼

Fig. 1. Fidelity of the proxy 𝐴(𝑃) to the intended use 𝐼 (𝑃); the human purpose (dashed) is not observable. Soundness excludes 𝐴 \ 𝐼, completeness 𝐼 \ 𝐴. Games are stated against 𝐼, so a false permit an adversary can find is a break.

3

Defining Purpose Limitation

A secret is purpose-limited when use outside its intended use is ruled out, refused, or attributed, depending on the regime. Sections 3.1 and 3.2 specify what each purpose permits and is meant to permit, and Sections 3.3–3.5 give one game per regime. 3.1

Purposes, Operations, and the Intended Use

A capability fixes what an unrestricted secret does and how one tells that it was done. Definition 1 (Capability). A capability is a triple ( Op, Ref, Succ): an operation family Op; a reference semantics Ref, giving the correct result Ref (𝑜) of an unrestricted secret on 𝑜 ∈ Op; and a success predicate Succ, with Succ (𝑜, 𝑦) = 1 iff 𝑦 is a valid achievement of 𝑜, and Succ (𝑜, Ref (𝑜)) = 1. If results should be hard to produce, as for signatures, Succ is public. A public success predicate makes a forbidden achievement a checkable event, whoever checks it. If results should stay hidden, as for PRF values, Succ (𝑜, 𝑦) = [ 𝑦 = Ref (𝑜) ] only states correctness and is not public, since a public test would tell a PRF value from a uniform one. Such capabilities are specified through the challenge and leakage of Game PL-CONF-IND (Definition 9). Purposes are ordered by how much they permit, and a predicate on a purpose and an operation decides what the mechanism permits. Definition 2 (Purposes and admissibility). Purposes form a bounded lattice (P, ⊑ , ⊔, ⊓, ⊤, ⊥) under refinement, where 𝑃′ ⊑ 𝑃 reads “𝑃′ is at most as permissive as 𝑃”: any two purposes have a least upper bound ⊔ and a greatest lower bound ⊓, ⊤ is the most permissive purpose, and ⊥ the least. An admissibility relation adm : P × Op → {0, 1} fixes which operations are in-purpose, and the admissible set, or proxy, of 𝑃 is 𝐴(𝑃) := { 𝑜 ∈ Op : adm (𝑃, 𝑜) = 1 }. Definition 3 (Monotone attenuation). adm satisfies monotone attenuation if 𝑃′ ⊑ 𝑃 ⇒ 𝐴(𝑃′ ) ⊆ 𝐴(𝑃), with 𝐴(⊤) = Op and 𝐴(⊥) = ∅.

Defining Purpose-Limited Secrets

5

Monotonicity makes narrowing safe: a holder who passes on a narrower purpose passes on a subset of its admissible operations. Example. In the payment task of Section 2, an operation 𝑜 = redeem (𝑎, 𝑀 ′ , 𝑡) is a payment of amount 𝑎 to merchant 𝑀 ′ at time 𝑡, and Succ (𝑜, 𝑦) = 1 iff the merchant accepts the redemption transcript 𝑦 for 𝑜. A purpose 𝑃 = (𝑀, 𝐶, 𝑇) is a merchant, an amount cap, and a time window, and adm (𝑃, 𝑜) = [ 𝑀 ′ ⪯ 𝑀 ∧ 𝑎 ≤ 𝐶 ∧ 𝑡 ∈ 𝑇 ], where 𝑀 ′ ⪯ 𝑀 means that 𝑀 ′ is 𝑀 or one of its outlets (Section 4.1). The invoice task is 𝑃0 = (𝑀, 50, 𝑇) for this week’s window 𝑇, and the sub-contract is (𝑀, 20, 𝑇) ⊑ 𝑃0 . A mechanism enforces 𝐴. What the issuer means is declared separately, as the intended use. Definition 4 (Intended use and fidelity). A scheme is specified relative to an intendeduse relation 𝐼 ⊆ P × Op, the target the proxy stands for; write 𝐼 (𝑃) := {𝑜 : (𝑃, 𝑜) ∈ 𝐼}. The proxy 𝐴 is sound for 𝐼 if 𝐴(𝑃) ⊆ 𝐼 (𝑃) for all 𝑃 (no false permit) and complete if 𝐴(𝑃) ⊇ 𝐼 (𝑃) for all 𝑃 (no false deny). Figure 1 shows the regions. The proxy is exact if 𝐴 = 𝐼, as in the running example, where the issuer means “pay at most 𝐶 to 𝑀 within 𝑇” and nothing else. Soundness is what a confinement claim needs when the proxy is not exact (Section 3.3), and completeness, with correctness (Definition 6), lets the holder perform every intended operation. Because 𝐼 is declared, its fidelity to the human purpose is a hypothesis of every result, not a cryptographic property (Section 1). An operation is off-purpose for a Ð set 𝑄 of purposes if it lies outside 𝑃∈𝑄 𝐼 (𝑃); the confinement and mediation games ask whether an adversary can achieve one. 3.2

Syntax and Correctness

The syntax is that of a constrained key, with optional narrowing and, for accountability, an identity that a trace recovers. Definition 5 (PLC scheme). Fix a capability ( Op, Ref, Succ) and a purpose lattice P. A purpose-limited capability scheme (PLC) consists of the following probabilistic polynomial-time (PPT) algorithms and protocols, with security parameter 𝜆. – Setup (1𝜆 ) → (pp, msk) outputs public parameters and the issuer’s master key. – Constrain ⟨Iss (msk), Hld⟩(𝑃) → sk 𝑃 is a protocol between an issuer Iss holding msk and a holder Hld, whose output sk 𝑃 may contain holder secrets the issuer never sees. A non-interactive scheme is the case where the issuer sends one message. – Use (pp, sk 𝑃 , 𝑜) → 𝑦 applies the secret to an operation and returns a result 𝑦, or ⊥. It may be a protocol between the holder and a verifier, in which case 𝑦 is the transcript. A scheme may also have: – Attenuate (pp, sk 𝑃 , 𝑃′ ) → sk 𝑃 ′ for 𝑃′ ⊑ 𝑃, run by the holder to derive a secret for a narrower purpose;

6

B. Mittal and A. Thakkar

– Make (pp, 𝑥) → 𝜔, a public algorithm creating the objects operations act on; an operation 𝑜 may then refer to Make (pp, 𝑥), and Use acts on it. The accountable variant adds: – AKg (1𝜆 ) → (id, ask), account key generation registering a public identity id with secret account key ask; – Constrain additionally takes id and, using ask, records the issuance in an issuer-held store 𝑅; – Trace (pp, iid, 𝐿, 𝑅) → id or ⊥, which, for an issued instance iid (a scheme-defined identifier of one issued secret), recovers a per-issuance handle from the uses of iid in a log 𝐿 of accepted uses and resolves it to id through 𝑅; we write “Trace outputs id” for this composite. Make lets encryption fit the syntax: for functional encryption, Constrain is key generation for 𝑓 and Make is encryption, so the operation “learn 𝑓 (𝑥)” acts on Make (pp, 𝑥). Purpose may instead be bound at encryption time, the dual syntax of ciphertext-policy schemes; the token of Section 4 binds purpose to the key and supports attenuation.

Example. For the payment token, Setup generates the bank’s keys, Constrain is withdrawal, Use is redemption with the merchant, Attenuate appends a delegation certificate, AKg is account registration, and Trace is double-spend tracing over the bank’s deposit log. Definition 6 (Correctness). For all (pp, msk) output by Setup, all 𝑃, all sk 𝑃 output by Constrain for 𝑃, and all 𝑜 with adm (𝑃, 𝑜) = 1,
Succ 𝑜, Use (pp, sk 𝑃 , 𝑜) = 1, and Attenuate preserves this on 𝐴(𝑃′ ). Correctness says nothing about limitation, since an all-powerful key is also correct. The three regimes capture limitation. 3.3

Confinement

Under confinement an off-purpose operation is computationally infeasible, and no party is trusted. “Beyond purpose” may mean producing a forbidden result, which fits capabilities whose output should be hard to produce (signatures, tokens, e-cash), or learning a forbidden thing, which fits capabilities whose output should stay hidden (encryption, PRFs, functional encryption). Game PL-CONF-UP covers the first case and Game PL-CONF-IND the second. Definition 7 (Game PL-CONF-UP). In Game PL-CONF-UP (Figure 2, left), A adaptively obtains secrets sk 𝑃 for purposes 𝑃 of its choice, recorded in 𝑄, and wins if it outputs an achievement 𝑦 ∗ of an operation 𝑜∗ that no purpose in 𝑄 intends. The scheme is unpredictability-confining for 𝐼 if every PPT A wins with probability negl (𝜆), a negligible function of 𝜆.

Defining Purpose-Limited Secrets Game PL-CONF-UP𝐼A (𝜆)

A Game PL-CONF-IND𝐼, (𝜆) Sim

(pp, msk) ← Setup (1𝜆 ); 𝑄 := ∅ (𝑜∗ , 𝑦 ∗ ) ← A 𝑂Constrain (pp) return Succ (𝑜∗ , 𝑦 ∗ ) = 1  Ð ∧ 𝑜 ∗ ∉ 𝑃 ∈𝑄 𝐼 (𝑃)

(pp, msk) ← Setup (1𝜆 ); 𝑄 := ∅ 𝑏 ← {0, 1} (𝑥, st) ← A 𝑂Constrain (pp) if 𝑏 = 0: 𝑐 ← Chal (msk, 𝑥) (real) else: ℓ := Leak 𝑄 (𝑥) 𝑐 ← Sim (pp, (𝑃, sk 𝑃 ) 𝑃 ∈𝑄 , |𝑥|, ℓ) (ideal) 𝑏 ′ ← A (st, 𝑐) return [ 𝑏 ′ = 𝑏 ]

Oracle 𝑂 Constrain (𝑃) 𝑄 := 𝑄 ∪ {𝑃} sk 𝑃 ← Constrain ⟨Iss (msk), Hld⟩(𝑃) return sk 𝑃

7

𝑂 Constrain as on the left. Chal (msk, 𝑥): the objects the scheme produces for 𝑥 (a ciphertext Make (pp, 𝑥); the PRF value at 𝑥). Leak 𝑄 (𝑥): the results on 𝑥 of the operations Ð in 𝑃 ∈𝑄 𝐼 (𝑃). st: A’s state.

Fig. 2. The confinement games. In PL-CONF-UP (left) the adversary wins by achieving an offpurpose operation; in PL-CONF-IND (right) it must tell real objects for its input from objects simulated from its entitled leakage.

The game is stated against 𝐼, not against 𝐴. An unsound proxy is therefore insecure once its false-permit region can be found: an adversary that efficiently finds 𝑃 and 𝑜 ∈ Ð 𝐴(𝑃) \ 𝐼 (𝑃) obtains sk 𝑃 , runs Use on 𝑜, and wins. Under a sound proxy 𝑃∈𝑄 𝐴(𝑃) ⊆ Ð 𝑃 ∈𝑄 𝐼 (𝑃), so confining the holder to the admissible sets confines it to the intended use. With one query (|𝑄| = 1) the game is single-key confinement. The general form is collusion resistance: a set of keys together achieves only the union of their intended sets. With Attenuate, confinement must survive delegation: an adversary that watches honest holders narrow and use secrets, and receives some of them, should still achieve nothing off-purpose for what it received. Definition 8 (Game PL-CONF-UP with delegation). In this game (Figure 3, left) the challenger plays the issuer and all honest holders. 𝑂 grant (𝑃) creates a secret at an honest holder and returns a handle ℎ with purpose 𝑃 ℎ ; 𝑂 att (ℎ, 𝑃′ ), for 𝑃′ ⊑ 𝑃 ℎ , attenuates it at that holder and returns a fresh handle; 𝑂 deleg (ℎ) hands A the secret behind ℎ and records 𝑃 ℎ in 𝑄; and 𝑂 use (ℎ, 𝑜), for adm (𝑃 ℎ , 𝑜) = 1, returns the transcript of an ∗ ∗ ∗ ∗ honest Ð use and records 𝑜 in T . A wins if it outputs (𝑜 , 𝑦 ) with Succ (𝑜 , 𝑦 ) = 1, 𝑜∗ ∉ 𝑃 ∈𝑄 𝐼 (𝑃), and 𝑜∗ ∉ T . Secrets leave honest parties only through 𝑂 deleg , so the coalition holds exactly the delegated secrets. The win condition excludes the operations of honest uses, not only their transcripts. A game that excluded only transcripts would count as a win a new transcript of an honest operation, for instance one carrying a re-randomized signature. Ruling that out needs strongly unforgeable signatures, and such a transcript is not an off-purpose achievement. In the payment task, 𝑂 deleg hands a narrowed token to a possibly malicious assistant, and 𝑂 use is an honest payment that the adversary observes. Definition 9 (Game PL-CONF-IND). In Game PL-CONF-IND (Figure 2, right), the setup and key queries are as in PL-CONF-UP. A then names a challenge input 𝑥 (a

8

B. Mittal and A. Thakkar

Game PL-CONF-UP with delegation

Game PL-MED, mode ∈ {held, gated}

(pp, msk) ← Setup (1𝜆 )

(pp, msk) ← Setup (1𝜆 ) 𝑆 := ∅; Y := ∅ , 𝑀1 , 𝑀2 ,... (pp) (𝑜∗ , 𝑦 ∗ ) ← A new  if held: return Succ (𝑜∗ , 𝑦 ∗ ) = 1  Ð ∧ 𝑜 ∗ ∉ 𝑃 ∈𝑆 𝐼 (𝑃) ∧ 𝑦 ∗ ∉ Y  if gated: return Accept (pp, 𝑜 ∗ , 𝑦 ∗ ) = 1  Ð ∧ 𝑜 ∗ ∉ 𝑃 ∈𝑆 𝐼 (𝑃)

𝑄 := ∅; T := ∅ (𝑜∗ , 𝑦 ∗ ) ← A 𝑂grant ,𝑂att ,𝑂deleg ,𝑂use (pp) return Succ (𝑜∗ , 𝑦 ∗ ) = 1  Ð ∧ 𝑜 ∗ ∉ 𝑃 ∈𝑄 𝐼 (𝑃) ∧ 𝑜 ∗ ∉ T 𝑂 grant (𝑃) sk ← Constrain ⟨Iss (msk), Hld⟩(𝑃) store (ℎ, 𝑃, sk) for a fresh handle ℎ return ℎ 𝑂 att (ℎ, 𝑃′ ) require 𝑃′ ⊑ 𝑃 ℎ sk′ ← Attenuate (pp, sk ℎ , 𝑃′ ) store (ℎ′ , 𝑃′ , sk′ ) for a fresh handle ℎ′ return ℎ′ 𝑂 deleg (ℎ) 𝑄 := 𝑄 ∪ {𝑃 ℎ }; return sk ℎ 𝑂 use (ℎ, 𝑜)

new (𝑃𝑖 )

𝑆 := 𝑆 ∪ {𝑃𝑖 } sk𝑖 ← Constrain ⟨Iss (msk), Hld⟩(𝑃𝑖 ) if gated: return sk𝑖 (bearer) if held: install sk𝑖 in 𝑀𝑖 (never leaves) 𝑀𝑖 (𝑜), held mode if adm (𝑃𝑖 , 𝑜) = 0: return ⊥ 𝑦 ← Use (pp, sk𝑖 , 𝑜); Y := Y ∪ {𝑦} return 𝑦 In gated mode there is no 𝑀𝑖 ; the verifier runs the public Accept.

require adm (𝑃 ℎ , 𝑜) = 1 𝑦 ← Use (pp, sk ℎ , 𝑜); T := T ∪ {𝑜} return 𝑦 Fig. 3. Left: PL-CONF-UP with delegation; operations of honest uses are not wins. Right: PL-MED, held and gated modes.

plaintext, a PRF point) and receives either the objects the scheme produces for 𝑥 (real) or the output of a simulator Sim (ideal). Sim is given the queried purposes, their real keys, the length |𝑥|, and the entitled leakage Leak 𝑄 (𝑥), the results on 𝑥 of the operations the queried purposes intend, but not 𝑥 itself. For functional encryption Sim gets the values 𝑓𝑖 (𝑥) and outputs a ciphertext; for a PRF, the value at a non-admissible point is replaced by a uniform one. The scheme is indistinguishability-confining for 𝐼, with a PPT simulator Sim that is part of the claim, if every PPT A guesses the hidden bit with probability at most 12 + negl (𝜆). Known primitives as instances. Three primitives fit the syntax with an exact proxy (𝐴 = 𝐼), and for each the game becomes the primitive’s own security notion in a key-query form. – Functional signatures [22]: a key sk 𝑓 derived from a master key signs exactly the messages in the range of 𝑓 . Here P is functions 𝑓 , 𝐴( 𝑓 ) = range ( 𝑓 ), and Succ (𝑚, 𝜎) = Verify (vk, 𝑚, 𝜎). Game PL-CONF-UP is unforgeability outside Ð 𝑖 range ( 𝑓𝑖 ) against an adversary with key queries and no signing oracle (Proposition 1). – Constrained PRFs [20]: a key 𝑘 𝐶 evaluates a pseudorandom function 𝐹𝑘 only at points with 𝐶 (𝑥) = 1. Here P is constraints 𝐶 and 𝐴(𝐶) = {𝑥 : 𝐶 (𝑥) = 1}. Game

Defining Purpose-Limited Secrets

9

PL-CONF-IND with a uniform ideal value is pseudorandomness at non-admissible

points against constrained-key queries made before the challenge (Proposition 2). The standard constrained-PRF game also has an evaluation oracle and key queries after the challenge, so the proposition concerns this weaker notion. – Functional encryption (FE) [19]: a key sk 𝑓 recovers 𝑓 (𝑥) from an encryption of 𝑥 and nothing more. Here P is functions 𝑓 , the admissible operation under 𝑓 is “learn 𝑓 (𝑥)” with entitled leakage 𝑓 (𝑥), and Make is encryption. Game PL-CONF-IND with the simulator given { 𝑓𝑖 (𝑥)} is non-adaptive FE simulation security, with real setup and keys and only the challenge simulated. This is a mapping of definitions, not a proved equivalence, and it inherits FE’s boundary: simulation-secure FE for general functions is impossible against unbounded collusion, even with non-adaptive queries [4], so the instance is meaningful for bounded collusion. Proposition 1 (Functional signatures). Fix a functional signature scheme FS and its instance PLC ( FS) above. The instance is unpredictability-confining for 𝐼 (Game PLCONF-UP) iff FS is unforgeable against key-query adversaries. Proposition 2 (Constrained PRFs). For a constrained PRF 𝐹, the instance PLC (𝐹) above is indistinguishability-confining for 𝐼 (Game PL-CONF-IND, one challenge point, with the simulator that outputs the entitled leakage if it is nonempty and a uniform value otherwise) iff 𝐹 is pseudorandom at non-admissible points against constrained-key queries made before the challenge, with no evaluation oracle. Both proofs translate one game into the other without loss (Appendix A). 3.4

Policy-Based Signatures as an Instance

The build key of Section 1 is an instance of Proposition 1, not a new construction, and it shows what stating the game against 𝐼 adds. The capability is signing: Op is messages and Succ (𝑚, 𝜎) = Verify (vk, 𝑚, 𝜎). Purposes are predicates 𝑃 over messages (“a wellformed project-𝑋 artifact”), with the exact proxy 𝐴(𝑃) = 𝐼 (𝑃) = {𝑚 : 𝑃(𝑚) = 1}. A policy-based signature [11] is then a PLC: Constrain (msk, 𝑃) returns a key that signs exactly the messages satisfying 𝑃, and Use signs. Policy-based signatures have no delegation algorithm, and we construct no Attenuate. Corollary 1 (Signing-instance confinement). If the underlying policy-based signature is unforgeable against key-query adversaries, this PLC is unpredictability-confining for 𝐼 (Game PL-CONF-UP). Proof. As for Proposition 1 with {𝑚 : 𝑃(𝑚) = 1} in place of range ( 𝑓 ): a PL-CONFUP winner outputs (𝑚 ∗ , 𝜎 ∗ ) with Verify (vk, 𝑚 ∗ , 𝜎 ∗ ) = 1 and 𝑃𝑖 (𝑚 ∗ ) = 0 for every queried 𝑃𝑖 , a key-query forgery. ⊔ ⊓ A functional signature realizes the same instance when {𝑚 : 𝑃(𝑚) = 1} has an efficient encoding as the range of a function. The exact proxy 𝐴(𝑃) = 𝐼 (𝑃) is an assumption about the predicate, and it can fail. Suppose the policy language can express only a coarser predicate 𝑃˜ that checks that an artifact’s name starts with the project prefix.

10

B. Mittal and A. Thakkar

˜ but not in 𝐼 (𝑃), the false-permit region A malicious build with that name is in 𝐴( 𝑃) ˜ but the PLC is not of Figure 1. The policy-based signature is still unforgeable for 𝑃, confining for 𝐼. Game PL-CONF-UP, stated against 𝐼, records the failure; the primitive’s own game, stated against the predicate, does not. 3.5

Mediation and Accountability

Mediation. Under mediation a trusted component, not hardness, keeps use in purpose. The component may be a hardware security module (HSM) that stores keys, a trusted execution environment (TEE) that runs code in an attested enclave, or a verifier that checks results. The game models it as an oracle, and that interface is the integrity assumption an instantiation must justify. Definition 10 (Game PL-MED). In Game PL-MED (Figure 3, right), A controls the host and creates monitors 𝑀𝑖 through new (𝑃𝑖 ) for purposes of its choice, in one of two modes. – Monitor-held: the secret sk 𝑃𝑖 never leaves 𝑀𝑖 , which runs Use only on operations Ð admissible for 𝑃𝑖 . A wins if it outputs (𝑜 ∗ , 𝑦 ∗ ) with Succ (𝑜∗ , 𝑦 ∗ ) = 1, 𝑜∗ ∉ 𝑖 𝐼 (𝑃𝑖 ), and 𝑦 ∗ not returned by any monitor. – Verifier-gated: the secret is a bearer object (usable by whoever holds it) given to A, and the monitor is an honest verifier running a public acceptance algorithm Accept (pp, 𝑜, 𝑦) that the scheme specifies. Accept reads the purpose from 𝑦 (a certificate, a chain), checks that it admits 𝑜, accepts honest uses of admissible operations, and accepts only if Succ (𝑜, 𝑦) = 1. A wins if the verifier accepts an Ð off-purpose operation, Accept (pp, 𝑜 ∗ , 𝑦 ∗ ) = 1 with 𝑜∗ ∉ 𝑖 𝐼 (𝑃𝑖 ). The scheme is mediation-secure if Advmed (A) := Pr[A wins] is negligible for all PPT A. Monitor-held mediation turns “the monitor honors a flag” into “the secret is unusable outside an attested boundary”, and an instantiation must justify that the secret stays inside (attestation, sealing). Verifier-gated mediation, which the token uses at redemption, needs only an honest verifier. The deployed purpose flags of Section 1 are mediation: a PKCS#11 token is a monitor that holds the key, and an X.509 relying party that checks the key-usage field is verifier-gated, as is a server that checks OAuth access tokens or JSON Web Tokens (JWTs) [36,58,47,49,30,42]. Neither flag confines the key: once the check is bypassed, the key achieves off-purpose operations and wins PL-CONF-UP [21]. Remark 1 (Verifier-gated mediation and confinement). In the verifier-gated mode A holds the secrets of the purposes passed to new, and an accepted result is valid. A gated win is therefore a PL-CONF-UP win with 𝑄 those purposes, and unpredictability confinement for 𝐼 implies verifier-gated mediation security for 𝐼. The converse fails: an X.509 key whose certificate the adversary cannot forge is gated-secure, since the relying party reads the key usage from the signed certificate, yet the key signs off-purpose messages and is not confining. The gated mode asks only that a forbidden result not be accepted, and assumes that the verifier runs Accept before honoring a result.

Defining Purpose-Limited Secrets

11

Accountability. Under accountability, use beyond a stated bound is possible but attributable: issuance binds an identity, and Trace resolves a log of accepted uses to it. The regime governs how often a secret is used, not which operations. Whether each use lies in 𝐴(𝑃) is left to confinement and mediation, so here each accepted use is assumed in-purpose; an extra use is permitted and attributed, not prevented. Definition 11 (Traceable limitation and non-frameability). Extend the intended use with a use bound: purpose 𝑃 intends at most 𝑘 𝑃 uses of a secret. The game is the delegation-extended game (Definition 8) for the accountable variant (Definition 5), with these changes. – Honest accounts are created with AKg, and 𝑂 grant binds the issued secret to an account’s identity id. – 𝐿 is the issuer’s log of accepted uses and 𝑅 its record store when A halts. Each use is logged once, in a form the scheme fixes, so a resubmitted use is a replay and does not count. A corrupt verifier lets A submit uses, which enter 𝐿 only if they pass the scheme’s public checks. – For non-frameability the issuer may be corrupt; then A writes 𝑅, but honest accounts keep their account keys. A secret over-spends if 𝐿 contains more than 𝑘 𝑃 uses of it. – Traceable limitation: if a secret iid bound to id over-spends, whoever spent it, then Trace (pp, iid, 𝐿, 𝑅) = id except with negligible probability. – Non-frameability: except with negligible probability, there is no iid for which Trace (pp, iid, 𝐿, 𝑅) names an honest identity to which iid was never issued, or one to which it was issued that neither shared nor over-spent it. Non-frameability is per secret: an identity that delegates one secret is still protected on the others. Attribution follows possession, so a delegated secret that over-spends traces to the identity it was issued to, however often it was delegated. For a one-use token (𝑘 𝑃 = 1), traceable limitation is “a double-spend identifies the withdrawing account” [33,23], and non-frameability is e-cash exculpability. Traitor tracing is the many-user analogue [34]. Relations among the regimes. Table 3 in Section 5.1 summarizes the regimes, and Remark 1 relates confinement to gated mediation. A purpose has a content part (which operations) and may have a count part (how many times). Confinement and mediation can enforce the content part. A stateless check cannot enforce the count part, because a verifier without state cannot tell a second presentation of a bearer secret from the first; the count part needs a stateful monitor or accountability over a log.

4

A Purpose-Limited Payment Token

The token realizes the invoice task of Section 2 and uses all three regimes on one secret. It is an off-line e-cash coin (the bank is not contacted at payment time) whose bank signature also covers a maximal purpose 𝑃0 and a root public key. A holder narrows the purpose by appending certificates to a chain that starts at that key. At redemption the merchant checks

12

B. Mittal and A. Thakkar

the chain, checks that the payment is admissible for the chain’s last purpose, and checks an e-cash opening that identifies the withdrawing account if the coin is spent twice. The building blocks are known: the representation coin of Brands [23], e-cash double-spend equations [33], and public-key delegation in the tradition of SPKI/SDSI (the Simple Public Key Infrastructure and Simple Distributed Security Infrastructure) [39]. No new hardness assumption is used. 4.1

Capability and Purpose Space

Operations redeem (𝑎, 𝑀 ′ , 𝑡) and purposes 𝑃 = (𝑀, 𝐶, 𝑇) are those of the example in Section 3.1, with use bound 𝑘 𝑃 = 1, which accountability enforces over the deposit log. Merchant identifiers form a tree: a merchant, its outlets as children, and a wildcard ∗ at the root. Write 𝑀 ′ ⪯ 𝑀 if 𝑀 ′ is 𝑀 or a descendant of 𝑀. Then
adm (𝑀, 𝐶, 𝑇), redeem (𝑎, 𝑀 ′ , 𝑡) = [ 𝑀 ′ ⪯ 𝑀 ∧ 𝑎 ≤ 𝐶 ∧ 𝑡 ∈ 𝑇 ]. Caps range over [0, ∞], and windows 𝑇 = [𝑡0 , 𝑡1 ] are ordered by inclusion. Refinement is componentwise, (𝑀 ′ , 𝐶 ′ , 𝑇 ′ ) ⊑ (𝑀, 𝐶, 𝑇) iff 𝑀 ′ ⪯ 𝑀, 𝐶 ′ ≤ 𝐶, and 𝑇 ′ ⊆ 𝑇, and makes purposes a bounded lattice whose meet and join are componentwise: minimum and maximum for caps, intersection and interval hull for windows, and for merchants the deeper of two comparable nodes, or an empty merchant if they are incomparable, and the nearest common ancestor. ⊤ = (∗, ∞, (−∞, ∞)) admits every operation, and all purposes with an empty merchant or an empty window are identified with ⊥, so 𝐴(⊥) = ∅; the join with ⊥ is ⊥ ⊔ 𝑃 = 𝑃 rather than componentwise. Each conjunct of adm is downward closed in its order, so 𝑃′ ⊑ 𝑃 implies 𝐴(𝑃′ ) ⊆ 𝐴(𝑃) (Definition 3), and a verifier decides 𝑃𝑖 ⊑ 𝑃𝑖−1 by three efficient tests. The proxy is the purpose predicate itself, so 𝐴 = 𝐼 and the confinement claims need no soundness hypothesis. 4.2

Building Blocks

Group and hash. Let G be a group of prime order 𝑞 with generators 𝑔1 , 𝑔2 such that 𝑤2 := log𝑔1 𝑔2 is unknown to all parties, for instance with 𝑔2 derived from a hash of a public string; the hardness assumption is discrete log (DL) in G. A representation of 𝑋 ∈ G is a pair (𝑟 1 , 𝑟 2 ) with 𝑋 = 𝑔1𝑟1 𝑔2𝑟2 , and two representations of one element reveal 𝑤2 (Lemma 1), the basis of Brands’ e-cash [23]. A hash function 𝐻 : {0, 1}∗ → Z𝑞 is modeled as a random oracle [13] in Theorems 2 and 3 and assumed only collision-resistant in Theorem 1. Signatures and proofs. The bank signs with an EUF-CMA (existentially unforgeable under chosen-message attack) signature ( Sign, Verify) [45] and key pair (bsk, bvk). Delegation certificates and account records use an EUF-CMA signature Σdel = ( Kg, Sg, Vf); Schnorr signatures over G are a natural choice, but their unforgeability is proved in the randomoracle model [62]. At issuance the holder proves knowledge of the coin identity 𝑢 and the coin secret 𝑠, written 𝜋 ← PoK{(𝑢, 𝑠) : 𝑌 = 𝑔1𝑢 ∧ 𝐴 = (𝑌 𝑔2 ) 𝑠 }: a Schnorr proof [65] for the conjunction, a three-move Σ-protocol with one challenge, made non-interactive by the Fiat–Shamir transform [43] over 𝐻, whose input contains the full statement. In

Defining Purpose-Limited Secrets Holder 𝑈 (holds ask𝑈 )

13

Bank (holds bsk, store 𝑅)

𝑢, 𝑠, 𝑎 1 , 𝑎 2 ← Z𝑞 ; (sk0 , vk0 ) ← Kg 𝑌 := 𝑔1𝑢 ; 𝐴 := (𝑌 𝑔2 ) 𝑠 𝑎 𝑎 𝐷 := 𝑔1 1 𝑔2 2 𝜋 ← PoK{(𝑢, 𝑠) : 𝑌 = 𝑔1𝑢 ∧ 𝐴 = (𝑌 𝑔2 ) 𝑠 } 𝜌𝑤 := Sgask𝑈 (𝑌 , 𝐴, 𝐷) avk𝑈 , 𝑃0 , 𝑌 , 𝐴, 𝐷 vk0 , 𝜋, 𝜌𝑤 −−−−−−−−−− −−−−−−−−−−−−→ check 𝜋, and 𝜌𝑤 under avk𝑈 refuse if 𝐴 = 1 or ( 𝐴, 𝐷) in 𝑅 store (avk𝑈 , 𝑌 , 𝐴, 𝐷, 𝜌𝑤 ) in 𝑅 𝜎 := Signbsk ( 𝐴, 𝐷, 𝑃0 , vk0 ) 𝜎 ←−−−−−−−−−−−−−−−−−−−−−− sk 𝑃 := (𝑢, 𝑠, 𝑎 1 , 𝑎 2 , sk0 , vk0 , 𝐴, 𝐷, 𝜎, 𝑃0 ) Fig. 4. Issuance (Constrain) for maximal purpose 𝑃0 . The account-signed record 𝜌𝑤 is what tracing resolves to an account.

the random-oracle model the proof is zero-knowledge (a simulator programs 𝐻) and extractable (rewinding to the query that fixed the challenge yields the witness) [62]. Every signed message and hash input is canonically encoded and begins with a tag for its role (bank signature, certificate, spend authorization, withdrawal record, proof challenge, redemption challenge), so no signature or hash value serves two roles. Design choices. The coin uses two generators and a per-coin pad commitment 𝐷, the first message of a Σ-protocol, as in Brands’ scheme and compact e-cash [23,27]. A one-generator coin with a Schnorr nonce gives a trace equation but no simulatable one-spend transcript, since its nonce commitment is certified before the challenge is known; the pad commitment lets the non-frameability reduction choose the opening first and solve for 𝐷. Attenuation uses a public-key delegation chain [39] rather than macaroons, which chain message authentication codes (MACs) under a root key that every verifier, here every merchant, would hold and could use to mint looser caveats [16]. 4.3

The Scheme

Issuance. Holder 𝑈 registers, under the bank’s know-your-customer (KYC) checks, a verification key avk𝑈 and keeps the signing key ask𝑈 ; there is no long-term discrete-log identity. To withdraw a coin for a maximal purpose 𝑃0 (Figure 4), 𝑈 samples a fresh coin identity 𝑢 with pseudonym 𝑌 = 𝑔1𝑢 , a coin secret 𝑠, pads 𝑎 1 , 𝑎 2 , and a root delegation key pair (sk0 , vk0 ), all independent per coin. It forms the coin 𝐴 = (𝑌 𝑔2 ) 𝑠 = 𝑔1𝑢𝑠 𝑔2𝑠 and the pad commitment 𝐷 = 𝑔1𝑎1 𝑔2𝑎2 , proves knowledge of (𝑢, 𝑠), and signs the withdrawal record 𝜌𝑤 on (𝑌 , 𝐴, 𝐷). The bank checks both, stores the record, and signs 𝜎 on ( 𝐴, 𝐷, 𝑃0 , vk0 ); the holder keeps sk 𝑃 = (𝑢, 𝑠, 𝑎 1 , 𝑎 2 , sk0 , vk0 , 𝐴, 𝐷, 𝜎, 𝑃0 ), and the empty chain authorizes spending at 𝑃0 . One withdrawal creates one instance ( 𝐴, 𝐷), and the secret sk 𝑃 is

14

B. Mittal and A. Thakkar Merchant 𝑀 ′ (holds bvk)

Spender (holds ch, sk 𝑛 , 𝑢, 𝑠, 𝑎 1 , 𝑎 2 )

pick a nonce 𝑁 𝑁 ←−−−−−−−−−−−−−−−−−−−−−− 𝑁𝑈 ← {0, 1}𝜆 𝑑 := 𝐻 ( 𝐴, 𝐷, vk 𝑛 , 𝑀 ′ , 𝑎, 𝑡, 𝑁, 𝑁𝑈 ) 𝑟 1 := 𝑢𝑠𝑑 + 𝑎 1 ; 𝑟 2 := 𝑠𝑑 + 𝑎 2 𝜌 := Sgsk𝑛 (𝑑) 𝐴, 𝐷, ch, 𝑁𝑈 , 𝑎, 𝑡 𝑟 , 𝑟 , 𝜌 −−−−−−−−−1−−−−2−−−−−−−−−→ recompute 𝑑 accept iff (V1)–(V5) hold bank re-checks, logs ( 𝐴, 𝐷, 𝑑, 𝑟 1 , 𝑟 2 ) Fig. 5. Redemption (Use) of redeem (𝑎, 𝑀 ′ , 𝑡) with a chain ending at (𝑃𝑛 , vk 𝑛 ); 𝑑 binds the operation.

everything the holder keeps for it. Each check at issuance serves tracing. The proof’s first conjunct keeps 𝑌 free of a 𝑔2 -component, without which a double-spend could trace to a value matching no pseudonym; the second ties 𝐴 to 𝑢. The bank refuses 𝐴 = 1, which forces 𝑠 ≠ 0, as tracing needs: 𝑠 = 0 gives 𝐴 = 1, and 𝐴 = 1 with 𝑠 ≠ 0 would need 𝑢 = −𝑤2 . It refuses an instance ( 𝐴, 𝐷) already in 𝑅, so each instance has one record, but not a repeated 𝐴 with a new 𝐷, since tracing operates on the instance ( 𝐴, 𝐷) and each withdrawal is debited separately. Attenuation. A holder of the key skcur at the end of a chain for purpose 𝑃cur narrows it to 𝑃′ ⊑ 𝑃cur by drawing (sk′ , vk′ ) ← Kg and signing the certificate 𝛿 := Sgskcur (⟨𝑃′ , vk′ ⟩). The authorization for 𝑃′ is the chain
ch = (𝑃0 , vk0 , 𝜎), (𝑃1 , vk1 , 𝛿1 ), . . . , (𝑃𝑛 , vk 𝑛 , 𝛿 𝑛 ) , 𝑃0 ⊒ 𝑃1 ⊒ · · · ⊒ 𝑃 𝑛 = 𝑃 ′ , handed to the delegate with the terminal key sk 𝑛 and the coin secrets (𝑢, 𝑠, 𝑎 1 , 𝑎 2 ). In the running example the account withdraws at 𝑃0 = (𝑀, 50, 𝑇) and hands the coin to the assistant, which gives its sub-contractor one certificate for 𝑃1 = (𝑀, 20, 𝑇) and the key sk1 . Redemption. To redeem 𝑜 = redeem (𝑎, 𝑀 ′ , 𝑡) with a chain ending at (𝑃𝑛 , vk 𝑛 ) (Figure 5), the spender answers the merchant’s nonce 𝑁 with its own nonce 𝑁𝑈 , sets the challenge 𝑑 := 𝐻 ( 𝐴, 𝐷, vk 𝑛 , 𝑀 ′ , 𝑎, 𝑡, 𝑁, 𝑁𝑈 ), and sends the opening 𝑟 1 := 𝑢𝑠𝑑 + 𝑎 1 , 𝑟 2 := 𝑠𝑑 + 𝑎 2 (mod 𝑞) and the spend authorization 𝜌 := Sgsk𝑛 (𝑑) together with ( 𝐴, 𝐷, ch, 𝑁𝑈 , 𝑎, 𝑡). The merchant recomputes 𝑑 and accepts iff (V1) Verifybvk (( 𝐴, 𝐷, 𝑃0 , vk0 ), 𝜎) = 1; (V2) for 𝑖 = 1, . . . , 𝑛: Vfvk𝑖−1 (⟨𝑃𝑖 , vk𝑖 ⟩, 𝛿𝑖 ) = 1 and 𝑃𝑖 ⊑ 𝑃𝑖−1 ; (V3) adm (𝑃𝑛 , 𝑜) = 1; (V4) Vfvk𝑛 (𝑑, 𝜌) = 1;

Defining Purpose-Limited Secrets

15

Table 1. Security results for the token, each proved separately. CR: collision resistance; ROM: random-oracle model. “Standard” describes the reduction; with Schnorr certificates, whose unforgeability is proved in the ROM, Theorem 1 also rests on the ROM. Result

Regime

Assumptions

Model

Thm. 1 attenuation Thm. 2 traceability Thm. 3 non-frameability Cor. 2 mediation Thm. 4 unlinkability

confinement accountability accountability mediation, gated privacy (variant)

EUF-CMA (Σdel , bank), CR of 𝐻 DL DL, EUF-CMA (accounts) as Thm. 1; honest verifier well-formed bank key

standard ROM ROM standard perfect

(V5) 𝑔1𝑟1 𝑔2𝑟2 = 𝐴 𝑑 · 𝐷. On deposit the bank re-runs (V1)–(V5) on the transcript, so a corrupt merchant cannot log a tuple that fails them, adds ( 𝐴, 𝐷, 𝑑, 𝑟 1 , 𝑟 2 ) to its deposit log 𝐿, and discards a tuple already present as a replay. Checks (V1)–(V2) authenticate the chain, (V3) enforces its terminal purpose, (V4) shows that the spender holds the terminal key, so it cannot present a shorter chain ending at a wider purpose, and (V5) is the traceable opening, which an honest spender satisfies since 𝐴 𝑑 𝐷 = 𝑔1𝑢𝑠𝑑+𝑎1 𝑔2𝑠𝑑+𝑎2 . The merchant identity 𝑀 ′ enters 𝑑 and is compared with 𝑃𝑛 in (V3). That the party running the checks is the merchant 𝑀 ′ it claims to be, for example because the spender reaches it over a channel authenticated to 𝑀 ′ , is part of the trust placed in the verifier and so belongs to mediation. Theorem 1 bounds which operations can be accepted; the verifier’s honesty and authenticity ensure that an accepted operation is the one that took place. Identity binding and delegation. Tracing follows a chain of bindings from two openings to 𝑢 (the issuance proof ties 𝐴 to 𝑢), to 𝑌 , and to the account (the record 𝜌𝑤 binds 𝑌 and ( 𝐴, 𝐷) to it). The coin secrets belong to one coin, so attenuation hands over one single-use instance, narrowed in purpose, and nothing long-term: a delegate learns that coin’s 𝑢, since an opening needs both 𝑢𝑠 and 𝑠, but nothing about the account’s other coins or its signing key. Tracing, Trace (pp, ( 𝐴, 𝐷), 𝐿, 𝑅). If 𝐿 contains two tuples for the instance ( 𝐴, 𝐷) with 𝑟 2 ≠ 𝑟 2′ , Trace computes 𝑢 := (𝑟 1 − 𝑟 1′ ) (𝑟 2 − 𝑟 2′ ) −1 mod 𝑞 and 𝑌 := 𝑔1𝑢 , and otherwise outputs ⊥; this is correct because 𝑟 1 − 𝑟 1′ = 𝑢𝑠(𝑑 − 𝑑 ′ ) and 𝑟 2 − 𝑟 2′ = 𝑠(𝑑 − 𝑑 ′ ). It outputs the account of the record (avk𝑈 , 𝑌 , 𝐴, 𝐷, 𝜌𝑤 ) ∈ 𝑅 if it is the only record for ( 𝐴, 𝐷), carries 𝑌 , and verifies, Vfavk𝑈 ((𝑌 , 𝐴, 𝐷), 𝜌𝑤 ) = 1, and ⊥ otherwise. The signature check matters when the bank is corrupt and writes 𝑅 (Theorem 3). 4.4

Security

Each regime has its own result, proved separately on the same token (Figure 6). Theorem 1 (confinement) says that narrowing cannot be undone: a coalition achieves nothing outside the purposes delegated to it, apart from operations that honest holders performed.

16

B. Mittal and A. Thakkar 1. Issuance (bank, holder). Holder forms coin 𝐴 = (𝑌 𝑔2 ) 𝑠 , pad 𝐷, root key vk0 ; bank signs 𝜎 = Sign ( 𝐴, 𝐷, 𝑃0 , vk0 ) and stores the accountsigned withdrawal record. 2. Attenuation (delegation chain). Certificate 𝛿𝑖 = Sgsk𝑖−1 ⟨𝑃𝑖 , vk𝑖 ⟩ narrows 𝑃0 ⊒ 𝑃1 ⊒ · · · ⊒ 𝑃𝑛 ; a bearer cannot widen.

Confinement

3. Redemption (spender, merchant). Send ( 𝐴, 𝐷, ch, 𝑁𝑈 , 𝑎, 𝑡, 𝑟 1 , 𝑟 2 , 𝜌); the merchant checks (V1)–(V5).

Mediation

Reuse. Two redemptions of one instance ( 𝐴, 𝐷) give Trace: 𝑢 = (𝑟 1 − 𝑟 1′ )(𝑟 2 − 𝑟 2′ ) −1 , the coin identity, traced to the account.

Accountability

Fig. 6. Phases of the token and the result that covers each. Attenuation is confinement (Theorem 1), redemption is verifier-gated mediation (Corollary 2), and reuse is held to account (Theorems 2 and 3).

Theorems 2 and 3 (accountability) say that a double-spend names the withdrawing account and that an honest account is not named for an instance it never withdrew, or withdrew but neither delegated nor spent twice. Corollary 2 gives verifier-gated mediation, and Table 1 lists the assumptions. There is no joint security statement (Section 5.1). For confinement, an off-purpose operation is an accepted redemption outside the purposes delegated to the adversary; for accountability, the target is reuse, with use bound 1. Lemma 1 (Representation binding). If a PPT algorithm, given (𝑔1 , 𝑔2 ), outputs 𝑋 ∈ G and two pairs (𝑟 1 , 𝑟 2 ) ≠ (𝑟˜1 , 𝑟˜2 ) with 𝑔1𝑟1 𝑔2𝑟2 = 𝑋 = 𝑔1𝑟˜1 𝑔2𝑟˜2 , then 𝑤2 = (𝑟 1 − 𝑟˜1 ) (𝑟˜2 − 𝑟 2 ) −1 mod 𝑞, so it solves discrete log. Proof. From 𝑔1𝑟1 −𝑟˜1 = 𝑔2𝑟˜2 −𝑟2 we get 𝑟 1 − 𝑟˜1 ≡ 𝑤2 (𝑟˜2 − 𝑟 2 ) (mod 𝑞). If 𝑟˜2 = 𝑟 2 then 𝑟 1 = 𝑟˜1 , a contradiction, so 𝑟˜2 − 𝑟 2 is invertible. ⊔ ⊓ Theorem 1 (Attenuation unforgeability). In the game of Definition 8, assume the delegation and bank signatures are EUF-CMA and 𝐻 is collision-resistant. Let the adversary’s 𝑂 deleg queries for a coin 𝐴 delegate the purposes 𝐺 = {𝑃𝑛1 , . . . , 𝑃𝑛𝑘 }, each with its chain, terminal key, and the coin secrets. Then, except with negligible Ð probability, the adversary obtains no accepted redemption of 𝐴 for an operation outside 𝑗 𝐴(𝑃𝑛 𝑗 ) other than the operations performed through 𝑂 use . Across coins the achievable set is the union over coins, since each redemption presents one coin. The reduction uses no random oracle, so the result holds in the standard model when both signatures are unforgeable in the standard model. Proof. An accepted redemption presents a chain 𝜎, (𝑃1 , vk1 , 𝛿1 ), . . . , (𝑃𝑚 , vk 𝑚 , 𝛿 𝑚 ) with 𝑃𝑖 ⊑ 𝑃𝑖−1 for all 𝑖 (V2), a spend authorization 𝜌 valid under vk 𝑚 (V4), and

Defining Purpose-Limited Secrets

17

𝑜 ∈ 𝐴(𝑃𝑚 ) (V3). Purposes along the chain do not increase, so 𝐴(𝑃𝑚 ) ⊆ 𝐴(𝑃0 ), and no redemption exceeds the bank-signed 𝑃0 unless 𝜎 is forged. Ð Suppose the coalition wins, so 𝑜 ∉ 𝑗 𝐴(𝑃𝑛 𝑗 ), 𝑜 was not performed through 𝑂 use , and hence 𝑃𝑚 @ 𝑃𝑛 𝑗 for every 𝑗 (otherwise 𝑜 ∈ 𝐴(𝑃𝑚 ) ⊆ 𝐴(𝑃𝑛 𝑗 ) by Definition 3). Call a key honest if an honest holder or delegator generated it. Secrets leave honest parties only through 𝑂 deleg , so the coalition holds the secret of an honest key only if that key was delegated, with purpose in 𝐺. An honest-use transcript contains a spend authorization on its own challenge, which hashes its operation, so reusing it for 𝑜 requires a collision in 𝐻. We show that the winning transcript contains a valid signature, a certificate 𝛿𝑖 or the spend authorization 𝜌, under an honest key on a message its owner never signed. Case 1: vk 𝑚 is honest and not delegated. Then 𝜌 is a signature under vk 𝑚 on a challenge its owner never signed: the owner signed only the challenges of its own 𝑂 use spends, whose operations differ from 𝑜, so an equal challenge is a collision in 𝐻. Call the chain authentic if the bank issued 𝜎 and, for each 𝑖, the honest owner of vk𝑖−1 signed ⟨𝑃𝑖 , vk𝑖 ⟩. An honest key is certified once, by its creator, for the purpose of its handle. Case 2: vk 𝑚 is honest and delegated. On an authentic chain 𝑃𝑚 is the purpose with which vk 𝑚 was delegated, so 𝑃𝑚 ∈ 𝐺, a contradiction. So the chain is not authentic. Case 3: vk 𝑚 is not honest. The coalition may supply vk 𝑚 without knowing a secret key for it. An authentic chain ends at an honest key, so again the chain is not authentic. In Cases 2 and 3, let 𝑖★ be the least index whose certificate was not honestly issued. Unless 𝜎 is forged, 𝑖★ ≥ 1 and the prefix up to vk𝑖★ −1 is authentic, so vk𝑖★ −1 is honest. If the coalition held sk𝑖★ −1 , then vk𝑖★ −1 was delegated for 𝑃𝑖★ −1 ∈ 𝐺, and (V2) would give 𝑃𝑚 ⊑ 𝑃𝑖★ −1 , a contradiction. So the honest owner of vk𝑖★ −1 kept its key and never signed ⟨𝑃𝑖★ , vk𝑖★ ⟩, yet (V2) accepts 𝛿𝑖★ . A reduction guesses which honest key receives the forgery, or that it is the bank signature, plants its EUF-CMA challenge key there, answers every honest signature with its signing oracle, and outputs the forged 𝛿𝑖★ , 𝜌, or 𝜎. With 𝑞 𝑘 honest delegation keys, and AdvEUF and AdvCR 𝑋 𝐻 the maximal advantages of a PPT adversary in forging 𝑋 and finding a collision in 𝐻, EUF CR Advatten (A) ≤ 𝑞 𝑘 · AdvEUF Σdel + Advbank + Adv 𝐻 .

The spend authorization (V4) rules out the truncation attack, in which the coalition presents a shorter, all-honest chain ending at the key of a wider prefix, a key it was never given. ⊔ ⊓ Theorem 2 (One-use traceability). This is traceable limitation (Definition 11) for use bound 1, with 𝐿 the bank’s deposit log, in which a use is a distinct tuple ( 𝐴, 𝐷, 𝑑, 𝑟 1 , 𝑟 2 ), 𝑅 its withdrawal-record store, and the secret the instance ( 𝐴, 𝐷). Assume discrete log is hard in G, in the random-oracle model. If 𝐿 contains two tuples for an instance ( 𝐴, 𝐷) issued under pseudonym 𝑌 = 𝑔1𝑢 , then, except with negligible probability, Trace (pp, ( 𝐴, 𝐷), 𝐿, 𝑅) recovers 𝑢, hence 𝑌 , and outputs the withdrawing account, whose record for ( 𝐴, 𝐷) is unique. No nonce freshness is assumed, and merchants may collude with the spender, though logged tuples pass (V1)–(V5). That a holder cannot forge a second certified instance from one withdrawal is unforgeability of the bank signature (Theorem 1).

18

B. Mittal and A. Thakkar

Proof. The reduction B is given (𝑔1 , 𝑔2 ), must output 𝑤2 , and plays the bank. Dividing the two (V5) equations cancels 𝐷: ′

𝑔1Δ1 𝑔2Δ2 = 𝐴 𝑑−𝑑 ,

(Δ1 , Δ2 ) := (𝑟 1 − 𝑟 1′ , 𝑟 2 − 𝑟 2′ ).

Extracting 𝜋 by rewinding (accounted gives 𝑢 and 𝑠, so B knows the
for below) ′ ′ representation 𝑢𝑠(𝑑 − 𝑑 ′ ), 𝑠(𝑑 − 𝑑 ′ ) of 𝐴 𝑑−𝑑 . If 𝑑 = 𝑑 ′ , then 𝐴 𝑑−𝑑 = 1 has the representation (0, 0), and since the tuples differ, (Δ1 , Δ2 ) ≠ (0, 0) is
a second one, giving 𝑤2 by Lemma 1. If 𝑑 ≠ 𝑑 ′ and (Δ1 , Δ2 ) ≠ 𝑢𝑠(𝑑 − 𝑑 ′ ), 𝑠(𝑑 − 𝑑 ′ ) , again B outputs 𝑤2 . Otherwise Δ2 = 𝑠(𝑑 − 𝑑 ′ ) ≠ 0, since the bank’s check 𝐴 ≠ 1 forces 𝑠 ≠ 0 (by the check, not by sampling, since 𝑠 is adversarial), and Δ1 Δ2−1 = 𝑢; so Trace outputs ⊥ on Δ2 = 0 only for an off-form pair. Then 𝑌 = 𝑔1𝑢 is the declared pseudonym, and the bank’s record for ( 𝐴, 𝐷), unique and verifying because the bank checked both at issuance, names the account. Call an opening pair off-form if it is not the representation above; Trace fails only on an off-form pair. Let 𝜀 be its probability and 𝑞 𝐻 the number of random-oracle queries. As usual, the adversary queries 𝐻 on the input of every 𝜋 it submits, at the cost of one query each in 𝑞 𝐻 , so each accepted 𝜋 has a query that fixed its challenge; B selects the query for this instance’s 𝜋, whose input contains (𝑌 , 𝐴), rewinds the adversary to it, and reruns it with a fresh answer. By the general forking lemma [62,12], with probability at least 𝜀(𝜀/𝑞 𝐻 − 1/𝑞) both runs produce an accepted 𝜋 with the same commitment and different challenges, giving (𝑢, 𝑠), together with an off-form pair, giving 𝑤2 . So 𝜀(𝜀/𝑞 𝐻 − 1/𝑞) ≤ AdvDL , which gives √︃ 𝑞𝐻 + 𝑞 𝐻 · AdvDL , Pr[ Trace fails] ≤ 𝜀 ≤ 𝑞 negligible in 𝜆.

⊔ ⊓

Theorem 3 (Non-frameability). This is the non-frameability of Definition 11 for the token, per instance, with “sharing” meaning delegating that instance. Assume discrete log is hard in G and the account signature is EUF-CMA, in the random-oracle model. Then no PPT coalition, including a corrupt bank, merchants, and delegates of other instances, makes Trace name an honest account 𝑈 for an instance that 𝑈 never withdrew, or withdrew but neither delegated nor spent twice, except with negligible probability. Proof (sketch). Trace names 𝑈 only through a record verifying under avk𝑈 . A record 𝑈 did not sign is a forgery of the account signature. For a record 𝑈 did sign, on an instance 𝑈 neither delegated nor double-spent, a reduction plants a discrete-log challenge as the coin’s pseudonym 𝑌 ∗ and simulates the one honest spend by choosing the opening first, solving for 𝐷, and programming the random oracle, so any framing of 𝑈 recovers log𝑔1 𝑌 ∗ ; the corrupt-bank case is included. The full proof is in Appendix B. ⊔ ⊓ Corollary 2 (Verifier-gated mediation). Under the assumptions of Theorem 1, the token is mediation-secure in the verifier-gated mode (Definition 10), with the secret a bearer object and Accept the checks (V1)–(V5) run by the merchant or bank. Proof. new (𝑃) is 𝑂 grant (𝑃) Ð followed by Ð𝑂 deleg , so a gated win is an accepted redemption of an operation outside 𝑗 𝐼 (𝑃𝑛 𝑗 ) = 𝑗 𝐴(𝑃𝑛 𝑗 ), the proxy being exact, with no 𝑂 use queries. Theorem 1 bounds its probability; this is Remark 1 for the token. ⊔ ⊓

Defining Purpose-Limited Secrets

19

Table 2. Properties of related designs in their base form. Each property of the token appears in an earlier design; the token combines them. Public verif.: verifiers hold no key that lets them mint credentials. –: not provided. Design

Attenuation Public verif. Use bound Over-use traced Payer anonymity

Macaroons [16] SPKI/SDSI [39] Brands e-cash [23] Compact e-cash [27] Deleg. anon. cred. [10]

✓ ✓ – – ✓

– ✓ ✓ ✓ ✓

– online check 1 wallet size –

– – ✓ ✓ –

– – ✓ ✓ ✓

This token Anonymous variant

✓ –

✓ ✓

1 1

✓, per coin ✓, per account

– ✓

4.5

Comparison with Related Designs

The token combines attenuation with public verification, a per-coin use bound with tracing, and non-frameability for coins the account never delegated. None of these properties is new, and the token does not provide anonymity together with delegation (Table 2). Macaroons attenuate, but their verifiers can mint (Section 4.2), which suits a service that both issues and verifies. SPKI/SDSI chains attenuate with public verification, and the token’s chain is an instance of them; SPKI bounds use only through an online check with the issuer, which is stateful mediation, and does not trace over-use. Brands’ e-cash and compact e-cash bound use and trace double-spenders while keeping honest payers anonymous, but have no delegation and no purpose beyond the coin’s value. Delegatable anonymous credentials attenuate along anonymous chains but neither bound nor trace use. The anonymous variant below gives payer anonymity without delegation. 4.6

An Anonymous Variant

The token is not anonymous: the bank sees ( 𝐴, 𝐷) at issuance, so it can link a redemption to the withdrawal. Hiding ( 𝐴, 𝐷) removes the per-coin record that tracing uses, and tracing must then go through a per-account value, which a delegate would learn (Section 4.3). An anonymous variant therefore drops delegation and replaces the per-coin identity by a per-account one, as in Brands’ scheme [23]: the account registers 𝑌 = 𝑔1𝑢 once, which the bank refuses if 𝑌 𝑔2 = 1, since every coin would then be 1, and each coin is 𝐴 = (𝑌 𝑔2 ) 𝑠 for a fresh 𝑠 ≠ 0. The bank signs ( 𝐴, 𝐷, vk0 ) blindly. The maximal purpose stays authenticated through the key: the bank keeps one signing key for each of a fixed set of maximal purposes 𝑃0 , as e-cash keeps one key per denomination, and (V1) uses the key for 𝑃0 . Issuance in the variant. Issuance is Brands’ withdrawal protocol [23] with vk0 added to the signed message. For a third generator 𝑔0 , the key for 𝑃0 is 𝑥 ∈ Z𝑞 with public ℎ = 𝑔0𝑥 , and each account holds 𝑧 = (𝑌 𝑔2 ) 𝑥 . A signature on 𝑚 = ( 𝐴, 𝐷, vk0 ) is a tuple 𝜎 = (𝑧 ′ , 𝛼′ , 𝛽′ , 𝛾 ′ ) with 𝛾′

′

𝑔0 = ℎ 𝑐 𝛼 ′ ,

′

′

𝐴 𝛾 = (𝑧 ′ ) 𝑐 𝛽′ ,

𝑐 ′ = 𝐻 (𝑚, 𝑧 ′ , 𝛼′ , 𝛽′ ),

20

B. Mittal and A. Thakkar 𝜂

the hash value read in Z𝑞 \ {0}. In a session the bank sends 𝛼 = 𝑔0 and 𝛽 = (𝑌 𝑔2 ) 𝜂 for a fresh 𝜂. The holder draws 𝑠 ≠ 0, the pads, (sk0 , vk0 ) ← Kg, and blinding values 𝑒 1 ∈ Z𝑞 \ {0} and 𝑒 2 ∈ Z𝑞 ; it forms 𝐴 and 𝐷, sets 𝑧 ′ = 𝑧 𝑠 , 𝛼′ = 𝛼 𝑒1 𝑔0𝑒2 , and 𝛽′ = 𝛽 𝑠𝑒1 𝐴𝑒2 , 𝛾 and sends 𝑐 = 𝑐 ′ /𝑒 1 . The bank answers 𝛾 = 𝑐𝑥 + 𝜂; the holder accepts iff 𝑔0 = ℎ 𝑐 𝛼 and 𝛾 𝑐 ′ (𝑌 𝑔2 ) = 𝑧 𝛽, and sets 𝛾 = 𝑒 1 𝛾 + 𝑒 2 . Redemption is as in Section 4.3 with the empty chain, so 𝜌 = Sgsk0 (𝑑), and (V1) checks 𝜎 under the key for 𝑃0 . The key is well formed if every account’s 𝑧 is (𝑌 𝑔2 ) 𝑥 for the 𝑥 with ℎ = 𝑔0𝑥 ; the bank can make this checkable by publishing 𝑔1𝑥 and 𝑔2𝑥 with a proof that they share the exponent of ℎ, so that each holder computes 𝑧 itself. A bank that gave two accounts values 𝑧 with different exponents could tell their coins apart by 𝑧 ′ . Lemma 2 (Issuance view). Let 𝑊 = (𝑠, 𝑎 1 , 𝑎 2 , sk0 ) be a holder’s coin values, 𝑚 = ( 𝐴, 𝐷, vk0 ) the message they determine for account 𝑌 , and 𝑆(𝑚) the set of valid signatures on 𝑚 whose first component is 𝐴 𝑥 . For every bank strategy under a well-formed key and every view 𝑣 of a session in which the holder accepts, Pr[𝑊 = 𝑤, 𝜎 = 𝜁 | 𝑉 = 𝑣] = Pr[𝑊 = 𝑤] ·

[ 𝜁 ∈ 𝑆(𝑚) ] . 𝑞

So, given the bank’s view, the coin values keep their honest distribution, and 𝜎 is uniform on 𝑆(𝑚) and depends on the coin values only through 𝑚. Theorem 4 (Payer unlinkability, anonymous variant). In the anonymous variant under a well-formed key, let an adversary of unbounded power play the bank and all merchants, run two sequential issuance sessions with honest accounts of its choice under the key for one 𝑃0 , and then see each coin redeemed once, in random order, for one public transaction (𝑀 ′ , 𝑎, 𝑡). It guesses the order with advantage 0. So issuance is unlinkable to redemption, and distinct single spends are mutually unlinkable, among coins issued for the same 𝑃0 and redeemed for the same transaction. Proof (sketch). For a fixed accepting view, each pair of a coin value and a valid signature is reached by exactly one choice of (𝑒 1 , 𝑒 2 ), which gives Lemma 2; this is Brands’ count of the holder’s choices that match a withdrawal view to a payment view [23, Prop. 11], and vk0 and the pads enter the holder’s only message through 𝑐 ′ . Given the bank’s view, for an account value 𝑢, which has 𝑢 + 𝑤2 ≠ 0 by the registration check, a uniform 𝑠 ≠ 0 makes 𝐴 = 𝑔1𝑠 (𝑢+𝑤2 ) uniform over G \ {1}; given ( 𝐴, 𝐷, 𝑑) and 𝜎, the opening (𝑟 1 , 𝑟 2 ) is uniform over the 𝑞 representations of 𝐴 𝑑 𝐷; and 𝜌 depends only on sk0 and 𝑑. None of these depends on 𝑢, so a redemption transcript is independent of the account, though not of 𝑠, which 𝐴 determines. The full proofs are in Appendix C. ⊔ ⊓ The variant changes the accountability model. The bank never sees ( 𝐴, 𝐷), so it cannot store the per-coin record 𝜌𝑤 ; a double-spend recovers the registered value 𝑢, which names the account [23,27]. That tracing rests on Brands’ assumption that the protocol is restrictive, so that every coin a holder obtains has 𝐴 = (𝑌 𝑔2 ) 𝑠 for an 𝑠 ≠ 0 it knows, a nonstandard assumption [23,27], and the bank’s unforgeability needs sequential issuance, since concurrent blind Schnorr issuance falls to a polynomial-time attack on the underlying ROS problem [66,14]. The variant thus trades the per-coin identity and its

Defining Purpose-Limited Secrets

21

Table 3. The enforcement regimes. All are stated against the same intended use 𝐼; they differ in what happens to an off-purpose operation and in what the guarantee rests on. Regime

a violation is

rests on

examples

Confinement (UP)

infeasible to produce

hardness

Confinement (IND) Mediation, held

infeasible to learn refused by a monitor that holds the key rejected by a verifier

hardness integrity of the monitor honest verifier

possible; over-use is traced

log and Trace soundness

functional and policy-based sig., token attenuation constrained PRF, FE HSM or TEE key, PKCS#11 X.509 key usage, OAuth/JWT, token redemption e-cash double-spend, traitor tracing

Mediation, gated

Accountability

non-frameable delegation for a per-account value, and the claim that one secret spans all three regimes is for the non-anonymous token. Combining anonymity with per-coin non-frameable delegation is open.

5

Discussion

5.1

What the Common Specification Adds

The paper introduces no new primitive and no new hardness assumption. The confinement games coincide with existing notions by construction (Propositions 1 and 2), the use bound of Definition 11 is e-cash over-spend tracing, and the token is assembled from known parts (Section 4.5). What the common specification changes is the target: each guarantee is stated against the intended use 𝐼, not against the predicate a primitive enforces. The game of a functional or policy-based signature is stated against the range of 𝑓 or the policy, so it cannot express that the predicate itself permits too much; the coarse build-key predicate of Section 3.4 is unforgeable in the primitive’s game and insecure in Game PL-CONF-UP. Stating every regime against one 𝐼 also relates the regimes: verifier-gated mediation follows from unpredictability confinement and an honest verifier (Remark 1), and a use bound needs a stateful monitor or accountability (Section 3.5). Table 3 places mechanisms from functional cryptography, hardware key stores, e-cash, and capability tokens in this common form. The token’s results are proved one regime at a time. We prove neither a joint security statement for the token nor a general composition theorem, which would state when a scheme that meets one regime’s game for the content of a purpose and another’s for its count meets a combined game for the whole purpose. Such a theorem would give the specification a role beyond organizing existing notions; we leave it open.

22

5.2

B. Mittal and A. Thakkar

Limitations

The release problem. Cryptography governs access to a capability, not the use of released plaintext: once the analytics firm or model trainer holds cleartext, no key can take it back. This is the cryptographic analogue of the “analog hole” in digital rights management (DRM) [40], and a formal impossibility would need a model of release. Functional encryption avoids release, since the plaintext never appears, but does not govern it. Release can be addressed only by mediation, with a trusted execution environment keeping plaintext inside an attested boundary, or by accountability after the fact. The “train one model” example is of this kind, and we construct no scheme for it. Authorship of the proxy. A mechanism enforces the proxy 𝐴, so someone must write 𝐴 and audit its fidelity to 𝐼 (Section 1). Purpose-limitation cryptography leaves this policy problem in place and moves the trust from “the monitor honors the flag” to “the proxy is faithful to the purpose”. Given a faithful proxy, a confinement guarantee holds under the stated assumptions without a trusted monitor; given an unfaithful one, the mechanism enforces the wrong predicate. Legal alignment. A scheme can enforce the specification part of GDPR Art. 5(1)(b), in that the secret cannot be used outside the declared proxy, but the compatible-use test of Art. 6(4) is a controller’s context-dependent judgment [5]. Mühlhoff and Ruschemeier argue that the doctrine cannot be traced at machine-learning scale [56]. The framework does not resolve that question; it moves the difficulty to writing and auditing the proxy. This, and reviving purpose limitation in data-driven systems more broadly [44,70], is interdisciplinary future work. Evolving purposes and further constructions. Purposes change over time, and usage control treats control as continuous rather than one-shot [60]; how attenuation, revocation, and time-bounded purposes compose is open. So are a mediation construction that binds a decryption key to an attested trusted execution environment and an accountability construction that traces off-purpose use of a trained model.

6

Related Work

Unifying frameworks and delegatable credentials. Cryptographic agents [3] give one schema-based security notion for functional encryption, obfuscation, and related secrecy primitives; they cover the indistinguishability side, without an unforgeable-capability form, a delegation lattice, or an accountability regime. Access control encryption [38] governs which parties may send and receive information, with a sanitizer in our mediation position, and so combines confinement and mediation for one capability. Küsters, Truderung, and Vogt [53] define accountability in general; traceable limitation is a purpose-specific instance over usage logs. Delegatable anonymous credentials [31,10] give monotone attenuation along anonymous chains; Section 4.5 compares them, macaroons, SPKI/SDSI [39], and e-cash with the token.

Defining Purpose-Limited Secrets

23

Confinement. Functional encryption and its relatives confine what a ciphertext reveals [63,46,15,51,19,1]; constrained and puncturable PRFs confine which inputs a key evaluates [20,22,52,64]; functional, policy-based, attribute-based, and sanitizable signatures confine which messages a key signs [22,11,55,7]; and conditional proxy re-encryption confines a delegated transformation [17,8,69]. Each is an instance of a confinement game with the primitive’s predicate as the proxy. Mediation. X.509 and PKCS#11 usage flags are the deployed “key for a purpose”, mediation without confinement at the key level (Section 3.5); the attacks on PKCS#11 show that the flags carry no cryptographic hardness [36,58,35,21,26]. Macaroons and the OAuth/JWT token family attenuate and bind bearer credentials checked by verifiers [16,47,30,49,42]. Macaroons sit between hardness and mediation: attenuation is unforgeable to bearers, but the verifier enforces the meaning of a caveat and holds the root key. Accountability. Traitor tracing attributes leaked keys [34,18], non-transferable credentials deter sharing [28], and e-cash makes a coin a one-use token whose double-spend identifies the withdrawer [32,33,23,27,29], the pattern the token adopts. Purpose in access control, usage control, and law. Purpose-based access control [24,25] attaches intended purposes to data and access purposes to requests, and grants access when they comply; usage control (UCON) [60] adds obligations, conditions, and continuous enforcement; Hippocratic databases [2], policy languages [37,6], and sticky policies [50,61] carry purpose with the data. These lines specify an intended-use relation, often richer than ours since it can be stateful and depend on context, and enforce it through a reference monitor; in our terms they specify 𝐼 by policy and enforce it by mediation. The difference we address is narrow: under confinement the secret itself enforces the proxy by hardness, so the limit holds when no monitor is present or the monitor is bypassed. Purpose has also been formalized for audit, as a plan [68] or a workflow [48] against which behavior is tested after the fact, close in spirit to accountability; contextual integrity identifies the observable flow parameters (sender, recipient, information type, transmission conditions) [57,9], the kind of observable over which an intended-use relation is written. The legal texts [59,41,5] define purpose limitation as a principle, and the confinement idea goes back to Lampson [54]. The closest cryptographic treatment uses attribute-based encryption to enforce purposes rather than defining a property [67].

7

Conclusion

Purpose limitation can be defined and proved as a property of a secret once two objects are kept apart: the admissible set 𝐴(𝑃) that a mechanism permits and the intended use 𝐼 that the issuer declares, against which confinement, mediation, and accountability give three different guarantees. The confinement games recover existing notions in key-query form; stated against 𝐼, they also register a predicate that permits too much and relate the regimes, and one payment token uses all three on a single secret. The paper introduces no new primitive or hardness assumption, and a general composition theorem is open. A

24

B. Mittal and A. Thakkar

mechanism enforces 𝐴(𝑃), not the human purpose, so fidelity to that purpose remains a declared, non-cryptographic obligation; within that boundary, “this key can be used only for the operations in 𝐴(𝑃)” is a statement one can prove.

References 1. Abdalla, M., Bourse, F., De Caro, A., Pointcheval, D.: Simple functional encryption schemes for inner products. In: PKC. LNCS, vol. 9020, pp. 733–751. Springer (2015) 2. Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Hippocratic databases. In: VLDB. pp. 143–154 (2002) 3. Agrawal, S., Agrawal, S., Prabhakaran, M.: Cryptographic agents: Towards a unified theory of computing on encrypted data. In: EUROCRYPT. LNCS, vol. 9057, pp. 501–531. Springer (2015) 4. Agrawal, S., Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption: New perspectives and lower bounds. In: CRYPTO. LNCS, vol. 8043, pp. 500–518. Springer (2013) 5. Article 29 Data Protection Working Party: Opinion 03/2013 on purpose limitation (WP 203). European Commission (2013) 6. Ashley, P., Hada, S., Karjoth, G., Powers, C., Schunter, M.: Enterprise privacy authorization language (EPAL 1.2). W3C Member Submission (2003) 7. Ateniese, G., Chou, D.H., de Medeiros, B., Tsudik, G.: Sanitizable signatures. In: ESORICS. LNCS, vol. 3679, pp. 159–177. Springer (2005) 8. Ateniese, G., Fu, K., Green, M., Hohenberger, S.: Improved proxy re-encryption schemes with applications to secure distributed storage. In: NDSS (2005) 9. Barth, A., Datta, A., Mitchell, J.C., Nissenbaum, H.: Privacy and contextual integrity: Framework and applications. In: IEEE S&P. pp. 184–198 (2006) 10. Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., Shacham, H.: Randomizable proofs and delegatable anonymous credentials. In: CRYPTO. LNCS, vol. 5677, pp. 108–125. Springer (2009) 11. Bellare, M., Fuchsbauer, G.: Policy-based signatures. In: PKC. LNCS, vol. 8383, pp. 520–537. Springer (2014) 12. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: ACM CCS. pp. 390–399 (2006) 13. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS. pp. 62–73 (1993) 14. Benhamouda, F., Lepoint, T., Loss, J., Orrù, M., Raykova, M.: On the (in)security of ROS. In: EUROCRYPT. LNCS, vol. 12696, pp. 33–53. Springer (2021) 15. Bethencourt, J., Sahai, A., Waters, B.: Ciphertext-policy attribute-based encryption. In: IEEE S&P. pp. 321–334 (2007) 16. Birgisson, A., Politz, J.G., Erlingsson, Ú., Taly, A., Vrable, M., Lentczner, M.: Macaroons: Cookies with contextual caveats for decentralized authorization in the cloud. In: NDSS (2014) 17. Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. In: EUROCRYPT. LNCS, vol. 1403, pp. 127–144. Springer (1998) 18. Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: EUROCRYPT. LNCS, vol. 4004, pp. 573–592. Springer (2006) 19. Boneh, D., Sahai, A., Waters, B.: Functional encryption: Definitions and challenges. In: TCC. LNCS, vol. 6597, pp. 253–273. Springer (2011) 20. Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: ASIACRYPT. LNCS, vol. 8270, pp. 280–300. Springer (2013)

Defining Purpose-Limited Secrets

25

21. Bortolozzo, M., Centenaro, M., Focardi, R., Steel, G.: Attacking and fixing PKCS#11 security tokens. In: ACM CCS. pp. 260–269 (2010) 22. Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: PKC. LNCS, vol. 8383, pp. 501–519. Springer (2014) 23. Brands, S.: Untraceable off-line cash in wallets with observers. In: CRYPTO. LNCS, vol. 773, pp. 302–318. Springer (1993) 24. Byun, J.W., Bertino, E., Li, N.: Purpose based access control of complex data for privacy protection. In: ACM SACMAT. pp. 102–110 (2005) 25. Byun, J.W., Li, N.: Purpose based access control for privacy protection in relational database systems. The VLDB Journal 17(4), 603–619 (2008) 26. Cachin, C., Chandran, N.: A secure cryptographic token interface. In: IEEE CSF. pp. 141–153 (2009) 27. Camenisch, J., Hohenberger, S., Lysyanskaya, A.: Compact e-cash. In: EUROCRYPT. LNCS, vol. 3494, pp. 302–321. Springer (2005) 28. Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: EUROCRYPT. LNCS, vol. 2045, pp. 93–118. Springer (2001) 29. Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: CRYPTO. LNCS, vol. 3152, pp. 56–72. Springer (2004) 30. Campbell, B., Bradley, J., Tschofenig, H.: Resource indicators for OAuth 2.0. RFC 8707 (2020) 31. Chase, M., Lysyanskaya, A.: On signatures of knowledge. In: CRYPTO. LNCS, vol. 4117, pp. 78–96. Springer (2006) 32. Chaum, D.: Blind signatures for untraceable payments. In: CRYPTO. pp. 199–203. Plenum Press (1982) 33. Chaum, D., Fiat, A., Naor, M.: Untraceable electronic cash. In: CRYPTO. LNCS, vol. 403, pp. 319–327. Springer (1988) 34. Chor, B., Fiat, A., Naor, M.: Tracing traitors. In: CRYPTO. LNCS, vol. 839, pp. 257–270. Springer (1994) 35. Clulow, J.: On the security of PKCS #11. In: CHES. LNCS, vol. 2779, pp. 411–425. Springer (2003) 36. Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., Polk, W.: Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile. RFC 5280 (2008) 37. Cranor, L., Langheinrich, M., Marchiori, M., Presler-Marshall, M., Reagle, J.: The platform for privacy preferences 1.0 (P3P1.0) specification. W3C Recommendation (2002) 38. Damgård, I., Haagh, H., Orlandi, C.: Access control encryption: Enforcing information flow with cryptography. In: TCC-B. LNCS, vol. 9986, pp. 547–576. Springer (2016) 39. Ellison, C.M., Frantz, B., Lampson, B., Rivest, R., Thomas, B., Ylonen, T.: SPKI certificate theory. RFC 2693 (1999) 40. Erickson, J.S.: Fair use, DRM, and trusted computing. Communications of the ACM 46(4), 34–39 (2003) 41. European Union: Regulation (EU) 2016/679 (general data protection regulation), art. 5(1)(b), art. 6(4). Official Journal of the European Union (2016) 42. Fett, D., Campbell, B., Bradley, J., Lodderstedt, T., Jones, M.B., Waite, D.: OAuth 2.0 demonstrating proof of possession (DPoP). RFC 9449 (2023) 43. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: CRYPTO. LNCS, vol. 263, pp. 186–194. Springer (1986) 44. Finck, M., Biega, A.J.: Reviving purpose limitation and data minimisation in data-driven systems. Technology and Regulation 2021, 44–61 (2021) 45. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281–308 (1988)

26

B. Mittal and A. Thakkar

46. Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM CCS. pp. 89–98 (2006) 47. Hardt, D.: The OAuth 2.0 authorization framework. RFC 6749 (2012) 48. Jafari, M., Fong, P.W.L., Safavi-Naini, R., Barker, K., Sheppard, N.P.: Towards defining semantic foundations for purpose-based privacy policies. In: ACM CODASPY. pp. 213–224 (2011) 49. Jones, M.B., Bradley, J., Sakimura, N.: JSON web token (JWT). RFC 7519 (2015) 50. Karjoth, G., Schunter, M., Waidner, M.: Platform for enterprise privacy practices: Privacyenabled management of customer data. In: PET. LNCS, vol. 2482, pp. 69–84. Springer (2002) 51. Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: EUROCRYPT. LNCS, vol. 4965, pp. 146–162. Springer (2008) 52. Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM CCS. pp. 669–684 (2013) 53. Küsters, R., Truderung, T., Vogt, A.: Accountability: Definition and relationship to verifiability. In: ACM CCS. pp. 526–535 (2010) 54. Lampson, B.W.: A note on the confinement problem. Communications of the ACM 16(10), 613–615 (1973) 55. Maji, H.K., Prabhakaran, M., Rosulek, M.: Attribute-based signatures. In: CT-RSA. LNCS, vol. 6558, pp. 376–392. Springer (2011) 56. Mühlhoff, R., Ruschemeier, H.: Updating purpose limitation for AI: A normative approach from law and philosophy. International Journal of Law and Information Technology 33, eaaf003 (2025) 57. Nissenbaum, H.: Privacy as contextual integrity. Washington Law Review 79(1) (2004) 58. OASIS: PKCS #11 cryptographic token interface base specification, v3.0. OASIS Standard (2020) 59. OECD: Guidelines governing the protection of privacy and transborder flows of personal data. OECD (1980) 60. Park, J., Sandhu, R.: The UCON 𝐴𝐵𝐶 usage control model. ACM Transactions on Information and System Security (TISSEC) 7(1), 128–174 (2004) 61. Pearson, S., Casassa Mont, M.: Sticky policies: An approach for managing privacy across multiple parties. IEEE Computer 44(9), 60–68 (2011) 62. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361–396 (2000) 63. Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: EUROCRYPT. LNCS, vol. 3494, pp. 457–473. Springer (2005) 64. Sahai, A., Waters, B.: How to use indistinguishability obfuscation: Deniable encryption, and more. In: ACM STOC. pp. 475–484 (2014) 65. Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991) 66. Schnorr, C.P.: Security of blind discrete log signatures against interactive attacks. In: ICICS. LNCS, vol. 2229, pp. 1–12. Springer (2001) 67. Syed-Winkler, S., Pape, S., Sabouri, A.: A data protection-oriented system model enforcing purpose limitation for connected mobility. In: ACM CSCS. pp. 10:1–10:11 (2022) 68. Tschantz, M.C., Datta, A., Wing, J.M.: Formalizing and enforcing purpose restrictions in privacy policies. In: IEEE S&P. pp. 176–190 (2012) 69. Weng, J., Deng, R.H., Ding, X., Chu, C.K., Lai, J.: Conditional proxy re-encryption secure against chosen-ciphertext attack. In: ASIACCS. pp. 322–332 (2009) 70. Wolf, K., Pallas, F., Tai, S.: Messaging with purpose limitation: Privacy-compliant publishsubscribe systems. In: IEEE EDOC. pp. 162–172 (2021)

Defining Purpose-Limited Secrets

A

27

Proofs of Propositions 1 and 2

Proof (of Proposition 1). Forward: given A winning PL-CONF-UP, the reduction plays the unforgeability game, receives vk, sets pp := vk, forwards each 𝑂 Constrain ( 𝑓 ) to its key oracle, and returns A’s output (𝑚 ∗ , 𝜎 ∗ ). A’s win gives Verify (vk, 𝑚 ∗ , 𝜎 ∗ ) = 1 and Ð 𝑚 ∗ ∉ 𝑖 range ( 𝑓𝑖 ), a forgery; no signing query is made. Back: a key-query forger is a PL-CONF-UP adversary under the same translation. Both directions preserve the advantage. ⊔ ⊓ Proof (of Proposition 2). The two games coincide after renaming, with the simulator that outputs the entitled leakage when it is nonempty and a uniform value otherwise. 𝑂 Constrain (𝐶) is the constrained-key oracle, and all its queries precede the challenge. If the challenge point 𝑥 ∗ is admissible for some queried 𝐶𝑖 , the entitled leakage is 𝐹𝑘 (𝑥 ∗ ) itself and the twoÐexperiments are identical. Otherwise 𝐶𝑖 (𝑥 ∗ ) = 0 for every queried 𝐶𝑖 , that is, 𝑥 ∗ ∉ 𝑖 𝐼 (𝐶𝑖 ); the entitled leakage is empty, and real-versus-ideal is 𝐹𝑘 (𝑥 ∗ )-versus-uniform, the constrained-PRF challenge. Advantages are equal. The proposition is for one challenge point, since a hybrid over several points needs 𝐹𝑘 at the other non-admissible points, which a game without an evaluation oracle does not supply. ⊔ ⊓

B

Proof of Theorem 3

Proof. A framing makes Trace (pp, ( 𝐴, 𝐷), 𝐿, 𝑅) name an honest account 𝑈, necessarily through a record verifying under avk𝑈 , for an instance 𝑈 never withdrew, or withdrew but neither delegated nor spent twice. Split its probability as 𝜀 = 𝜀forge + 𝜀kept by whether 𝑈 signed the naming record. Branch 1 (forged record). A reduction guesses the framed account among the 𝑛 = poly(𝜆) honest accounts, plants its EUF-CMA challenge key as that avk𝑈 , answers the account’s withdrawals with its signing oracle, and outputs the naming record. Since 𝜌𝑤 signs (𝑌 , 𝐴, 𝐷), a record for an instance 𝑈 never withdrew, or with a swapped pseudonym, is such a forgery. So 𝜀 forge ≤ 𝑛 · AdvEUF . Branch 2 (genuine record). The instance is one 𝑈 withdrew and neither delegated nor spent twice. B receives Γ ∈ G and must output log𝑔1 Γ. It guesses the framed instance among the 𝑁 = poly(𝜆) honest withdrawals and plants 𝑌 ∗ := Γ as its pseudonym, without knowing 𝑢 ∗ = log𝑔1 Γ. Every other honest coin gets a coin identity B samples, so B answers issuance, spends, and 𝑂 deleg for them normally. B uses the public (𝑔1 , 𝑔2 ) and never needs 𝑤2 ; it generates the bank keys if the bank is honest, and otherwise plays honest holders to A’s bank. It holds the honest accounts’ keys, so it signs records normally. The planted coin. B picks 𝑠 ← Z𝑞 and (sk0 , vk0 ) ← Kg, sets 𝐴 := (Γ𝑔2 ) 𝑠 , and ∗ simulates 𝜋 for the true statement 𝑌 ∗ = 𝑔1𝑢 ∧ 𝐴 = (𝑌 ∗ 𝑔2 ) 𝑠 by programming the random oracle. It picks the spend values 𝑑, 𝑟 1 , 𝑟 2 ← Z𝑞 in advance, sets 𝐷 := 𝑔1𝑟1 𝑔2𝑟2 𝐴 −𝑑 , signs the record on (𝑌 ∗ , 𝐴, 𝐷), and obtains 𝜎 on ( 𝐴, 𝐷, 𝑃0 , vk0 ). When the owner spends the coin, through a handle whose chain ends at vk 𝑛 , on (𝑀 ′ , 𝑎, 𝑡) with merchant nonce 𝑁, B picks a fresh 𝑁𝑈 , programs 𝐻 ( 𝐴, 𝐷, vk 𝑛 , 𝑀 ′ , 𝑎, 𝑡, 𝑁, 𝑁𝑈 ) := 𝑑, and sends the opening with

28

B. Mittal and A. Thakkar

𝜌 := Sgsk𝑛 (𝑑) and that handle’s chain. Since 𝑁𝑈 is fresh and uniform, the programmed point is unqueried except with negligible probability, even if a corrupt bank fixed ( 𝐴, 𝐷) and the transaction in advance, and (V1)–(V5) hold by construction. If the planted instance is later delegated or spent again, it is no longer a framing target and B aborts, losing no framing on it. If the owner never spends it, the coalition must produce both openings itself. Unless the programmed point was queried earlier or B aborts, the simulation is perfect. In a real spend, (𝑟 1 , 𝑟 2 ) = (𝑢𝑠𝑑 + 𝑎 1 , 𝑠𝑑 + 𝑎 2 ) is uniform in Z2𝑞 with 𝐷 = 𝑔1𝑟1 𝑔2𝑟2 𝐴 −𝑑 , which is the distribution B samples; 𝜌 is a real signature, and the oracle is programmed at one high-entropy point. Extraction. A framing on the planted instance makes Trace recover the recorded ∗ pseudonym 𝑌 ∗ = 𝑔1𝑢 , which happens exactly when the linear recovery from the two ∗ openings returns 𝑢 . Openings that encode another representation of 𝐴 give some 𝑢 ′ ≠ 𝑢 ∗ and attribute elsewhere, so they do not frame 𝑈. Hence B outputs 𝑢 ∗ , and ′ AdvDL B ≥ 𝜀 kept /𝑁 − negl (𝜆), the negligible term collecting oracle clashes, 𝑑 = 𝑑 EUF DL collisions, and 𝑠 = 0. With Branch 1, 𝜀 ≤ 𝑛 · Adv + 𝑁 · Adv + negl (𝜆). ⊔ ⊓

C

Proofs of Lemma 2 and Theorem 4

Proof (of Lemma 2). Fix an accepting view 𝑣, which contains the bank’s messages 𝛼, 𝛽, 𝛾, the account’s 𝑧 = (𝑌 𝑔2 ) 𝑥 , and the holder’s message 𝑐. The holder’s randomness is (𝑤, 𝑒 1 , 𝑒 2 ), independent of the bank’s coins, with (𝑒 1 , 𝑒 2 ) uniform on (Z𝑞 \ {0}) × Z𝑞 . For each 𝑤 and 𝜁 = (𝑧 ′ , 𝛼′ , 𝛽′ , 𝛾 ′ ) ∈ 𝑆(𝑚), exactly one pair (𝑒 1 , 𝑒 2 ) makes the holder, on 𝑤 against 𝑣, send 𝑐 and output 𝜁. ′ 𝛾′ Every output is valid and has 𝑧 ′ = 𝑧 𝑠 = 𝐴 𝑥 , since 𝑔0 = (ℎ 𝑐 𝛼) 𝑒1 𝑔0𝑒2 = ℎ 𝑐 𝛼′ and ′ ′ 𝐴 𝛾 = (𝑧 𝑐 𝛽) 𝑠𝑒1 𝐴𝑒2 = (𝑧 ′ ) 𝑐 𝛽′ by the holder’s checks. Conversely, let 𝜁 ∈ 𝑆(𝑚) have ′ hash value 𝑐 . Hash values are nonzero, so 𝑐 ≠ 0; set 𝑒 1 := 𝑐 ′ /𝑐 and 𝑒 2 := 𝛾 ′ − 𝑒 1 𝛾. By the checks, 𝛾′

−𝛾

𝛾′

′

𝛼 𝑒1 𝑔0𝑒2 = 𝑔0 (𝛼𝑔0 ) 𝑒1 = 𝑔0 ℎ −𝑐 = 𝛼′ ,
𝑠𝑒 ′ ′ ′ 𝛽 𝑠𝑒1 𝐴𝑒2 = 𝐴 𝛾 𝛽(𝑌 𝑔2 ) −𝛾 1 = 𝐴 𝛾 (𝑧 ′ ) −𝑐 = 𝛽′ , so the holder computes the same 𝛼′ , 𝛽′ , hence the same 𝑐 ′ , sends 𝑐 ′ /𝑒 1 = 𝑐, and outputs 𝛾 ′ = 𝑒 1 𝛾 + 𝑒 2 . The relations 𝑐 = 𝑐 ′ /𝑒 1 and 𝛾 ′ = 𝑒 1 𝛾 + 𝑒 2 make the pair unique. A valid signature with first component 𝐴 𝑥 is ( 𝐴 𝑥 , 𝑔0𝜏 , 𝐴 𝜏 , 𝜏 + 𝑥𝑐 ′ ) for 𝜏 = 𝛾 ′ − 𝑥𝑐 ′ , so |𝑆(𝑚)| = 𝑞 for every 𝑚. The bank’s messages depend on its coins and on 𝑐, so their probability is a factor 𝑃(𝑣) that does not depend on (𝑤, 𝜁), and Pr[𝑉 = 𝑣, 𝑊 = 𝑤, 𝜎 = 𝜁] = 𝑃(𝑣) · Pr[𝑊 = 𝑤] ·

[ 𝜁 ∈ 𝑆(𝑚) ] . 𝑞(𝑞 − 1)

Summing over 𝜁 and 𝑤 gives Pr[𝑉 = 𝑣] = 𝑃(𝑣)/(𝑞 − 1), and dividing gives the lemma. The hash enters only through 𝑐 ′ = 𝐻 (𝑚, 𝑧 ′ , 𝛼′ , 𝛽′ ), so adding vk0 to 𝑚 changes nothing, and the pads and sk0 reach the bank only through 𝑚. ⊔ ⊓

Defining Purpose-Limited Secrets

29

Proof (of Theorem 4). Unlinkability game. The adversary A plays the bank and all merchants. It runs two issuance sessions, for honest accounts of its choice, under the key for one maximal purpose 𝑃0 and names one transaction (𝑀 ′ , 𝑎, 𝑡). A challenger flips 𝑏 ← {0, 1} and redeems each coin once for (𝑀 ′ , 𝑎, 𝑡), answering A’s merchant nonces, in the order (𝑏, 1 − 𝑏). A outputs 𝑏 ′ and wins if 𝑏 ′ = 𝑏. Both coins share 𝑃0 and (𝑀 ′ , 𝑎, 𝑡), since these are public in the transcript. Step 1 (conditioning on issuance). Let 𝑉 be A’s view of both issuance sessions, which includes the accounts 𝑌1 , 𝑌2 . Sessions are sequential and no coin is redeemed before both end, so Lemma 2 applies to each session in turn. Given 𝑉, the coin values 𝑊1 , 𝑊2 are independent with their honest distribution, and each 𝜎 𝑗 is uniform on 𝑆(𝑚 𝑗 ), independently of everything else given 𝑚 𝑗 . Step 2 (hiding the account). Every distribution below is conditioned on 𝑉. Besides the public (𝑀 ′ , 𝑎, 𝑡) and A’s nonce 𝑁, a redemption reveals ( 𝐴, 𝐷, vk0 , 𝜎, 𝑁𝑈 , 𝑟 1 , 𝑟 2 , 𝜌). The nonce 𝑁𝑈 is fresh. Fix the account value 𝑢; the registration check gives 𝑌 𝑔2 ≠ 1, so 𝑢 + 𝑤2 ≠ 0. Then 𝐴 = (𝑌 𝑔2 ) 𝑠 = 𝑔1𝑠 (𝑢+𝑤2 ) is uniform over G \ {1}. The pads are uniform and independent of 𝑠 and sk0 , so 𝐷 is uniform, and given 𝐷 the pads are uniform over the 𝑞 representations of 𝐷. The challenge 𝑑 = 𝐻 ( 𝐴, 𝐷, vk0 , 𝑀 ′ , 𝑎, 𝑡, 𝑁, 𝑁𝑈 ) depends on the pads only through 𝐷, and 𝜎 depends on the coin values only through 𝑚 = ( 𝐴, 𝐷, vk0 ), so conditioning on 𝑑 and 𝜎 does not change this. For fixed (𝑢, 𝑠, 𝑑) the map (𝑎 1 , 𝑎 2 ) ↦→ (𝑢𝑠𝑑 +𝑎 1 , 𝑠𝑑 +𝑎 2 ) is a bijection from the representations of 𝐷 to those of 𝐴 𝑑 𝐷, so, given ( 𝐴, 𝐷, 𝑑, 𝜎), the opening is uniform over {(𝑟 1 , 𝑟 2 ) : 𝑔1𝑟1 𝑔2𝑟2 = 𝐴 𝑑 𝐷}. The spend authorization is 𝜌 = Sgsk0 (𝑑), and sk0 given vk0 is distributed by Kg independently of 𝑢, 𝑠, the pads, and 𝜎, so 𝜌 given (vk0 , 𝑑) does not depend on the account. None of these distributions depends on 𝑢 or on the session, so each redemption transcript is distributed as the same function of the public (𝑃0 , 𝑀 ′ , 𝑎, 𝑡), A’s nonce, and fresh randomness. The two coins are independent given 𝑉, so A’s view, including nonces chosen after the first redemption, has the same distribution for 𝑏 = 0 and 𝑏 = 1, and the advantage is 0. ⊓ ⊔

Related documents

• Defining Purpose-Limited Secrets#1234377
• The NSA (No Secrecy Afforded) Certificate Extension#399049
• Privacy, Transparency, and Accountability in the NSA’s Bulk Metadata Program#764359
• Software encryption — Trustonic Limited (US11218299B2)#607275
• The Secret of Secrets#1313810