ECDSA Adaptor Signature

Open Table of contents

What it is
How it works
- Setup
- PreSign
- PreVerify
- Adapt
- Extract
Why it works
- PreVerify
- Adapt
- Extract
References

What it is

An adaptor signature scheme is a signing algorithm that’s carried out in two steps while binding itself to a secret value. During signature creation an incomplete, partial signature is generated which can then be turned into a valid, full signature by incorporating a secret value. Once the full signature is published, the secret value can be recovered using the partial- and full signature.

Adaptor signatures are useful primitives for Blockchain applications as they support the implementation of ”Scriptless Scripts”. Scriptless scripts can be implemented as rules that rely only on the existence of digital signatures and their verification algorithm, a requirement all Blockchains support out-of-the-box.

A prominent example for the usage of adaptor signatures is that of an ”Atomic Swap”, a protocol that allows two parties to exchange digital currencies with each other without having to trust one another. At a high level, Party A would leak the secret value that turns a partial signature into a full signature when posting a valid transaction on Blockchain #1 to move funds from Party B to Party A. Party B can then use this leaked secret to adapt a partial into a full signature to move funds from Party A to Party B on Blockchain #2.

How it works

This post describes adaptor signatures based on ECDSA Signatures, so it’s useful to have a solid understanding of both concepts before continuing.

Let’s quickly refresh our memory about adaptor signatures. There are four different operations that characterize an adaptor signature scheme:

PreSign generates a partial signature bound to a secret value
PreVerify verifies a partial signature for correctness
Adapt turns a partial signature into a full signature
Extract recovers the secret value using the partial- and full signature

In addition to the operations outlined above, there’s also a requirement for a statement / witness pair for a hard relation $R$ . In our case such hard relation is that of the discrete logarithm problem on Elliptic Curves (ECDLP). So if one has access to $T = tG$ it’s computationally infeasible to calculate $t$ from $T$ . The statement which can be publicly shared would be $T = tG$ whereas the witness which needs to be kept private is $t$ .

As discussed, we’ll work with an Elliptic Curve $E$ that has a generator $G$ and is of order $q$ . All calculations are done $\bmod\ q$ if not stated otherwise.

Our example scenario we’ll work through to learn about ECDSA-based adaptor signatures is that of Alice who knows the statement $T$ and witness $t$ wanting to get a signature over her message $m$ from Bob. Bob, however doesn’t simply want to sign Alice’s message $m$ with his private key $x$ . In exchange for signing her message $m$ , he wants to be able to learn the witness $t$ which could be useful for him in future interactions (e.g. when Alice and Bob use adaptor signatures in an ”Atomic Swap” protocol as touched upon above).

Setup

At first, Alice generates her statement / witness pair. She does so by randomly sampling a value $t$ from $\mathbb{Z}_q$ which is her witness. She then multiplies the witness by the generator $G$ to derive the statement $T$ .

t \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

T = tG

Bob on the other hand generates his private- and public key pair. He samples a random value $x$ from $\mathbb{Z}_q$ which is his private key. Multiplying this private key by the generator $G$ results in his public key $X$ .

x \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

X = xG

Next up, Alice sends the message $m$ she wants to get a signature for alongside her statement $T$ to Bob.

PreSign

Given that Bob doesn’t want go generate a full signature thats valid according to the ECDSA Signature verification algorithm, he creates a partial signature using Alice’s statement $T$ instead. This partial signature can then be verified for correctness by Alice.

To do so Bob generates a random nonce $k$ which he then multiplies by the generator $G$ to derive a publicly shareable nonce value $R'$ .

k \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R' = kG

Bob also generates a second, publicly shareable nonce value $R$ by multiplying the randomly sampled $k$ with Alice’s statement $T$ .

R = kT

Both values $R'$ and $R$ are points on the Elliptic Curve and therefore have $x$ - and $y$ -coordinates. Because of that Bob can define a value $r$ as the $x$ -coordinate of $R$ .

r = R_x

Next up, Bob needs to turn Alice’s message $m$ into a representation that can be “mapped onto” the Elliptic Curve $E$ . This is done by hashing $m$ with a cryptographic hash function $H$ and interpreting the result as a point on the curve.

z = H(m)

As a last step, he computes the value $s'$ as the inverse of the nonce $k$ multiplied by the hashed message $z$ which is added to the product of the point $r$ and his secret key $x$ .

s' = k^{-1}(z + rx)

Bob has successfully calculated the partial signature which consists of the values $r$ and $s'$ . He sends these values alongside his public key $X$ as well as $R$ and $R'$ to Alice.

PreVerify

Alice can now check if the partial signature was calculated correctly.

At first, she checks if she can recompute the same value for $r$ by comparing it to the $x$ -coordinate of the $R$ value Bob shared.

r \overset{?}{=} R_x

She recomputes $z$ by hashing her message with the same cryptographic hash function $H$ that Bob used.

z = H(m)

Next up, the values $u$ and $v$ are calculated using the inverse of $s'$ and multiplying it by the hashed message $z$ and the value $r$ respectively.

u = s'^{-1}z

v = s'^{-1}r

Alice then checks if the $R'$ value she received from Bob equals $u$ multiplied by the generator $G$ added to the multiplication of $v$ by Bob’s public key $X$ .

R' \overset{?}{=} uG + vX

The partial signature was calculated correctly if the above statement is true.

Adapt

Once the verification of the partial signature succeeds, Alice can turn it into a full signature by multiplying $s'$ with the inverse of her witness $t$ .

s = s't^{-1}

Extract

When Alice shares the full, valid signature publicly Bob can recover Alice’s witness $t$ using both, the partial- and full signature.

t = s^{-1}s'

ECDSA Adaptor Signature

Why it works

The core building block that turns a regular ECDSA Signature into an adaptor signature is the usage of the witness $t$ and its statement $T$ in the calculation of $r$ and $s$ .

PreVerify

First, recall that $z$ is the hash of the message $m$ which is interpreted as a point on the Elliptic Curve $E$ .

Using the equation of $s'$ , we can isolate $k$ .

\begin{aligned} s' &= k^{-1}(z + rx) && \mid \times k \\ s'k &= z + rx && \mid \times s'^{-1} \\ k &= s'^{-1}(z + rx) \end{aligned}

Expanding $R' = uG + vX$ and substituting $k$ for $s'^{-1}(z + rx)$ (which we’ve just calculated), we can see that $R' = kG$ .

\begin{aligned} R' &= uG + vX \\ &= uG + vxG \\ &= G(u + vx) \\ &= G(s'^{-1}z + s'^{-1}rx) \\ &= s'^{-1}G(z + rx) && \mid k = s'^{-1}(z + rx) \\ &= kG \end{aligned}

Taking a look at the partial signature generation above, we can verify that this Elliptic Curve point $R'$ is the same as the one Bob calculated by multiplying $k$ with $G$ .

However, $R'$ is not the same as $R = kT$ which was used by Bob to derive the $r$ value used for a full signature. Alice therefore needs to adapt the partial signature first to turn it into a full, valid signature.

Adapt

A partial signature can be adapted by multiplying $s'$ with the inverse of the witness $t$ .

\begin{aligned} s &= s't^{-1} \\ &= k^{-1}(z + rx)t^{-1} \\ &= k^{-1}t^{-1}(z + rx) \end{aligned}

Deriving $s$ this way turns the partial signature into a full signature that verifies according to the ECDSA Signature verification algorithm.

Again, recall that the value $z$ is the result of hashing the message $m$ with a cryptographic hash function.

Using the $s$ value we just derived, we can isolate $kt$ .

\begin{aligned} s &= s't^{-1} \\ &= k^{-1}(z + rx)t^{-1} \\ &= k^{-1}t^{-1}(z + rx) && \mid \times kt \\ skt &= z + rx && \mid \times s^{-1} \\ kt &= s^{-1}(z + rx) \end{aligned}

We can now use the regular ECDSA Signature verification algorithm to verify the adapted signature.

\begin{aligned} R &= uG + vX \\ &= uG + vxG \\ &= G(u + vx) \\ &= G(s^{-1}z + s^{-1}rx) \\ &= s^{-1}G(z + rx) && \mid kt = s^{-1}(z + rx) \\ &= ktG \\ &= kT \end{aligned}

Checking the partial signature generation, we can see that this Elliptic Curve point $R$ is the same that Bob used to derive the value $r$ . The signature is therefore valid.

Extract

Once Alice shares the full signature publicly, it can be used together with the partial signature to extract the witness $t$ .

\begin{aligned} t &= s^{-1}s' \\ &= (s't^{-1})^{-1}s' \\ &= \frac{1}{s't^{-1}}s' \\ &= \frac{1}{s'\frac{1}{t}}s' \\ &= \frac{1}{\frac{s'}{t}}s' \\ &= \frac{t}{s'}s' \\ &= \frac{ts'}{s'} \\ &= \frac{t\cancel{s'}}{\cancel{s'}} \\ &= t \end{aligned}

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.