Two-Party Adaptor Signatures from Identification Schemes

Abstract

Adaptor signatures are a novel cryptographic primitive with important applications for cryptocurrencies. They have been used to construct second layer solutions such as payment channels or cross-currency swaps. The basic idea of an adaptor signature scheme is to tie the signing process to the revelation of a secret value in the sense that, much like a regular signature scheme, an adaptor signature scheme can authenticate messages, but simultaneously leaks a secret to certain parties. Recently, Aumayr et al. provide the first formalization of adaptor signature schemes, and present provably secure constructions from ECDSA and Schnorr signatures. Unfortunately, the formalization and constructions given in this work have two limitations: (1) current schemes are limited to ECDSA and Schnorr signatures, and no generic transformation for constructing adaptor signatures is known; (2) they do not offer support for aggregated two-party signing, which can significantly reduce the blockchain footprint in applications of adaptor signatures.

In this work, we address these two shortcomings. First, we show that signature schemes that are constructed from identification (ID) schemes, which additionally satisfy certain homomorphic properties, can generically be transformed into adaptor signature schemes. We further provide an impossibility result which proves that unique signature schemes (e.g., the BLS scheme) cannot be transformed into an adaptor signature scheme. In addition, we define two-party adaptor signature schemes with aggregatable public keys and show how to instantiate them via a generic transformation from ID-based signature schemes. Finally, we give instantiations of our generic transformations for the Schnorr, Katz-Wang and Guillou-Quisquater signature schemes.

K. Hostáková—Research partially conducted at Technische Universität Darmstadt, Germany.

M. Maitra—Research partially conducted at Indian Institute of Technology Madras, India.

1 Introduction

Blockchain technologies, envisioned first in 2009 [34], have spurred enormous interest by academia and industry. This technology puts forth a decentralized payment paradigm, where financial transactions are stored in a decentralized data structure – often referred to as the blockchain. The main cryptographic primitive used by blockchain systems is the one of digital signature schemes, which allow users to authenticate payment transactions. Various different flavors of digital signature schemes are used by blockchain systems, e.g., ring signatures [39] add privacy-preserving features to cryptocurrencies [40], while threshold signatures and multi-signatures are used for multi-factor authorization of transactions [18].

Adaptor signatures (sometimes also referred to as scriptless scripts) are another important type of digital signature scheme introduced by the cryptocurrency community [37] and recently formalized by Aumayr et al. [2]. In a nutshell, adaptor signatures tie together authorization of a message and the leakage of a secret value. Namely, they allow a signer to produce a pre-signature under her secret key such that this pre-signature can be adapted into a valid signature by a publisher knowing a certain secret value. If the completed signature gets published, the signer is able to extract the embedded secret used by the publisher.

To demonstrate the concept of adaptor signatures, let us discuss the simple example of a preimage sale which serves as an important building block in many blockchain applications such as payment channels [2, 6, 10, 38], payment routing in payment channel networks (PCNs) [13, 30, 33] or atomic swaps [11, 21]. Assume that a seller offers to reveal a preimage of a hash value h in exchange for c coins from a concrete buyer. This is a classical instance of a fair exchange problem, which can be solved using the blockchain as follows. The buyer locks c coins in a transaction which can be spent by another transaction if it is authorized by the seller and contains a preimage of the hash value h.

While this solution implements the preimage sale, it has various drawbacks: (i) The only hash functions that can be used are the ones supported by the underlying blockchain. For example, the most popular blockchain-based cryptocurrency, Bitcoin, supports only SHA-1, SHA-256 and RIPEMD-160 [5]. This makes the above solution unsuitable for applications like privacy-preserving payment routing in PCNs [13, 30] that crucially rely on the preimage sale instantiated with a homomorphic hash function. (ii) The hash value has to be fixed at the beginning of the sale and cannot be changed later without a new transaction being posted on the blockchain. This is problematic in, e.g., generalized payment channels [2], where users utilize the ideas from the preimage sale to repeatedly update channel balances without any blockchain interaction. (iii) Finally, the blockchain script is non-standard as, in addition to a signature verification, it contains a hash preimage verification. This does not only make the transaction more expensive but also allows parties who are maintaining the blockchain (also known as miners) to censor transactions belonging to a preimage sale.

The concept of adaptor signatures allows us to implement a preimage sale in a way that overcomes most of the aforementioned drawbacks. The protocol works at a high level as follows. The buyer locks c coins in a transaction which can be spent by a transaction authorized by both the seller and the buyer. Thereafter, the buyer pre-signs a transaction spending the c coins with respect to the hash value h. If the seller knows a preimage of h, she can adapt the pre-signature of the buyer, attach her own signature and claim the c coins. The buyer can then extract a preimage from the adapted signature. Hence, parties are not restricted to the hash functions supported by the blockchain, i.e., drawback (i) is addressed. Moreover, the buyer can pre-sign the spending transaction with respect to multiple hash values which overcomes drawback (ii). However, the third drawback remains. While the usage of adaptor signatures avoids the hash preimage verification in the script, it adds a signature verification (i.e., there are now 2 signature verifications in total) which makes this type of exchange easily distinguishable from a normal payment transaction. Hence, the sale remains rather expensive and censorship is not prevented.

The idea of two-party adaptor signatures is to replace the two signature verifications by one. The transaction implementing a preimage sale then has exactly the same format as a transaction simply transferring coins. As a result the price (in terms of fees paid to the miners) of the preimage sale transaction is the same as the price for a normal payment. Moreover, censorship is prevented as miners cannot distinguish the transactions belonging to the preimage sale from a standard payment transaction. Hence, point (iii) is fully addressed.

The idea of replacing two signatures by one has already appeared in the literature in the context of payment channels. Namely, Malavolta et al. [30] presented protocols for two-party threshold adaptor signatures based on Schnorr and ECDSA digital signatures. However, they did not present a standalone definition for the threshold primitive and hence security for these schemes has not been analyzed. Furthermore, the key generation of the existing threshold adaptor signature schemes is interactive which is undesirable. Last but not least, their constructions are tailored to Schnorr and ECDSA signature schemes and hence is not generic. From the above points, the following natural question arises:

Is it possible to define and instantiate two-party adaptor signature schemes with non-interactive key generation in a generic way?

1.1 Our Contribution

Our main goal is to define two-party adaptor signatures and explore from which digital signature we can instantiate this new primitive. We proceed in three steps which we summarize below and depict in Fig. 1.

Step 1: From ID Schemes to Adaptor Signatures. Our first goal is to determine if there exists a specific class of signature schemes which can be generically transformed into adaptor signatures. Given the existing Schnorr-based construction [2, 37], a natural choice is to explore signature schemes constructed in a similar fashion. To this end, we focus on signature schemes built from identification (ID) schemes using the Fiat-Shamir transform [25]. We show that ID-based signature schemes satisfying certain additional properties can be transformed to adaptor signature schemes generically. In addition to Schnorr signatures [41], this class includes Katz-Wang and Guillou-Quisquater signatures [22, 24]. As an additional result, we show that adaptor signatures cannot be built from unique signatures, ruling out constructions from, e.g., BLS signatures [9].

Our generic transformation of adaptor signatures from ID schemes has multiple benefits. Firstly, by instantiating it with the Guillou-Quisquater signature scheme, we obtain the first RSA-based adaptor signature scheme. Secondly, since Katz-Wang signatures offers tight security (under the decisional Diffie-Hellman (DDH) assumption), and our generic transformation also achieves tight security, our result shows how to construct adaptor signatures with a tight reduction to the underlying DDH assumption.

Step 2: From ID Schemes to Two-Party Signatures. Our second goal is to generically transform signature schemes built from ID schemes into two-party signature schemes with aggregatable public keys. Unlike threshold signatures, these signatures have non-interactive key generation. This means that parties can independently generate their key pairs and later collaboratively generate signatures that are valid under their combined public key. For our transformation, we require the signature scheme to satisfy certain aggregation properties which, as we show, are present in the three aforementioned signature schemes. While this transformation serves as a middle step towards our main goal of constructing two-party adaptor signatures, we believe it is of independent interest.

Step 3: From ID Schemes to Two-Party Adaptor Signatures. Finally, we define two-party adaptor signature schemes with aggregatable public keys. In order to instantiate this novel cryptographic primitive, we use similar techniques as in step 1 where we “lifted” standard signature schemes to adaptor signature schemes. More precisely, we present a transformation turning a two-party signature scheme based on an ID scheme into a two-party adaptor signature scheme.

Fig. 1.

Overview of our results. Full arrow represents a generic transformation, dotted and dashed arrows represent a generic transformation which requires additional homomorphic or aggregation properties respectively.

Remark 1

Let us point out that Fig. 1 presents our transformation steps from signature schemes based on ID schemes to two-party adaptor signatures. Despite the fact that we generically construct our two-party adaptor signature scheme from two-party signature schemes based on ID schemes, we reduce its security to the strong unforgeability of the underlying single party signature scheme. Therefore, we do not need the two-party signature scheme from ID schemes to be strongly unforgeable. This gives us a more general result than proving security based on strong unforgeability of the two-party signature scheme from ID schemes. We note that any ID scheme can be transformed to a signature scheme with strong unforgeability by Bellare and Shoup [4].

Let us further mention that our security proofs are in the random oracle model. Proving the security of our constructions and the original constructions from [2] in the standard model remains an interesting open problem.

1.2 Related Work

Adaptor Signatures. The notion of adaptor signatures was first introduced by Poelstra [37] and has since been used in many blockchain related applications, such as PCNs [30], payment channel hubs [43] or atomic swaps [11]. However, the adaptor signatures as a standalone primitive were only formalized later by Aumayr et al. [2], where they were used to generalize the concept of payment channels. Concurrently, Fournier [17] attempted to formalize adaptor signatures, however, as pointed out in [2], his definition is weaker than the one given in [2] and not sufficient for certain applications. All the previously mentioned works constructed adaptor signatures only from Schnorr and ECDSA signatures, i.e., they did not show generic transformations for building adaptor signature schemes. As previously mentioned, a two-party threshold variant of adaptor signatures was presented by Malavolta et al. [30]. Their construction requires interactive key generation, thereby differing from our two-party adaptor signature notion. Moreover, no standalone definition of the threshold primitive was provided.

Two works [15, 44] have recently introduced post-quantum secure adaptor signature schemes, i.e., schemes that remain secure even in presence of an adversary having access to a quantum computer. In order to achieve post-quantum security, [15] based its scheme on standard and well-studied lattice assumptions, namely Module-SIS and Module-LWE, while the scheme in [44] is based on lesser known assumptions for isogenies. Both works additionally show how to construct post-quantum secure PCNs from their respective adaptor signature schemes.

Multi-Signatures and ID Schemes. Multi-Signatures have been subject to extensive research in the past (e.g., [23, 35, 36]). In a nutshell, multi-signatures allow a set of signers to collaboratively generate a signature for a common message such that the signature can be verified given the public key of each signer. More recently, the notion of multi-signatures with aggregatable public keys has been introduced [31] and worked on [8, 26], which allows to aggregate the public keys of all signers into one single public key. We use some results from the work of Kiltz et al. [25], which provides a concrete and modular security analysis of signatures schemes from ID schemes obtained via the Fiat-Shamir transformation. Our paper builds up on their work and uses some of their notation.

2 Preliminaries

In this section, we introduce notation that we use throughout this work and preliminaries on adaptor signatures and identification schemes. Due to space limitations, we provide formal definitions of digital signature schemes, non-interactive zero-knowledge proofs and extractable commitments in the full version of this paper [14].

Notation. We denote by $x \leftarrow _\$\mathcal {X}$ the uniform sampling of x from the set $\mathcal {X}$. Throughout this paper, $n$ denotes the security parameter. By $x \leftarrow \mathsf {A}(y)$ we denote a probabilistic polynomial time (PPT) algorithm $\mathsf {A}$ that on input y, outputs x. When $\mathsf {A}$ is a deterministic polynomial time (DPT) algorithm, we use the notation $x :=\mathsf {A}(y)$. A function $\nu :\mathbb {N}\rightarrow \mathbb {R}$ is negligible in $n$ if for every $k \in \mathbb {N}$, there exists $n_0 \in \mathbb {N}$ s.t. for every $n\ge n_0$ it holds that $\vert \nu (n)\vert \le 1/ n^k$.

Hard Relation. Let $\mathsf {R}\subseteq \mathcal {D}_S\times \mathcal {D}_{\mathsf {w}}$ be a relation with statement/witness pairs $(Y,y)\in \mathcal {D}_S\times \mathcal {D}_{\mathsf {w}}$ and let the language $L_\mathsf {R}\subseteq \mathcal {D}_S$ associated to $\mathsf {R}$ be defined as $L_\mathsf {R}:= \{Y\in \mathcal {D}_S\mid \exists y\in \mathcal {D}_{\mathsf {w}}\text { s.t. } (Y,y) \in \mathsf {R}\}$. We say that $\mathsf {R}$ is a hard relation if: (i) There exists a PPT  sampling algorithm $\mathsf {GenR}(1^n)$ that on input the security parameter outputs a pair $(Y,y) \in \mathsf {R}$; (ii) The relation $\mathsf {R}$ is poly-time decidable; (iii) For all PPT  adversaries $\mathcal {A}$, the probability that $\mathcal {A}$ outputs a valid witness $y\in \mathcal {D}_{\mathsf {w}}$ for $Y\in L_\mathsf {R}$ is negligible.

2.1 Adaptor Signatures

We now recall the definition of adaptor signatures, recently put forward in [2].

Definition 1

(Adaptor Signature). An adaptor signature scheme w.r.t. a hard relation $\mathsf {R}$ and a signature scheme $\mathsf {SIG}= (\mathsf {Gen},\mathsf {Sign}, \mathsf {Vrfy})$ consists of a tuple of four algorithms $\mathsf {aSIG}_{\mathsf {R}, \mathsf {SIG}} = (\mathsf {pSign}, \mathsf {Adapt}, \mathsf {pVrfy}, \mathsf {Ext})$ defined as:

• $\mathsf {pSign}_{ sk }(m, Y)$: is a PPT  algorithm that on input a secret key $sk$, message $m \in \{0,1\}^*$ and statement $Y\in L_\mathsf {R}$, outputs a pre-signature $\widetilde{\sigma }$.

• $\mathsf {pVrfy}_{ pk }(m, Y; \widetilde{\sigma })$: is a DPT  algorithm that on input a public key $pk$, message $m \in \{0,1\}^*$, statement $Y\in L_\mathsf {R}$ and pre-signature $\widetilde{\sigma }$, outputs a bit b.

• $\mathsf {Adapt}_ pk (\widetilde{\sigma },y)$: is a DPT  algorithm that on input a pre-signature $\widetilde{\sigma }$ and witness $y$, outputs a signature $\sigma$.

• $\mathsf {Ext}_ pk (\sigma ,\widetilde{\sigma },Y)$: is a DPT  algorithm that on input a signature $\sigma$, pre-signature $\widetilde{\sigma }$ and statement $Y\in L_\mathsf {R}$, outputs a witness $y$ such that $(Y,y) \in \mathsf {R}$, or $\bot$.

An adaptor signature scheme, besides satisfying plain digital signature correctness, should also satisfy pre-signature correctness that we formalize next.

Definition 2

(Pre-Signature Correctness). An adaptor signature $\mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}$ satisfies pre-signature correctness, if for all $n\in \! \mathbb {N}$ and $m \in \{0,1\}^*$:

An adaptor signature scheme $\mathsf {aSIG}_{\mathsf {R}, \mathsf {SIG}}$ is called secure if it satisfies three security properties: existential unforgeablity under chosen message attack for adaptor signatures, pre-signature adaptability and witness extractability. Let us recall the formal definition of these properties next.

The notion of unforgeability for adaptor signatures is similar to existential unforgeability under chosen message attacks for standard digital signatures but additionally requires that producing a forgery $\sigma$ for some message $m^*$ is hard even given a pre-signature on $m^*$ w.r.t. a random statement $Y\in L_\mathsf {R}$.

Definition 3

(${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ Security). An adaptor signature scheme $\mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}$ is unforgeable if for every PPT  adversary $\mathcal {A}$ there exists a negligible function $\nu$ such that: $\Pr [\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}}(n) = 1] \le \nu (n),$ where the definition of the experiment $\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}}$ is as follows:

A natural requirement for an adaptor signature scheme is that any valid pre-signature w.r.t. $Y$ (possibly produced by a malicious signer) can be completed into a valid signature using a witness $y$ with $(Y, y) \in \mathsf {R}$.

Definition 4

(Pre-Signature Adaptability). An adaptor signature scheme $\mathsf {aSIG}_{\mathsf {SIG}, \mathsf {R}}$ satisfies pre-signature adaptability, if for all $n\in \mathbb {N}$, messages $m \in \{0,1\}^*$, statement/witness pairs $(Y, y)\in \mathsf {R}$, public keys $pk$ and pre-signatures $\widetilde{\sigma }\leftarrow \{0,1\}^*$ we have $\mathsf {pVrfy}_{ pk }(m,Y; \widetilde{\sigma }) =1$, then $\mathsf {Vrfy}_{ pk }(m;\mathsf {Adapt}_ pk (\widetilde{\sigma },y))=1$.

The last property that we are interested in is witness extractability. Informally, it guarantees that a valid signature/pre-signatue pair $(\sigma ,\widetilde{\sigma })$ for message/statement $(m,Y)$ can be used to extract a corresponding witness $y$.

Definition 5

(Witness Extractability). An adaptor signature scheme $\mathsf {aSIG}_\mathsf {R}$ is witness extractable if for every PPT  adversary $\mathcal {A}$, there exists a negligible function $\nu$ such that the following holds: $\Pr [\mathsf {aWitExt}_{\mathcal {A}, \mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}}(n) = 1] \le \nu (n),$ where the experiment $\mathsf {aWitExt}_{\mathcal {A}, \mathsf {aSIG}_{\mathsf {R},\mathsf {SIG}}}$ is defined as follows:

Let us stress that while the witness extractability experiment $\mathsf {aWitExt}$ looks fairly similar to the experiment $\mathsf {aSigForge}$, there is one crucial difference; namely, the adversary is allowed to choose the forgery statement $Y^*$. Hence, we can assume that it knows a witness for $Y^*$ and can thus generate a valid signature on the forgery message $m^*$. However, this is not sufficient to win the experiment. The adversary wins only if the valid signature does not reveal a witness for $Y^*$.

2.2 Identification and Signature Schemes

In this section we recall the definition of identification schemes and how they are transformed to signature schemes as described in [25].

Definition 6

(Canonical Identification Scheme [25]). A canonical identification scheme $\mathsf {ID}$ is defined as a tuple of four algorithms $\mathsf {ID}:= (\mathsf {IGen}, \mathsf {P}, \mathsf {ChSet},\mathsf {V})$.

• The key generation algorithm $\mathsf {IGen}$ takes the system parameters $\mathsf {par}$ as input and returns secret and public key $( sk , pk )$. We assume that $pk$ defines the set of challenges, namely $\mathsf {ChSet}$.

• The prover algorithm $\mathsf {P}$ consists of two algorithms namely $\mathsf {P}_1$ and $\mathsf {P}_2$:

  • $\mathsf {P}_1$ takes as input the secret key $sk$ and returns a commitment $R \in \mathcal {D}_\mathsf {rand}$ and a state St.

  • $\mathsf {P}_2$ takes as input the secret key $sk$, a commitment $R \in \mathcal {D}_\mathsf {rand}$, a challenge $h \in \mathsf {ChSet}$, and a state $St$ and returns a response $s\in \mathcal {D}_\mathsf {resp}$.

• The verifier algorithm $\mathsf {V}$ is a deterministic algorithm that takes the public key $pk$ and the conversation transcript as input and outputs 1 (acceptance) or 0 (rejection).

We require that for all $( sk , pk )\in \mathsf {IGen}(\mathsf {par})$, all $(R, St) \in \mathsf {P}_1( sk )$, all $h \in \mathsf {ChSet}$ and all $s\in \mathsf {P}_2( sk ,R, h, St)$, we have $\mathsf {V}( pk ,R, h, s) = 1$.

We recall that an identification scheme $\mathsf {ID}$ is called commitment-recoverable, if $\mathsf {V}$ first internally calls a function $\mathsf {V}_0$ which recomputes $R_0 = \mathsf {V}_0(pk, h, s)$ and then outputs 1, iff $R_0 = R$. Using Fiat-Shamir heuristic one can transform any identification scheme $\mathsf {ID}$ of the above form into a digital signature scheme $\mathsf {SIG}^{\mathsf {ID}}$. We recall this transformation in Fig. 2 when $\mathsf {ID}$ is commitment-recoverable.

Fig. 2.

$\mathsf {SIG}^{\mathsf {ID}}$: Digital signature schemes from identification schemes [25]

3 Adaptor Signatures from $\mathsf {SIG}^{\mathsf {ID}}$

Our first goal is to explore and find digital signature schemes which can generically be transformed to adaptor signatures. Interestingly, we observe that both existing adaptor signature schemes, namely the Schnorr-based and the ECDSA-based schemes, utilize the randomness used during signature generation to transform digital signatures to adaptor signatures [2]. We first prove a negative result, namely that it is impossible to construct an adaptor signature scheme from a unique signature scheme [19, 29, 42]. Thereafter, we focus on signature schemes constructed from identification schemes (cf. Fig. 2) and show that if the underlying ID-based signature scheme $\mathsf {SIG}^{\mathsf {ID}}$ satisfies certain additional properties, then we can generically transform it into an adaptor signature scheme. To demonstrate the applicability of our generic transformation, we show in the full version of this paper [14] that many existing $\mathsf {SIG}^{\mathsf {ID}}$ instantiations satisfy the required properties.

3.1 Impossibility Result for Unique Signatures

An important class of digital signatures are those where the signing algorithm is deterministic and the generated signatures are unique. Given the efficiency of deterministic signature schemes along with numerous other advantages that come from signatures being unique [19, 29, 42], it would be tempting to design adaptor signatures based on unique signatures. However, we show in Theorem 1 that if the signature scheme has unique signatures, then it is impossible to construct a secure adaptor signature scheme from it.

Theorem 1

Let $\mathsf {R}$ be a hard relation and $\mathsf {SIG}= (\mathsf {Gen},\mathsf {Sign}, \mathsf {Vrfy})$ be a signature scheme with unique signatures. Then there does not exist an adaptor signature scheme $\mathsf {aSIG}_{\mathsf {R}, \mathsf {SIG}}$.

Proof

We prove this theorem by contradiction. Assume there exists an adaptor signature scheme where the underlying signature scheme, $\mathsf {SIG}$, has unique signatures. We construct a $\text {{PPT}}$ algorithm $\mathcal {A}$ which internally uses the adaptor signature and breaks the hardness of $\mathsf {R}$. In other words, $\mathcal {A}$ receives $(1^n, Y)$ as input and outputs $y$, such that $(Y,y) \in \mathsf {R}$. Below, we describe $\mathcal {A}$ formally.

We now show that $y$ returned by $\mathcal {A}$ is indeed a witness of $Y$, i.e., $(Y,y)\in \mathsf {R}$. From the correctness of the adaptor signature scheme, we know that for any $y'$ s.t. $(Y,y')\in \mathsf {R}$ the signature $\sigma ' :=\mathsf {Adapt}(\widetilde{\sigma },y')$ is a valid signature, i.e., $\mathsf {Vrfy}_{pk}(m,\sigma ') = 1$. Moreover, we know that $y'' :=\mathsf {Ext}_ pk (\sigma ',\widetilde{\sigma },Y)$ is such that $(Y, y'') \in \mathsf {R}$. As $\mathsf {SIG}$ is a unique signature scheme, this implies that $\sigma ' = \sigma$ which in turn implies that the witness $y$ returned by $\mathcal {A}$ is $y''$. Hence, $\mathcal {A}$ breaks the hardness of $\mathsf {R}$ with probability 1.

Let us briefly discuss which signature schemes are affected by our impossibility result. Unique signature schemes (also known as verifiable unpredictable functions (VUF)) have been first introduced in [19]. Furthermore, many follow-up works such as [29, 32] and most recently [42], have shown how to instantiate this primitive in the standard model. Another famous example of a unique signature scheme is BLS [9]. Naturally, due to our impossibility result, an adaptor signature scheme cannot be instantiated from these signature schemes.

3.2 Generic Transformation to Adaptor Signatures

We now describe how to generically transform a randomized digital signature scheme $\mathsf {SIG}^{\mathsf {ID}}$ from Fig. 2 into an adaptor signature scheme w.r.t. a hard relation $\mathsf {R}$. For brevity, we denote the resulting adaptor signature scheme as $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ instead of $\mathsf {aSIG}_{\mathsf {R}, \mathsf {SIG}^{\mathsf {ID}}}$. The main idea behind our transformation is to shift the public randomness of the $\mathsf {Sign}$ procedure by a statement $Y$ for the relation $\mathsf {R}$ in order to generate a modified signature called a pre-signature. Using a corresponding witness $y$ (i.e., $(Y, y)\in \mathsf {R}$), the shift of the public randomness in the pre-signature can be reversed (or adapted), in order to obtain a regular (or full) signature. Moreover, it should be possible to extract a witness given both the pre-signature and the full-signature. To this end, let us formalize three new deterministic functions which we will use later in our transformation.

• 1. For the randomness shift, we define a function $f_\mathsf {shift}:\mathcal {D}_\mathsf {rand}\times L_\mathsf {R}\rightarrow \mathcal {D}_\mathsf {rand}$ that takes as input a commitment value $R \in \mathcal {D}_\mathsf {rand}$ of the identification scheme and a statement $Y\in L_\mathsf {R}$ of the hard relation, and outputs a new commitment value $R' \in \mathcal {D}_\mathsf {rand}$.

• 2. For the adapt operation, we define $f_\mathsf {adapt}:\mathcal {D}_\mathsf {resp}\times \mathcal {D}_{\mathsf {w}}\rightarrow \mathcal {D}_\mathsf {resp}$ that takes as input a response value $\tilde{s}\in \mathcal {D}_\mathsf {resp}$ of the identification scheme and a witness $y\in \mathcal {D}_{\mathsf {w}}$ of the hard relation, and outputs a new response value $s\in \mathcal {D}_\mathsf {resp}$.

• 3. Finally, for witness extraction, we define $f_\mathsf {ext}:\mathcal {D}_\mathsf {resp}\times \mathcal {D}_\mathsf {resp}\rightarrow \mathcal {D}_{\mathsf {w}}$ that takes as input two response values $\tilde{s}, s\in \mathcal {D}_\mathsf {resp}$ and outputs a witness $y\in \mathcal {D}_{\mathsf {w}}$.

Our transformation from $\mathsf {SIG}^{\mathsf {ID}}$ to $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ is shown in Fig. 3.

Fig. 3.

Generic transformation from $\mathsf {SIG}^{\mathsf {ID}}$ to a $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ scheme

Fig. 4.

Schnorr signature scheme

In order for $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ to be an adaptor signature scheme, we need the functions $f_\mathsf {shift}$, $f_\mathsf {adapt}$ and $f_\mathsf {ext}$ to satisfy two properties. The first property is a homomorphic one and relates the functions $f_\mathsf {shift}$ and $f_\mathsf {adapt}$ to the commitment-recoverable component $\mathsf {V}_0$ and the hard relation $\mathsf {R}$. Informally, for all $(Y,y)\in \mathsf {R}$, we need the following to be equivalent: (i) Extract the public randomness from a response $\tilde{s}$ using $\mathsf {V}_0$ and then apply $f_\mathsf {shift}$ to shift the public randomness by $Y$, and (ii) apply $f_\mathsf {adapt}$ to shift the secret randomness in $\tilde{s}$ by $y$ and then extract the public randomness using $\mathsf {V}_0$. Formally, for any public key $pk$, any challenge $h \in \mathsf {ChSet}$, any response value $\tilde{s}\in \mathcal {D}_\mathsf {resp}$ and any statement/witness pair $(Y, y) \in \mathsf {R}$, it must hold that:

(1)

The second property requires that the function $f_\mathsf {ext}(\tilde{s}, \cdot )$ is the inverse function of $f_\mathsf {adapt}(\tilde{s},\cdot )$ for any $\tilde{s}\in \mathcal {D}_\mathsf {resp}$. Formally, for any $y\in \mathcal {D}_{\mathsf {w}}$ and $\tilde{s}\in \mathcal {D}_\mathsf {resp}$, we have

$$\begin{aligned} y=f_\mathsf {ext}(f_\mathsf {adapt}(\tilde{s},y), \tilde{s}). \end{aligned}$$

(2)

To give an intuition about the functions $f_\mathsf {shift}$, $f_\mathsf {adapt}$ and $f_\mathsf {ext}$ and their purpose, let us discuss their concrete instantiations for Schnorr signatures and show that they satisfy Equations (1) and (2). The instantiations for Katz-Wang signatures and Guillou-Quisquater signatures can be found in the full version of this paper [14].

Example 1

(Schnorr signatures). Let be a cyclic group of prime order p where the discrete logarithm problem in $\mathbb {G}$ is hard. The functions $\mathsf {IGen}$, $\mathsf {P}_1$, $\mathsf {P}_2$ and $\mathsf {V}_0$ for Schnorr’s signature scheme are defined in Fig. 4.

Let us consider the hard relation $\mathsf {R}= \{(Y, y) \mid Y= g^y\}$, i.e., group elements and their discrete logarithms, and let us define the functions $f_\mathsf {shift}$, $f_\mathsf {adapt}$, $f_\mathsf {ext}$ as:

$$\begin{aligned} f_\mathsf {shift}(Y,R) :=Y\cdot R, \quad f_\mathsf {adapt}(\tilde{s},y) :=\tilde{s}+y, \quad f_\mathsf {ext}(s, \tilde{s}) :=s- \tilde{s}. \end{aligned}$$

Intuitively, the function $f_\mathsf {shift}$ is shifting randomness in the group while the function $f_\mathsf {adapt}$ shifts randomness in the exponent. To prove that Eq. (1) holds, let us fix an arbitrary public key $pk \in \mathbb {G}$, a challenge $h \in \mathbb {Z}_q$, a response value $s\in \mathbb {Z}_q$ and a statement witness pair $(Y,y) \in \mathsf {R}$, i.e., $Y= g^y$. We have

$$\begin{aligned} f_\mathsf {shift}(\mathsf {V}_0( pk , h, s),Y)&= f_\mathsf {shift}(g^{s}\cdot pk ^{-h},Y) = g^{s}\cdot pk ^{-h} \cdot Y\\&= g^{s+y} \cdot pk ^{-h} = \mathsf {V}_0( pk , h, s+y) =\mathsf {V}_0( pk , h, f_\mathsf {adapt}(s,y)) \end{aligned}$$

which is what we wanted to prove. In order to show that Eq. (2) holds, let us fix an arbitrary witness $y\in \mathbb {Z}_q$ and a response value $s\in \mathbb {Z}_q$. Then we have

$$\begin{aligned} f_\mathsf {ext}(f_\mathsf {adapt}(s,y), s) = f_\mathsf {ext}(s+y, s) = s+y- s= y\end{aligned}$$

and hence Eq. (2) is satisfied as well.

We now show that the transformation from Fig. 3 is a secure adaptor signature scheme if functions $f_\mathsf {shift},f_\mathsf {adapt}, f_\mathsf {ext}$ satisfying Equations (1) and (2) exist.

Theorem 2

Assume that $\mathsf {SIG}^{\mathsf {ID}}$ is a ${\mathsf {SUF\mathrm{{-}}CMA}}$-secure signature scheme transformed using Fig. 2, let $f_\mathsf {shift}, f_\mathsf {adapt}$ and $f_\mathsf {ext}$ be functions satisfying the relations from Equations (1) and (2), and $\mathsf {R}$ be a hard relation. Then the resulting $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ scheme from the transformation in Fig. 3 is a secure adaptor signature scheme in the random oracle model.

In order to prove Theorem 2, we must show that $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ satisfies pre-signature correctness, ${\mathsf {{aEUF\mathrm{{-}}CMA}}}$security, pre-signature adaptability and witness extractability properties described in Definitions 2 to 5 respectively.

Lemma 1

(Pre-Signature Correctness). Under the assumptions of Theorem 2, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ satisfies pre-signature correctness as for Definition 2.

Proof

Let us fix an arbitrary message m and a statement witness pair $(Y, y) \in \mathsf {R}$. Let , $\widetilde{\sigma }\leftarrow \mathsf {pSign}_ sk (m, Y)$, $\sigma :=\mathsf {Adapt}_ pk (\widetilde{\sigma },y)$ and $y' :=\mathsf {Ext}_ pk (\sigma , \widetilde{\sigma }, Y)$. From Fig. 3 we know that $\widetilde{\sigma }= (h,\tilde{s}), \quad \sigma = (h,s) \quad \text {and } \quad y' = f_\mathsf {ext}(s, \tilde{s}),$ where we have $s:=f_\mathsf {adapt}(\tilde{s}, y)$, $\tilde{s}\leftarrow \mathsf {P}_2( sk , R_\mathsf {pre}, h, St)$, $h :=\mathcal {H}(R_\mathsf {sign}, m)$, $R_\mathsf {sign}:=f_\mathsf {shift}(R_\mathsf {pre}, Y)$ and $(R_\mathsf {pre}, St) \leftarrow \mathsf {P}_1( sk )$. We first show $\mathsf {pVrfy}_{ pk }(m, Y;\widetilde{\sigma })=1$. From completeness of the $\mathsf {ID}$ scheme, we know that $\mathsf {V}_0( pk , h, \tilde{s}) = R_\mathsf {pre}$. Hence:

$$\begin{aligned} \mathcal {H}(f_\mathsf {shift}(\mathsf {V}_0( pk , h, \tilde{s}),Y),m) = \mathcal {H}(f_\mathsf {shift}(R_\mathsf {pre},Y),m) = \mathcal {H}(R_\mathsf {sign},m)= h \end{aligned}$$

(3)

which is what we needed to prove. We now show that $\mathsf {Vrfy}_{ pk }(m;\sigma )=1$. By Fig. 2, we need to show that $h = \mathcal {H}(\mathsf {V}_0( pk , h, s), m)$. This follows from the property of $f_\mathsf {shift}$, $f_\mathsf {adapt}$ (cf. Eq. (1)) and Eq. (3) as follows:

$$\begin{aligned} \mathcal {H}(\mathsf {V}_0( pk , h, s), m) =&\mathcal {H}(\mathsf {V}_0( pk , h, f_\mathsf {adapt}(\tilde{s}, y)), m)\\ \overset{(1)}{=}&\mathcal {H}(f_\mathsf {shift}(\mathsf {V}_0( pk , h, \tilde{s}),Y),m) \overset{(3)}{=} h. \end{aligned}$$

Finally, we need to show that $(Y, y') \in \mathsf {R}$. This follows from (2) since:

$$ y' = f_\mathsf {ext}(s, \tilde{s}) = f_\mathsf {ext}(f_\mathsf {adapt}(\tilde{s}, y), \tilde{s}) \overset{(2)}{=} y. $$

Lemma 2

(${\mathsf {{aEUF\mathrm{{-}}CMA}}}$-Security).Under the assumptions of Theorem 2, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ satisfies the ${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ security as for Definition 3.

Let us give first a high level overview of the proof. Our goal is to provide a reduction such that, given an adversary $\mathcal {A}$ who can win the experiment $\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}}$, we can build a simulator who can win the $\mathsf {strongSigForge}$ experiment of the underlying signature or can break the hardness of the relation $\mathsf {R}$. In the first case, we check if $\mathcal {A}$’s forgery $\sigma ^*$ is equal to $\mathsf {Adapt}_ pk (\widetilde{\sigma },y)$. If so, we use $\mathcal {A}$ to break the hardness of the relation $\mathsf {R}$ by extracting the witness $y=\mathsf {Ext}(\sigma ^*, \widetilde{\sigma },Y)$. Otherwise, $\mathcal {A}$ was able to forge a signature “unrelated” to the pre-signature provided to it. In this case, it is used to win the $\mathsf {strongSigForge}$ experiment. All that remains is to answer $\mathcal {A}$’s signing and pre-signing queries using $\mathsf {strongSigForge}$’s signing queries. This is done by programming the random oracle such that the full-signatures generated by the challenger in the $\mathsf {strongSigForge}$ game look like pre-signatures for $\mathcal {A}$.

Proof

We prove the lemma by defining a series of game hops. The modifications for each game hop is presented in code form in the full version of this paper [14].

$\mathbf{Game} \pmb {G_0}$: This game is the original $\mathsf {aSigForge}$ experiment, where the adversary $\mathcal {A}$ outputs a valid forgery $\sigma ^*$ for a message m of its choice, while having access to pre-signing and signing oracles $\mathcal {O}_{\mathrm {pS}}$ and $\mathcal {O}_{\mathrm {S}}$ respectively. Being in the random oracle model, all the algorithms of the scheme and the adversary have access to the random oracle $\mathcal {H}$. Since $\pmb {G_0}$ corresponds to $\mathsf {aSigForge}$, it follows that $\Pr [\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}}(n) = 1] = \Pr [\pmb {G_0} = 1]$.

Game $\pmb {G_1}$: This game works as $\pmb {G_0}$ except when the adversary outputs a forgery $\sigma ^*$, the game checks if adapting the pre-signature $\widetilde{\sigma }$ using the secret witness $y$ results in $\sigma ^*$. If so, the game aborts.

Claim

Let $\mathsf {Bad}_1$ be the event where $\pmb {G_1}$ aborts. Then $\Pr [\mathsf {Bad}_1] \le \nu _1(n)$, where $\nu _1$ is a negligible function in $n$.

Proof: This claim is proven by a reduction to the relation $\mathsf {R}$. We construct a simulator $\mathcal {S}$ which breaks the hardness of $\mathsf {R}$ using $\mathcal {A}$ that causes $\pmb {G_1}$ to abort with non-negligible probability. The simulator receives a challenge $Y^*$, and generates a key pair $( sk , pk ) \leftarrow \mathsf {Gen}(1^n)$ in order to simulate $\mathcal {A}$’s queries to the oracles $\mathcal {H}$, $\mathcal {O}_{\mathrm {pS}}$ and $\mathcal {O}_{\mathrm {S}}$. This simulation of the oracles work as described in $\pmb {G_1}$.

Upon receiving the challenge message $m^*$ from $\mathcal {A}$, $\mathcal {S}$ computes a pre-signature $\widetilde{\sigma }\leftarrow \mathsf {pSign}_{ sk }(m^*,Y^*)$ and returns the pair $(\widetilde{\sigma }, Y)$ to the adversary. Upon $\mathcal {A}$ outputting a forgery $\sigma ^*$ and assuming that $\mathsf {Bad}_1$ happened (i.e., $\mathsf {Adapt}(\widetilde{\sigma },y) = \sigma$), pre-signature correctness (Definition 2) implies that the simulator can extract $y^*$ by executing $\mathsf {Ext}(\sigma ^*, \widetilde{\sigma },Y^*)$ in order to obtain $(Y^*,y^*) \in \mathsf {R}$.

We note that the view of $\mathcal {A}$ in this simulation and in $\pmb {G_1}$ are indistinguishable, since the challenge $Y^*$ is an instance of the hard relation $\mathsf {R}$ and has the same distribution to the public output of $\mathsf {GenR}$. Therefore, the probability that $\mathcal {S}$ breaks the hardness of $\mathsf {R}$ is equal to the probability that the event $\mathsf {Bad}_1$ happens. Hence, we conclude that $\mathsf {Bad}_1$ only happens with negligible probability.    $\blacksquare$

Since games $\pmb {G_1}$ and $\pmb {G_0}$ are equivalent except if event $\mathsf {Bad}_1$ occurs, it holds that $\Pr [\pmb {G_0} = 1]\le \Pr [\pmb {G_1} = 1]+ \nu _1(n)$.

Game $\pmb {G_2}$: This game is similar to the previous game except for a modification in the $\mathcal {O}_{\mathrm {pS}}$ oracle. After the execution of $\mathsf {preSign}_{ sk }$, the oracle obtains a pre-signature $\widetilde{\sigma }$ from which it extracts the randomness $R_\mathsf {pre}\leftarrow \mathsf {V}_0( pk ,\widetilde{\sigma })$. The oracle computes $R_\mathsf {sign}= f_\mathsf {shift}(R_\mathsf {pre},Y)$ and checks if $\mathcal {H}$ was already queried on the inputs $R_\mathsf {pre}\Vert m$ or $R_\mathsf {sign}\Vert m$ before the execution of $\mathsf {pSign}_{ sk }$. In this case the game aborts.

Claim

Let $\mathsf {Bad}_2$ be the event that $\pmb {G_2}$ aborts in $\mathcal {O}_{\mathrm {pS}}$. Then $\Pr [\mathsf {Bad}_2] \le \nu _2(n)$, where $\nu _2$ is a negligible function in n.

Proof: We first recall that the output of $\mathsf {P}_1$ (i.e.,  $R_\mathsf {pre}$) is uniformly random from a super-polynomial set of size q in the security parameter. From this it follows that $R_\mathsf {sign}$ is distributed uniformly at random in the same set. Furthermore, $\mathcal {A}$ being a $\text {{PPT}}$ algorithm, it can only make polynomially many queries to $\mathcal {H}$, $\mathcal {O}_{\mathrm {S}}$ and $\mathcal {O}_{\mathrm {pS}}$ oracles. Denoting $\ell$ as the total number of queries to $\mathcal {H}$, $\mathcal {O}_{\mathrm {S}}$ and $\mathcal {O}_{\mathrm {pS}}$, we have: $\Pr [\mathsf {Bad}_2] = \Pr [H'[R_\mathsf {pre}|| m] \ne \bot \vee H'[R_\mathsf {sign}|| m] \ne \bot ]\le 2\frac{\ell }{q} \le \nu _2(n).$ This follows from the fact that $\ell$ is polynomial in the security parameter.    $\blacksquare$

Since games $\pmb {G_2}$ and $\pmb {G_1}$ are identical except in the case where $\mathsf {Bad}_2$ occurs, it holds that $\Pr [\pmb {G_1} = 1]\le \Pr [\pmb {G_2} = 1]+\nu _2(n).$

Game $\pmb {G_3}$: In this game, upon a query to the $\mathcal {O}_{\mathrm {pS}}$, the game produces a full-signature instead of a pre-signature by executing $\mathsf {Sign}_{ sk }$ instead of $\mathsf {preSign}_{ sk }$. Accordingly, it programs the random oracle $\mathcal {H}$ to make the full-signature “look like” a pre-signature from the point of view of the adversary $\mathcal {A}$. This is done by:

• 1. It sets $\mathcal {H}(R_\mathsf {pre}\Vert m)$ to the value stored at position $\mathcal {H}(R_\mathsf {sign}\Vert m)$.

• 2. It sets $\mathcal {H}(R_\mathsf {sign}\Vert m)$ to a fresh value chosen uniformly at random.

The above programming makes sense as our definition of $f_\mathsf {shift}$ requires it to be deterministic and to possess the same domain and codomain with respect to the commitment set $\mathcal {D}_\mathsf {rand}$. Note further that $\mathcal {A}$ can only notice that $\mathcal {H}$ was programmed if it was previously queried on either $R_\mathsf {pre}\Vert m$ or $R_\mathsf {sign}\Vert m$. But as described in the previous game, we abort if such an event happens. Hence, we have that $\Pr [\pmb {G_2} = 1]=\Pr [\pmb {G_3} = 1]$.

Game $\pmb {G_4}$: In this game, we impose new checks during the challenge phase that are same as the ones imposed in $\pmb {G_2}$ during the execution of $\mathcal {O}_{\mathrm {pS}}$.

Claim

Let $\mathsf {Bad}_3$ be the event that $\pmb {G_4}$ aborts in the challenge phase. Then $\Pr [\mathsf {Bad}_3] \le \nu _3(n)$, where $\nu _3$ is a negligible function in n.

Proof: The proof is identical to the proof in $\pmb {G_2}$.    $\blacksquare$

It follows that $\Pr [\pmb {G_4} = 1]\le \Pr [\pmb {G_3} = 1]+\nu _3(n)$.

Game $\pmb {G_5}$: Similar to game $\pmb {G_3}$, we generate a signature instead of a pre-signature in the challenge phase and program $\mathcal {H}$ such that the full-signature looks like a correct pre-signature from $\mathcal {A}$’s point of view. We get $\Pr [\pmb {G_5} = 1]=\Pr [\pmb {G_4} = 1]$.

Now that the transition from the original $\mathsf {aSigForge}$ experiment (game $\pmb {G_0}$) to game $\pmb {G_5}$ is indistinguishable, it only remains to show the existence of a simulator $\mathcal {S}$ that can perfectly simulate $\pmb {G_5}$ and uses $\mathcal {A}$ to win the $\mathsf {strongSigForge}$ game. The modifications from games $\pmb {G_1}$ - $\pmb {G_5}$ and the simulation in code form can be found in the full version of this paper [14].

We emphasize that the main differences between the simulation and Game $\pmb {G_5}$ are syntactical. Namely, instead of generating the public and secret keys and computing the algorithm $\mathsf {Sign}_{ sk }$ and the random oracle $\mathcal {H}$, $\mathcal {S}$ uses its oracles $\mathsf {SIG}^{\mathsf {ID}}$ and $\mathcal {H}^{\mathsf {ID}}$. Therefore, $\mathcal {S}$ perfectly simulates $\pmb {G_5}$. It remains to show that $\mathcal {S}$ can use the forgery output by $\mathcal {A}$ to win the $\mathsf {strongSigForge}$ game.

Claim

$(m^*,\sigma ^*)$ constitutes a valid forgery in game $\mathsf {strongSigForge}$.

Proof: To prove this claim, we show that the tuple $(m^*, \sigma ^*)$ has not been returned by the oracle $\mathsf {SIG}^{\mathsf {ID}}$ before. First note that $\mathcal {A}$ wins the experiment if it has not queried on the challenge message $m^*$ to $\mathcal {O}_{\mathrm {pS}}$ or $\mathcal {O}_{\mathrm {S}}$. Therefore, $\mathsf {SIG}^{\mathsf {ID}}$ is queried on $m^*$ only during the challenge phase. If $\mathcal {A}$ outputs a forgery $\sigma ^*$ that is equal to the signature $\sigma$ as output by $\mathsf {SIG}^{\mathsf {ID}}$, it would lose the game since this signature is not valid given the fact that $\mathcal {H}$ is programmed.

Hence, $\mathsf {SIG}^{\mathsf {ID}}$ has never output $\sigma ^*$ when queried on $m^*$ before, thus making $(m^*,\sigma ^*)$ a valid forgery for game $\mathsf {strongSigForge}$.    $\blacksquare$

From games $\pmb {G_0} - \pmb {G_5}$, we have that $\Pr [\pmb {G_0} = 1] \le \Pr [\pmb {G_5} = 1] + \nu (n)$, where $\nu (n) = \nu _1(n)+\nu _2(n)+\nu _3(n)$ is a negligible function in n. Since $\mathcal {S}$ simulates game $\pmb {G_5}$ perfectly, we also have that $\Pr [\pmb {G_5} = 1] = \Pr [\mathsf {strongSigForge}_{\mathcal {S}^\mathcal {A}, \mathsf {SIG}}(n) = 1]$. Combining this with the probability statement in $\pmb {G_0}$, we obtain the following:

$\Pr [\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}}(n) = 1] \le \Pr [\mathsf {strongSigForge}_{\mathcal {S}^\mathcal {A}, \mathsf {SIG}^{\mathsf {ID}}}(n) = 1] + \nu (n).$

Recall that the negligible function $\nu _1(n)$, contained in the sum $\nu (n)$ above, precisely quantifies the adversary’s advantage in breaking the hard relation $\mathsf {R}$. Thus, the probability of breaking the unforgeability of the $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ is clearly bounded above by that of breaking either $\mathsf {R}$ or the strong unforgeability of $\mathsf {SIG}^{\mathsf {ID}}$.

Lemma 3

(Pre-Signature Adaptability).Under the assumptions of Theorem 2, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ satisfies the pre-signature adaptability as for Definition 4.

Proof

Assume $\mathsf {pVrfy}_{ pk }(m,Y; \widetilde{\sigma }) =1$, with the notations having their usual meanings from Fig. 3, which means $h=\mathcal {H}(f_\mathsf {shift}(\mathsf {V}_0( pk , h, \tilde{s}),Y),m)$. For any valid pair $(Y, y)\in R$, we can use the homomorphic property from Eq. (1). Then, for such a pair $(Y, y)\in R$, plugging $f_\mathsf {shift}(\mathsf {V}_0( pk , h, \tilde{s}),Y) = \mathsf {V}_0( pk , h, f_\mathsf {adapt}(\tilde{s},y))$ in the above equation implies $h=\mathcal {H}(\mathsf {V}_0( pk , h, f_\mathsf {adapt}(\tilde{s},y)),m)$. This directly implies $\mathsf {Vrfy}_{ pk }(m; \sigma ) = 1$, where $s= f_\mathsf {adapt}(\tilde{s}, y)$ and $\sigma = (h,s)$. Therefore, adapting the valid pre-signature would also result in a valid full-signature.

Lemma 4

(Witness Extractability). Under the assumptions of Theorem 2, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ satisfies the witness extractability as for Definition 5.

This proof is very similar to the proof of Lemma 2 with the mere difference that we only need to provide a reduction to the $\mathsf {strongSigForge}$ experiment. This is because in the $\mathsf {aWitExt}_{\mathcal {A}, \mathsf {aSIG}_{\mathsf {R}_g,\mathsf {SIG}^{\mathsf {ID}}}}$ experiment, $\mathcal {A}$ provides the public value $Y^*$ and must forge a valid full-signature $\sigma ^*$ such that $(Y^*,\mathsf {Ext}_ pk (\sigma ^*, \widetilde{\sigma },Y^*)) \not \in \mathsf {R}$. The full proof can be found in the full version of this paper [14].

Remark 2

We note that our proofs for the ${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ security and witness extractability are in its essence reductions to the strong unforgeability of the underlying signature schemes. Yet the Fiat-Shamir transformation does not immediately guarantee the resulting signature scheme to be strongly unforgeable. However, we first note that many such signature schemes are indeed strongly unforgeable, for instance Schnorr [25], Katz-Wang (from Chaum-Pedersen identification scheme) [24] and Guillou-Quisquater [1] signature schemes all satisfy strong unforgeability. Moreover, one can transform any Fiat-Shamir based existentially unforgeable signature scheme into a strongly unforgeable one via the generic transformation using the results of Bellare et.al. [4].

4 Two-Party Signatures with Aggregatable Public Keys from Identification Schemes

Before providing our definition and generic transformation for two-party adaptor signatures, we show how to generically transform signature schemes based on identification schemes into two-party signature schemes with aggregatable public keys denoted by $\mathsf {SIG}_2$. In Sect. 5, we then combine the techniques used in this section with the ones from Sect. 3 in order to generically transform identification schemes into two-party adaptor signature schemes.

Informally, a $\mathsf {SIG}_2$ scheme allows two parties to jointly generate a signature which can be verified under their combined public keys. An application of such signature schemes can be found in cryptocurrencies where two parties wish to only allow conditional payments such that both users have to sign a transaction in order to spend some funds. Using $\mathsf {SIG}_2$, instead of submitting two separate signatures, the parties can submit a single signature while enforcing the same condition (i.e., a transaction must have a valid signature under the combined key) and hence reduce the communication necessary with the blockchain. Importantly and unlike threshold signature schemes, the key generation here is non-interactive. In other words, parties generate their public and secret keys independently and anyone who knows both public keys can compute the joint public key of the two parties.

We use the notation to represent a two-party interactive protocol $\mathsf {Func}$ between $P_i$ and $P_{1-i}$ with respective secret inputs $x_i,x_{1-i}$ for $i \in \{0,1\}$. Furthermore, if there are common public inputs e.g., $y_1,\cdots , y_n$ we use the notation . We note that the execution of a protocol might not be symmetric, i.e., party $\mathcal {P}_i$ executes the procedures while party $\mathcal {P}_{1-i}$ executes the procedures .

4.1 Two-Party Signatures with Aggregatable Public Keys

We start with defining a two-party signature scheme with aggregatable public keys. Our definition is inspired by the definitions from prior works [7, 8, 26].

Definition 7

(Two-Party Signature with Aggregatable Public Keys). A two-party signature scheme with aggregatable public keys is a tuple of PPT  protocols and algorithms $\mathsf {SIG}_2= (\mathsf {Setup}, \mathsf {Gen},\varPi _\mathsf {Sign }, \mathsf {KAg}, \mathsf {Vrfy})$, formally defined as:

• $\mathsf {Setup}(1^n)$: is a PPT  algorithm that on input a security parameter $n$, outputs public parameters $pp$.

• $\mathsf {Gen}( pp )$: is a PPT  algorithm that on input public parameter $pp$, outputs a key pair $( sk , pk )$.

• : is an interactive, $\text {{PPT}}$ protocol that on input secret keys $sk _i$ from party $\mathcal {P}_i$ with $i \in \{0,1\}$ and common values $m \in \{0,1\}^*$ and $pk _0$, $pk _1$, outputs a signature $\sigma$.

• $\mathsf {KAg}( pk _0, pk _1)$: is a DPT  algorithm that on input two public keys $pk _0, pk _1$, outputs an aggregated public key $apk$.

• $\mathsf {Vrfy}_{ apk }(m;\sigma )$: is a DPT  algorithm that on input public parameters $pp$, a public key $apk$, a message $m \in \{0,1\}^*$ and a signature $\sigma$, outputs a bit b.

The completeness property of $\mathsf {SIG}_2$ guarantees that if the protocol $\varPi _\mathsf {Sign }$ is executed correctly between the two parties, the resulting signature is a valid signature under the aggregated public key.

Definition 8

(Completeness). A two-party signature with aggregatable public keys $\mathsf {SIG}_2$ satisfies completeness, if for all key pairs $( sk , pk ) \leftarrow \mathsf {Gen}(1^n)$ and messages $m \in \{0,1\}^*$, the protocol outputs a signature $\sigma$ to both parties $\mathcal {P}_0,\mathcal {P}_1$ such that $\mathsf {Vrfy}_{ apk }( m;\sigma ) = 1$ where $apk :=\mathsf {KAg}( pk _0, pk _1)$.

A two-party signature scheme with aggregatable public keys should satisfy unforgeability. At a high level, this property guarantees that if one of the two parties is malicious, this party is not able to produce a valid signature under the aggregated public key without cooperation of the other party. We formalize the property through an experiment $\mathsf {SigForge}^b_{\mathcal {A},\mathsf {SIG}_2}$, where $b\in \{0,1\}$ defines which of the two parties is corrupt. This experiment is initialized by a security parameter and run between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$, which proceeds as follows. The challenger first generates the public parameters $pp$ by running the setup procedure $\mathsf {Setup}(1^n)$ as well as a signing key pair $( sk _{1-b}, pk _{1-b})$ by executing , thereby simulating the honest party $\mathcal {P}_{1-b}$. Thereafter, $\mathcal {C}$ forwards $pp _\mathsf {C}$ and $pk _{1-b}$ to the adversary $\mathcal {A}$ who generates its own key pair $( sk _{b}, pk _{b})$, thereby emulating the malicious party $P_b$, and submits $( sk _{b}, pk _{b})$ to $\mathcal {C}$. The adversary $\mathcal {A}$ additionally obtains access to an interactive and stateful signing oracle $\mathcal {O}_{\varPi _\mathrm {S}}^b$, which simulates the honest party $\mathcal {P}_{1-b}$ during the execution of . Furthermore, every queried message m is stored in a query list $\mathcal {Q}$.

Eventually, $\mathcal {A}$ outputs a forgery in form of a $\mathsf {SIG}^{\mathsf {ID}}_2$ signature $\sigma ^*$ and a message $m^*$. $\mathcal {A}$ wins the experiment if $\sigma ^*$ is a valid signature for $m^*$ under the aggregated public key $apk :=\mathsf {KAg}( pk _0, pk _1)$ and $m^*$ was never queried before, i.e., $m^* \not \in \mathcal {Q}$. Below, we give a formal definition of the unforgeability game.

Definition 9

(2-${\mathsf {EUF \mathrm{{-}}CMA}}$Security). A two-party, public key aggregatable signature scheme $\mathsf {SIG}_2$ is unforgeable if for every PPT  adversary $\mathcal {A}$, there exists a negligible function $\nu$ such that: for $b\in \{0,1\}$, $\Pr [\mathsf {SigForge}^b_{\mathcal {A},\mathsf {SIG}_2}(n) = 1] \le \nu (n),$ where the experiment $\mathsf {SigForge}^b_{\mathcal {A},\mathsf {SIG}_2}(n)$ is defined as follows:

Remark 3

(On Security Definition). There are two different approaches for modeling signatures with aggregatable public keys in the literature, namely the plain public-key model [3] (also known as key-verification model [12]) and the knowledge-of-secret-key (KOSK) model [7]. In the plain public-key setting the adversary chooses a key pair $( sk _b, pk _b)$ and only declares the public key $pk _b$ to the challenger in the security game. However, security proofs in this setting typically require rewinding techniques with the forking lemma. This is undesirable for the purpose of this paper, as we aim to construct adaptor signatures and its two-party variant generically as building blocks for further applications such as payment channels [2]. Payment channels are proven secure in the UC framework that does not allow the use of rewinding techniques in order to ensure concurrency. Thus, the plain public-key model does not seem suitable for our purpose. In the KOSK setting, however, the adversary outputs its (possibly maliciously chosen) key pair $( sk _b, pk _b)$ to the challenger. In practice this means that the parties need to exchange zero-knowledge proofs of knowledge of their secret key¹. Similar to previous works [7, 28], we do not require the forking lemma or rewinding in the KOSK setting and hence follow this approach.

4.2 Generic Transformation from $\mathsf {SIG}^{\mathsf {ID}}$ to $\mathsf {SIG}^{\mathsf {ID}}_2$

We now give a generic transformation from $\mathsf {SIG}^{\mathsf {ID}}$ schemes to two-party signature schemes with aggregatable public keys.

At a high level, our transformation turns the signing procedure into an interactive protocol which is executed between the two parties $\mathcal {P}_0, \mathcal {P}_1$. The main idea is to let both parties engage in a randomness exchange protocol in order to generate a joint public randomness which can then be used for the signing procedure. In a bit more detail, to create a joint signature, each party $\mathcal {P}_i$ for $i \in \{0,1\}$ can individually create a partial signature with respect to the joint randomness by using the secret key $sk _i$ and exchange her partial signature with $\mathcal {P}_{1-i}$. The joint randomness ensures that both partial signatures can be combined to one jointly computed signature.

In the following, we describe the randomness exchange protocol that is executed during the signing procedure in more detail, as our transformation heavily relies on it. The protocol, denoted by $\varPi _{\mathsf {Rand}\text {-}\mathsf {Exc}}$, makes use of two cryptographic building blocks, namely an extractable commitment scheme $\mathsf {C}= (\mathsf {Gen}, \mathsf {Com}, \mathsf {Dec}, \mathsf {Extract})$ and a NIZK proof system $\mathsf {NIZK}= (\mathsf {Setup}_\mathsf {R}, \mathsf {Prove}, \mathsf {Verify})$. Consequently, the common input to both parties $\mathcal {P}_0$ and $\mathcal {P}_1$ are the public parameters $pp _\mathsf {C}$ of the commitment scheme, while each party $P_i$ takes as secret input her secret key $sk _i$. In the following, we give description of the protocol and present it in a concise way in Fig. 5.

Fig. 5.

$\varPi _{\mathsf {Rand}\text {-}\mathsf {Exc}}$ Protocol

• 1. Party $\mathcal {P}_0$ generates her public randomness $R_0$ using algorithm $\mathsf {P}_1$ from the underlying $\mathsf {ID}$ scheme alongside a $\mathsf {NIZK}$ proof $\pi _0 \leftarrow \mathsf {NIZK}.\mathsf {Prove}(\mathsf {crs},R_0, sk _0)$ that this computation was executed correctly with the corresponding secret value $sk _0$. $\mathcal {P}_0$ executes $(c,d) \leftarrow \mathsf {C}.\mathsf {Com}( pp ,(R_0,\pi _0))$ to commit to $R_0$ and $\pi _0$ and sends the commitment c to $\mathcal {P}_1$.

• 2. Upon receiving the commitment c from $\mathcal {P}_0$, party $\mathcal {P}_1$ generates her public randomness $R_1$ using algorithm $\mathsf {P}_1$. She also computes a $\mathsf {NIZK}$ proof as $\pi _1 \leftarrow \mathsf {NIZK}.\mathsf {Prove}(\mathsf {crs},R_1, sk _1)$, which proves correct computation of $R_1$, and sends $R_1$ and $\pi _1$ to $\mathcal {P}_0$.

• 3. Upon receiving $R_1$ and $\pi _1$ from $\mathcal {P}_1$, $\mathcal {P}_0$ sends the opening d to her commitment c to $\mathcal {P}_1$.

• 4. $\mathcal {P}_1$ opens the commitment in this round. At this stage, both parties check that the received zero-knowledge proofs are valid. If the proofs are valid, each party $\mathcal {P}_i$ for $i \in \{0,1\}$ outputs $R_i,St_i,R_{1-i}$.

Our transformation can be found in Fig. 6. Note that we use a deterministic function $f_{\mathsf {com}\text {-}\mathsf {rand}}(\cdot , \cdot )$ in step 3 in the signing protocol which combines the two public random values $R_0$ and $R_{1}$. In step 6 of the same protocol, we assume that the partial signatures are exchanged between the parties via the protocol $\varPi _\mathsf {Exchange}$ upon which the parties can combine them using a deterministic function $f_{\mathsf {com}\text {-}\mathsf {sig}}(\cdot ,\cdot )$ in step 7. Further, a combined signature can be verified under a combined public key of the two parties. In more detail, to verify a combined signature $(h, s) :=f_{\mathsf {com}\text {-}\mathsf {sig}}(h,(s_0, s_{1}))$, in step 7, there must exist an additional deterministic function $f_{\mathsf {com}\text {-}\mathsf {pk}}(\cdot ,\cdot )$ (in step 1 of the $\mathsf {KAg}$ algorithm) such that:

Fig. 6.

$\mathsf {SIG}^{\mathsf {ID}}_2$: $\mathsf {SIG}_2$ scheme from identification scheme.

(4)

We also require that given a full signature and a secret key $sk _i$ with $i\in \{0,1\}$, it is possible to extract a valid partial signature under the the public key $pk _{1-i}$ of the other party. In particular, there exists a function $f_{\mathsf {dec}\text {-}\mathsf {sig}}(\cdot ,\cdot ,\cdot )$ such that:

(5)

Note that Eqs. 4 and 5 implicitly define $f_{\mathsf {com}\text {-}\mathsf {sig}}$ through the execution of $\varPi _\mathsf {Sign }$ in the conditional probabilities.

The instantiations of these functions for Schnorr, Katz-Wang signatures and Guillou-Quisquater signatures can be found in the full version of this paper [14].

We note the similarity between this transformation with that in Fig. 3. In particular, both of them compute the public randomness $R_\mathsf {sign}$ by shifting the original random values. Note also that running the algorithm $\mathsf {V}_0$ on the inputs $( pk _i, h, s_i)$ would return $R_i, \forall i\in \{0,1\}$.

Below, we show that the transformation in Fig. 6 provides a secure two-party signature with aggregatable public keys. To this end, we show that $\mathsf {SIG}^{\mathsf {ID}}_2$ satisfies $\mathsf {SIG}_2$ completeness and unforgeability from Definitions 8 and 9, respectively.

Theorem 3

Assume that $\mathsf {SIG}^{\mathsf {ID}}$ is a signature scheme based on the transformation from an identification scheme as per Fig. 2. Further, assume that the functions $f_{\mathsf {com}\text {-}\mathsf {sig}}$, $f_{\mathsf {com}\text {-}\mathsf {pk}}$ and $f_{\mathsf {dec}\text {-}\mathsf {sig}}$ satisfy the relations, Equations (4) and (5) respectively. Then the resulting $\mathsf {SIG}^{\mathsf {ID}}_2$ scheme from the transformation in Fig. 6 is a secure two-party signature scheme with aggregatable public keys in the random oracle model.

Lemma 5

Under the assumptions of Theorem 3, $\mathsf {SIG}^{\mathsf {ID}}_2$ satisfies Definition 8.

Proof

The proof follows directly from Eq. 4 and the construction of $\mathsf {KAg}$ algorithm in Fig. 6.

Lemma 6

Under the assumptions of Theorem 3, $\mathsf {SIG}^{\mathsf {ID}}_2$ satisfies Definition 9.

Proof

We prove this lemma by exhibiting a simulator $\mathcal {S}$ that breaks the unforgeability of the $\mathsf {SIG}^{\mathsf {ID}}$ scheme if it has access to an adversary that can break the unforgeability of the $\mathsf {SIG}^{\mathsf {ID}}_2$ scheme. More precisely, we show a series of games, starting with the $\mathsf {SigForge}^b_{\mathcal {A}, \mathsf {SIG}_2}$ experiment, such that each game is computationally indistinguishable from the previous one. The last game is modified in such a way that the simulator can use the adversary’s forgery to create its own forgery for the unforgeability game against the $\mathsf {SIG}^{\mathsf {ID}}$ scheme.

To construct this simulator, we note that the $\varPi _{\mathsf {Rand}\text {-}\mathsf {Exc}}$ protocol in Fig. 6 must satisfy two properties (similar to [27]). First, the commitment scheme must be extractable for the simulator, and second, the NIZK proof used must be simulatable. The reasons for these two properties become evident in the proof.

We prove Lemma 6 by separately considering the cases of the adversary corrupting party $\mathcal {P}_0$ or party $\mathcal {P}_1$, respectively.

Adversary Corrupts $\mathcal {P}_0$. In the following we give the security proof in case the adversary corrupts party $\mathcal {P}_0$.

Game $\pmb {G_0}$: This is the regular $\mathsf {SigForge}^0_{\mathcal {A},\mathsf {SIG}_2}(n)$ experiment, in which the adversary plays the role of party $\mathcal {P}_0$. In the beginning of the game, the simulator generates the public parameters as . Note that the $\mathsf {Setup}$ procedure, apart from computing $\mathsf {crs}\leftarrow \mathsf {NIZK}.\mathsf {Setup}_\mathsf {R}(1^n)$, includes the execution of $\mathsf {C}.\mathsf {Gen}$ through which the simulator learns the trapdoor $tr$ for the commitment scheme $\mathsf {C}$. Further, $\mathcal {S}$ generates a fresh signing key pair $( sk _{1}, pk _{1}) \leftarrow \mathsf {Gen}(1^n)$, sends $pp$ and $pk _{1}$ to $\mathcal {A}$ and receives the adversary’s key pair $( pk _0, sk _0)$. The simulator simulates the experiment honestly. In particular, it simulates the interactive signing oracle $\mathcal {O}_{\varPi _\mathrm {S}}^0$ honestly by playing the role of party $\mathcal {P}_1$.

Game $\pmb {G_1}$: This game proceeds exactly like the previous game, with a modification in the simulation of the signing oracle. Upon $\mathcal {A}$ initiating the signing protocol by calling the interactive signing oracle, $\mathcal {S}$ receives the commitment c to its public randomness $R_0$ from $\mathcal {A}$. The simulator, using the trapdoor $tr$, then extracts a randomness $R_0' \leftarrow \mathsf {C}.\mathsf {Extract}( pp , tr ,c)$ and computes the joint randomness as $R_\mathsf {sign}\leftarrow f_{\mathsf {com}\text {-}\mathsf {rand}}(R_0',R_1)$. $\mathcal {S}$ honestly computes the zero-knowledge proof to its own randomness $R_1$ and sends it to $\mathcal {A}$. Upon receiving the opening d to c from the adversary, $\mathcal {S}$ checks if $R_0' = \mathsf {C}.\mathsf {Dec}( pp ,c,d)$. If this does not hold, $\mathcal {S}$ aborts, otherwise $\mathcal {S}$ continues to simulate the rest of the experiment honestly.

Claim

Let $\mathsf {Bad}_1$ be the event that $\pmb {G_1}$ aborts in the signing oracle. Then, we have $\Pr [\mathsf {Bad}_1] \le \nu _1(n)$, where $\nu _1$ is a negligible function in n.

Proof: Note that game $\pmb {G_1}$ aborts only if the extracted value $R_0'$ from commitment c is not equal to the actual committed value $R_0$ in c, i.e., if $\mathsf {C}.\mathsf {Extract}( pp , tr ,c) \ne \mathsf {C}.\mathsf {Dec}( pp ,c,d)$. By the extractability property of $\mathsf {C}$ this happens only with negligible probability. In other words, it holds that $\Pr [\mathsf {Bad}_1] \le \nu _1(n)$, where $\nu _1$ is a negligible function in n.    $\blacksquare$

Game $\pmb {G_2}$: This game proceeds as game $\pmb {G_1}$, with a modification to the signing oracle. Upon input message m, instead of generating its signature $(h,s_0)$ with respect to the joint public randomness $R_\mathsf {sign}$, the simulator generates it only with respect to its own randomness $R_0$. Further, the simulator programs the random oracle in the following way: as in the previous game, it computes the joint randomness $R_\mathsf {sign}$ and then programs the random oracle in a way such that on input $(R_\mathsf {sign},m)$ the random oracle returns h.

It is easy to see that this game is indistinguishable from $\pmb {G_1}$ if the adversary has not queried the random oracle on input $(R_\mathsf {sign},m)$ before the signing query. If, however, the adversary has issued this random oracle query before the signing query (i.e., $\mathcal {H}(R_\mathsf {sign},m) \ne \bot )$), then the simulation aborts.

Claim

Let $\mathsf {Bad}_2$ be the event that $\pmb {G_2}$ aborts in the signing oracle. Then, we have $\Pr [\mathsf {Bad}_2] \le \nu _2(n)$, where $\nu _2$ is a negligible function in n.

Proof: We first recall that the output of $\mathsf {P}_1$ (i.e.,  $R_\mathsf {pre}$) is uniformly random from a super-polynomial set of size q in the security parameter. From this it follows that $R_\mathsf {sign}$ is distributed uniformly at random in the same set. Furthermore, $\mathcal {A}$ being a $\text {{PPT}}$ algorithm, can only make polynomially many queries to $\mathcal {H}$ and $\mathcal {O}_{\mathrm {pS}}$ oracles. Denoting $\ell$ as the total number of queries to $\mathcal {H}$ and $\mathcal {O}_{\mathrm {S}}$, we have: $\Pr [\mathsf {Bad}_2] = \Pr [\mathcal {H}(R_\mathsf {sign},m) \ne \bot ]\le \frac{\ell }{q} \le \nu _2(n).$ This follows from the fact that $\ell$ is polynomial in the security parameter.    $\blacksquare$

Game $\pmb {G_3}$: In this game, the only modification as compared to the previous game is that during the $\mathsf {Setup}$ procedure, the simulator executes the algorithm $(\widetilde{\mathsf {crs}},\tau ) \leftarrow \mathsf {NIZK}.\mathsf {Setup}'_\mathsf {R}(1^n)$ instead of $\mathsf {crs}\leftarrow \mathsf {Setup}_\mathsf {R}(1^n)$, which allows the simulator to learn the trapdoor $\tau$. Since the two distributions $\{\mathsf {crs}:\mathsf {crs}\leftarrow \mathsf {Setup}_\mathsf {R}(1^n)\}$ and $\{\widetilde{\mathsf {crs}}:(\widetilde{\mathsf {crs}},\tau ) \leftarrow \mathsf {Setup}'_\mathsf {R}(1^n)\}$ are indistinguishable to $\mathcal {A}$ except with negligible probability, we have that $\Pr [\pmb {G_2}=1] \le \Pr [\pmb {G_3}=1] + \nu _3(n)$ where $\nu _3$ is a negligible function in $n$.

Game $\pmb {G_4}$: This game proceeds exactly like the previous game except that the simulator does not choose its own key pair, but rather uses its signing oracle from the ${\mathsf {EUF \mathrm{{-}}CMA}}$ game to simulate the adversary’s interactive signing oracle $\mathcal {O}_{\varPi _\mathrm {S}}^0$. More concretely, upon the adversary calling $\mathcal {O}_{\varPi _\mathrm {S}}^0$ on message m, the simulator calls its own signing oracle which provides a signature $(h,s_1)$ for m under secret key $sk _{1}$. Note that the simulator does not know $sk _1$ or the secret randomness $r_1$ used in $s_1$. Therefore, the simulator has to additionally simulate the NIZK proof that proves knowledge of $r_1$ in $s_1$. More concretely, the simulator executes $\pi _{\mathsf {S}} \leftarrow \mathsf {S}(\widetilde{\mathsf {crs}},\tau ,R_1)$, where $R_1$ is the public randomness used in $s_1$. Due to the fact that the distributions $\{\pi : \pi \leftarrow \mathsf {Prove}(\widetilde{\mathsf {crs}},R_1,r_1)\}$ and $\{\pi _{\mathsf {S}}:\pi _{\mathsf {S}} \leftarrow \mathsf {S}(\widetilde{\mathsf {crs}},\tau ,R_1)\}$ are indistinguishable to $\mathcal {A}$ except with negligible probability, it holds that $\Pr [\pmb {G_3}=1] \le \Pr [\pmb {G_4}=1] + \nu _4(n)$ where $\nu _4$ is a negligible function in $n$.

It remains to show that the simulator can use a valid forgery output by $\mathcal {A}$ to break unforgeability of the $\mathsf {SIG}^{\mathsf {ID}}$ scheme.

Claim

A valid forgery $(m^*, (h^*,s^*))$ output by $\mathcal {A}$ in game $\mathsf {SigForge}_{\mathcal {A}, \mathsf {SIG}^{\mathsf {ID}}_2}$ can be transformed into a valid forgery $(m^*,(h^*, s^*_{1}))$ in game $\mathsf {SigForge}_{\mathcal {S}, \mathsf {SIG}^{\mathsf {ID}}}$.

Proof: When $\mathcal {A}$ outputs a valid forgery $(m^*, (h^*,s^*))$, $\mathcal {S}$ extracts the partial signature $(h^*, s^*_{1})$ by executing $f_{\mathsf {dec}\text {-}\mathsf {sig}}( sk _0, pk _0, (h^*,s^*))$ (from Eq. (5)). Note that the simulator knows the adversary’s key pair $( sk _0, pk _0)$. The simulator then submits $(m^*,(h^*,s^*_{1}))$ as its own forgery to the ${\mathsf {EUF \mathrm{{-}}CMA}}$ challenger. By definition, $\mathcal {A}$ wins this game if it has not queried a signature on $m^*$ before. Thus, $\mathcal {S}$ has also not queried the ${\mathsf {EUF \mathrm{{-}}CMA}}$ signing oracle on $m^*$ before. Further, Eq. (5) implies that $(m^*,(h^*, s^*_{1}))$ is a valid forgery under the public key $pk _{1}$.    $\blacksquare$

From games $\pmb {G_0}-\pmb {G_4}$, we have that $\Pr [\pmb {G_0} = 1] \le \Pr [\pmb {G_4}=1] + \nu (n)$, where $\nu (n) = \nu _1(n) + \nu _2(n) + \nu _3(n)+ \nu _4(n)$ is a negligible function in $n$. Thus, we have $\Pr [\mathsf {SigForge}_{\mathcal {A}, \mathsf {SIG}^{\mathsf {ID}}_2}(n) = 1] \le \Pr [\mathsf {SigForge}_{\mathcal {S}, \mathsf {SIG}^{\mathsf {ID}}}(n) = 1]+\nu (n).$

Adversary Corrupts $\mathcal {P}_1$. In case the adversary corrupts $\mathcal {P}_1$, the simulator has to simulate $\mathcal {P}_0$. The proof for this case follows exactly the same steps as above with the exception that game $\pmb {G_1}$ is not required. This is due to the reason that the simulator now plays the role of the committing party in the randomness exchange and hence does not have to extract $\mathcal {A}$’s randomness from the commitment c.

5 Two-Party Aggregatable Adaptor Signatures

We are now ready to formally introduce the notion of two-party adaptor signatures with aggregatable public keys which we denote by $\mathsf {aSIG}_2$. Our definition can be seen as a combination of the definition of adaptor signatures from Sect. 3 and the definition of two-party signatures with aggregatable public keys from Sect. 4. Unlike the single party adaptor signatures, in $\mathsf {aSIG}_2$ both parties have the role of the signer and generate pre-signatures cooperatively. Furthermore, both parties can adapt the pre-signature given a witness value $y$. We note that both the pre-signature and the full-signature are valid under the aggregated public keys of the two parties. We formally define an $\mathsf {aSIG}_2$ scheme w.r.t. a $\mathsf {SIG}_2$ scheme (which is in turn defined w.r.t. a $\mathsf {SIG}$ scheme) and a hard relation $\mathsf {R}$.

Afterwards, we show how to instantiate our new definition. Concretely, we present a generic transformation that turns a $\mathsf {SIG}^{\mathsf {ID}}_2$ scheme with certain homomorphic properties into a two-party adaptor signatures scheme. As a $\mathsf {SIG}^{\mathsf {ID}}_2$ scheme is constructed w.r.t. a $\mathsf {SIG}^{\mathsf {ID}}$ scheme (cf. Sect. 4), the construction presented in this section can implicitly transform digital signatures based on ID schemes to two-party adaptor signatures.

The definition of a two-party adaptor signature scheme $\mathsf {aSIG}_2$ is similar to the definition of a standard adaptor signature scheme as for Definition 1. The main difference lies in the pre-signature generation. Namely, the algorithm $\mathsf {pSign}$ is replaced by a protocol $\varPi _\mathsf {pSign }$ which is executed between two parties.

Definition 10

(Two-Party Adaptor Signature Scheme with Aggregatable Public Keys). A two-party adaptor signature scheme with aggregatable public keys is defined w.r.t. a hard relation $\mathsf {R}$ and a two-party signature scheme with aggregatable public keys $\mathsf {SIG}_2= (\mathsf {Setup},\mathsf {Gen},\varPi _\mathsf {Sign ,} \mathsf {KAg}, \mathsf {Vrfy})$. It is run between parties $\mathcal {P}_0,\mathcal {P}_1$ and consists of a tuple $\mathsf {aSIG}_2= (\varPi _\mathsf {pSign ,} \mathsf {Adapt}, \mathsf {pVrfy}, \mathsf {Ext})$ of efficient protocols and algorithms which are defined as follows:

• : is an interactive protocol that on input secret keys $sk _i$ from party $\mathcal {P}_i$ with $i \in \{0,1\}$ and common values public keys $pk _i$, message $m \in \{0,1\}^*$ and statement $Y\in L_\mathsf {R}$, outputs a pre-signature $\widetilde{\sigma }$.

• $\mathsf {pVrfy}_{ apk }(m, Y; \widetilde{\sigma })$: is a DPT  algorithm that on input an aggregated public key $apk$, a message $m \in \{0,1\}^*$, a statement $Y\in L_\mathsf {R}$ and a pre-signature $\widetilde{\sigma }$, outputs a bit b.

• $\mathsf {Adapt}_{ apk }(\widetilde{\sigma },y)$: is a DPT  algorithm that on input an aggregated public key $apk$, a pre-signature $\widetilde{\sigma }$ and witness $y$, outputs a signature $\sigma$.

• $\mathsf {Ext}_{ apk }(\sigma ,\widetilde{\sigma },Y)$: is a DPT  algorithm that on input an aggregated public key $apk$, a signature $\sigma$, pre-signature $\widetilde{\sigma }$ and statement $Y\in L_\mathsf {R}$, outputs a witness $y$ such that $(Y,y) \in \mathsf {R}$, or $\bot$.

We note that in $\mathsf {aSIG}_2$, the $\mathsf {pVrfy}$ algorithm enables public verifiability of the pre-signatures, e.g., $\mathsf {aSIG}_2$ can be used in a three-party protocol where the third party needs to verify the validity of the generated pre-signatrue.

In the following, we formally define properties that a two-party adaptor signature scheme with aggregatable public keys $\mathsf {aSIG}_2$ has to satisfy. These properties are similar to the ones for single party adaptor signature schemes. We start by defining two-party pre-signature correctness which, similarly to Definition 2 states that an honestly generated pre-signature and signature are valid, and it is possible to extract a valid witness from them.

Definition 11

(Two-Party Pre-Signature Correctness). A two-party adaptor signature with aggregatable public keys $\mathsf {aSIG}_2$ satisfies two-party pre-signature correctness, if for all $n\in \mathbb {N}$, messages $m \in \{0,1\}^*$, it holds that:

The unforgeability security definition is similar to Definition 9, except the adversary interacts with two oracles $\mathcal {O}_{\varPi _\mathrm {S}}^b, \mathcal {O}_{\varPi _\mathrm {pS}}^b$ in order to generate signatures and pre-signatures, as in Definition 3. More precisely, in the $\mathsf {aSigForge}^b_{\mathcal {A}, \mathsf {aSIG}_2}(n)$ experiment defined below, $\mathcal {A}$ obtains access to interactive, stateful signing and pre-signing oracles $\mathcal {O}_{\varPi _\mathrm {S}}^b$ and $\mathcal {O}_{\varPi _\mathrm {pS}}^b$ respectively. Oracles $\mathcal {O}_{\varPi _\mathrm {S}}^b$ and $\mathcal {O}_{\varPi _\mathrm {pS}}^b$ simulate the honest party $\mathcal {P}_{1-b}$ during an execution of the protocols and respectively. Similar to Definition 9, both the protocols employed by the respective oracles $\mathcal {O}_{\varPi _\mathrm {S}}^b, \mathcal {O}_{\varPi _\mathrm {pS}}^b$ gets an oracle access to $\mathcal {A}$ as well.

Definition 12

(2-${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ Security). A two-party adaptor signature with aggregatable public keys $\mathsf {aSIG}_2$ is unforgeable if for every PPT  adversary $\mathcal {A}$ there exists a negligible function $\nu$ such that: $\Pr [\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}_2}(n) = 1] \le \nu (n),$ where the experiment $\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}_2}(n)$ is defined as follows:

The definition of two-party pre-signature adaptability follows Definition 4 closely. The only difference is that in this setting the pre-signature must be valid under the aggregated public keys.

Definition 13

(Two-Party Pre-Signature Adaptability). A two-party adaptor signature scheme with aggregatable public keys $\mathsf {aSIG}_2$ satisfies two-party pre-signature adaptability, if for all $n\in \mathbb {N}$, messages $m \in \{0,1\}^*$, statement and witness pairs $(Y, y)\in \mathsf {R}$, public keys $pk _{0}$ and $pk _{1}$, and pre-signatures $\widetilde{\sigma }\in \{0,1\}^*$ satisfying $\mathsf {pVrfy}_{ apk }(m,Y; \widetilde{\sigma }) =1$ where $apk :=\mathsf {KAg}( pk _0, pk _1)$, we have $\Pr [\mathsf {Vrfy}_{ apk }(m; \mathsf {Adapt}_ apk (\widetilde{\sigma },y))=1]=1$.

Finally, we define two-party witness extractability.

Definition 14

(Two-Party Witness Extractability). A two-party public key aggregatable adaptor signature scheme $\mathsf {aSIG}_2$ is witness extractable if for every PPT  adversary $\mathcal {A}$, there exists a negligible function $\nu$ such that the following holds: $\Pr [\mathsf {aWitExt}_{\mathcal {A}, \mathsf {aSIG}_2}(n) = 1] \le \nu (n),$ where the experiment $\mathsf {aWitExt}_{\mathcal {A}, \mathsf {aSIG}_2}$ is defined as follows:

Note that the only difference between this experiment and the $\mathsf {aSigForge}_{\mathcal {A}, \mathsf {aSIG}_2}$ experiment is that here the adversary is allowed to choose the statement/witness pair $(Y^*,y^*)$ and that the winning condition additionally requires that for the extracted witness $y' \leftarrow \mathsf {Ext}_ apk (\sigma ^*, \widetilde{\sigma }, Y^*)$ it holds that $(Y^*,y')\not \in \mathsf {R}$.

A two-party adaptor signature scheme with aggregatable public keys $\mathsf {aSIG}_2$ is called secure if it satisfies the properties 2${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ security, two-party pre-signature adaptability and two-party witness extractability.

5.1 Generic Transformation from $\mathsf {SIG}^{\mathsf {ID}}_2$ to $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$

We now present our generic transformation to achieve two-party adaptor signature schemes with aggregatable public keys from identification schemes. In its essence, this transformation is a combination of the transformations presented in Figs. 3 and 6. More precisely, similar to the transformation from $\mathsf {SIG}^{\mathsf {ID}}$ to $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}$ presented in Fig. 3, we assume the existence of functions $f_\mathsf {shift}$, $f_\mathsf {adapt}$ and $f_\mathsf {ext}$ with respect to the relation $\mathsf {R}$. We then make use of the $\varPi _{\mathsf {Rand}\text {-}\mathsf {Exc}}$ protocol from the transformation in Fig. 6 to let parties agree on the randomness that is going to be used during the pre-signing process. However, unlike the transformation in Fig. 6, the resulting randomness is shifted by a statement $Y$ for relation $\mathsf {R}$ using the function $f_\mathsf {shift}$. The transformation can be found in Fig. 7.

Theorem 4

Assume that $\mathsf {SIG}^{\mathsf {ID}}$ is an ${\mathsf {SUF\mathrm{{-}}CMA}}$-secure signature scheme transformed using Fig. 2. Let $f_\mathsf {shift}, f_\mathsf {adapt}$ and $f_\mathsf {ext}$ be functions satisfying the relations from Equations (1) and 2, and $\mathsf {R}$ be a hard relation. Further, assume that $f_{\mathsf {com}\text {-}\mathsf {sig}}$, $f_{\mathsf {com}\text {-}\mathsf {pk}}$ and $f_{\mathsf {dec}\text {-}\mathsf {sig}}$ satisfy the relation from Equations (4) and (5). Then the resulting $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ scheme from the transformation in Fig. 7 is a secure two-party adaptor signature scheme with aggregatable public keys in the random oracle model.

Fig. 7.

A two-party adaptor signature scheme with aggregatable public keys $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ defined with respect to a $\mathsf {SIG}^{\mathsf {ID}}_2$ scheme and a hard relation R.

In order to prove Theorem 4, we must show that $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ satisfies the pre-signature correctness, 2-${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ security, pre-signature adaptability and witness extractability properties as described in Definitions 11 to 14 respectively. We provide the full proofs of the following lemmas in the full version of this paper [14] and only mention the intuition behind the proofs here. As mentioned in the introduction of this work, despite the fact that $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ is constructed from $\mathsf {SIG}^{\mathsf {ID}}_2$, we require only $\mathsf {SIG}^{\mathsf {ID}}$ to be ${\mathsf {SUF\mathrm{{-}}CMA}}$-secure in order to prove 2-${\mathsf {{aEUF\mathrm{{-}}CMA}}}$ security for $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$.

Lemma 7

(Two-Party Pre-Signature Correctness). Under the assumptions of Theorem 4, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ satisfies Definition 11.

The proof of Lemma 7 follows directly from Equations (1) to (2) and the correctness of $\mathsf {SIG}_2$ from Lemma 5.

Lemma 8

(2-${\mathsf {{aEUF\mathrm{{-}}CMA}}}$-Security). Under the assumptions of Theorem 4, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ satisfies Definition 12.

Proof Sketch: In a nutshell the proof of this lemma is a combination of the proofs of Lemmas 2 and 6, i.e., the proof is done by a reduction to the hardness of the relation $\mathsf {R}$ and the ${\mathsf {SUF\mathrm{{-}}CMA}}$ of the underlying signature scheme. During the signing process, the challenger queries its ${\mathsf {SUF\mathrm{{-}}CMA}}$ signing oracle and receives a signature $\sigma$. As in the proof of Lemma 6, the challenger

programs the random oracle such that $\sigma$ appears like a signature generated with the combined randomness of the challenger and the adversary. Simulating the pre-signing process is similar with the exception that before programming the random oracle, the randomness must be shifted using the function $f_\mathsf {shift}$. Finally, the challenger and the adversary generate a pre-signature $\widetilde{\sigma }^* = (h,\tilde{s})$ on the challenge message $m^*$ and the adversary outputs the forgery $\sigma ^*=(h,s)$. If $f_\mathsf {ext}(s, \tilde{s})$ returns the $y$ generated by the challenger, as in the proof of Lemma 2, the hardness of the relation $\mathsf {R}$ can be broken. Otherwise, using $f_{\mathsf {dec}\text {-}\mathsf {sig}}$, it is possible to use the forgery provided by the adversary to extract a forgery for the ${\mathsf {SUF\mathrm{{-}}CMA}}$ game.

Lemma 9

(Two-Party Pre-Signature Adaptability). Under the assumptions of Theorem 4, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ satisfies Definition 13.

Proof Sketch: The proof of Lemma 9 is analogous to the proof of Lemma 3.

Lemma 10

(Two-Party Witness Extractability). Under the assumptions of Theorem 4, $\mathsf {aSIG}^{\mathsf {ID},\mathsf {R}}_{2}$ satisfies Definition 14.

Proof Sketch: The proof of Lemma 10 is very similar to the proof of Lemma 8 except that the adversary chooses $Y$ now and thus, no reduction to the hardness of the relation $\mathsf {R}$ is needed.