Keywords

1 Introduction

In public key infrastructure (PKI), digital certificates are used to authenticate users’ public keys. However, the burden of certificate issuance and management would become costly when PKI systems are implemented in a large scale. Shamir [13] proffered identity-based cryptography to eliminate the need of certificates by using the user’s identifying information (e.g., email address) as her public key. The user private key is computed by a trusted third party called the private key generator (PKG). Unfortunately, the knowledge of the PKG on the users’ private keys results in a key escrow problem.

Al-Riyami and Paterson [1] proposed certificateless cryptography to overcome the key escrow problem in identity-based systems and eliminate the need of certificates in traditional public key cryptography (PKC) at the same time. This is achieved by computing the user’s private key from two distinct secrets: secret value chosen by the user and the (identity-based) partial private key computed by a semi-trusted key generation center (KGC). The user’s public key has to be computed (based on the secret value) and made publicly available.

Efficient revocation of public keys has always been a critical issue in PKC. As pointed out in [6, 12], the situation is worsened in identity-based and certificateless systems. A possible solution in such systems is to concatenate validity periods to identities and reissue new private keys (or partial private keys) at the beginning of each period. Unfortunately, this approach does not provide fine-grained revocation for environments that demand instant revocation.

Boneh et al. [3] proposed security-mediated cryptography to provide immediate revocation in a RSA-type cryptosystem. It relies on an online semi-trusted security mediator (SEM) which holds a portion of each user’s private key to issue message-specific tokens. The user is unable to undergo any main cryptographic function (e.g., sign or decrypt) without acquiring the token from the SEM. Accordingly, instantaneous revocation is achieved by instructing the SEM to stop issuing tokens for revoked public keys. Ju et al. [10] proposed security-mediated certificateless (SMC) cryptography and gave an encryption and a signature scheme, without defining the security details. Chow et al. [6] defined the notion of SMC cryptography and proposed a SMC encryption with security proofs. Later, Yap et al. [14] formalized the security models of SMC signatures and proposed a novel SMC signature without pairing.

Digital signatures can be verified publicly with the knowledge of the signer’s public key. However, this property may not be desirable in some situations (e.g., two business parties signing a confidential contract). Chaum and van Antwerpen [5] introduced the notion of undeniable signatures, such that the verifier can only verify the validity or invalidity of an undeniable signature with the direct help of its signer via the confirmation or disavowal protocol.

Motivation. Security-mediated cryptography is a well-known approach to effectively provide immediate public key revocation. The goal of undeniable signature schemes is to preserve the signer’s privacy by limiting the public verifiability of her signatures. The notion of security-mediated undeniable signature scheme combines the aforementioned features and results in introducing new applications and recuperating the current applications of undeniable signature schemes.

The leakage of the signer’s secret information in undeniable signature scheme is more catastrophic than in ordinary signatures. Not only the leakage of her secret information enables the adversary to sign new signatures (similar to the case of ordinary signatures), but it also assists the adversary to prove the validity/invalidity of her existing signatures to unauthorized parties or even convertFootnote 1 them to ordinary signatures. Aside from the well-studied features of security-mediated schemes [3, 6, 12, 14], a security-mediated undeniable signature can tackle this problem by protecting the signer’s secret information from any single point of failure since the adversary would need the cooperation of the SEM in order to sign on behalf of the signer. For example, a security-mediated undeniable signatures can enable the company to assign a trusted supervisor to work as a SEM and have control over the operation of the company’s representatives. This can help to immediately revoke the public key of the representatives in the case of private key compromisation or privilege revocation. The new notion can also establish a proactive supervisory control and cogently impoverish the possible malicious intentions of a disgruntled employee.

Contribution. In this paper, we propose the first security-mediated undeniable signature scheme. We extend the security models of undeniable signatures in a SMC setting. Our scheme complies with the fundamental definitions of security-mediated cryptography [3] by preventing the signer from performing any cryptography operation (i.e., signature or proof generation) without the help of the online SEM, while hiding the SMC infrastructure from the verifiers (verifiers can verify proofs without the need to interact with the SEM). Furthermore, our scheme employs the non-interactive designated verifier proofs of [9] in the confirmation and disavowal protocols so as to prevent blackmailing and man-in-the-middle attacks. In order to enhance the efficiency for multiple signature verification, we equipped our scheme with batch verification [2] which enables the signer/verifier to generate/verify proofs on the validity or invalidity of multiple signatures at the same time in a more efficient approach. To the best of our knowledge, our scheme is the first undeniable signatures which provides batch verification in its proof generation and verification protocols. Finally, we prove the security of our scheme based on some well-known assumptions in the random oracle model.

Organization. In Sect. 2, we recall some mathematical backgrounds. In Sect. 3, we define the notion and security models of SMC undeniable signatures. In Sect. 4, we propose our concrete scheme. We provide a security analysis for our scheme in Sect. 5 and conclude our paper in Sect. 6.

2 Preliminaries

Bilinear Pairing. Let \(\mathbb {G}_{1}\) denote an additive cyclic group of prime order q with generator P and \(\mathbb {G}_{2}\) be a multiplicative cyclic group of the same order. An admissible bilinear pairing \(e:\mathbb {G}_{1}\times \mathbb {G}_{1}\mathbb {\rightarrow G}_{2}\) is given which satisfies:

  1. 1.

    Bilinearity: \(\forall \) \(P,Q\in \mathbb {G}_{1}\), \(\forall \) \(a,b\in \mathbb {Z}_{q}\) we have: \(e(aP,bQ)=e(P,Q)^{ab}\) and \(e(aP,bQ)=e(abP,Q)\).

  2. 2.

    Non-degeneracy: There exist P and \(Q\in \mathbb {G}_{1}\) such that \(e(P,Q)\ne 1.\)

  3. 3.

    Computability: e is efficiently computable.

3 Security Model of SMC Undeniable Signatures

3.1 Definition of SMC Undeniable Signatures

Our proposed notion involves three parties: the KGC, the signer, and the SEM.

  • Setup: On input the system security parameter(s), the KGC outputs its key pair \((s,P_{Pub})\) where s is the master secret key and \(P_{Pub}\) is the corresponding public key. It also generates and outputs the system public parameters params which are shared in the system. For simplicity, we omit the inclusion of params as the input of the remaining algorithms.

  • Set-user-key: On input identity ID, the user generates a secret value \(x_{ID}\) and the corresponding public key \(P_{ID}\).

  • Register: On input the identity ID and public key \(P_{ID}\), the KGC computes the user’s main partial private key \(D_{ID}\) (which is kept secure by the KGC), partial private key \(D_{ID}^{USER}\), and the SEM’s private key \(D_{ID}^{SEM}\).

  • Sign: An interactive protocol between the signer (with identity \(ID_{A}\) and public key \(P_{A}\)) and the SEM. The common input is a message m to be signed, and the private inputs are the SEM’s private key \(D_{A}^{SEM}\) and the signer’s secret value \(x_{A}\) and partial private key \(D_{A}^{USER}\). The final output of the protocol is either \(\bot \) (where the SEM refuses to cooperate) or a valid signature \(\sigma \) on \((m,ID_{A},P_{A})\).

  • Confirmation/disavowal protocol: A three-party protocol between the signer, the SEM, and the verifier (possibly designated). The common input is a message–signature pair \((m,\sigma )\), and the private inputs are the SEM’s private key \(D_{A}^{SEM}\) and the signer’s secret value \(x_{A}\) and partial private key \(D_{A}^{USER}\). The final output of the protocol is either \(\bot \) (where the SEM refuses to cooperate) or a non-transferable proof transcript on the validity/invalidity of the message–signature pair \((m,\sigma )\) for the claimed signer.

3.2 Security Models

The security model will be given in the full version of the paper due to the space limit. In short, it includes Unforgeability for three types of adversaries: Type I adversary \(\mathcal {A}_{I}\) and Type II adversary \(\mathcal {A}_{II}\) similar to the existing security model of undeniable signatures, and new insider forger \(\mathcal {F}_{I}\) that is willing to generate signatures without the help of the SEM. As a legitimate user, \(\mathcal {F}_{I}\) is assumed to successfully generate its secret value and public key and register itself in order to receive a valid partial private key. The notion of Invisibility means that the adversary is not able to confirm the validity/invalidity of an undeniable signature without the signer’s help. The notion of Non-transferability refers to the inability of the verifier to transfer the proof of the validity or invalidity of an undeniable signature to a third party.

4 Proposed SMC Undeniable Signature Scheme

In this section, we propose our SMC undeniable signature scheme and discuss its characteristics and features.

  • Setup: Provided the security parameters k and l, the KGC generates groups \(\mathbb {G}_{1}\) and \(\mathbb {G}_{2}\) of prime order \(q\ge 2^{k}\), picks an arbitrary generator \(P\in \mathbb {G}_{1},\) selects a bilinear map \(e:\mathbb {G}_{1}\times \mathbb {G}_{1}\rightarrow \mathbb {G}_{2}\), and chooses five cryptographic hash functions: \(H_{1}:\{0,1\}^{*}\rightarrow \mathbb {G}_{1},\) \(H_{2}:\{0,1\}^{*}\times \{0,1\}^{l}\times \{0,1\}^{*}\rightarrow \mathbb {G}_{1}\), \(H_{3}:\{0,1\}^{*}\times \{0,1\}^{l}\times \{0,1\}^{*}\times \mathbb {G}_{1}\rightarrow \mathbb {G}_{1}\), and \(H_{4},H_{5}:\{0,1\}^{*}\rightarrow \mathbb {Z}_{q}\). Next, it randomly generates its master secret key \(s\in \mathbb {Z}_{q}\) and calculates the public key \(P_{Pub}=sP\). Lastly, the KGC publishes the system public parameters as \(params = (q,\mathbb {G}_{1}, \mathbb {G}_{2}, P, P_{Pub}, H_{1}, H_{2}, H_{3}, H_{4}, H_{5})\).

  • Set-user-key: On input identity ID, the user randomly chooses \(x_{ID}\in \mathbb {Z}_{q}\) as the secret value and computes the public key \(P_{ID}=x_{ID}P\).

  • Register: Provided the user’s identity ID and public key \(P_{ID}\), the KGC authenticates the user and computes the main partial private key \(D_{ID}=sQ_{ID}=sH_{1}(ID)\). Next, it selects the partial private key of the user \(D_{ID}^{USER}\in \mathbb {G}_{1}\) at random and computes the SEM’s private key \(D_{ID}^{SEM}=D_{ID}-D_{ID}^{USER}\). Lastly, the KGC delivers \(D_{ID}^{USER}\) and \(D_{ID}^{SEM}\) to the user and the SEM in a secure manner.

  • Sign: On input a message \(m\in \{0,1\}^{*}\), the signer’s public key \(P_{A}\), and identity \(ID_{A}\), the signer Alice and the SEM work as follows.

  1. 1.

    Alice randomly chooses \(r\in \{0,1\}^{l}\), computes \(O_{2}=H_{2}(m,r,ID_{A})\) and \(O_{3}=H_{3}(m,r,ID_{A},P_{A})\), and sends \((ID_{A},P_{A},O_{2})\) to the SEM.

  2. 2.

    The SEM first authenticates Alice and checks if \(ID_{A}\) has been revoked, and it rejects and outputs \(\bot \). Otherwise, it computes \(\mathcal {U}^{SEM}=e(O_{2},D_{A}^{SEM})\) and sends \(\mathcal {U}^{SEM}\) to Alice.

  3. 3.

    Alice computes \(\lambda =e(O_{3},x_{A}Q_{A})e(O_{2},D_{A}^{USER})\mathcal {U}^{SEM}\) and outputs the signature as \(\sigma =(\lambda ,r)\).

  • Confirmation: Provided a valid message–signature pair \((m,\sigma =(\lambda ,r))\), Alice computes a confirmation proof for a designated verifier Bob (with public key \(P_{B}\) and identity \(ID_{B}\)) as follows.

  1. 1.

    Alice computes and sends \(O_{2}=H_{2}(m,r,ID_{A})\) to the SEM in order to request a proof on the provided message–signature pair \((m,\sigma =(\lambda ,r))\). Upon receiving such request, the SEM first authenticates Alice and checks if \(ID_{A}\) has been revoked, and it rejects and outputs \(\bot \). Otherwise, it picks \(W^{SEM}\in \mathbb {G}_{1}\) at random, computes \(k_{1}^{SEM}=e(P,W^{SEM})\) and \(k_{2}^{SEM}=e(O_{2},W^{SEM})\), and sends \((k_{1}^{SEM},k_{2}^{SEM})\) to Alice.

  2. 2.

    Next, Alice computes \(Q_{B}=H_{1}(ID_{B})\ \text {and}\ O_{3}=H_{3}(m,r,ID_{A},P{}_{A})\) and picks \(U,W^{USER}\in \mathbb {G}_{1}\) and \(\beta ,\tau ,v\in \mathbb {Z}_{q}\) at random to calculate:

    $$\begin{aligned} n_{1}&=e(P_{Pub},Q_{B})^{v}e(P,U),\; n_{2}=vP{}_{B}+\tau P,\\ g_{1}&=e(P,W^{USER})k_{1}^{SEM},\quad g_{2}=e(P,P)^{\beta },\\ g_{3}&=e(O_{3},Q_{A})^{\beta }e(O_{2},W^{USER})k_{2}^{SEM}. \end{aligned}$$

    She then sets \(h_{C}=H_{4}(n_{1},n_{2},g_{1},g_{2},g_{3},\sigma )\) and \(h=(h_{C}+v)\) and sends h to the SEM.

  3. 3.

    Upon receiving h, the SEM computes \(R^{SEM}=W^{SEM}-hD_{A}^{SEM}\) and sends \(R^{SEM}\) to Alice.

  4. 4.

    Lastly, Alice sets the values of \(b=\beta -(h_{C}+\nu )x_{A}\), \(R^{USER}=W^{USER}-(h_{C}+\nu )D_{A}^{USER}\), and \(R=R^{USER}+R^{SEM}\) and sends the confirmation proof transcript as \((U,v,\tau ,b,R,h_{C})\).

    Upon receiving \((U,v,\tau ,b,R,h_{C})\), the designated verifier Bob sets \(O_{2}=H_{2}(m,r,ID_{A})\ \text {and}\ O_{3}=H_{3}(m,r,ID_{A},P_{A})\) and computes the following:

    $$\begin{aligned} n_{1}^{'}&=e(P_{Pub},Q_{B})^{v}e(P,U),\quad n_{2}^{'}=vP_{B}+\tau P,\\ g_{1}^{'}&=e(P,R)e(P_{Pub},Q_{A})^{(h_{C}+v)},\quad g_{2}^{'}=e(P,P)^{b}e(P,P_{A})^{(h_{C}+v)},\\ g_{3}^{'}&=e(O_{3},Q_{A})^{b}e(O_{2},R)\lambda ^{(h_{C}+v)}. \end{aligned}$$

    Bob accepts the proof if \(h_{C}=H_{4}(n_{1}^{'},n_{2}^{'},g_{1}^{'},g_{2}^{'},g_{3}^{'},\sigma )\) or rejects it otherwise.

  • Disavowal: Provided an invalid message–signature pair \((m,\sigma =(\lambda ,r))\), Alice generates a disavowal proof for a designated verifier Bob as follows.

  1. 1.

    Alice first parses \(\sigma \) into \((\lambda ,r)\) and computes \(Q_{B}=H_{1}(ID_{B}),O_{2}=H_{2}(m,r\), \(ID_{A}),\ \text {and}\ O_{3}=H_{3}(m,r,ID_{A},P{}_{A})\). Then, she picks \(U\in \mathbb {G}_{1}\) and \(\tau ,v\in \mathbb {Z}_{q}\) at random in order to compute the values of \(n_{1}=e(P_{Pub},Q_{B})^{v}e(P,U)\) and \(n_{2}=vP{}_{B}+\tau P\). Next, she passes \(O_{2}\) to the SEM in order to request for a partial signature.

  2. 2.

    The SEM first authenticates Alice and checks if \(ID_{A}\) has been revoked, and it rejects and outputs \(\bot \). Otherwise, it computes \(\mathcal {U}^{SEM}=e(O_{2},D_{A}^{SEM})\) and sends \(\mathcal {U}^{SEM}\) to Alice.

  3. 3.

    Alice picks \(\omega \in \mathbb {Z}_{q}\) and computes \(C=(\frac{e(O_{3},x_{A}Q_{A})e(O_{2},D_{A}^{USER})\mathcal {U}^{SEM}}{\lambda })^{\omega }\). She proves the knowledge of a tuple \((T,\mu ,\alpha )\in \mathbb {G}_{1}\times \mathbb {Z}_{q}\times \mathbb {Z}_{q}\) where \(C=\frac{e(O_{3},\mu Q_{A})e(O_{2},T)}{\lambda ^{\alpha }}\) , \(\frac{e(P,T)}{e(Q_{A},P_{Pub})^{\alpha }}=1\) and \(\frac{\alpha P{}_{A}}{\mu P}=1\).

    1. (a)

      Again, she sends \(O_{2}\) to the SEM to request for a proof. The SEM picks \(X^{SEM}\in \mathbb {G}_{1}\) at random, computes \(z_{1}^{SEM}=e(P,X^{SEM})\) and \(z_{2}^{SEM}=e(O_{2},X^{SEM})\), and sends \((z_{1}^{SEM},z_{2}^{SEM})\) to Alice.

    2. (b)

      Next, Alice picks \(X^{USER}\in \mathbb {G}_{1}\) and \(a,i\in \mathbb {Z}_{q}\) at random and computes:

      $$\begin{aligned} j_{1}&=\frac{e(P,X^{USER})z_{1}^{SEM}}{e(Q_{A},P_{Pub})^{a}},\quad j_{2}=\frac{e(P,P)^{i}}{e(P,P{}_{A})^{a}},\\ j_{3}&=\frac{e(O_{3},Q_{A})^{i}e(O_{2},X^{USER})z_{2}^{SEM}}{\lambda ^{a}} \end{aligned}$$

      She then sets \(h_{D}=H_{5}(C,n_{1},n_{2},j_{1},j_{2},j_{3},\sigma )\) and \(h=\alpha (h_{D}+v)\) and sends h to the SEM.

    3. (c)

      Upon receiving h, the SEM computes \(Y^{SEM}=X^{SEM}-hD_{A}^{SEM}\) and sends \(Y^{SEM}\) to Alice.

    4. (d)

      Lastly, Alice sets the values of \(w_{1}=i-(h_{D}+v)\mu \), \(w_{2}=a-(h_{D}+v)\alpha \), \(Y^{USER}=X^{USER}-(h_{D}+v)\alpha D_{A}^{USER}\), and \(Y=Y^{USER}+Y^{SEM}\). She outputs the proof transcript: \((C,U,\tau ,v,h_{D},Y,w_{1},w_{2})\).

  4. 4.

    Upon receiving \((C,U,\tau ,v,h_{D},Y,w_{1},w_{2})\), Bob first checks if \(C=1\), he rejects and outputs \(\bot \). Otherwise, he calculates \(O_{2}=H_{2}(m,r,ID_{A})\ \text {and}\ O_{3}=H_{3}(m,r,ID_{A},P{}_{A})\) and verifies the proof by computing the following:

    $$\begin{aligned} n_{1}^{'}&=e(P_{Pub},Q_{B})^{v}e(P,U),\quad n_{2}^{'}=vP{}_{B}+\tau P,\\ j_{1}^{'}&=\frac{e(P,Y)}{e(Q_{A},P_{Pub})^{w_{2}}},\quad j_{2}^{'}=\frac{e(P,P)^{w_{1}}}{e(P,P{}_{A})^{w_{2}}},\\ j_{3}^{'}&=\frac{e(O_{3},Q_{A})^{w_{1}}e(O_{2},Y)}{\lambda ^{w_{2}}}C^{(h_{D}+v)} \end{aligned}$$

    Bob accepts the proof if \(h_{D}=H_{5}(C,n_{1}^{'},n_{2}^{'},j_{1}^{'},j_{2}^{'},j_{3}^{'},\sigma )\) or rejects it otherwise.

Characteristics and Features. The feature of batch verification and convertibility will be given in the full version of the paper.

5 Security Analysis

In the full version of the paper, we show that our scheme is secure (both unforgeable and invisible) against the aforementioned adversary types (Type I/II adversary and insider forger) in the random oracle model, given the hardness of some well-known complexity assumptions.

6 Conclusion

We proposed the first security-mediated undeniable signature scheme. We also formalized the security models of such schemes in a certificateless setting for the first time. We provided a formal security proof for our scheme in the random oracle model so as to rely its security on the intractability of the BDH and the DBDH assumptions. As a result, our construction allows the design of undeniable signature scheme in a SMC setting. The direction for future research would be to propose SMC schemes which are more efficient and require less pairing evaluations while satisfying all the security requirements.