Behavior-Bound Signatures: Semantic Self-Restriction of Signing Authority
Y.Y.N. Li · Zenodo (CERN European Organization for Nuclear Research) · 2026
In the conventional total-domain syntax for digital signatures, correctnessfixes the acceptance language of every honestly generated verification key tothe declared message space. Signature security therefore studies access toaccepting witnesses, while the extent of the language remains outside thedesign space. We expose and remove this hidden totality assumption. For a verification key pk and policy P, define the acceptance and policylanguages by A_pk = { (m, ctx) : exists σ, Verify(pk, m, ctx, σ) = 1 }, L_P = { (m, ctx) : P(Encode(m, ctx)) = 1 }.We call pk behavior-bound to the signer-chosen policy P when A_pk ⊆ L_P.This restriction must reside in the verification relation: constraining thehonest signing algorithm is insufficient once an adversary controls thesigning key and may bypass it. Four experiments separate unforgeability, full-compromise policy soundness,adversarial-key policy binding, and policy privacy. For public policies, adirect construction places P in the public key and makes verificationevaluate it, yielding the exact identity A_pk = L_P under completeness of thebase signature and zero policy-soundness advantage even against unboundedadversaries, independently of base-signature unforgeability. For hiddenpolicies, commitment binding fixes the policy, proof-system soundnessenforces it, and zero knowledge supplies privacy, yielding computationalbehavior-binding under explicit assumptions. Unforgeability and behavior-binding are independent security objectives: theformer restricts access to accepting witnesses, whereas the latter restrictsthe acceptance language itself. Full key disclosure may therefore destroycontrol within the policy boundary without enlarging it. Stateless policiesadmit local verification; history-dependent policies additionally require anagreed state to prevent equivocation. Behavior-bound signatures thusconstrain delegated signing authority without replacing key security, policycorrectness, or consensus.