LoRo-Mark:Provably Lossless and Robust Agent Watermarking

• In agent repackaging, an adversary proxies a protected agent through an API under its own identity and may alter its presentation or execution, while the owner has only black-box access.Watermarking embeds ownership evidence in behavior for later verification.Source: §1 · p. 2
• Effective agent watermarks must preserve original functionality and retain recoverable ownership evidence after modification, requirements that existing behavior-selection and trajectory methods struggle to meet.Those methods can intervene in decisions, making strict functionality preservation difficult, while their evidence remains vulnerable to downstream behavior modification.Source: §1 · p. 2
• For verification, the owner uses a secret key to reconstruct pseudorandom behavior mappings, translate observed behaviors into watermark bits, and recover the copyright message through redundancy-aware decoding.Source: §1 · pp. 2–3
• LoRo-Mark leaves normal execution untouched, activates watermarking through a MAC-authenticated forensic branch, and redundantly distributes ownership information across forensic behavior sequences.Unauthorized branch activation is reduced to MAC-EUF-CMA security, while recovery guarantees cover behavior substitution and sequence truncation.Source: §1 · pp. 2–3
• Experiments across diverse agents, models, and tasks show zero degradation on normal execution and reliable ownership verification under substantial sequence modifications.Source: §1 · p. 3

2.1 AGENT WATERMARKING

• Prior agent watermarking covers planning, execution trajectories, and memory, including Agent-Guide, AgentMark, SeqWM, ACTHOOK, AGENTWM, and MEMMARK.Agent-Guide (Huang et al., 2025) uses a green-list and aggregated z-statistic, while AgentMark (Huang et al., 2026) uses distribution-preserving conditional sampling. SeqWM (An et al., 2026) conditions on history, ACTHOOK (Meng et al., 2026) uses trigger-activated decoy actions, AGENTWM (Wang et al., 2026) biases among equivalent tool paths, and MEMMARK (Zhang et al., 2026) embeds signals in memory transitions.Source: §2.1 · p. 3

2.2 CRYPTOGRAPHICALLY UNDETECTABLE BACKDOORS

• Classifier backdoor work uses secret-key-gated signature verification, but agent reasoning and tool-use semantics require a tailored protocol.Goldwasser et al. (2022) describe a signature-verification circuit activated only for valid-signature inputs; the paper draws on this key-driven behavioral asymmetry but says classifier constructions cannot be directly reused for agents.Source: §2.2 · p. 3

3.1 THREAT MODEL

• The threat model allows a repackager to alter the service’s exposed presentation but not its execution flow, decision logic, tools, or actual trajectory; verification uses black-box access and an owner-authorized request.The adversary may know the watermarking mechanism but lacks the owner’s secret keys; verification seeks recovery despite partial trace modification or truncation.Source: §3.1 · p. 4

3.2 LORO-MARK

• LoRo-Mark combines an untouched ordinary execution path with redundant ownership information distributed across forensic behavior sequences.The two components are forensic branching for losslessness and redundant behavioral watermarking for robustness.Source: §3.2 · pp. 4–5

3.2.1 FORENSIC BRANCHING

• Only requests with a valid owner-generated authentication tag activate the forensic branch; unauthorized activation succeeds with negligible probability under standard MAC security.The tag is encoded in semantically valid task parameters, keeping the forensic request valid.Source: §3.2.1 · p. 5

3.2.2 REDUNDANT BEHAVIORAL WATERMARKING

• Redundant, interleaved copies of each ownership bit are mapped across keyed forensic behaviors, allowing recovery when sufficient copies survive substitution or truncation.Interleaving spreads copies across distant sequence positions rather than placing them consecutively.Source: §3.2.2 · pp. 5–6

4 PROVABLE LOSSLESSNESS

• If LoRo-Mark’s MAC is (εMAC, t, q, λ)-EUF-CMA secure, LoRo-Mark is (εMAC, t, q, λ)-lossless.This is the stated guarantee for distinguishers making at most q API queries without the owner’s secret keys.Source: §4 · p. 6
• An unauthorized request accepted by Forensic Detection yields a valid MAC forgery, so the probability of any unauthorized activation is at most εMAC(λ).Acceptance requires D(P, k_emb) = MAC(k_det, T_body).Source: §4 · p. 7
• Conditioned on no unauthorized activation, LoRo-Mark follows the original execution path and induces the same output distribution as the unwatermarked agent.On this path, the underlying model, orchestration policy, tool invocation, and output generation are unchanged; the APIs can differ only if unauthorized activation occurs.Source: §4 · pp. 6–7

5.1 EXPERIMENTAL SETUP

• Experiments use XLAM-FUNCTION-CALLING-60K, Qwen3-4B with ReAct by default, and additional Qwen3-8B and Ministral-8B-Instruct-2410 tests, whose results are reported as highly consistent.Utility tasks were sampled from Data, Business, and Social; evaluation reports TPR/FPR for verification and PR, RS, TS, and SR for utility. LoRo-Mark uses HMAC-SHA256, a 104-bit copyright message, and r = 3 by default.Source: §5.1 · pp. 7–8

5.2 LOSSLESSNESS

• Across Data, Business, and Social, LoRo-Mark matches the unwatermarked agent on PR, RS, TS, and SR, with ΔPR = ΔRS = ΔTS = ΔSR = 0.Each domain included 100 tasks, with DeepSeek-V3 as judge; the compared watermarking baselines introduced performance degradation.Source: Table 1 · p. 8, §5.2 · p. 8
• None of 10,000 normal requests activated the forensic branch, yielding FPR = 0.00%.This empirical result is consistent with the theoretical analysis bounding unauthorized activation by the security of the authentication mechanism.Source: §5.2 · p. 8

5.3 ROBUSTNESS

• With r = 3, LoRo-Mark maintains higher TPR than AGENTWM and AgentMark as behavior-substitution ratios increase, remaining reliable under moderate modification.The experiment randomly replaces a fraction of behaviors in the forensic sequence and tests copyright-message recovery.Source: §5.3 · p. 9, Figure 3 · p. 9
• With r = 3, LoRo-Mark reaches 100% TPR when approximately 34.6% of original steps are retained; shorter prefixes do not enable complete recovery.The experiment truncates the forensic sequence to a prefix of the original execution trace.Source: §5.3 · p. 9, Figure 3 · p. 9

5.4 ABLATION AND PARAMETER ANALYSIS

• Increasing r improves TPR at the same substitution ratio but grows forensic trace length linearly, so r = 3 is the default balance between robustness and verification overhead.This trade-off was tested with |B| = 64, |c| = 13 bytes, and r ∈ {3, 5, 7}.Source: §5.4 · p. 9, Table 2 · p. 9
• Across 12 capacity_bits and mac_bits configurations, empirical FPR follows 2^−min(capacity_bits,mac_bits); capacity_bits = 14 yields FPR = 5.0 × 10^−5, while at least 32 effective bits yield zero activations in 10,000 trials.Effective security is determined by the smaller of parameter capacity and MAC length.Source: §5.4 · p. 9

6 CONCLUSION

• LoRo-Mark uses an authenticated forensic branch and redundant ownership information to preserve normal-task utility and recover watermarks after behavior substitution or sequence truncation.The authors formally establish performance preservation under standard MAC security.Source: §6 · p. 10

AI USE STATEMENT

• The authors independently reviewed and verified AI-assisted research, experimental work, data summaries, citations, and revisions, and take responsibility for the final content.AI tools assisted with literature research, experimental design, benchmark organization, data summaries, and language polishing.Source: AI USE STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

• Reproduction materials include implementation code, dependencies, configurations, experiment instructions, and documented settings and parameters.The appendix provides detailed algorithms, assumptions, and complete proofs; the main paper describes the threat model, construction, and evaluation setup.Source: REPRODUCIBILITY STATEMENT · p. 10

Key Generation

• Key generation derives separate detection, proof, and embedding keys from a master key using PRF.Source: A DETAILED ALGORITHMS OF LORO-MARK · p. 14

Trigger Task Generation and Forensic Detection

• Trigger generation MAC-tags the task body, encodes the tag, and XORs the encoded payload into the request; detection checks the decoded tag against the expected MAC.Detection returns a positive result and tag only when the values match; otherwise it returns failure.Source: A DETAILED ALGORITHMS OF LORO-MARK · p. 14

Redundant Encoding and Behavioral Embedding

• The embedding algorithm repeats the copyright message r times and uses keyed, context-dependent selection from behavior candidates to encode it across steps.It requires reproducible execution contexts, at least two behavior candidates per step, and sufficient cumulative capacity for n·r bits.Source: A DETAILED ALGORITHMS OF LORO-MARK · p. 15

Watermark Verification

• Verification first authenticates the request, then reconstructs execution contexts and majority-decodes the claimed message while ignoring erasures and rejecting ties or empty groups.Missing behavior steps are represented as erasures; verification succeeds only when the decoded message matches the claimed message.Source: A DETAILED ALGORITHMS OF LORO-MARK · p. 15

B.1 CORRECTNESS (NO FALSE NEGATIVES)

• The guarantee assumes a positive odd repetition factor, a correctly generated trigger task, and an intact forensic sequence under reconstructible execution contexts.The configured copyright message is c, and the trigger task is produced using a correct parameter encoder–decoder pair.Source: §B.1 · p. 16
• Forensic Detection returns (1, σ) and activates the forensic branch under the proposition’s conditions.Source: §B.1 · p. 16
• Behavioral Embedding and Watermark Verification derive the same step key and reconstruct the same π_t at every step.Both derive k_step = MAC(k_prv, σ) and reconstruct π_t = PRF(k_step, o_t, B_t).Source: §B.1 · p. 16
• Each intact behavior maps back to its original index and therefore to the same q_t-bit chunk.Source: §B.1 · p. 16
• The verifier’s retained chunks concatenate to M, consisting of r identical copies of the n-bit copyright message, where n = 8|c|.The verifier retains only the first ℓ_t bits of the final chunk.Source: §B.1 · p. 16
• Majority decoding recovers ĉ = c, so Watermark Verification returns 1.Source: §B.1 · p. 16

B.2 BEHAVIOR-SEQUENCE UNFORGEABILITY

• The one-shot adversary knows T*, k_det, and k_emb, but lacks k_prv, target permutation-oracle access, and authentic forensic behavior for the distinct target contexts.The proposition also assumes n ≥ max_t q_t, pseudorandom derivation of k_step, and jointly indistinguishable domain-separated PRF evaluations.Source: §B.2 · p. 16
• In the ideal experiment, nonmember behaviors become erasures, while active-step payload positions yield independent unbiased bits across steps.For each copyright bit, its r positions lie in distinct steps; empty groups and ties are rejected, leaving acceptance probability at most 2^-n.Source: §B.2 · p. 16
• Acceptance is at most 2^-n + εKDF(λ) + εPRF(λ, S′) for fresh-context forgery under the proposition’s assumptions.The hybrid losses are bounded by εKDF(λ) and εPRF(λ, S′), respectively.Source: §B.2 · p. 16

B.3 ROBUSTNESS

• For default n=104, β=6, and r=3, retaining at least 18/52 ≈34.6% of the forensic sequence is sufficient for verification to return 1 with probability 1.Verification ignores erased copies and takes a majority over surviving copies; the retained prefix includes at least one complete copy of every copyright bit.Source: §B.3 · p. 17
• Under independent per-step substitutions and n≥β, each repeated bit has per-copy error probability ρ/2, and a union bound over n bits bounds verification failure by n p_bit(ρ).The r copies of each bit occupy distinct steps under n≥β, making their substitution events and replacement draws independent.Source: §B.3 · p. 17
• The union-bound failure estimate is approximately 0.007, 0.028, and 0.156 at substitution rates ρ=0.1, 0.2, and 0.5, respectively.The bound may be loose because different copyright bits can share step-level substitution events; it does not require cross-bit independence.Source: §B.3 · p. 17