The following four theorems deal with the four kinds of adversaries respectively. As will be seen, all these security reductions are perfectly tight and depend on no random oracles. These two reduction features show that both concepts of CBS and CLS are very closely related to each other.
Proof.
Let $\mathcal{C}$ denote the ${\Pi ^{\mathit{CL}}}$ challenger against ${\mathcal{B}^{I}}$. ${\mathcal{B}^{I}}$ mounts a Type I attack on ${\Pi ^{\mathit{CL}}}$ by simulating the challenger for ${\mathcal{A}^{I}}$ and using help from ${\mathcal{A}^{I}}$ as follows.
Initial phase for CBS game. ${\mathcal{B}^{I}}$ obtains from $\mathcal{C}$ the system parameter of ${\Pi ^{\mathit{CL}}}$ and extends it into the system parameter $\mathit{CB}.\mathit{param}$ of ${\Pi ^{\mathit{CB}}}$ as done in $\mathsf{CB}.\mathsf{Setup}$ of ${\Pi ^{\mathit{CB}}}$. ${\mathcal{B}^{I}}$ supplies $\mathit{CB}.\mathit{param}$ to ${\mathcal{A}^{I}}$.
Queries Phase for CBS game. When ${\mathcal{A}^{I}}$ enters the Queries phase for the CBS game, ${\mathcal{B}^{I}}$ accordingly enters the Queries phase of the CLS game. For the oracle queries from ${\mathcal{A}^{I}}$, ${\mathcal{B}^{I}}$ handles these queries as follows.
(1) ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})\to {\mathit{CB}.\mathit{PK}_{\mathit{ID}}}$. If the query $\mathit{ID}$ has been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, it will directly return the previous answer which is recorded in the list L. Otherwise, it does as follows. ${\mathcal{B}^{I}}$ chooses a random identity ${\mathsf{ID}^{\prime }}$ and obtains its original public key $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ through the oracle ${O^{\mathit{CL}.\mathit{CreateU}}}$. It sets $\mathsf{ID}=\mathit{ID}||{\mathit{CB}.\mathit{PK}_{{\mathsf{ID}^{\prime }}}}$ and requires the oracle ${O^{\mathit{CL}.\mathit{ReplacePK}}}$ to change the public key of $\mathsf{ID}$ into $\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$. In this case, the CBS original public key of ID is the CLS original public key of ${\mathsf{ID}^{\prime }}$. In other words, every original public key for ${\Pi ^{\mathit{CB}}}$ is related with a certain original public key for ${\Pi ^{\mathit{CL}}}$.
Additionally, to record the above operations for future use,
${\mathcal{B}^{I}}$ sets the original public key
and the current public key
and adds the tuple
to the initially empty list
L.
(2) ${O^{\mathit{CB}.\mathit{ReplacePK}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to \varnothing $. If $\mathit{ID}$ has not been submitted to the oracle ${O^{\mathit{CB}.\mathit{CreateU}}}$, ${\mathcal{B}^{I}}$ first makes the query ${O^{\mathit{CB}.\mathit{CreateU}}}(\mathit{ID})$ by himself before the following operations. Otherwise, it directly does the following. ${\mathcal{B}^{I}}$ sets $\mathsf{ID}=\mathit{ID}||\mathit{CB}.\mathit{PK}$, and sequentially makes two oracle queries ${O^{\mathit{CL}.\mathit{CreateU}}}(\mathsf{ID})$ and ${O^{\mathit{CL}.\mathit{ReplacePK}}}$ $(\mathsf{ID},\mathit{CB}.\mathit{PK})$ to change the public key value of $\mathsf{ID}$ into $\mathit{CB}.\mathit{PK}$.
Additionally, to record the above operation,
${\mathcal{B}^{I}}$ searches the relative tuple
and then changes the value of
$\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ into
$\mathit{CB}.\mathit{PK}$.
(3)
${O^{\mathit{CB}.\mathit{Corrupt}}}(\mathit{ID})\to {\mathit{CB}.\mathit{SK}_{\mathit{ID}}}$. Without loss of generality, we assume that
$\mathit{ID}$ has been submitted to the oracle
${O^{\mathit{CB}.\mathit{CreateU}}}$.
${\mathcal{B}^{I}}$ searches the corresponding tuple
in the list
L. Then it makes the oracle query
${O^{\mathit{CL}.\mathit{SecretV}}}(\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}})$ and relays this answer to the attacker
${\mathcal{A}^{I}}$. Here note
$\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$.
(4)
${O^{\mathit{CB}.\mathit{Cert}}}(\mathit{ID},\mathit{CB}.\mathit{PK})\to {\mathit{cert}_{\mathit{ID}}}$. Without loss of generality, we assume that the current public key
$\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}=\mathit{CB}.\mathit{PK}$ in the corresponding tuple
of the list
L.
${\mathcal{B}^{I}}$ sets
$\mathsf{ID}=\mathit{ID}||\mathit{CB}.\mathit{PK}$, makes the oracle query
${O^{\mathit{CL}.\mathit{PartialPK}}}(\mathsf{ID})$, and then relays the returned partial private key
${D_{\mathsf{ID}}}$ as the certificate for
${\mathcal{A}^{I}}$.
(5)
${O^{\mathit{CB}.\mathit{SSign}}}(\mathit{ID},m)\to \mathit{CB}.\sigma $. For a query
$(\mathit{ID},m)$, this oracle browses the list
L for the corresponding tuple
Then it sets
$\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$, makes the signing oracle query
${O^{\mathit{CL}.\mathit{SSign}}}(\mathsf{ID},m)$ and relays this answer to
${\mathcal{A}^{I}}$.
Output for CBS game. Now the attacker
${\mathcal{A}^{I}}$ returns its forgery
$({\mathit{ID}^{\ast }},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }})$. Without loss of generality, we assume that
${\mathcal{A}^{I}}$ has made the oracle query
${O^{\mathit{CB}.\mathit{CreateU}}}$ or the replacing public key oracle query for
${\mathit{ID}^{\ast }}$.
${\mathcal{B}^{I}}$ browses the list
L for the the corresponding tuple
and returns
$({\mathsf{ID}^{\ast }},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }})$ to its challenger
$\mathcal{C}$, where
Analysis. First, from the relations of
${\Pi ^{\mathit{CB}}}$ and
${\Pi ^{\mathit{CL}}}$, it can be easily or trivially seen that
${\mathcal{B}^{I}}$ perfectly simulates the game settings for
${\mathcal{A}^{I}}$ in the two phases of
Initial and
Queries. Second, if the forgery
$({\mathit{ID}^{\ast }},{m^{\ast }},\mathit{CB}.{\sigma ^{\ast }})$ is successful, i.e. this forgery satisfies the three additions:
then, by checking these two groups of three restrictions one by one (the above and the below), it easily follows that
$({\mathsf{ID}^{\ast }},{m^{\ast }},\mathit{CL}.{\sigma ^{\ast }})$ is also successful, i.e. this forgery satisfies that
Hence, the success probability of
${\mathcal{B}^{I}}$ is same to that of
${\mathcal{A}^{I}}$. Additionally, since what
${\mathcal{B}^{I}}$ mainly does in reduction is just issuing some relative queries to
$\mathcal{C}$, it is obvious that the time of
${\mathcal{B}^{I}}$ is almost equal to the time
t of
${\mathcal{A}^{I}}$. Hence we say that the running time of
${\mathcal{B}^{I}}$ is
$O(t)$. □
Proof.
Let $\mathcal{C}$ denote a ${\Pi ^{\mathit{CL}}}$ challenger against Type II adversary ${\mathcal{B}^{\mathit{II}}}$. ${\mathcal{B}^{\mathit{II}}}$ mounts a Type II attack on ${\Pi ^{\mathit{CL}}}$ using help from ${\mathcal{A}^{\mathit{II}}}$ as follows.
Initial for CBS game. How
${\mathcal{B}^{\mathit{II}}}$ communicates with
${\mathcal{A}^{\mathit{II}}}$ is the same to how
${\mathcal{B}^{I}}$ communicates with
${\mathcal{A}^{I}}$ in the above proof for Theorem
1, except that
${\mathcal{B}^{\mathit{II}}}$ additionally gets the master private key
$\mathit{CL}.\mathit{msk}$ and relays it to
${\mathcal{A}^{\mathit{II}}}$ as the master key
$\mathit{CB}.\mathit{msk}$ for
${\Pi ^{\mathit{CB}}}$.
Queries for CBS game. How
${\mathcal{B}^{\mathit{II}}}$ answers these queries from
${\mathcal{A}^{\mathit{II}}}$ is the same to how
${\mathcal{B}^{I}}$ simulates the oracles for
${\mathcal{A}^{I}}$ in the above proof for Theorem
1, except that
${\mathcal{A}^{\mathit{II}}}$ does not query the oracle
${O^{\mathit{CB}.\mathit{Cert}}}$.
Output for CBS game. How
${\mathcal{B}^{\mathit{II}}}$ generates the forged signature is the same to how
${\mathcal{B}^{I}}$ generates the forged signature in the above proof for Theorem
1. Of course, the forged signatures from
${\mathcal{B}^{I}}$ and
${\mathcal{B}^{\mathit{II}}}$ satisfy different conditions.
Analysis. This analysis can immediately follow from the analysis in the above proof of Theorem
1. Here, we only deal with the somewhat difficult part of the analysis. In particular, we will show how to get
from
where
By checking the simulation of the oracle
${O^{\mathit{CB}.\mathit{CreateU}}}$ by
${\mathcal{B}^{\mathit{II}}}$ for
${\mathcal{A}^{\mathit{II}}}$ (same to those in the proof of Theorem
1), the equation
$\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}={O^{\mathit{CB}.\mathit{CreateU}}}({\mathit{ID}^{\ast }})$ means that the original public key
$\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$ is equal to the current public key
$\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$, i.e. that
By checking the simulation of oracles
${O^{\mathit{CB}.\mathit{CreateU}}}$ and
${O^{\mathit{CB}.\mathit{ReplacePK}}}$, it can be seen that the CLS current public key
$\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ of
$\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ is always equal to the CBS current public key
$\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ of
$\mathit{ID}$. In particular, for
${\mathsf{ID}^{\ast }}={\mathit{ID}^{\ast }}||\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$, we have
Let the tuple
$({\mathit{ID}^{\ast }},{\mathsf{ID}^{\prime \ast }},\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}},\mathit{CB}.{\overline{\mathit{PK}}_{{\mathit{ID}^{\ast }}}})$ be the corresponding record in
L. Then by checking the simulation of the oracle
${O^{\mathit{CB}.\mathit{CreateU}}}$ again, it can be seen that the CBS original public key
$\mathit{CB}.{\widetilde{\mathit{PK}}_{{\mathit{ID}^{\ast }}}}$ is equal to the CLS original public key
$\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}$ of
${\mathsf{ID}^{\prime \ast }}$, i.e. that
By the above three equations, we can get
Hence, from
we can get that
By checking the oracle simulation process provided by
${\mathcal{B}^{\mathit{II}}}$ to
${\mathcal{A}^{\mathit{II}}}$ (same to those in the proof of Theorem
1), it can be seen that
${O^{\mathit{CL}.\mathit{SecretV}}}(\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}})$ is queried by
${\mathcal{B}^{\mathit{II}}}$ only when
${O^{\mathit{CB}.\mathit{Corrupt}}}({\mathit{ID}^{\ast }})$ is queried by
${\mathcal{A}^{\mathit{II}}}$. Then by the just proved equation
$\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}}=\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime \ast }}}}$, we prove that
${O^{\mathit{CL}.\mathit{SecretV}}}$ $(\mathit{CL}.{\overline{\mathit{PK}}_{{\mathsf{ID}^{\ast }}}})$ is queried by
${\mathcal{B}^{\mathit{II}}}$ only when
${O^{\mathit{CB}.\mathit{Corrupt}}}({\mathit{ID}^{\ast }})$ is queried by
${\mathcal{A}^{\mathit{II}}}$. In other words, from
we can get
□
Proof.
The proof for Theorem
3 is the same to that for Theorem
1, except the difference that the CBS normal signing oracle is simulated depending on the CLS normal signing oracle in this proof for Theorem
3, while the CBS super signing oracle is simulated depending on the CLS super signing oracle in this proof for Theorem
1. Now show how to simulate the CBS normal signing oracle using the CLS normal signing oracle.
For a normal signing query
${O^{\mathit{CB}.\mathit{NSign}}}(\mathit{ID},m)$, browse the list
L for the corresponding tuple
Set
$\mathsf{ID}=\mathit{ID}||\mathit{CB}.{\overline{\mathit{PK}}_{\mathit{ID}}}$ and make the signing oracle query
${O^{\mathit{CL}.\mathit{NSign}}}(\mathsf{ID},m)$ and relay this answer to
${\mathcal{A}^{I}}$. By checking the simulation of the oracle
${O^{\mathit{CB}.\mathit{CreateU}}}$, it can be seen that the original CBS public key
$\mathit{CB}.{\widetilde{\mathit{PK}}_{\mathit{ID}}}$ of
$\mathit{ID}$ is the original CLS public key
$\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ of
${\mathsf{ID}^{\prime }}$, and the original CLS public key
$\mathit{CL}.{\widetilde{\mathit{PK}}_{{\mathsf{ID}^{\prime }}}}$ of
${\mathsf{ID}^{\prime }}$ is the current CLS public key
$\mathit{CL}.{\overline{\mathit{PK}}_{\mathsf{ID}}}$ of
$\mathsf{ID}$. Hence, the query
$(\mathsf{ID},m)$ will not be rejected by the oracle
${O^{\mathit{CL}.\mathit{NSign}}}$. Hence, this proof can immediately follow Theorem
1. □