Withdrawable Signature: How to Call Off a Signature

Abstract

Digital signatures are a cornerstone of security and trust in cryptography, providing authenticity, integrity, and non-repudiation. Despite their benefits, traditional digital signature schemes suffer from inherent immutability, offering no provision for a signer to retract a previously issued signature. This paper introduces the concept of a withdrawable signature scheme, which allows for the retraction of a signature without revealing the signer’s private key or compromising the security of other signatures the signer created before. This property, defined as “withdrawability”, is particularly relevant in decentralized systems, such as e-voting, blockchain-based smart contracts, and escrow services, where signers may wish to revoke or alter their commitment.

The core idea of our construction of a withdrawable signature scheme is to ensure that the parties with a withdrawable signature are not convinced whether the signer signed a specific message. This ability to generate a signature while preventing validity from being verified is a fundamental requirement of our scheme, epitomizing the property of withdrawability. After formally defining security notions for withdrawable signatures, we present two constructions of the scheme based on the pairing and the discrete logarithm. We provide proofs that both constructions are unforgeable under insider corruption and satisfy the criteria of withdrawability. We anticipate our new type of signature will significantly enhance flexibility and security in digital transactions and communications.

This work is partly supported by the Australian Research Council (ARC) Discovery Project DP200100144. W. Susilo is supported by the ARC Laureate Fellowship FL230100033.

1 Introduction

Digital signatures are instrumental in constructing trust and security, acting as the essential mechanism for authentication, data integrity, and non-repudiation in contemporary digital communications and transactions. In specific applications of digital signature schemes, such as decentralized e-voting systems, there may arise a natural need for the signer to possess the capability to “undo” a digital signature. Undoing a digital signature implies that the signer may desire to retract the signature they created, as seen in e-voting systems where a voter might wish to change or withdraw their vote before the final vote tally.

However, in traditional digital signature schemes, undoing a digital signature is impossible, as it persists indefinitely once a signature is created. Furthermore, digital signatures provide authenticity, integrity, and non-repudiation for signed messages. As a result, when a message is signed, the non-repudiation of its content is guaranteed, meaning that once the signature is generated, the signer cannot rescind it. In light of this limitation, one might ask whether it is possible for a signer to efficiently revoke or withdraw a previously issued digital signature without revealing their private key or compromising the security of other signatures created by the signer. We answer this question by presenting a withdrawable signature scheme that provides a practical and secure solution for revocating or withdrawing a signature in a desirable situation.

We note that a traditional signature scheme can achieve “withdrawability” by employing a trusted third party (TTP) to establish signature revocation lists. In cases where a signer desires to invalidate a signature, they notify the TTP, which subsequently adds the revoked signature to the revocation list. This enables future verifiers to consult the revocation list via the TTP, allowing them to determine if the signature has been previously revoked before acknowledging its validity. As all participants fully trust the TTP, including the revoked signature in the revocation list ensures its validity and enables the withdrawal of the signature. However, this approach has a centralized nature as it depends on the TTP’s involvement, which may not be desirable in decentralized systems. As in decentralized systems, signers may prefer to manage their signatures without relying on centralized authorities. Therefore, constructing a withdrawable signature scheme that does not rely on a TTP turns out to be a non-trivial problem to solve.

Withdrawable signatures can have various applications in different scenarios where the ability to revoke a signature without compromising the signer’s private key is demanded. Here are some potential applications:

Smart Contracts [19]. In the context of blockchain-based smart contracts, withdrawable signatures can enable users to sign off on contract conditions while retaining the ability to revoke their commitment. This can be particularly useful in situations where the fulfillment of the contract depends on the actions of multiple parties or external events.

E-Voting Systems [9]. In a decentralized e-voting system, withdrawable signatures enable voters to securely sign their votes while retaining the option to modify or retract their choices before the final votes count. This additional flexibility improves the voting procedure by allowing voters to respond to fresh insights or unfolding events before the voting period concludes.

Escrow Services [6]. Withdrawable signatures could be employed in decentralized escrow services where multiple parties must sign off on a transaction. If one party decides not to proceed with the transaction due to disputes or changes in conditions, they can revoke their signature without affecting the security of other parties’ signatures.

In light of the above discussion, we require the following three properties from the withdrawable signature:

• 1. A withdrawable signature should be verifiable, especially, it should be verified through the signer’s valid public key.

• 2. Only the signer can generate a valid withdrawable signature.

• 3. A withdrawable signature, once withdrawn, cannot become valid again without the original signer’s involvement.

In the forthcoming subsection, we provide a technical outline of the withdrawable signature scheme, focusing on the technical challenges we had to face.

1.1 Technical Overview

The most important feature of our withdrawable signature scheme is withdrawability. The idea behind this is that a signer, Alice, should not only be able to sign a message m with her private key to obtain the signature $\sigma$ but also have the option to revoke the signature if she changes her mind. This means the signature $\sigma$ will no longer be verifiable with Alice’s valid public key. In what follows, we describe the challenges to realizing the withdrawable signature at a technical level.

First Attempt: A Simple Withdrawable Signature Scheme with TTP. As mentioned earlier, one straightforward solution to achieve withdrawability is to have a trusted third party (TTP) maintain a signature revocation list. However, if we want to attain withdrawability without relying on a revocation list, an alternative approach can be explored as follows: In this approach, the signer, Alice, “hides” a signature $\omega$ by encrypting it using her public key and the TTP’s public key, resulting in a hidden signature $\sigma$. For example, the BLS signature [4] on a message m, computed as $\omega =H(m)^{\textsf{sk}_s}$ with the signer’s secret key $\textsf{sk}_s\in \mathbb {Z}_p$ and the hash function $H:\{{0,1}\}^*\rightarrow \mathbb {Z}_p$, can be encrypted into $\sigma =(g^{\mathsf {\textsf{sk}_t}a}\cdot H(m)^{\textsf{sk}_s},g^a)$, where $g^{\mathsf {\textsf{sk}_t}}$ is the TTP’s public key, with $\mathsf {\textsf{sk}_t}$ as the corresponding secret key, and $a \in \mathbb {Z}_p^*$ is a uniform random value chosen by the signer.

The hidden signature $\sigma$ preserves the verifiability of the signature as the verification works by checking whether the following equality holds: $e(g^{\mathsf {\textsf{sk}_t}a}\cdot H(m)^{\textsf{sk}_s}, g){\mathop {=}\limits ^{?}} e(g^{\mathsf {\textsf{sk}_t}},g^a)e(H(m),g^{\mathsf {\textsf{sk}_s}}),$ where $g^{\mathsf {\textsf{sk}_s}}$ is the signer’s public key.

In the above scheme, everyone can ensure that the signer has generated a valid signature for the message m under her public key $\textsf{pk}_s(=g^{\mathsf {\textsf{sk}_s}})$, but they cannot extract the original signature $\omega (=H(m)^{\textsf{sk}_s})$ from $\sigma$. (No party except for the TTP can obtain $\omega$.) The signer then has the option to withdraw $\sigma$ merely by taking no action. Later, the signer can request the TTP to “decrypt” the signature $\sigma$ into the original signature $\omega$ using the TTP’s secret key $\textsf{sk}_t$.

Towards a Withdrawable Signature Scheme Without TTP. Implementing a withdrawable signature scheme using a TTP presents a significant drawback, as signers, particularly in decentralized and trustless systems, may wish to achieve withdrawability without reliance on the TTP. How can we achieve withdrawability without the help of the TTP? One possible method involves directly removing the TTP and allowing the signer to create $\sigma$ using a secret random value $r\in \mathbb {Z}_p^*$ chosen by her, which can be regarded as equivalent to the TTP’s secret key $\mathsf {sk_t}$. Subsequently, the signer publishes the corresponding “public key”, represented as $g^r$, and selects another random value $a \in \mathbb {Z}_p^*$.

The withdrawable signature $\sigma$ is then computed as $\sigma =(g^{ra}\cdot H(m)^{\textsf{sk}_s},g^a),$ where the verification of $\sigma$ can be easily performed using the public keys $g^{\textsf{sk}_s}$ and $g^r$ (with the value $g^a$) with the following verification algorithm: $e(g^{ra}\cdot H(m)^{\textsf{sk}_s},g){\mathop {=}\limits ^{?}}e(g^r,g^a)e(H(m),g^{\textsf{sk}_s}).$

However, without the TTP, the signature $\sigma$ immediately becomes a valid signature that can be verified using the signer’s public keys $(g^\mathsf {sk_t},g^r)$; thus, the withdrawability is lost.

Because of this issue, we still need to introduce an additional entity that, while not a TTP, will act as a specific verifier chosen by the signer. More specifically, the signer can produce a signature that cannot be authenticated solely by the signer’s public key but also requires the verifier’s secret key. This ensures the signature appears unverifiable to everyone except for the chosen verifier, as everyone can only be convinced that the signature was created either by the signer or the verifier. If the verifier cannot transform back this signature into a signature that can be verified using the signer’s public key only, this scheme will achieve the withdrawability. In particular, only the signer has the option to transform this signature into a verifiable one. To optimize the length of the withdrawable signature, we limit the number of specific verifiers to one.

Another technical issue then surfaces: How can a signer transform the withdrawable signature into a signature that can be directly verifiable using the signer’s public key (and possibly with additional public parameters)? A straightforward solution might be having the signer re-sign the message with her secret key. However, this newly generated signature will have no connection to the original withdrawable signature.

Our Response to the Challenges. To overcome the aforementioned limitations, we introduce a designated-verifier signature scheme to generate a withdrawable signature for a message m, denoted as $\sigma$, rather than directly generating a regular signature. For a signer Alice, she can create a withdrawable signature for a certain verifier, Bob. Later, if Alice wants to withdraw the signature $\sigma$, she just takes no action. If Alice wants to transform the withdrawable signature, she executes an algorithm, “$\textsf{Confirm}$”, to lift the limitation on verifying $\sigma$ and yield a signature $\widetilde{\sigma }$, which we call “confirmed signature”, verifiable using both Alice’s and Bob’s public keys. Note that the confirmed signature $\widetilde{\sigma }$ can then be deterministically traced back to the original $\sigma$.

Generally, there is a withdrawable signature scheme involving two parties, denoted by $\textsf{user}_1$ and $\textsf{user}_2$. Without loss of generality, assume that $\textsf{user}_1$ is the signing user, while $\textsf{user}_2$ is the certain verifier. Let a set of their public keys be $\gamma =\{{\textsf{pk}_{\textsf{user}_1},\textsf{pk}_{\textsf{user}_2}}\}$. At a high level, we leverage the structure of the underlying regular signature to construct a withdrawable signature $\sigma$ designated to the verifier $\textsf{user}_2$. Later with the signer’s secret key $\textsf{sk}_{\textsf{user}_1}$ and $\sigma$, $\textsf{user}_1$ can generate a verifiable signature for m of the public key set $\gamma$. This signature is the confirmed signature $\widetilde{\sigma }$ and can easily be linked with the withdrawable signature $\sigma$ through the public key set $\gamma$.

If we still take the BLS-like signature scheme as a concrete instantiation with $\textsf{pk}_{\textsf{user}_1}=g^{\textsf{sk}_{\textsf{user}_1}}, \textsf{pk}_{\textsf{user}_2}=g^{\textsf{sk}_{\textsf{user}_2}}$, and two hash functions $H_1:\{{0,1}\}^*\rightarrow \mathbb {G}$ and $H_2:\{{0,1}\}^*\rightarrow \mathbb {Z}_p^*$. The signer $\textsf{user}_1$ can generate the withdrawable signature $\sigma$ of message m for $\textsf{user}_2$ as follows:

$$\begin{aligned} &y\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*,r=H_2(m,g^y\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_1}}), u=H_1(m)^r\\ &\sigma =\left( e(u^{y}\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_1}}, g^{\textsf{sk}_{\textsf{user}_2}}),g^{y}, u\right) . \end{aligned}$$

The verification algorithm of $\sigma$ can be performed using the secret key of $\textsf{user}_2$ and the public key of $\textsf{user}_1$ as follows:

$$\begin{aligned} e(H_1(m)^{r\cdot y}\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_1}},g^{\textsf{sk}_{\textsf{user}_2}}){\mathop {=}\limits ^{?}}e(u^{\textsf{sk}_{\textsf{user}_2}},g^y)e(H_1(m)^{\textsf{sk}_{\textsf{user}_2}},g^{\textsf{sk}_{\textsf{user}_1}}). \end{aligned}$$

Now, assume that $\textsf{user}_1$ needs to transform $\sigma$ into a confirmed signature that is associated with $\gamma$. Since $\textsf{user}_1$ has the secret key $\textsf{sk}_{\textsf{user}_1}$, $\textsf{user}_1$ can easily reconstruct randomness $r=H_2(m,g^y\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_1}})$ and transform $\sigma$ into a confirmed signature $\widetilde{\sigma }$ for m of public key set $\gamma$ with r as follows.

$$\begin{aligned} \widetilde{\sigma }=\left( g^{\textsf{sk}_{\textsf{user}_2}\cdot \textsf{sk}_{\textsf{user}_1}\cdot r}H_1(m)^{\textsf{sk}_{\textsf{user}_1}},g^r,u,(g^{\textsf{sk}_{\textsf{user}_2}})^r\right) . \end{aligned}$$

This withdrawable signature scheme achieves withdrawability in such a way that even if $\textsf{user}_2$ reveals its secret key $\textsf{sk}_{\textsf{user}_2}$, other users won’t be convinced that $\sigma$ was generated from $\textsf{user}_1$. This is due to the potential for $\textsf{user}_2$ to compute the same $\sigma$ using $\textsf{sk}_{\textsf{user}_2}$, as described below:

$$\begin{aligned} \sigma &=\left( e(u^{y}\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_2}},g^{\textsf{sk}_{\textsf{user}_1}}),g^{y},u\right) \\ &=\left( e(u^{y}\cdot H_1(m)^{\textsf{sk}_{\textsf{user}_1}},g^{\textsf{sk}_{\textsf{user}_2}}),g^{y},u\right) . \end{aligned}$$

Later in this paper, we show that a withdrawable signature scheme can be constructed using the Schnorr [16]-like signature scheme.

1.2 Our Contributions

Motivated by the absence of the type of signature scheme we want for various aforementioned applications, we present the concept withdrawable signature scheme. Our contributions in this regard can be summarized as follows:

• 1. We provide a formal definition of a withdrawable signature scheme that reflects all the characteristics we discussed previously.

• 2. We formulate security notions of withdrawable signature, reflecting the withdrawability and unforgeability, two essential security properties.

• 3. We propose two constructions of withdrawable signature schemes based on discrete logarithm (DL) and pairing.

This paper is organized as follows: We first review the related work in Sect. 2. In Sect. 3, we provide a comprehensive definition of withdrawable signatures, including their syntax and security notion. Section 4 begins with a detailed overview of the preliminaries we used to build our withdrawable signature schemes, then we give the full description of our two proposed constructions. Following that, Sect. 5 focuses on the security analysis of these two withdrawable signature constructions.

2 Related Work

In this section, we review the previous work relevant to our withdrawable signature scheme and highlight differences between our scheme and existing ones.

Designated-Verifier Signature Scheme. The concept of designated-verifier signature (or proof) (DVS) was introduced by Jakobsson et al. [8], and independently by Chaum [5]. Since then, the field has been studied for several decades and admitted instantiations from a variety of assumptions [11, 21,22,23,24].

Revocable Group Signature Scheme. Group signature [1, 3, 5] allows any member within a group to authenticate a message on behalf of the collective. In the context of revocable group signature schemes [2, 12, 15], revocation refers to the capability of the group manager to revoke a member’s signing privilege.

Revocable Ring Signature Scheme. The notion of revocable ring signatures [13] was first introduced in 2007. This concept added new functionality where a specified group of revocation authorities could remove the signer’s anonymity. In  [27], Zhang et al. presented a revocable and linkable ring signature (RLRS) scheme. This innovative framework empowers a revocation authority to reveal the real signer’s identity in a linkable ring signature scheme [14].

Universal Designated Verifier Signature Scheme. Designated-verifier signature schemes have multiple variations, including Universal Designated Verifier Signature (UDVS) schemes. Steinfeld et al. proposed the first UDVS scheme based on the bilinear group [17]. They developed two other UDVS schemes, which expanded the conventional Schnorr/RSA signature schemes [18]. Following the work by Steinfeld et al., several UDVS schemes have been proposed in literature [7, 20, 25, 26]. Additionally, the first lattice-based UDVS was proposed in [10], this approach was subsequently further developed in other studies, one of which is referenced here.

Discussion on Differences. Our withdrawable signature constructions presented above comprise two primary parts: withdrawable signature generation and transformation of a withdrawable signature into a confirmed one. When viewed through the “withdrawability” requirements of the first part, our withdrawable signature scheme is relevant to existing group and ring signatures, wherein the signer retains anonymity within a two-party setup. What distinguishes our approach is the second transformation stage, which offers a unique feature not found in the aforementioned revocable group and ring signatures. Our scheme empowers signers to retract their signatures independently, without relying on a certain group manager or a set of revocation authorities. Additionally, the right to remove its “anonymity” rests solely with the signer.

Readers might also discern similarities between our withdrawable signature scheme and the designated-verifier signature (DVS) scheme. In the withdrawable signature generation phase of our scheme, the generated signature can only convince a specific verifier (the designated verifier) that the signer has generated a signature, the same as the core concept of DVS. Note that a DVS holds ‘non-transferability”, which means that a DVS cannot be transferred by either the signer or the verifier to convince a third party. Although this non-transferability aligns with our concept of withdrawability, our scheme diverges by permitting the signer to transform the withdrawable signature into one that’s verifiable using both the signer’s and verifier’s public keys, challenging the foundational property of DVS.

To achieve this additional property at the transformation stage, we consider leveraging the structural properties of existing regular signatures. Provided that our withdrawable signature scheme was derived from a particular signature, which has been generated with the signer’s secret key, only the signer can access this underlying regular signature during the transformation stage. Then one might have also noticed that the construction of our withdrawable signature scheme is related to the UDVS scheme. In a UDVS scheme, once the signer produces a signature on a message, any party possessing this message-signature pair can designate a third party as the certain verifier by producing a DVS with this message-signature pair for this verifier. Much like DVS, UDVS is bound by non-transferability as well. Meanwhile, our withdrawable signature scheme takes another different approach than UDVS’s as our scheme does not require the signer to reveal the underlying regular signature at the withdrawable signature generation stage.

In our withdrawable signature scheme construction, the underlying regular signature is treated as a secret held by the signer. This secret ensures the signer creates a corresponding withdrawable signature specific to a certain (designated) verifier. Later at the transformation stage, we require the additional input as the public key set of signer and verifier and the signer’s secret key to reconstruct the underlying additional regular signature. With these inputs, we can finalize our transformation algorithm.

3 Definitions

In this section, we provide a comprehensive overview of the syntax and security notion of withdrawable signature.

3.1 Notation and Terminology

Throughout this paper, we use $\lambda$ as the security parameter. By $a\overset{{}_\$}{\leftarrow }\mathcal {S}$, we denote an element a is chosen uniformly at random from a set $\mathcal {S}$. Let $\mathcal {S}=\{{\textsf{pk}_1,\cdots ,\textsf{pk}_{\mu }}\}$ be a set of public keys, where each public key $\textsf{pk}_i$ is generated by the same key generation algorithm $\textsf{KeyGen}(1^k)$ and $\mu =|\mathcal {S}|$. The corresponding secret key of $\textsf{pk}_i$ is denoted by $\textsf{sk}_i$. Given two distinct public keys $\textsf{pk}_s,\textsf{pk}_j\overset{{}_\$}{\leftarrow }\mathcal {S}$ where $j\ne s$, the signer’s public key is denoted by $\textsf{pk}_s$.

3.2 Withdrawable Signature: A Formal Definition

Naturally, our withdrawable signature scheme involves two parties: signers and verifiers. At a high level, the scheme consists of two stages, i.e., generating a withdrawable signature and transforming it into a confirmed signature. These two stages are all completed by the signer.

More precisely, a withdrawable signature scheme $\mathcal{W}\mathcal{S}$ consists of five polynomial time algorithms, $(\textsf{KeyGen},\textsf{WSign},\textsf{WSVerify},\textsf{Confirm},\textsf{CVerify})$, each of which is described below:

• $(\textsf{pk},\textsf{sk})\leftarrow \textsf{KeyGen}(1^k)$: The key generation algorithm takes the security parameters $1^k$ as input, to return a public/secret key pair $(\textsf{pk},\textsf{sk})$.

• $\sigma \leftarrow \textsf{WSign}(m,\textsf{sk}_s,\gamma )$: The “withdrawable signing” algorithm takes as input a message m, signer’s secret key $\textsf{sk}_s$ and $\gamma =\{{\textsf{pk}_s,\textsf{pk}_j}\}$ where $\textsf{pk}_s,\textsf{pk}_j\in \mathcal {S}$, to return a new withdrawable signature $\sigma$ of m respect to $\textsf{pk}_s$, which is designated to verifier $\textsf{pk}_j$.

• $1/0\leftarrow \textsf{WSVerify}(m,\textsf{sk}_j,\textsf{pk}_s,\sigma )$: The “withdrawable signature verification” algorithm takes as input a withdrawable signature $\sigma$ of m with respect to $\textsf{pk}_s$, the designated verifier’s secret key $\textsf{sk}_j$, to return either 1 or 0.

• $\widetilde{\sigma }\leftarrow \textsf{Confirm}(m,\textsf{sk}_s,\gamma ,\sigma )$: The “confirm” algorithm takes as input a withdrawable signature $\sigma$ of m with respect to $\textsf{pk}_s$, signer’s secret key $\textsf{sk}_s$, the public key set $\gamma$, to return a confirmed signature $\widetilde{\sigma }$ of m, $\widetilde{\sigma }$ is a verifiable signature with respect to $\gamma$.

• $1/0\leftarrow \textsf{CVerify}(m,\gamma ,\sigma ,\widetilde{\sigma })$: The “confirmed signature verification” algorithm takes as input a confirmed signature $\widetilde{\sigma }$ of m with respect to $\gamma$, and the corresponding withdrawable signature $\sigma$, to return either 1 or 0.

3.3 Security Notions of Withdrawable Signature

The security notion of a withdrawable signature scheme $\mathcal{W}\mathcal{S}$ covers the properties of correctness, unforgeability under insider corruption, and withdrawability three aspects.

• Correctness. As long as the withdrawable signature $\sigma$ is verifiable through the withdrawable signature verification algorithm $\textsf{WSVerify}$, it can be concluded that the corresponding confirmed signature $\widetilde{\sigma }$ will also be verifiable through the confirm verification algorithm $\textsf{CVerify}$.

• Unforgeability under insider corruption. Nobody except the signer can transform a verifiable withdrawable signature $\sigma$ generated from $\textsf{sk}_s$ for $\textsf{pk}_j$ into corresponding confirmed signature $\widetilde{\sigma }$, even the adversary can always obtain the secret key $\textsf{sk}_j$ of the verifier.

• Withdrawability. The withdrawability means that, given a verifiable withdrawable signature $\sigma$, it must be intractable for any PPT adversary $\mathcal {A}$ to distinguish whether $\sigma$ was generated by the signer or the verifier.

Below, we provide formal security definitions. The formal definitions of correctness, unforgeability under insider corruption, and withdrawability.

We call a withdrawable signature scheme $\mathcal{W}\mathcal{S}$ secure if it is correct, unforgeable under insider corruption, withdrawable.

Definition 1 (Correctness)

A withdrawable signature scheme $\mathcal{W}\mathcal{S}$ is considered correct for any security parameter k, any public key set $\gamma$, and any message $m\in \{{0,1}\}^*$, if with following algorithms:

• $(\textsf{pk}_s,\textsf{sk}_s),(\textsf{pk}_j,\textsf{sk}_j)\leftarrow \textsf{KeyGen}(1^k)$

• $\gamma \leftarrow \{{\textsf{pk}_s,\textsf{pk}_j}\}$

• $\sigma \leftarrow \textsf{WSign}(m,\textsf{sk}_s,\gamma )$

• $\widetilde{\sigma }\leftarrow \textsf{Confirm}(m,\textsf{sk}_s,\gamma ,\sigma )$

it holds with an overwhelming probability (in k) that the corresponding verification algorithms:

$$\begin{aligned} \textsf{WSVerify}(m,\textsf{sk}_j,\textsf{pk}_s,\sigma )=1\text { and }\textsf{CVerify}(m,\gamma ,\sigma ,\widetilde{\sigma })=1. \end{aligned}$$

Definition 2 (Unforgeability under insider corruption)

Considering an unforgeability under insider corruption experiment $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)$ for a PPT adversary $\mathcal {A}$ and security parameter k.

The three oracles we use to build the $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)$ are shown as follows.

With these three oracles, we have the following experiment $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)$:

A withdrawable signature scheme $\mathcal{W}\mathcal{S}$ is unforgeable under insider corruption of EUF-CMA security if for all PPT adversary $\mathcal {A}$, there exists a negligible function $\textsf{negl}$ such that:

$$\begin{aligned} {\text {Pr}}[\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)=1]\le \textsf{negl}{\left( 1^k\right) }. \end{aligned}$$

Definition 3 (Withdrawability)

Assume two public/secret key pairs are generated as $(\textsf{pk}_0, \textsf{sk}_0),(\textsf{pk}_1,\textsf{sk}_1)\leftarrow \textsf{KeyGen}(1^k)$. Let $\gamma =\{{\textsf{pk}_0,\textsf{pk}_1}\}$ and $b\overset{{}_\$}{\leftarrow }\{{0,1}\}$, considering a withdrawability experiment $\textsf{Exp}^{\textsf{Withdraw}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)$ for a PPT adversary $\mathcal {A}$ and security parameter k.

The oracle we use to build our withdrawability experiment $\textsf{Exp}^{\textsf{Withdraw}}_{\mathcal{W}\mathcal{S}}(1^k)$ is shown as follows.

With this signing oracle, we have the following experiment $\textsf{Exp}^{\textsf{Withdraw}}_{\mathcal{W}\mathcal{S}}(1^k)$:

A withdrawable signature $\mathcal{W}\mathcal{S}$ achieves withdrawability if, for any PPT adversary $\mathcal {A}$, as long as the $\textsf{Confirm}$ algorithm hasn’t been executed, there exists a negligible function $\textsf{negl}$ such that:

$$\begin{aligned} {\text {Pr}}[\textsf{Exp}^{\textsf{Withdraw}}_{\mathcal{W}\mathcal{S},\mathcal {A}}(1^k)=1]\le \frac{1}{2}+\textsf{negl}{\left( 1^k\right) }. \end{aligned}$$

4 Our Withdrawable Signature Schemes

In this section, we present two specific constructions of withdrawable signatures. We start by introducing the necessary preliminaries that form the basis of our constructions.

4.1 Preliminaries

Digital Signatures. A signature scheme $\textsf{DS}$ consists of three PPT algorithms, described as follows:

$$\begin{aligned} \textsf{DS}= {\left\{ \begin{array}{ll} (\textsf{pk},\textsf{sk})&{}\leftarrow \textsf{KeyGen}(1^k)\\ \sigma &{}\leftarrow \textsf{Sign}(m,\textsf{sk})\\ 0/1&{}\leftarrow \textsf{Verify}(m,\textsf{pk},\sigma ) \end{array}\right. } \end{aligned}$$

The relevant security model of existential unforgeability against chosen-message attacks ($\mathrm {EUF\text {-}CMA}$) for digital signature schemes is given in Appendix A.

Bilinear Groups. Let $\mathbb {G}_1$, $\mathbb {G}_2$ and $\mathbb {G}_T$ be three (multiplicative) cyclic groups of prime order p. Let $g_1$ be a generator of $\mathbb {G}_1$ and $g_2$ be a generator of $\mathbb {G}_2$. A bilinear map is a map $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$ with the following properties:

• Bilinearity: For all $u\in \mathbb {G}_1$, $v\in \mathbb {G}_2$ and $a,b\in \mathbb {Z}_p$, we have $e(u^a, v^b) = e(u, v)^{ab}$.

• Non-degeneracy: $e(g_1,g_2)\ne 1$ (i.e. $e(g_1,g_2)$ generates $\mathbb {G}_T$).

• Computability: For all $u\in \mathbb {G}_1,\ v\in \mathbb {G}_2$, there exists an efficient algorithm to compute e(u, v).

If $\mathbb {G}_1=\mathbb {G}_2$, then e is symmetric (Type-1) and asymmetric (Type-2 or 3) otherwise. For Type-2 pairings, there is an efficiently computable homomorphism $\phi$: $\mathbb {G}_2\rightarrow \mathbb {G}_1$. For Type-3 pairings no such homomorphism is known.

4.2 A Construction Based on BLS

Suppose $\mathbb {G}$ is a generic group of prime order p, and g is a generator, with two hash functions $H_1:\{{0,1}\}^*\rightarrow \mathbb {G}$ and $H_2:\{{0,1}\}^*\rightarrow \mathbb {Z}_p^*$. $\mathbb {P}\mathbb {G}:\mathbb {G}\times \mathbb {G}=\mathbb {G}_T$ is a Type-1 bilinear pairing as defined in Sect. 4.1.

Let $\mathsf {BLS.DS}$ denotes the BLS signature scheme [4], which contains three algorithms: $\mathsf {BLS.DS}=(\textsf{KeyGen},\mathsf {BLS.Sign},\mathsf {BLS.Verify})$. Comprehensive details of these three algorithms are outlined in [4]. The output of the signing algorithm is denoted as $\omega \leftarrow \mathsf {BLS.Sign}(m,\textsf{sk}_s)$ where $\omega$ is derived as follows: $\omega =H_1(m)^{\textsf{sk}_s}$.

Following this, we have a construction of a withdrawable signature based on the original BLS signature (Fig. 1):

Fig. 1.

A Construction Based on BLS

4.3 A Construction Based on Schnorr

Recall that $\mathbb {G}$ is a generic group of prime order p, and g is a generator, with hash function $H:\{{0,1}\}^*\rightarrow \mathbb {Z}_p$.

Let $\mathsf {Sch.DS}$ denote the Schnorr signature scheme [16], which contains three algorithms: $\mathsf {Sch.DS}=(\textsf{KeyGen},\mathsf {Sch.Sign},\mathsf {Sch.Verify})$. Details of these three algorithms are outlined in [16]. The output of the signing algorithm is also denoted as $\omega \leftarrow \mathsf {Sch.Sign}(m,\textsf{sk}_s)$ where $\omega =(t,z)$ is derived as follows:

A randomness e is randomly selected from $\mathbb {Z}_p$, then u is calculated as $u=g^e$. The value t is computed using the hash function $t=H(m,u)$. Finally, z is calculated as $z=(e-x\cdot t)\mod p$.

Following this, we have a construction of a withdrawable signature based on the Schnorr signature (Fig. 2):

Fig. 2.

A Construction Based on Schnorr

5 Security Analysis

In this section, we provide the security analysis of our two constructed withdrawable signature schemes.

5.1 Security of Our Withdrawable Signature Scheme Based on BLS

Theorem 1

If the underlying BLS signature scheme $\mathsf {BLS.DS}$ is unforgeable against chosen-message attacks ($\mathrm {EUF\text {-}CMA}$) as defined in Appendix A, our withdrawable signature scheme based on BLS presented in Sect. 4.2 is unforgeable under insider corruption (Definition 2) in the random oracle model with reduction loss $L=q_{H_1}$ where $q_{H_1}$ denotes the number of hash queries to the random oracle $H_1$.

Proof

We show how to build a simulator $\mathcal {B}$ to provide unforgeability under insider corruption for our withdrawable signature scheme based on BLS in the random oracle model.

Setup. $\mathcal {B}$ has access to the algorithm $\mathcal {C}$, which provides unforgeability in the random oracle for our underlying signature scheme $\mathsf {BLS.DS}$. $\mathcal {C}$ executes the $\mathrm {EUF\text {-}CMA}$ game of $\mathsf {BLS.DS}$, denoted as $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal {A}}$ which includes a signing oracle denoted as $\mathcal {O}^{\mathsf {BLS.DS}}_{\textsf{sk}_s}(\cdot )$, where $\mathcal {O}^{\mathsf {BLS.DS}}_{\textsf{sk}_s}(\cdot ): \omega \leftarrow \mathsf {BLS.Sign}(m,\textsf{sk}_s)$.

For $s\in [1,q_\mu ]$, $\mathcal {C}$ first generates $(\textsf{pk}_s,\textsf{sk}_s)\leftarrow \textsf{KeyGen}(1^k)$. $\mathcal {B}$ then generates $\mathcal {S}=\{{\textsf{pk}_1,\cdots ,\textsf{pk}_{s-1},\textsf{pk}_{s+1},\cdots ,\textsf{pk}_{\mu }}\}$ and gains $\textsf{pk}_s$ from $\mathcal {C}$.

$\mathcal {B}$ now can set the public key set of the signer and a specific (designated) verifier as $\gamma =\{{\textsf{pk}_s,\textsf{pk}_j}\}$ where $j\ne s$ and provide $\gamma$ to $\mathcal {A}$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

Corruption Query. The adversary $\mathcal {A}$ makes secret key queries of $\textsf{pk}_i,i\in [1,\mu ]$ in this phase. If $\mathcal {A}$ queries for the secret key of $\textsf{pk}_s$, abort. Otherwise, $\mathcal {B}$ returns the corresponding $\textsf{sk}_i$ to $\mathcal {A}$, and adds $\textsf{sk}_i$ to the corrupted secret key list $\mathcal{C}\mathcal{O}$.

H-Query. The adversary $\mathcal {A}$ makes hash queries in this phase. $\mathcal {C}$ simulates $H_1$ as a random oracle, $\mathcal {B}$ then answers the hash queries of $H_1$ through $\mathcal {C}$.

Signature Query. $\mathcal {A}$ outputs a message $m_i$ and queries for withdrawable signature with signer $\textsf{pk}_s$ and the specific (designated) verifier $\textsf{pk}_j$. If the signer isn’t $\textsf{pk}_s$, $\mathcal {B}$ abort. Otherwise, $\mathcal {B}$ sets $m_i$ as the input of $\mathcal {C}$. $\mathcal {B}$ then asks for the signing output of $\mathcal {C}$ as $\omega _i\leftarrow \mathsf {BLS.Sign}(m_i,\textsf{sk}_s)$. With $\omega _i=H_1(m_i)^{\textsf{sk}_s}$ from $\mathcal {C}$, $\mathcal {B}$ could respond to the signature query of $\mathcal {A}$ with the specific verifier $\textsf{pk}_j$ as follows:

• $\mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_s,\gamma }(\cdot )$: Given the output $\omega _i$ of $\mathcal {C}$, $\mathcal {B}$ can compute the withdrawable signature $\sigma _i\leftarrow \mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_s,\gamma }(\cdot )$ for $\mathcal {A}$ as:

  • 1. $r_i,y_i\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*$, $\sigma _i=\left( e(H_1(m_i)^{y_i\cdot r_i}\cdot \omega _i,\textsf{pk}_j),H_1(m_i)^{r_i},g^{y_i}\right)$

• $\mathcal {O}^{\textsf{Confirm}}_{\textsf{sk}_s,\sigma ,\gamma }(\cdot )$: With $\omega _i$ and $\sigma _i$, $\mathcal {B}$ can compute the corresponding confirmed signature $\widetilde{\sigma }_i\leftarrow \mathcal {O}^{\textsf{Confirm}}_{\textsf{sk}_s,\sigma ,\gamma }(\cdot )$ for $\mathcal {A}$ with underlying signature $\omega _i=H_1(m_i)^{\textsf{sk}_s}$ and $r_i$ as:

  • 1. Compute $\delta _{1,i}=\textsf{pk}_s^{\textsf{sk}_j \cdot r_i}\cdot \sigma _i$.

  • 2. Compute $\delta _{2,i}=\textsf{pk}_j^{r_i}$, $\delta _{3,i}=g^{r_i}$, $\delta _{4,i}=H_1(m_i)^{r_i}$

  • 3. $\widetilde{\sigma }_i=(\delta _{1,i},\delta _{2,i},\delta _{3,i},\delta _{4,i})$

Meanwhile, $\mathcal {B}$ sets $\mathcal {M}\leftarrow \mathcal {M}\cup m_i$ and $\mathcal {W}\leftarrow \mathcal {W}\cup \sigma _i$.

Forgery. On the forgery phase, the simulator $\mathcal {B}$ returns a withdrawable signature $\sigma ^*$ for signer $\textsf{pk}_s$ that designated to verifier $\textsf{pk}_j$, and $\gamma ^*=\{{\textsf{pk}_s,\textsf{pk}_j}\}$ on some $m^*$ that has not been queried before. $\sigma ^*$ is generated by $\mathcal {B}$ as follows:

$$\begin{aligned} \sigma ^*=\left( e(H_1(m^*)^{r^*\cdot y^*}H_1(m^*)^{\textsf{sk}_j},\textsf{pk}_s),g^{y^*},H_1(m^*)^{r^*}\right) \end{aligned}$$

Then $\sigma ^*$ could be transformed into $\widetilde{\sigma }^*$ under $\gamma ^*$ correctly. After $\mathcal {A}$ transforms $\sigma ^*$ into $\widetilde{\sigma }^*$, if $\widetilde{\sigma }^*$ could not be verified through $\textsf{CVerify}(m^*,\gamma ^*,\sigma ^*,\widetilde{\sigma }^*)$, abort.

Otherwise, if $\widetilde{\sigma }^*=(\delta _1^*,\delta _2^*,\delta _3^*,\delta _4^*)$ is valid, $\mathcal {B}$ then could obtain a forged signature $\omega ^*$ for $\textsf{pk}_s$ on $m^*$. Since $\mathcal {B}$ is capable of directly computing $\textsf{pk}_s^{\textsf{sk}_j\cdot r}$, the forged signature $\omega ^*$ can be determined as: $\omega ^*=\delta _1^*/\textsf{pk}_s^{\textsf{sk}_j\cdot r}$.

Therefore, we can use $\mathcal {A}$ to break the unforgeability in the $\mathrm {EUF\text {-}CMA}$ model of our underlying signature scheme $\mathsf {BLS.DS}$, which contradicts the property of our underlying signature scheme.

Probability of Successful Simulation. All queried signatures $\omega _i$ are simulatable, and the forged signature is reducible because the message $m^*$ cannot be chosen for a signature query as it will be used for the signature forgery. Therefore, the probability of successful simulation is $\frac{1}{q_{H_1}}$ for $q_{H_1}$ queries.   $\square$

Theorem 2

Our withdrawable signature scheme based on BLS presented in Sect. 4.2 is withdrawable (Definition 3) in the random oracle model.

Proof

In our proof of Theorem 2, $\mathcal {B}$ sets the challenge signer/verifier public key set as $\gamma =\{{\textsf{pk}_0,\textsf{pk}_1}\}$ and associated secret key set as $\delta =\{{\textsf{sk}_0,\textsf{sk}_1}\}$. The signer is denoted as $\textsf{pk}_b$ where $b\overset{{}_\$}{\leftarrow }\{{0,1}\}$, and the specific verifier is denoted as $\textsf{pk}_{1-b}$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

H-Query. The adversary $\mathcal {A}$ makes hash queries in this phase, where $\mathcal {B}$ simulates $H_1$ as a random oracle.

Signature Query. $\mathcal {A}$ outputs a message $m_i$ and queries for withdrawable signature with corresponding signer $\textsf{pk}_s$ and the specific verifier $\textsf{pk}_j$, $\mathcal {B}$ responses the signature query of $\mathcal {A}$ as follows:

• $\mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_b,\gamma }(\cdot )$: $r_i,y_i\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*,\sigma _{b,i}=\left( e(H_1(m_i)^{r_i\cdot y_i}\cdot H_1(m_i)^{\textsf{sk}_b},\textsf{pk}_{1-b}),H_1(m_i)^{r_i},g^{y_i}\right)$.

Meanwhile, $\mathcal {B}$ sets $\mathcal {M}\leftarrow \mathcal {M}\cup m_i$.

Challenge. On the challenge phrase, $\mathcal {A}$ gives $\mathcal {B}$ a message $m^*\notin \mathcal {M}$, where $m^*\notin \mathcal {M}$. $\mathcal {B}$ now executes the challenge phrase and computes the challenge withdrawable signature $\sigma ^*_b$ for $\mathcal {A}$ where $b\overset{{}_\$}{\leftarrow }[0,1]$ as follows:

$$\begin{aligned} \sigma ^*_0&=\left( e(H_1(m^*)^{r^*\cdot y^*}\cdot H_1(m^*)^{\textsf{sk}_0},\textsf{pk}_1),H_1(m^*)^{r^*},g^{y^*}\right) \\ \sigma ^*_{1}&=\left( e(H_1(m^*)^{r^*\cdot y^*}\cdot H_1(m)^{\textsf{sk}_1},\textsf{pk}_0),H_1(m^*)^{r^*},g^{y^*}\right) \\ &=\left( e(H_1(m^*)^{r^*\cdot y^*}\cdot H_1(m^*)^{\textsf{sk}_0},\textsf{pk}_1),H_1(m^*)^{r^*},g^{y^*}\right) =\sigma ^*_0. \end{aligned}$$

Guess. $\mathcal {A}$ outputs a guess $b'$ of b. The simulator outputs true if $b'=b$. Otherwise, false.

Probability of Breaking the Withdrawability Property. It’s easy to see that $\sigma ^*_{0}$ and $\sigma ^*_{1}$ have the same distributions, hence they are indistinguishable. Therefore, the adversary $\mathcal {A}$ only has a probability 1/2 of guessing the signer’s identity correctly.

Probability of Successful Simulation. There is no abort in our simulation, the probability of successful simulation is 1.    $\square$

5.2 Security of the Withdrawable Signature Scheme Based on Schnorr

Theorem 3

If the underlying Schnorr signature scheme $\mathsf {Sch.DS}$ is unforgeable against chosen-message attacks ($\mathrm {EUF\text {-}CMA}$) as defined in Appendix A, our withdrawable signature scheme based on Schnorr presented in Sect. 4.3 is unforgeable under insider corruption (Definition 2) in the random oracle model with reduction loss $L=2q_{H}-1$ where $q_{H}$ denotes the number of hash queries to the random oracle H.

The proof of Theorem 3 follows the same proof structure shown in Proof 5.1, which also contains three algorithms, $\mathcal {A}$, $\mathcal {B}$, and $\mathcal {C}$. The completed proof of Theorem 3 is given in Appendix B.

Theorem 4

Our withdrawable signature scheme based on Schnorr presented in Sect. 4.3 is withdrawable (Definition 3) in the random oracle model.

The complete detailed proof of Theorem 4 is available in Appendix B.

6 Conclusion

In this paper, we discussed the challenges associated with traditional signature schemes and the need for a mechanism to revoke or replace signatures. We introduced a unique withdrawability feature for signature schemes, allowing signers to have the ability to call off their signatures as withdrawable signatures, and later, the signature could be transformed into a confirmed signature that could be verified through their public keys.

Furthermore, we proposed cryptographic primitives and two constructions of the withdrawable signature based on the BLS/Schnorr signature. We formally proved that the two proposed constructions are unforgeable under insider corruption and satisfy withdrawability.

There are several directions for future work: one is improving the efficiency of our withdrawable signature scheme. Exploring further to discover practical applications and use cases of withdrawable signature schemes can also be an interesting avenue for future work.

Appendices

A Security Definitions of Existing Cryptographic Primitives

Definition 4

($\mathrm {EUF\text {-}CMA}$). Given a signature scheme $\textsf{DS}=(\textsf{KeyGen},\textsf{Sign},\textsf{Verify})$, and a ppt adversary $\mathcal {A}$, considering the following game $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal {A}}$:

• Let SP be the system parameters. The challenger $\mathcal {B}$ runs the key generation algorithm to generate a key pair $(\textsf{pk}, \textsf{sk})$ and sends $\textsf{pk}$ to the adversary $\mathcal {A}$. The challenger keeps $\textsf{sk}$ to respond to signature queries from the adversary.

• $\mathcal {A}$ is given access to an oracle $\mathcal {O}^{\textsf{Sign}}_{\textsf{sk}}(\cdot )$ such that $\mathcal {O}^{\textsf{Sign}}_{\textsf{sk}}(\cdot ): \sigma \leftarrow \textsf{Sign}(m,\textsf{sk})$.

• $\mathcal {A}$ outputs a message $m^*$, and returns a forged signature $\sigma _{m^*}$ on $m^*$.

• $\mathcal {A}$ succeeds if $\sigma _{m^*}$ is a valid signature of the message $m^*$ and the signature of $m^*$ has not been queried in the query phase.

A signature scheme is $\left( t, q_s, \varepsilon \right)$-secure in the $\mathrm {EUF\text {-}CMA}$ security model if there exists no adversary who can win the above game in time t with advantage $\varepsilon$ after it has made $q_s$ signature queries.

B Security Proofs of Our Withdrawable Signature

We give the detailed proof of Theorem 3 as follows.

Proof

We show how to build a simulator $\mathcal {B}$ to provide unforgeability under insider corruption for our withdrawable signature scheme based on Schnorr in the random oracle model.

Setup. Simulator $\mathcal {B}$ has access to algorithm $\mathcal {C}$, which provides unforgeability in the random oracle for our underlying Schnorr signature scheme $\mathsf {Sch.DS}$.

$\mathcal {C}$ executes the $\mathrm {EUF\text {-}CMA}$ game of $\mathsf {Sch.DS}$, denoted as $\textsf{Exp}^{\mathrm {EUF\text {-}CMA}}_{\mathcal {A}}$ which includes a signing oracle $\mathcal {O}^{\mathsf {Sch.Sign}}_{\textsf{sk}_s}(\cdot )$, where $\mathcal {O}^{\mathsf {Sch.Sign}}_{\textsf{sk}_s}(\cdot ):\omega \leftarrow \mathsf {Sch.Sign}(m,\textsf{sk}_s)$. $\mathcal {B}$ first generates $\mathcal {S}=\{{\textsf{pk}_1,\cdots ,\textsf{pk}_{s-1},\textsf{pk}_{s+1},\cdots ,\textsf{pk}_{\mu }}\}$, $\mathcal {C}$ generates $(\textsf{pk}_s,\textsf{sk}_s)\leftarrow \textsf{KeyGen}(1^k)$, $\mathcal {B}$ then gains $\textsf{pk}_s$ from $\mathcal {C}$ and sets $s\in [1,q_\mu ]$.

$\mathcal {B}$ now can set the public key set of the signer with a specific (designated) verifier as $\gamma =\{{\textsf{pk}_s,\textsf{pk}_j}\}$ where $j\ne s$ and provide $\gamma$ to $\mathcal {A}$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

Corruption Query. The adversary $\mathcal {A}$ makes secret key queries of public key $\textsf{pk}_i,i\in [1,\mu ]$ in this phase. If $\mathcal {A}$ queries for the secret key of $\textsf{pk}_s$, abort. Otherwise, $\mathcal {B}$ returns the corresponding $\textsf{sk}_i$ to $\mathcal {A}$, and add $\textsf{sk}_i$ to the corrupted secret key list $\mathcal{C}\mathcal{O}$.

H-Query. $\mathcal {C}$ simulates H as a random oracle, $\mathcal {B}$ then answers the hash queries of H through $\mathcal {C}$.

Signature Query. $\mathcal {A}$ outputs a message $m_i$ and queries for withdrawable signature with corresponding signer $\textsf{pk}_s$ and specific verifier $\textsf{pk}_j$. If the signer isn’t $\textsf{pk}_s$, abort. Otherwise, $\mathcal {B}$ sets $m_i$ as the input of $\mathcal {C}$. $\mathcal {B}$ then asks the signing output of $\mathcal {C}$ as $\omega _i=\mathsf {Sch.Sign}(m_i,\textsf{sk}_s)$. With $\omega _i$, $\mathcal {B}$ could response the signature query for the specific verifier $\textsf{pk}_j$ chosen by $\mathcal {A}$ as follows:

• $\mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_s,\gamma }(\cdot )$: With the output of $\mathcal {C}$, $\mathcal {B}$ can compute the withdrawable signature $\sigma _i\leftarrow \mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_s,\gamma }(\cdot )$ for $\mathcal {A}$ with $\omega _i=(t_i,z_i)=(H(m_i,u_i),z_i)$ as:

  • 1. Randomly choose $r_i\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*$

  • 2. Compute $\sigma _{1,i} = g^{z_i}\textsf{pk}_s^{t_i}$, $\sigma _{2,i}=\textsf{pk}_j^{z_i-r_i\cdot t_i}$, $\sigma _{3,i}=g^{r_i}$

  • 3. $\sigma _i=(\sigma _{1,i},\sigma _{2,i},\sigma _{3,i})$

• $\mathcal {O}^{\textsf{Confirm}}_{\textsf{sk}_s,\sigma ,\gamma }(\cdot )$: $\mathcal {B}$ then queries for the Schnorr signature of $m_i$ again to $\mathcal {C}$ and returns a corresponding $\omega _{s,i}=(t_{s,i},z_{s,i})$ instead. With $\omega _i$, $\omega _{s,i}$ and $\sigma _i$, $\mathcal {B}$ can compute the confirmed signature $\widetilde{\sigma }_i\leftarrow \mathcal {O}^{\textsf{Confirm}}_{\textsf{sk}_s,\sigma ,\gamma }(\cdot )$ for $\mathcal {A}$ as follows:

  • 1. Compute $\delta _{1,i}=g^{z_{s,i}}\textsf{pk}_s^{t_{s,i}}$, $\delta _{2,i}=z_{s,i}-r_i\cdot t_{s,i}$.

  • 2. Randomly choose $e_{j,i},t_{j,i}\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*$, $\delta _{4,i}=t_{j,i}$

  • 3. Compute $\delta _{5,i}=e_{j,i}-r_i\cdot t_{j,i}$

  • 4. $\widetilde{\sigma }_i=(\delta _{1,i},\delta _{2,i},\delta _{3,i},\delta _{4,i},\delta _{5,i})$

Meanwhile, $\mathcal {B}$ sets the queried message set as $\mathcal {M}\leftarrow \mathcal {M}\cup m$ and queried withdrawable signature set as $\mathcal {W}\leftarrow \mathcal {W}\cup \sigma$.

Forgery. On the forgery phase, $\mathcal {B}$ returns a withdrawable signature $\sigma ^*$ for $\gamma ^*=\{{\textsf{pk}_s,\textsf{pk}_j}\}$ on some $m^*$ that has not been queried before. Then $\sigma ^*$ could be transformed into $\widetilde{\sigma }^*$ under $\gamma ^*$ correctly. After $\mathcal {A}$ transforms $\sigma ^*$ into $\widetilde{\sigma }^*$, if $\widetilde{\sigma }^*$ could not be verified through $\textsf{CVerify}(m^*,\gamma ^*,\sigma ^*,\widetilde{\sigma }^*)$, abort.

Otherwise, if $\widetilde{\sigma }^*=(\delta _1^*,\delta _2^*,\delta _3^*,\delta _4^*,\delta _5^*)$ is valid, $\mathcal {B}$ then could obtain a forged signature $\omega ^*$ for $\textsf{pk}_s$ on $m^*$. Since $\mathcal {B}$ is capable of directly computing $r^*\cdot t_s^*$, the forged signature $\omega ^*$ can be determined as: $\omega ^*=\delta _2^*+r^*\cdot t_s^*\cdot$.

Therefore, we can use $\mathcal {A}$ to break the unforgeability in the $\mathrm {EUF\text {-}CMA}$ model of our underlying signature scheme $\mathsf {Sch.DS}$, which contradicts the property of our underlying signature scheme.

Probability of Successful Simulation. All queried signatures $\omega _i$ are simulatable, and the forged signature is reducible because the message $m^*$ cannot be chosen for a signature query as it will be used for the signature forgery. Therefore, the probability of successful simulation is $\frac{1}{2q_{H}-1}$.   $\square$

We give the proof of Theorem 4 as follows.

Proof

In our proof of Theorem 4, $\mathcal {B}$ sets the challenge public key set as $\gamma =\{{\textsf{pk}_0,\textsf{pk}_1}\}$ and associated secret key set $\delta =\{{\textsf{sk}_0,\textsf{sk}_1}\}$. The signer is denoted as $\textsf{pk}_b$ where $b\overset{{}_\$}{\leftarrow }\{{0,1}\}$, and the specific verifier is denoted as $\textsf{pk}_{1-b}$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

H-Query. The adversary $\mathcal {A}$ makes hash queries in this phase where $\mathcal {B}$ simulates H as a random oracle.

Signature Query. $\mathcal {A}$ outputs a message $m_i$ and queries the withdrawable signature for corresponding signer $\textsf{pk}_s$ and specific verifier $\textsf{pk}_j$, $\mathcal {B}$ responses the signature queries of $\mathcal {A}$ as follows:

• $\mathcal {O}^{\textsf{WSign}}_{\textsf{sk}_b,\gamma }(\cdot )$: $e_i\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*$, $t_i=H(m_i,g^{e_i})$, $\sigma _{b,i}=\left( g^{e_i},\textsf{pk}_{1-b}^{z_{b,i}}\right) =\left( g^{e_i},\textsf{pk}_{1-b}^{e_i-\textsf{sk}_b\cdot t_i}\right)$

Meanwhile, $\mathcal {B}$ sets $\mathcal {M}\leftarrow \mathcal {M}\cup m_i$.

Challenge. In the challenge phase, $\mathcal {A}$ gives $\mathcal {B}$ a message $m^*$, where $m^*\notin \mathcal {M}$. $\mathcal {B}$ now computes the challenge withdrawable signature of $m^*$ as $\sigma ^*_b$ for $\mathcal {A}$ where $b\overset{{}_\$}{\leftarrow }\{{0,1}\}$ and $r^*\overset{{}_\$}{\leftarrow }\mathbb {Z}_p^*$ as follows:

$$\begin{aligned} \sigma ^*_{0}=\left( g^{e^*},\textsf{pk}_1^{z_0^*-r^*\cdot t^*}\right) &=\left( g^{e^*},g^{\textsf{sk}_1(e^*-\textsf{sk}_0\cdot t^*-r^*\cdot t^*)}\right) \\ \sigma ^*_{1}=\left( g^{e^*},\textsf{pk}_s^{z_1^*-r^*\cdot t^*}\right) &=\left( g^{e^*},(g^{e^*})^{\textsf{sk}_1}\textsf{pk}_0^{-\textsf{sk}_1\cdot t^*}g^{-\textsf{sk}_1\cdot r^*\cdot t^*}\right) \\ &=\left( g^{e^*},g^{\textsf{sk}_1(e^*-\textsf{sk}_0\cdot t^*-r^*\cdot t^*)}\right) =\sigma ^*_{0}. \end{aligned}$$

Guess. $\mathcal {A}$ outputs a guess $b'$ of b. The simulator outputs true if $b'=b$. Otherwise, false.

Probability of Breaking the Withdrawability Property. It’s easy to see that $\sigma ^*_{0}$ and $\sigma ^*_{1}$ have the same distributions, hence they are indistinguishable. Therefore, the adversary $\mathcal {A}$ only has a probability 1/2 of guessing the signer’s identity correctly.

Probability of Successful Simulation. There is no abort in our simulation, therefore, the probability of successful simulation is 1.    $\square$