1 Introduction
-
1. This paper first reveals the insecurity of the scheme in Tsai et al. (2014), and displays the forgery attack as well as the reason why their scheme is easily broken.
-
2. Next, this paper proposes a new certificateless signature scheme with revocation, whose security proof is provided in the standard model based on the Computational Diffie–Hellman assumption. And the attack mounted by the malicious-but-passive KGC is able to be resisted in our scheme.
-
3. Finally, by comparing the performance and properties with related works, the RCLS scheme in this paper outperforms the existing works.
1.1 Related Work
1.2 Organization
2 Preliminaries
2.1 Bilinear Pairing
2.2 Mathematical Concept and Assumption
-
• Computational Diffie–Hellman (CDH) Problem: Given a tuple $(g,{g^{a}},{g^{b}})$ to calculate ${g^{ab}}$ where $a,b\in {\mathcal{Z}_{p}^{\ast }}$, $g\in \mathcal{G}$.
-
• Computational Diffie–Hellman (CDH) Assumption: The CDH assumption in $\mathfrak{G}$ holds if there does not exist polynomial-time algorithm $\mathfrak{B}$ to solve the CDH problem with non-negligible advantage formulated as
2.3 Outline of RCLS
-
• Setup: A KGC produces a system master secret key $\mathsf{SSK}$ and system public parameters $\mathsf{SPP}$ on input the security parameter k.
-
• Partial-Private-Key-Extraction: A KGC produces a partial private key ${\mathsf{PPK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathsf{SSK}$ and an identity $\mathit{ID}$.
-
• Time-Key-Update: A KGC produces the time key ${\mathsf{TK}_{T}}$ on input $\mathsf{SSK}$, $\mathit{ID}$ and a time period T.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ calculates the secret value $s{v_{\mathit{ID}}}$ on input $\mathsf{SPP}$.
-
• Public-Key-Generation: A user calculates the public key ${\mathsf{PK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathit{ID}$ and the secret value $s{v_{\mathit{ID}}}$ of this identity $\mathit{ID}$.
-
• Secret-Key-Generation: A non-revocation user calculates the full secret key ${\mathsf{SK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathit{ID}$, $s{v_{\mathit{ID}}}$ and the corresponding ${\mathsf{PPK}_{\mathit{ID}}}$ and ${\mathsf{TK}_{T}}$.
-
• RCL-Sign: A signer produces a signature σ on input $\mathsf{SPP}$, $\mathit{ID}$, $s{v_{\mathit{ID}}}$, ${\mathsf{SK}_{\mathit{ID}}}$ and a message M.
-
• RCL-Verify: A verifier outputs VALID or INVALID to demonstrate signature σ’s validity on input $\mathsf{SPP}$, $\mathit{ID}$, σ, M, T, ${\mathsf{PK}_{\mathit{ID}}}$.
2.4 Security Model of RCLS
-
• Public-Key-Extract Query: After receiving an identity $\mathit{ID}$, this oracle produces the user’s public key ${\mathsf{PK}_{\mathit{ID}}}$.
-
• Partial-Private-Key-Extract Query: After receiving $\mathit{ID}$, this oracle produces the user $\mathit{ID}$’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}$.
-
• Time-Key-Update Query: After receiving $(\mathit{ID},T)$, this oracle produces the time key ${\mathsf{TK}_{T}}$.
-
• Secret-Value-Extract Query: After receiving $\mathit{ID}$, this oracle produces the user $\mathit{ID}$’s secret value $s{v_{\mathit{ID}}}$.
-
• Public-Key-Replace Query: After receiving $(\mathit{ID},{\mathsf{PK}^{\prime }_{\mathit{ID}}})$, a user $\mathit{ID}$’s public key is replaced with ${\mathsf{PK}^{\prime }_{\mathit{ID}}}$ through this oracle.
-
• RCL-Sign Query: After receiving $\mathit{ID}$, T, ${\mathsf{PK}_{\mathit{ID}}}$ and a message M, this oracle produces a valid signature σ.
Definition 1.
Definition 2.
Definition 3.
-
1. If $\mathfrak{A}\in {\mathfrak{A}_{I}}$, $\mathfrak{A}$ has never queried the oracle Partial-Private-Key-Extract Query with ${\mathit{ID}^{\ast }}$.
-
2. If $\mathfrak{A}\in {\mathfrak{A}_{\mathit{II}}}$, $\mathfrak{A}$ has never queried the oracle Secret-Value-Extract Query with ${\mathit{ID}^{\ast }}$ nor queried the oracle Public-Key-Replace Query with ${\mathsf{PK}_{{\mathit{ID}^{\ast }}}}$.
-
3. If $\mathfrak{A}\in {\mathfrak{A}_{\mathit{ru}}}$, $\mathfrak{A}$ has never queried the oracle Time-Key-Update Query with $({\mathit{ID}^{\ast }},{T^{\ast }})$.
-
4. $\mathfrak{A}$ has never queried the oracle RCL-Sign Query with $({\mathit{ID}^{\ast }},{M^{\ast }},{T^{\ast }})$.
-
5. $\mathit{VALID}\gets \text{RCL-Verify}(\mathsf{SPP},{\mathit{ID}^{\ast }},{\sigma ^{\ast }},{M^{\ast }},{T^{\ast }},{\mathsf{PK}_{{\mathit{ID}^{\ast }}}})$.
3 A Brief Analysis of Tsai et al.’s Scheme
3.1 Overview of Tsai et al.’s RCLS Scheme
-
• Setup: Taken k as the security parameter, KGC generates a bilinear map $\hat{e}:\mathcal{G}\times \mathcal{G}\to {\mathcal{G}_{T}}$, where $\mathcal{G}$, ${\mathcal{G}_{T}}$ are cyclic groups of order p. Furthermore, KGC picks $x,y\in {\mathcal{Z}_{p}^{\ast }}$, $g,{g_{1}},{g_{2}}\in \mathcal{G}$ and calculates ${g_{1}}={g^{x+y}}$, $\mathsf{SSK}={g_{2}^{x}}$, where $g,\mathsf{SSK}$ denote a generator of $\mathcal{G}$ and the system secret key respectively. In addition, let ${g_{2}^{y}}$ denotes the time secret key. After that, KGC randomly selects ${u^{\prime }},{t^{\prime }},{k^{\prime }},{s^{\prime }},{m^{\prime }}\in \mathcal{G}$, and five vectors $\mathbf{U}=[{u_{i}}]\in {\mathcal{G}^{{n_{u}}}}$, $\mathbf{T}=[{t_{i}}]\in {\mathcal{G}^{{n_{t}}}}$, $\mathbf{K}=[{k_{i}}]\in {\mathcal{G}^{{n_{k}}}}$, $\mathbf{S}=[{s_{i}}]\in {\mathcal{G}^{{n_{s}}}}$, $\mathbf{M}=[{m_{i}}]\in {\mathcal{G}^{{n_{m}}}}$. Finally, KGC issues the system public parameters $\mathsf{SPP}=\langle \mathcal{G},{\mathcal{G}_{T}},\hat{e},g,{g_{1}},{g_{2}},\mathbf{U},\mathbf{T},\mathbf{K},\mathbf{S},\mathbf{M},{\mathcal{H}_{0}},{\mathcal{H}_{1}},{\mathcal{H}_{2}},{\mathcal{H}_{3}},{\mathcal{H}_{4}},{u^{\prime }},{t^{\prime }},{k^{\prime }},{s^{\prime }},{m^{\prime }}\rangle $.
-
• Partial-Private-Key-Extraction: After receiving $\mathsf{SSK},\mathsf{SPP}$, and a user’s identity $\mathit{ID}$, KGC will first calculate a set as $\nu ={\mathcal{H}_{0}}(\mathit{ID})=\{{\nu _{1}},{\nu _{2}},\dots ,{\nu _{{n_{u}}}}\}$. Then KGC calculates the user’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})=({g_{2}^{x}}{({u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})^{{r_{\nu }}}},{g^{{r_{\nu }}}})$ where ${r_{\nu }}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Time-Key-Update: Upon receiving $\mathsf{SSK},\mathit{ID}$ and a time period T, KGC calculates a set as $\nu t={\mathcal{H}_{1}}(\mathit{ID},t)=(\nu {t_{1}},\nu {t_{2}},\dots ,\nu {t_{{n_{t}}}})$, and sets the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{y}}{({t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})^{{r_{t}}}},{g^{{r_{t}}}})$ where ${r_{t}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$ and sets the secret value $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$.
-
• Public-Key-Generation: The user with identity $\mathit{ID}$ calculates ${\mathsf{PK}_{\mathit{ID}}}=({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=({g^{{x_{1}}}},{g^{{x_{2}}}})$ as the public key.
-
• Secret-Key-Generation: The user $\mathit{ID}$ computes a set as $\nu u={\mathcal{H}_{2}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=\{\nu {u_{1}},\nu {u_{2}},\dots ,\nu {u_{{n_{k}}}}\}$ and $\nu s={\mathcal{H}_{3}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=\{\nu {s_{1}},\nu {s_{2}},\dots ,\nu {s_{{n_{s}}}}\}$. Then, the algorithm calculates the secret key ${\mathsf{SK}_{\mathit{ID}}}={g_{2}^{{x_{1}}}}{({k^{\prime }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}})^{{x_{1}}}}{({s^{\prime }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})^{{x_{2}}}}$.
-
• RCL-Sign: Upon receiving ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})$ and ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})$, a signer $\mathit{ID}$ can sign a message $M\in {\{0,1\}^{\ast }}$ with a secret key ${\mathsf{SK}_{\mathit{ID}}}$ by performing the following steps:
-
(1) Define a set as $\nu m={\mathcal{H}_{4}}(M)=\{\nu {m_{1}},\nu {m_{2}},\dots ,\nu {m_{{n_{m}}}}\}$.
-
(2) Randomly select ${r_{m}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculate ${\sigma _{1}}={\mathsf{PPK}^{(1)}}\cdot {\mathsf{TK}^{(1)}}\cdot {\mathsf{SK}_{\mathit{ID}}}{({m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})^{{r_{m}}}}$, ${\sigma _{2}}={\mathsf{PPK}^{(2)}}$, ${\sigma _{3}}={\mathsf{TK}^{(2)}}$, ${\sigma _{4}}={g^{{r_{m}}}}$.
-
(3) Output a revocable certificateless signature $\sigma =({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})$ of the message M and return to a verifier.
-
-
• RCL-Verify: Given $\mathsf{SPP}$, $\mathit{ID}$, σ, M, t, ${\mathsf{PK}_{\mathit{ID}}}$, the verifier calculates five sets $\nu ={\mathcal{H}_{0}}(\mathit{ID})$, $\nu t={\mathcal{H}_{1}}(\mathit{ID},t)$, $\nu u={\mathcal{H}_{2}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})$, $\nu s={\mathcal{H}_{3}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})$, $\nu m={\mathcal{H}_{4}}(M)$. After that, the verifier can check the equation : $\hat{e}(g,{\sigma _{1}})\stackrel{?}{=}\hat{e}({g_{1}},{g_{2}})\cdot \hat{e}({\sigma _{2}},{u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})\cdot \hat{e}({\sigma _{3}},{t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})\cdot \hat{e}({\mathsf{PK}^{(1)}},{g_{2}}({k^{\prime }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}))\cdot \hat{e}({\mathsf{PK}^{(2)}},{s^{\prime }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})\cdot \hat{e}({\sigma _{4}},{m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})$. If the equation holds, output VALID, otherwise, output INVALID.
3.2 Forgery Attack of Tsai et al.’s Scheme
-
(1) ${\mathfrak{A}_{\mathit{II}}}$ randomly selects $\alpha ,\beta ,\gamma \in {\mathcal{Z}_{p}^{\ast }}$ and calculates ${g_{2}^{\ast }}={g^{\gamma }},{k^{{^{\prime }}\ast }}={g^{\alpha }},{s^{{^{\prime }}\ast }}={g^{\beta }}$. Besides, ${\mathfrak{A}_{\mathit{II}}}$ sets ${K^{\ast }}=[{k_{i}}]=[{g^{{\alpha _{i}}}}]\in {\mathcal{G}^{{n_{k}}}}$, ${S^{\ast }}=[{s_{i}}]=[{g^{{\beta _{i}}}}]\in {\mathcal{G}^{{n_{s}}}}$, where ${\alpha _{i}},{\beta _{i}}\in {\mathbb{Z}_{p}^{\ast }}$. Other parameters in the system master secret key and system public parameters are generated normally by the KGC. Finally, ${\mathfrak{A}_{\mathit{II}}}$ publishes these public parameters.
-
(2) By making a hash query on $({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}}),{\mathfrak{A}_{\mathit{II}}}$ can obtain the hash value $vu,vs$. Then ${\mathfrak{A}_{\mathit{II}}}$ can calculate ${k^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}={g^{(\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}$, ${s^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}}={g^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}$.
-
(3) ${\mathfrak{A}_{\mathit{II}}}$ randomly picks $a,b,c\in {\mathcal{Z}_{p}^{\ast }}$ and calculates ${\sigma _{2}^{\ast }}={g^{a}},{\sigma _{3}^{\ast }}={g^{b}},{\sigma _{4}^{\ast }}={g^{c}}$.
-
(4) ${\mathfrak{A}_{\mathit{II}}}$ calculates ${\sigma _{1}^{\ast }}={g_{1}^{\gamma }}\cdot {({u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})^{a}}\cdot {({t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})^{b}}\cdot {({\mathsf{PK}^{(1)}})^{(\gamma +\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}\cdot {({\mathsf{PK}^{(2)}})^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}\cdot {({m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})^{c}}$.
-
(5) The signature on the message ${M^{\ast }}$ is ${\sigma ^{\ast }}=({\sigma _{1}^{\ast }},{\sigma _{2}^{\ast }},{\sigma _{3}^{\ast }},{\sigma _{4}^{\ast }})$.
4 Our Proposed RCLS Scheme
4.1 Construction
-
• Setup: Taken k as the security parameter, KGC generates a bilinear map $\hat{e}:\mathcal{G}\times \mathcal{G}\to {\mathcal{G}_{T}}$, where $\mathcal{G},{\mathcal{G}_{T}}$ are cyclic groups of order p. Furthermore, KGC picks $x,y\in {\mathcal{Z}_{p}^{\ast }},{g_{2}},{g_{3}}\in \mathcal{G}$ and calculates ${g_{1}}={g^{x+y}}$, $A=\hat{e}({g_{1}},{g_{2}})$, $\mathsf{SSK}=({g_{2}^{x}},{g_{2}^{y}})$, where $g,\mathsf{SSK}$ denote a generator of $\mathcal{G}$ and the system secret key respectively. After that, KGC randomly selects $\alpha ,\beta ,\gamma \in \mathcal{G}$, and three vectors $\mathbf{U}=[{u_{i}}]\in {\mathcal{G}^{{n_{u}}}}$, $\mathbf{T}=[{t_{i}}]\in {\mathcal{G}^{{n_{t}}}}$, $\mathbf{M}=[{m_{i}}]\in {\mathcal{G}^{{n_{m}}}}$. Define three functions ${f_{1}},{f_{2}},{f_{3}}$ via ${f_{1}}(\mathcal{U})=\alpha {\textstyle\prod _{i\in \mathcal{U}}}{u_{i}}$, ${f_{2}}(\mathcal{T})=\beta {\textstyle\prod _{i\in \mathcal{T}}}{t_{i}}$, ${f_{3}}(\mathcal{M})=\gamma {\textstyle\prod _{i\in \mathcal{M}}}{m_{i}}$, where $\mathcal{U}\subseteq \{1,2,\dots ,{n_{u}}\}$, $\mathcal{T}\subseteq \{1,2,\dots ,{n_{t}}\}$, $\mathcal{M}\subseteq \{1,2,\dots ,{n_{m}}\}$. Finally, KGC issues the system public parameters $\mathsf{SPP}=\langle \mathcal{G},{\mathcal{G}_{T}},\hat{e},g,{g_{1}},{g_{2}},{g_{3}},A,{f_{1}},{f_{2}},{f_{3}},\mathbf{U},\mathbf{T},\mathbf{M},{\mathcal{H}_{0}},{\mathcal{H}_{1}},{\mathcal{H}_{2}}\rangle $.
-
• Partial-Private-Key-Extraction: After receiving $\mathsf{SSK},\mathsf{SPP}$, and a user’s identity $\mathit{ID}$, KGC will first calculate a set as ${\mathcal{F}_{\mathit{ID}}}=\{i|u[i]=1,u={\mathcal{H}_{0}}(\mathit{ID})\}\subseteq \{1,2,\dots ,{n_{u}}\}$. Then KGC calculates the user’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})=({g_{2}^{x}}{f_{1}}{({\mathcal{F}_{\mathit{ID}}})^{{r_{u}}}},{g^{{r_{u}}}})$ where ${r_{u}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Time-Key-Update: Upon receiving $\mathsf{SSK},\mathit{ID}$ and a time period T, KGC calculates a set as ${\mathcal{F}_{\mathit{ID},t}}=\{i|{t^{\prime }}[i]=1,{t^{\prime }}={\mathcal{H}_{1}}(\mathit{ID},t)\}\subseteq \{1,2,\dots ,{n_{t}}\}$, and sets the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{y}}{f_{2}}{({\mathcal{F}_{\mathit{ID},t}})^{{r_{t}}}},{g^{{r_{t}}}})$ where ${r_{t}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$ and sets the secret value $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$.
-
• Public-Key-Generation: The user $\mathit{ID}$ calculates ${\mathsf{PK}_{\mathit{ID}}}=({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=({g^{{x_{1}}}},{g^{{x_{2}}}})$ as the public key.
-
• Secret-Key-Generation: The user $\mathit{ID}$ randomly selects $\lambda ,\mu \in {\mathcal{Z}_{p}^{\ast }}$ and calculates the secret key ${\mathsf{SK}_{\mathit{ID}}}=({\mathsf{SK}^{(1)}},{\mathsf{SK}^{(2)}},{\mathsf{SK}^{(3)}})=({({\mathsf{PPK}^{(1)}}\cdot {\mathsf{TK}^{(1)}}\cdot {f_{1}}{({\mathcal{F}_{\mathit{ID}}})^{\lambda }}\cdot {f_{2}}{({\mathcal{F}_{\mathit{ID},t}})^{\mu }}\cdot {g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}},{\mathsf{PPK}^{(2)}}\cdot {g^{\lambda }},{\mathsf{TK}^{(2)}}\cdot {g^{\mu }})$.
-
• RCL-Sign: Upon receiving $\mathsf{SPP}$ and ${\mathsf{PK}_{\mathit{ID}}}$, a signer $\mathit{ID}$ can sign a message $M\in {\{0,1\}^{\ast }}$ with a secret key ${\mathsf{SK}_{\mathit{ID}}}$ and signer’s secret value $s{v_{\mathit{ID}}}$ by performing the following steps:
-
(1) Define a set as ${\mathcal{F}_{M}}=\{i|m[i]=1,m={\mathcal{H}_{2}}(M,\mathit{ID},{\mathsf{PK}_{\mathit{ID}}})\}\subseteq \{1,2,\dots ,{n_{m}}\}$.
-
(2) Randomly select $\nu \in {\mathcal{Z}_{p}^{\ast }}$ and calculate ${\sigma _{1}}={\mathsf{SK}^{(1)}}\cdot {({f_{3}}{({\mathcal{F}_{M}})^{\nu }})^{{x_{1}^{-1}}}}$, ${\sigma _{2}}={\mathsf{SK}^{(2)}}$, ${\sigma _{3}}={\mathsf{SK}^{(3)}}$, ${\sigma _{4}}={g^{\nu }}$.
-
(3) Output a revocable certificateless signature $\sigma =({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})$ of the message M and return to a verifier.
-
-
• RCL-Verify: Given $\mathsf{SPP},\mathit{ID},\sigma ,M,t,{\mathsf{PK}_{\mathit{ID}}}$, any verifier can check the equation $\hat{e}({\sigma _{1}},{\mathsf{PK}^{(1)}})\stackrel{?}{=}A\cdot \hat{e}({f_{1}}({\mathcal{F}_{\mathit{ID}}}),{\sigma _{2}})\cdot \hat{e}({f_{2}}({\mathcal{F}_{\mathit{ID},t}}),{\sigma _{3}})\cdot \hat{e}({f_{3}}({\mathcal{F}_{M}}),{\sigma _{4}})\cdot \hat{e}({g_{3}},{\mathsf{PK}^{(2)}})$. If theequation holds, output VALID, otherwise, output INVALID.
4.2 Security Analysis
Theorem 1.
Proof.
-
• Public-Key-Extract Query: At first, $\mathfrak{B}$ maintains a list ${L_{\mathit{PK}}}=\{(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})\}$ in order to respond to these queries. When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PK}_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$, calculates ${g^{{x_{1}}}},{g^{{x_{2}}}}$, and sets $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$, ${\mathsf{PK}_{\mathit{ID}}}=({g^{{x_{1}}}},{g^{{x_{2}}}})$. After that, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PK}_{\mathit{ID}}}$ and inserts the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
-
• Partial-Private-Key-Extract Query: At first, $\mathfrak{B}$ maintains a list ${L_{\mathit{PPK}}}=\{(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})\}$ in order to respond to these queries. When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PPK}}}$:
-
(1) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PPK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PPK}_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$, $\mathfrak{B}$ randomly picks ${r_{u}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculates\[ {\mathsf{PPK}_{\mathit{ID}}}=\big({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}}\big)=\bigg({\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{{J_{1}}(u)}{{F_{1}}(u)}}}{f_{1}^{{r_{u}}}}(\mathcal{U}),{\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{1}{{F_{1}}(u)}}}{g^{{r_{u}}}}\bigg).\]After that, $\mathfrak{B}$ answer to ${\mathfrak{A}_{I}}$ with ${\mathsf{PPK}_{\mathit{ID}}}$ and inserts the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ into ${L_{\mathit{PPK}}}$.
-
(3) Otherwise, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
• Time-Key-Update Query: When a tuple $(\mathit{ID},T)$ is supplied to this oracle, $\mathfrak{B}$ randomly selects ${r_{t}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculates the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{\alpha }}{f_{2}^{{r_{t}}}}(\mathcal{T}),{g^{{r_{t}}}})$.
-
• Secret-Value-Extract Query: When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with $s{v_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ makes a Public-Key-Extract Query with $\mathit{ID}$ to obtain $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$. After that, $\mathfrak{B}$ updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$ and answers to ${\mathfrak{A}_{I}}$ with $s{v_{\mathit{ID}}}$.
-
-
• Public-Key-Replace Query: When an identity $(\mathit{ID},{\mathsf{PK}^{\prime }_{\mathit{ID}}})$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ sets ${\mathsf{PK}_{\mathit{ID}}}={\mathsf{PK}^{\prime }_{\mathit{ID}}},s{v_{\mathit{ID}}}=s{v^{\prime }_{\mathit{ID}}}$ and then updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ first makes a Public-Key-Extract Query with $\mathit{ID}$ to obtain $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$. And then $\mathfrak{B}$ sets ${\mathsf{PK}_{\mathit{ID}}}={\mathsf{PK}^{\prime }_{\mathit{ID}}},s{v_{\mathit{ID}}}=s{v^{\prime }_{\mathit{ID}}}$. After that, $\mathfrak{B}$ updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
-
• RCL-Sign Query: When the tuple $(M,\mathit{ID},T)$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ retrieves the list ${L_{\mathit{PPK}}}$:
-
(i) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PPK}}}$, $\mathfrak{B}$ produces a signature $\sigma \gets \text{RCL-Sign}(s{v_{\mathit{ID}}},{\mathsf{PPK}_{\mathit{ID}}},M)$ by running the algorithm RCL-Sign.
-
(ii) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, $\mathfrak{B}$ makes a Partial-Private-Key-Extract Query to get $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$, and then produces a signature by running the algorithm RCL-Sign.
-
(iii) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, $\mathfrak{B}$ calculates ${F_{2}}(m)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$:
-
① If ${F_{2}}(m)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, $\mathfrak{B}$ selects $\lambda ,\mu ,\nu \in {\mathcal{Z}_{p}^{\ast }}$ and calculates\[\begin{aligned}{}\sigma =& ({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})\\ {} =& \bigg({\bigg[{g_{2}^{\alpha }}{f_{1}^{\lambda }}(\mathcal{U}){f_{2}^{\mu }}(\mathcal{T}){\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{{J_{3}}(m)}{{F_{2}}(m)}}}{f_{3}^{\nu }}(\mathcal{M}){g_{3}^{{x_{2}}}}\bigg]^{{x_{1}^{-1}}}},\\ {} & {g^{\lambda }},{g^{\mu }},{g_{1}^{-\frac{1}{{F_{2}}(m)}}}{g^{\nu }}\bigg)\\ {} =& \big({\big[{g_{2}^{a+\alpha }}{f_{1}^{\lambda }}(\mathcal{U}){f_{2}^{\mu }}(\mathcal{T}){f_{3}^{{\nu ^{\prime }}}}(\mathcal{M}){g_{3}^{{x_{2}}}}\big]^{{x_{1}^{-1}}}},{g^{\lambda }},{g^{\mu }},{g^{{\nu ^{\prime }}}}\big),\end{aligned}\]where ${\nu ^{\prime }}=\nu -\frac{a}{{F_{2}}(m)}$.
-
② If ${F_{2}}(m)=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
(iv) Otherwise, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ makes a Public-Key-Extract Query with $\mathit{ID}$ and then repeats step (1).
-
(1) ${E_{i}}$ ($i=1,\dots ,{q_{U}}$): ${F_{1}}({u_{i}})\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, in other words, $\mathfrak{B}$ does not discontinue in the ${\mathfrak{A}_{I}}$’s Partial-Private-Key-Extract Query.
-
(2) ${E^{\ast }}$: ${F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$.
-
(3) ${E^{\prime }_{i}}$ ($i=1,\dots ,{q_{M}}$): ${F_{2}}({m_{i}})\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, in other words, $\mathfrak{B}$ does not discontinue in the ${\mathfrak{A}_{I}}$’s RCL-Sign Query.
-
(4) ${E^{\prime \hspace{0.1667em}\ast }}$: ${F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$.
-
(5) ${E_{S}^{\ast }}$: ${F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p,{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$, in other words, ${\mathfrak{A}_{I}}$ produces a valid signature.
Theorem 2.
Theorem 3.
5 Performance Evaluation
Table 1
Scheme | Tsai et al. | Xiong and Qin | Huang et al. | Zheng et al. | Our scheme |
Security against ${\mathfrak{A}_{I}}$ | ✓ | × | ✓ | ✓ | ✓ |
Security against ${\mathfrak{A}_{\mathit{II}}}$ | × | ✓ | ✓ | ✓ | ✓ |
Security against ${\mathfrak{A}_{\mathit{ru}}}$ | ✓ | × | ✓ | × | ✓ |
Revocable | ✓ | ✓ | ✓ | ✓ | ✓ |
Security model | SM | ROM | ROM | ROM | SM |
Security assumption | CDH | CDH | CDH | CDH | CDH |
Table 2
Scheme | Signature size | Signing cost | Verification cost |
Tsai et al. | $4|\mathcal{G}|$ | $1SM+(\frac{{n_{m}}}{2}+1)M$ | $7P+(\frac{{n_{u}}+{n_{t}}+{n_{k}}+{n_{s}}+{n_{m}}}{5}+5)M$ |
Xiong and Qin | $3|\mathcal{G}|$ | $5SM$ | $5P+3H$ |
Hung et al. | $1|\mathcal{G}|$ | $2SM+2M$ | $4P+3H$ |
Zheng et al. | $6|\mathcal{G}|$ | $4SM+2M$ | $9P+6H+2SM+3E$ |
Our scheme | $4|\mathcal{G}|$ | $3SM+(\frac{{n_{m}}}{2}+1)M$ | $5P+(\frac{{n_{u}}+{n_{t}}+{n_{m}}}{3}+3)M$ |