Skip to content

Adaptor Signature

Table of contents

Open Table of contents

What it is

An adaptor signature scheme is a two-step signing algorithm that’s bound to a secret. During signature creation, a partial signature is generated which can be adapted with the secret to turn it into a valid full signature. The secret can then be extracted using the partial- and full signature.

Adaptor signatures are a useful primitive in the Blockchain space as they tie together the authorization of a transaction with the leakage of a secret. In fact, adaptor signatures are the core building blocks used in Blockchain protocols to implement ”Scriptless Scripts” which are rules that can solely be implemented and enforced with digital signatures.

One such protocol implementation is that of an ”Atomic Swap”, in which two parties who don’t trust each other exchange digital currencies with one another on (potentially different) Blockchains. In this case, the secret that’s leaked by posting a valid transaction to move funds on Blockchain #1 can be used to finalize another, partial signature which moves funds on Blockchain #2.

How it works

An adaptor signature scheme is characterized by four different operations:

  1. PreSign
  2. PreVerify
  3. Adapt
  4. Extract

Furthermore, a statement / witness pair for a hard relation RR needs to be defined such that it’s computationally infeasible to extract the witness tt given the statement TT.

In practice, such a hard relation can be that of a discrete logarithm which is also used in cryptosystems such as Elliptic Curve Cryptography.

Given a generator GG of an Elliptic Curve EE with order qq we can define the statement / witness pair as follows:

t$Zqt \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q T=tGT = tG

Conceptually one can think of the statement / witness pair along the same lines as a public / private key pair, in which the statement TT can be publicly shared, while the witness tt needs to be kept secret.

PreSign

The PreSign operation creates a partial signature σ\sigma' for a message mm. It takes as input a private key xx, the message mm as well as the statement TT.

σPreSign(x,m,T)\sigma' \leftarrow PreSign(x, m, T)

The partial signature σ\sigma' is an incomplete signature according to the signature scheme’s verification method. However it can be checked for correctness with the help of the PreVerify operation.

PreVerify

PreVerify can be used to check if a partial signature σ\sigma' was generated correctly. Its inputs are the public key XX, the message mm, the partial signature σ\sigma' as well as the statement TT.

{0,1}PreVerify(X,m,σ,T)\{0, 1\} \leftarrow PreVerify(X, m, \sigma', T)

Adapt

The Adapt operation turns a partial signature σ\sigma' into a full signature σ\sigma with the help of the witness tt. It takes as input the partial signature σ\sigma' as well as the witness tt.

σAdapt(σ,t)\sigma \leftarrow Adapt(\sigma', t)

Extract

Extract operates on the full signature σ\sigma and its partial signature σ\sigma' to reveal the witness tt.

tExtract(σ,σ)t \leftarrow Extract(\sigma, \sigma')

Example

To illustrate how an adaptor signature scheme can be used in practice, we’ll walk through an example in which Alice, who knows the statement TT and witness tt wants Bob to generate a signature over her message mm with his private key xx of which the public key is XX.

Bob however doesn’t want to create a valid signature which Alice can use right away. He wants to generate a partial signature σ\sigma' that can be turned into a full signature σ\sigma by Alice using her secret witness tt. In doing so, Bob wants to be able to learn the witness tt once Alice shares the full signature σ\sigma publicly.

While this setup might sound fabricated, it’s in fact the foundation to implement an ”Atomic Swap” without the reliance on a Blockchain’s scripting capabilities.

Throughout this example we’ll use an Elliptic Curve EE that is of order qq and has a generator GG. All calculations are done mod q\bmod\ q if not stated otherwise.

As a first step, Alice generates her statement / witness pair by randomly sampling the witness tt from Zq\mathbb{Z}_q to then multiply it by the generator GG to derive the statement TT:

t$Zqt \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q T=tGT = tG

Bob generates his private- and public key pair similarly by randomly sampling a value xx from Zq\mathbb{Z}_q for the private key which is then multiplied by the generator GG to derive the public key XX.

x$Zqx \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q X=xGX = xG

Next up, Alice sends the message mm she wants Bob to sign alongside the statement TT to Bob. Bob in turn uses the PreSign operation to generate an incomplete, partial signature σ\sigma' over the message mm using his private key xx and Alice’s statement TT:

σPreSign(x,m,T)\sigma' \leftarrow PreSign(x, m, T)

Bob then sends this partial signature σ\sigma' to Alice alongside his public key XX.

Given that σ\sigma' is incomplete, it won’t verify using the signature scheme’s verification method. However Alice can check if what Bob sent her is in fact a correct partial signature σ\sigma' over her message mm. She does this by using PreVerify with the inputs of Bob’s public key XX, her message mm, the partial signature σ\sigma' as well as her statement TT.

{0,1}PreVerify(X,m,σ,T)\{0, 1\} \leftarrow PreVerify(X, m, \sigma', T)

Upon successful verification, she uses the Adapt operation which takes as inputs the partial signature σ\sigma' and the witness tt to generate a full signature σ\sigma.

σAdapt(σ,t)\sigma \leftarrow Adapt(\sigma', t)

Once the fill signature σ\sigma is publicly accessible (e.g. by posting it on a public Blockchain) Bob can learn Alice’s witness tt using both, the full signature σ\sigma Alice derived as well as the partial signature σ\sigma' he generated. He does this by using the Extract operation with the two signatures as input.

tExtract(σ,σ)t \leftarrow Extract(\sigma, \sigma')

Adaptor Signature

Why it works

While this is more of a conceptual writeup about adaptor signatures which are implemented differently for individual signature schemes, they all have the same high-level idea in common.

The intuition behind the inner-workings of adaptor signature is that of hiding the witness tt, which is necessary to turn a partial signature into a full signature, into the randomness that’s used for signing.

If you’re curious how an adaptor signature scheme can be implemented for signature schemes that are used in the real world, you can check out the writeups on Schnorr Adaptor Signatures as well as ECDSA Adaptor Signatures.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.