F-adsig — Adaptor signature

F-adsig (Adaptor signature) is part of Public-Key Primitives, Key Exchange, Messaging in the UC functionality encyclopedia. Status: a canonical, well-established UC functionality.

An adaptor signature ties a signature to a hard statement. The signer issues a pre-signature \(\tilde{\sigma}\) on a message \(\mathit{msg}\) and a statement \(Y\); anyone holding a witness \(y\) for \(Y\) can adapt it into an ordinary signature \(\sigma\); and anyone holding both \(\tilde{\sigma}\) and \(\sigma\) can extract \(y\) back out. That last direction is the point — it is what makes atomic swaps work, since publishing the signature necessarily discloses the witness.

The functionality below differs in shape from every other signature entry on this site, and the difference is deliberate: it does not take its algorithms from the adversary. \(\mathsf{KeyGen}\), \(\mathsf{Sign}\), \(\mathsf{PreSign}\), \(\mathsf{Verify}\), \(\mathsf{PreVerify}\), \(\mathsf{Adapt}\) and \(\mathsf{Extract}\) are all parameters, fixed when the instance is created (line 1), and the functionality runs them itself. What it adds on top is a set of overrides: each guarded branch in \(\mathsf{Verify}\) and \(\mathsf{PreVerify}\) is one security property, forcing the answer when the scheme’s own algorithm would have been allowed to get it wrong.

Functionality

Reading the box: require refuses the call, and the framework answers \(\textsf{rej}\), so no return is written for it; \(\mathbf{C}\) is the set of corrupted parties; \(\bot\) is a value that is set but empty; \(S\) is the key owner and \(R\) the hard relation, both parameters, and \(\mathsf{DS}\) names the tuple of scheme algorithms the instance is parameterized by; \(\mathcal{M}\) and \(\Sigma\) are the message and signature spaces.

Functionality \(\mathcal{F}_{\mathsf{aSig}}\)

\(\mathit{pid}\),   \(\mathbf{P}\),   \(\mathbf{N}\),   \(\mathbf{U} := \{(\mathcal{A},\mathsf{serves})\}\),   \(\mathit{par} := (S, R, \mathsf{DS})\)

Initialize():

1. \((\mathit{sk}, \mathit{vk}) \gets \mathsf{DS}.\mathsf{KeyGen}()\)
2. \(\mathtt{Sig}, \mathtt{Pre}, \mathtt{PVer} : \mathcal{M} \to 2^{\Sigma}\)
3. \(\mathtt{Sig}[*], \mathtt{Pre}[*], \mathtt{PVer}[*] \gets \varnothing\)
4. \(\mathtt{Adapt} \gets \varnothing\)

id.PubKey()from id′

5. \(\textbf{return}\ \mathit{vk}\)

id.Sign(msg)from id′

6. \(\textbf{require}\ \mathit{id}.P = S\)// one key pair per instance
7. \(\sigma \gets \mathsf{DS}.\mathsf{Sign}(\mathit{sk}, \mathit{msg})\)
8. \(\textbf{if}\ \sigma \neq \bot\ \textbf{then}\)
9. \(\mathtt{Sig}[\mathit{msg}] \gets \mathtt{Sig}[\mathit{msg}] \cup \{\sigma\}\)
10. \(\textbf{return}\ \sigma\)

id.PreSign(msg, Y)from id′

11. \(\textbf{require}\ \mathit{id}.P = S\)
12. \(\tilde{\sigma} \gets \mathsf{DS}.\mathsf{PreSign}(\mathit{sk}, \mathit{msg}, Y)\)
13. \(\textbf{if}\ \tilde{\sigma} \neq \bot\ \textbf{then}\)
14. \(\mathtt{Pre}[\mathit{msg}] \gets \mathtt{Pre}[\mathit{msg}] \cup \{(\tilde{\sigma}, Y)\}\)
15. \(\textbf{return}\ \tilde{\sigma}\)

id.Adapt(vk', tilde{\sigma}, y, Y)from id′

16. \(\sigma \gets \mathsf{DS}.\mathsf{Adapt}(\mathit{vk}', \tilde{\sigma}, y, Y)\)
17. \(\textbf{if}\ \mathit{vk}' = \mathit{vk} \ \wedge\ (Y, y) \in R\ \textbf{then}\)
18. \(\mathtt{Adapt} \gets \mathtt{Adapt} \cup \{(\tilde{\sigma}, Y, y, \sigma)\}\)
19. \(\textbf{return}\ \sigma\)

id.Extract(vk', tilde{\sigma}, σ, Y)from id′

20. \(y \gets \mathsf{DS}.\mathsf{Extract}(\mathit{vk}', \tilde{\sigma}, \sigma, Y)\)
21. \(\textbf{if}\ (Y, y) \notin R \ \wedge\ \exists\, y' : (\tilde{\sigma}, Y, y', \sigma) \in \mathtt{Adapt}\ \textbf{then}\)
22. \(y \gets y'\)// extract correctness
23. \(\textbf{return}\ y\)

id.PreVerify(vk', msg, Y, tilde{\sigma})from id′

24. \(b \gets \mathsf{DS}.\mathsf{PreVerify}(\mathit{vk}', \mathit{msg}, Y, \tilde{\sigma})\)
25. \(c \gets \bigl(\mathit{vk}' = \mathit{vk} \ \wedge\ (\tilde{\sigma}, Y) \in \mathtt{Pre}[\mathit{msg}]\bigr)\)
26. \(\textbf{if}\ c\ \textbf{then}\)
27. \(b \gets 1\)// pre-sign correctness
28. \(\textbf{if}\ \neg c \ \wedge\ \mathit{vk}' = \mathit{vk} \ \wedge\ S \notin \mathbf{C} \ \wedge\ \mathtt{Sig}[\mathit{msg}] = \varnothing\ \textbf{then}\)
29. \(b \gets 0\)// pre-signature unforgeability
30. \(\textbf{if}\ \mathit{vk}' = \mathit{vk} \ \wedge\ b = 1\ \textbf{then}\)
31. \(\mathtt{PVer}[\mathit{msg}] \gets \mathtt{PVer}[\mathit{msg}] \cup \{(\tilde{\sigma}, Y)\}\)
32. \(\textbf{return}\ b\)

id.Verify(vk', msg, σ)from id′

33. \(b \gets \mathsf{DS}.\mathsf{Verify}(\mathit{vk}', \mathit{msg}, \sigma)\)
34. \(e \gets \exists\, (\tilde{\sigma}, Y) \in \mathtt{Pre}[\mathit{msg}] : (Y, \mathsf{DS}.\mathsf{Extract}(\mathit{vk}', \tilde{\sigma}, \sigma, Y)) \in R\)
35. \(c \gets \bigl(\mathit{vk}' = \mathit{vk} \ \wedge\ \sigma \in \mathtt{Sig}[\mathit{msg}]\bigr)\)
36. \(a \gets \bigl(\mathit{vk}' = \mathit{vk} \ \wedge\ \exists\, (\tilde{\sigma},Y) \in \mathtt{PVer}[\mathit{msg}], y : (\tilde{\sigma}, Y, y, \sigma) \in \mathtt{Adapt}\bigr)\)
37. \(\textbf{if}\ c \ \vee\ a\ \textbf{then}\)
38. \(\textbf{return}\ 1\)// correctness; pre-signature adaptability
39. \(\textbf{if}\ \mathit{vk}' = \mathit{vk} \ \wedge\ S \notin \mathbf{C} \ \wedge\ \mathtt{Sig}[\mathit{msg}] = \varnothing \ \wedge\ \neg e\ \textbf{then}\)
40. \(\textbf{return}\ 0\)// unforgeability and extractability
41. \(\textbf{return}\ b\)

id.Leak()from id′

42. \(\textbf{if}\ \mathit{id}.P = S\ \textbf{then}\)
43. \(\textbf{return}\ (\mathit{sk}, \mathit{vk}, \mathtt{Sig}, \mathtt{Pre})\)
44. \(\textbf{return}\ (\mathit{vk}, \mathtt{Sig}, \mathtt{Pre})\)

Source: Figure 3, p. 14 of Gerhart, Rausch and Schröder, “Universally Composable Adaptor Signatures”, ePrint 2025/1363, revision 20260815:213942, the newer of two postings. The PDF’s pages and its printed folios agree.

The printed figure is the endpoint of a construction, not a first statement. This matters for anyone comparing versions. The paper builds the functionality in stages — a baseline in Figure 2, then four modifications in Figures 10 to 14, each adding one property and each paired with a claim that the gap it introduces is negligible — and Figure 3 is the assembled result. So Figures 10–14 are not variants to choose between; they are intermediate stages of the same object, and citing one of them as “the functionality” would be citing a draft. Figure 16 (and Figure 18) give a genuinely extended functionality, for unique extractability, which is a different and stronger object.

• Line 35 is correctness, and it is the reason the box stores \(\mathtt{Sig}\) at all. The predicate \(c\) says the signature is one this instance itself produced under its own key; lines 37–38 then accept it, whatever the scheme’s own \(\mathsf{Verify}\) says about it.
• Lines 39–40 carry two properties at once, and the conjunction is the delicate part. The clause fires only when the key is this instance’s, the owner is honest, nothing was signed for this message, and \(\neg e\) — where \(e\), computed at lines 33–34, says no recorded pre-signature for this message extracts a witness from \(\sigma\). Dropping \(\neg e\) would give plain unforgeability; keeping it is what makes the box state extractability, because it declines to reject exactly those signatures from which a witness can be recovered. The paper’s own account of this is that the verification oracle “is extended to additionally check the extractability property, but only in those cases where the signature is not already guaranteed to verify by correctness or by pre-signature adaptability”.
• Line 36 is pre-signature adaptability, and lines 37–38 must come before line 39 or the box is wrong. The predicate \(a\) holds of a signature obtained by adapting a pre-signature that previously passed \(\mathsf{PreVerify}\); such a signature is forced to verify even though the owner may never have signed that message — precisely the situation lines 39–40 would otherwise reject. The ordering is the content here: accept on \(c \vee a\) first, reject only after. The source writes the same priority as a chain of else if, and the two agree because \(c\) and the rejection condition are mutually exclusive (\(c\) needs a recorded signature, the rejection needs none).
• Lines 28–29 are pre-signature unforgeability, and the guard \(\mathtt{Sig}[\mathit{msg}] = \emptyset\) is doing real work. Once an ordinary signature on \(\mathit{msg}\) exists, a pre-signature is no longer unforgeable in general, so the clause withdraws. This is the property the paper defers to its own Definition 2 and Figure 13.
• Lines 21–22 are extract correctness. If the scheme’s \(\mathsf{Extract}\) returns something that is not a witness, but the pair was in fact produced by adapting with a witness \(y'\), the functionality substitutes \(y'\). So extraction never fails on a signature that honestly came from adaptation.
• Line 6 binds signing and pre-signing to \(S\) and nothing else does. Adapting, extracting and both verifications are open to any caller — correctly, since all four are public operations that take the key as an argument rather than using the stored one.

Mismatch register.

The source	This box	Why
Algorithms as parameters, run by the functionality	Kept as parameters, \(\mathsf{DS}\)	Unusual here — F-Sig, F-CERT and F-acc all take algorithms from the adversary — but it is what the source does, and changing it would change the object.
\(\mathit{corr}\), “true iff the key owner is corrupted”	\(S \in \mathbf{C}\)	The framework’s corruption set says the same thing; the source’s flag is a local abbreviation for exactly this test.
No leakage interface	\(\mathsf{Leak}\) at lines 42–44	Required here. The source’s corruption note says the attacker “also learns \(\mathit{sk}\)” when the owner is corrupt, which is lines 42–43; the rest is public.
Session id \(\mathit{sid} = (\mathit{pid}, \mathit{sid}')\) carrying the owner	\(S\), a parameter	Session identifiers live in the process id here. Clean, since the only use the source makes of \(\mathit{sid}\) is to name the owner.
\(\mathcal{H}_{\mathsf{sign}}\), \(\mathcal{H}_{\mathsf{pSign}}\), \(\mathcal{H}_{\mathsf{adapt}}\), \(\mathcal{H}_{\mathsf{pVerify}}\)	\(\mathtt{Sig}\), \(\mathtt{Pre}\), \(\mathtt{Adapt}\), \(\mathtt{PVer}\)	Renamed to the house convention; same contents.

Known realizations

Any sufficiently strong adaptor signature scheme: Theorem 2, p. 17. For an adaptor signature scheme \(\mathsf{AS}_{\Sigma,R}\) over a correct signature scheme and a hard relation, with \(\mathcal{F}_{\mathsf{aSig}}\) parameterized by the same algorithms: if \(\mathsf{AS}_{\Sigma,R}\) is extractable, pre-signature adaptable, correct, and has strong existentially unforgeable pre-signatures, then \(\mathsf{AS}_{\Sigma,R} \leq \mathcal{F}_{\mathsf{aSig}}\). The proof is a sequence of games following the staged construction of §4, deferred to Appendix C.

Staged, one property at a time: Claims 1 to 4, pp. 12–34. Each claim shows the gap introduced by one modification is negligible given one more property of the scheme — Claim 1 needs message-boundedness and correctness, and Claim 4 closes the sequence with extractability (Definition 10). Reading the claims in order is the cheapest way to see which property each branch in the box is buying.

A concrete scheme: Theorem 3, p. 18. The enhanced Schnorr adaptor signature construction (Construction 1) is correct and achieves extractability, pre-signature adaptability and unforgeable pre-signatures in the random oracle model — hence realizes the functionality by Theorem 2.

The extended object: Theorem 4, p. 38. The same statement for \(\mathcal{F}^{(\mathit{ext})}_{\mathsf{aSig}}\), the unique-extractability functionality of Figure 16. Not the box above.

Properties

• Correctness, with probability exactly \(1\). Lines 35 and 37–38: every signature the functionality issued verifies under the instance’s own key, regardless of the scheme’s algorithm.
• Pre-signature adaptability, with probability exactly \(1\). Lines 36 and 37–38, for any signature obtained by adapting a pre-signature that passed \(\mathsf{PreVerify}\) under this key.
• Unforgeability and extractability, with probability exactly \(0\) of a bad acceptance, while \(S \notin \mathbf{C}\). Lines 39–40. The quantifier is over messages the owner never signed, and the exception carved out by \(\neg e\) is exactly the set of signatures from which a recorded pre-signature extracts a witness — which is what “extractability” means as a property of the box rather than of the scheme.
• Pre-signature unforgeability, with probability exactly \(0\), while \(S \notin \mathbf{C}\) and no signature on the message exists. Lines 28–29.
• Extract correctness, with probability exactly \(1\) on adapted pairs. Lines 21–22.
• No hiding of the statement \(Y\). \(Y\) travels in the clear through \(\mathsf{PreSign}\), \(\mathsf{Adapt}\) and both verifications, and \(\mathtt{Pre}\) retains it. The functionality makes no secrecy claim about which statement a pre-signature is bound to.
• Nothing is promised for a foreign key. Every override is guarded by \(\mathit{vk}' = \mathit{vk}\); for any other key the box returns the scheme’s own answer unmodified.

Formal artifacts

No machine-checked formalization yet.

References:

• Gerhart, Rausch, and Schröder. Universally composable adaptor signatures. Cryptology ePrint Archive, Paper 2025/1363, 2025. The definition transcribed above is Figure 3, p. 14 of revision 20260815:213942, the newer of two postings; the baseline it is built from is Figure 2, p. 12, and the four staged modifications are Figures 10–14 with Claims 1–4 (pp. 12–34); the realization is Theorem 2, p. 17; the concrete Schnorr construction is Theorem 3, p. 18; the extended unique-extractability functionality is Figure 16 with Theorem 4, p. 38. Figure 1 (p. 8) reproduces, in simplified form, the earlier functionality of Tairi, Moreno-Sanchez and Schneidewind that this paper’s own §4 discusses and departs from — it is prior work shown for comparison, not a variant of the box above.