Practical Certificate-Less Infrastructure with Application in TLS

Abstract

We propose highly efficient certificate-less (CL) protocols for the infrastructure used by authenticated key exchange (AKE). The construction is based on elliptic curves (EC) without pairing, which means it can be easily supported by most industrial cryptography libraries on constrained devices. Compared with other pairing-free CL solutions, the new CL-AKE protocol enjoys the least number of scalar multiplications over EC groups. We use a unified game-based model to formalize the security of each protocol, while most previous works only assess the security against a list of attacks, provide informal theorems without proper modeling, or use separate models for protocols in different stages. We also present an efficient integration of the core protocols into the TLS cipher suites and a stand-alone implementation for constrained devices. The performance is evaluated on constrained devices in real-world settings, which further confirms the efficiency of our proposal.

1. Introduction

The authenticated key exchange protocols (AKE) based on conventional certificates are still widely deployed. Even in relatively new standards, such as TLS 1.3 [1], certificate-based cipher suites remains significant. Theoretical frameworks for evaluating protocol security, such as extensions of the Bellare–Rogaway model (BR) [2], eCK model [3] and universal composability (UC) [4], are usually used while assuming the existence of certificate-based public key infrastructure (PKI) [5,6].

However, the drawbacks of certificate-based infrastructure are also obvious. Ever-growing certificate revocation lists (CRL), floods of Online-Certificate States Protocol (OCSP) requests and the complicated logic of certificate chain verification may not fit into constrained devices [7] in the Internet of Things (IoT), where 50 KB RAM is already a luxury. Turning to pure symmetric key cryptography is not optimal in practice, either, as that introduces heterogeneity in the infrastructure, and scales poorly.

Therefore, exploring practical certificate-less AKE protocols (CL-AKE) is extremely meaningful.

CL-AKE solutions can use certificate-less public key encryption (CL-PKE) or signature (CL-SIG) to replace certificate chains. The syntax of the scheme and the types of adversaries have been defined for the first CL-PKE and CL-SIG by Al-Riyami and Paterson [8]. Unlike the key generation center (KGC) in identity-based or attribute-based cryptography (IBC, ABC), the KGC in CL-PKE can only compute partial private keys of users, so solutions based on CL-PKC do not suffer from the key escrow problem. The initial construction of CL-PKC in [8] is bilinear pairing based. Later, in 2007, Crampton et al. proposed a password-enabled and certificate-free grid security infrastructure (PECF-GSI) [9]. The protocols in PECF-GSI use bilinear pairing as heavily as the original Al-Ruyami–Paterson schemes. Other pairing-based certificate-less solutions in the last two decades [10,11,12,13,14,15] have experienced various improvement and trade-offs.

One of the major challenges for building certificate-less infrastructure is to optimize the efficiency of every protocol in its cryptographic core. As pointed out in [16], a bilinear pairing operation is about ten-times slower than a point multiplication on elliptic curves (EC), so it is necessary to avoid pairing and also to trim the redundant components, such as signature generation or decryption, off the CL-AKE main protocol.

Another critical challenge is establishing a unified security model for the two stages: user key registration and AKE. An adversary $\mathcal{A}$ against CL-PKE/SIG with key registration [8] has the power to corrupt users, corrupt KGC and register new public keys. However, whether $\mathcal{A}$ can see any message exchanged between an honest user and the KGC is undefined. In contrast, adversaries against AKE protocols have different powers in BR [2], eCK [3] and other game-based models [5]. These adversaries can tamper with messages and corrupt parties but may not be allowed to register new public keys. Although it has not been theoretically ruled out that messages in the key registration phase can threaten the AKE phase, most previous works on CL-AKE [15,17,18,19] used separate game-based models for the generation/registration of user key pairs (in a secure channel or out of band channel) and AKE protocol (in the public channel), or ignore the messages exchanged during the registration.

1.1. Our Contribution and Paper Outline

To meet the challenges mentioned above, we make the following contribution in this paper.

• We propose a practical cryptographic core of a certificate-less (CL) infrastructure, including user key registration and CL-AKE. The protocols are constructed from elliptic curves (EC) without pairing or any signature so that they can be easily supported by most industrial public key cryptography libraries for constrained devices. To the best of our knowledge, our AKE protocol also enjoys the optimal number of point multiplication over EC compared to other pairing-free solutions (see Table 1).

• We integrate CL-AKE into TLS ciphersuites [1]. The performance is compared with TLS-DHE with certificates in data volume and computation. We also deploy and test the slim implementation of CL-AKE without the TLS stack on constrained IoT devices. Subsequently, the evaluation confirms the real-world efficiency of our proposal.

• Our new provably secure CL signature scheme ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ with two-way public key reconstruction can be of independent interest.

After the introduction, we present the necessary notation and preliminaries in Section 2. As a starting point for building CL-AKE and proving its security in the game-based framework, we introduce a new certificate-less and paring-free signature scheme with two-way public key reconstruction in Section 3. The game-based AKE security model is presented in Section 4. The new certificate-less key registration, CL-AKE protocols and the security analysis can be found in Section 5. We present the integration to TLS and the evaluation in Section 6.

1.2. Technical Road Map

The cost of verifying a conventional certificate chain is proportional to the number of certificates on the chain. More specifically, to verify the end-level signature, a user has to verify the first-level signature with the public key in the root certificate and then the second-level signature with the public key of the first-level certificate. The verification continues until the signature on the end-level certificate is verified. For EC-based signatures, the verification usually involves a significant amount of point multiplication in an EC group.

A CL-SIG is designed to identify and utilize shortcuts during the verification process. Ideally, a user only has to verify the end-level public key with the root public key, usually the public key of the KGC. This verification can also be enforced implicitly through computation. If an end-level public key ${\mathsf{pk}}_j$ can be reconstructed by any honest user using the KGC’s public key ${\mathsf{pk}}_{\mathsf{KGC}}$ and the identifier ${\mathsf{PID}}_j$, then intuitively, the verification of ${\mathsf{pk}}_j$ is almost finished.

The shortcut we implement in CL-SIG is to replace the signature verification with a hash function, which is considerably more efficient. The hash function ${\mathsf{H}}_1\left(\right)$ maps binary strings to elements in an integer group. If a public key is an EC point that can be encoded as a binary string, and the corresponding private key is an integer in a group, ${\mathsf{H}}_1\left(\right)$ provides an efficient way to bind the public keys ${\mathsf{pk}}_j$, ${\mathsf{pk}}_{\mathsf{KGC}}$ and the identifier ${\mathsf{PID}}_j$ with the private key. Moreover, to make CL-SIG fully functional, there must be two alternatives to how ${\mathsf{pk}}_j$ can be reconstructed. One is through ${\mathsf{sk}}_j$, i.e., the way that only the key owner can take, and another one is through the use of ${\mathsf{H}}_1\left(\right)$, ${\mathsf{pk}}_{\mathsf{KGC}}$ and some additional information $B_j$, i.e., any user can do it. For details, we refer the reader to Figure 1 in Section 3.

We implement another shortcut to construct CL-AKE from CL-SIG. Instead of using the signing and verification algorithms in our CL-SIG, we keep only the public key reconstruction algorithms in the AKE. An AKE participant can reliably reconstruct its peer’s public key ${\mathsf{pk}}_j$ and then use ${\mathsf{pk}}_j$ with its own ephemeral key materials to derive the session keys. A message authenticate code is used to confirm the knowledge of all related secrets, replacing the expensive signature verification. For details, we refer the reader to Figure 2 in Section 5.

In summary, we replace as many public key operations (e.g., signature and point multiplication) with efficient symmetric essential operations (e.g., hash, message authentication code and pseudo-random function) as possible, while keeping the CL solution provably secure. The resulting CL-AKE enjoys forward secrecy due to the Gap Diffie–Hellman problem’s hardness and the new CL-SIG’s security.

1.3. Related Work

We review existing approaches to construct certificate-less AKE and authentication infrastructure, including identity-based cryptography, attribute-based cryptography, and CL-AKE with and without pairing.

1.3.1. IBC and ABC-Based CL Solutions

An important line of research is replacing certificate-based PKI with identity-based cryptography (IBC) [21]. In principle, the IBC public key is a user identity $\mathsf{pid}$ itself, and $\mathsf{pid}$ is embedded algebraically into the user’s secret key by KGC with its master secret key $\mathsf{msk}$. IBC eliminates certificates and simplifies the management of public keys greatly, but it suffers from the key escrow problem. More specifically, in the standard syntax of IBC, such as in [21,22], every user secret key is derived from its $\mathsf{pid}$ and a system-wide static $\mathsf{msk}$ of KGC. Once $\mathsf{msk}$ is compromised, the adversary can use $\mathsf{msk}$ to recover all previous user secret keys, destroying forward secrecy (FS). Attribute-based cryptography (ABC) [23] can be seen as a generalization of IBC. Instead of using one single identity, ABC uses a combination of multiple attributes to encrypt a message. However, the key escrow problem remains if any user secret key is derivable from $\mathsf{msk}$ and the attribute combinations alone. This KGC setting is preserved in various IBC-/ABC-based solutions [24,25], and some are flawed or without FS later [15,26].

1.3.2. CL-PKC and Pairing-Based Attempts

The notion of certificate-less public key cryptography (CL-PKC) was first formalized in 2003 by Al-Riyami and Paterson [8]. As the KGC in CL-PKC can only compute partial private keys for users, solutions based on CL-PKC do not inherently suffer from the key escrow problem. Later, Crampton et al. proposed a password-enabled and certificate-free grid security infrastructure (PECF-GSI) [9] in 2007. The protocols in PECF-GSI use bilinear pairing heavily as the original Al-Ruyami–Paterson schemes.

Various pairing-based attempts have been made for different trade-offs between security and efficiency. In 2012, Sanaa Taha et al. proposed certificate-less authentication key agreement (CL-AKA), a link-layer authentication and key agreement protocol based on CL-PKC, which does not consider ephemeral key leakage attacks [10]. Maity et al. proposed a novel certificate-less on-demand public key management (CL-PKM) protocol for self-organized MANETs [27]. Memon et al. proposed two authentication protocols based on Al-Ruyami–Paterson CL-PKC and IBE [11,12] in 2015. The security is analyzed with BAN-logic. Balakrishnan et al. proposed a practical email system based on CL-PKC with user authentication and key exchange in 2016, but the encryption of messages actually bears no forward secrecy when the receiver’s long-term keys are exposed [13]. Bala et al. proposed a secure key management and authentication protocol in 2017, making use of hybrid cryptography that involves both symmetric and CL-PKC but without formal security models [14]. Saeed et al. proposed a lightweight online/offline certificate-less signature (L-OOCLS) and a heterogeneous remote anonymous authentication protocol (HRAAP) for IoT applications in 2018 [15]. The L-OOCLS scheme is pairing-based and provably secure in random oracle model. The proposed HRAAP, however, cannot be proved secure in the BR or eCK model as the session key is directly used in handshake.

1.3.3. Pairing-Free CL-AKE

Pairin-free CL solutions have also been proposed. Song et al. [16] proposed a secure lightweight certificate-less authenticated key agreement (CL-AKA) for securing vehicle-to-vehicle (V2V) communication without using pairings. Unfortunately, the protocols need a large number of exponentiations in an integer group. Yang and Tan [17] proposed a CL-AKA that is provably secure in a dedicated model. He et al. [19] proposed efficient CL-AKA with security proofs in an extended eCK model dedicated to the key agreement part alone. Farouk et al. also introduced an efficient pairing-free CL-AKA protocol for grid computing environments [18] by extending the work of He et al. [19]. In 2018, KhanSafi et al. proposed an authentication framework for the message dissemination of toll payment information with a pairing-free CL-PKC system [20]. Unfortunately, there is no security proof provided in [19,20].

Defining a unified security model for each stage of CL-AKE is not a trivial task. On the one hand, the adversary for CL-PKE or CL-SIG in [8] has the power to corrupt users, corrupt the KGC or register new public keys, but cannot see any messages exchanged between the user and KGC. On the other hand, adversaries against authenticated key exchange (AKE) protocols, however, have different powers in BR [2], eCK [3] and other game-based models [5]. These adversaries can tamper with messages and corrupt parties (users) but cannot register new public keys. However, it has not been confirmed or denied whether messages in the key pair generation phase can threaten the AKE phase. Most previous works on CL-AKE [10,15,16,18,19] used separate models for the generation of user key pairs (in a secure channel or out-of-band channel) and AKE protocol (in public channels), or even ignore the messages exchanged during the key pair generation.

From 2021 till now, lattice-based (LBC) and isogeny-based cryptography have been introduced for post-quantum security, and new constructions have been proposed [28,29,30,31,32]. However, deploying LBC on constrained devices remains challenging now and in the near future, especially when facing the conflict between the large key/ciphertext size required by LBC and the limited RAM/storage on constrained devices [33].

2. Notation and Preliminaries

In this section, we introduce the necessary cryptographic building blocks of our solution.

2.1. Notations

We use $\kappa \in \mathbb{N}$ and $1^{\kappa }$ to denote the security parameter. Let $\left[n\right]=\{1,\dots ,n\}\subset \mathbb{N}$ be the set of integers from 1 to n. If S is a set, $a\stackrel{\$}{\leftarrow }S$ means sampling a uniformly random element a from S. If $\mathcal{A}\left(\right)$ is an algorithm, $m\leftarrow {\mathcal{A}}^{\mathcal{O}(·)}\left(x\right)$ and ${\mathcal{A}}^{\mathcal{O}(·)}\left(x\right)\stackrel{\$}{\to }m$ denote that $\mathcal{A}$ outputs m on input x with the help of another oracle $\mathcal{O}(·)$. $X\left|\right|Y$ means concatenating two binary strings X and Y. We use $Pr[E:A]$ to denote the probability that event E happens if action A is taken. Other notations will be introduced as needed.

2.2. Cryptographic Primitives and Hardness Assumptions

Message authentication code (MAC) is frequently used in AKE protocols for message integrity and can also work as a proof of the knowledge of the secret key.

Definition 1 

(Message Authentication Code, MAC). A MAC scheme $\mathsf{MAC}=(\mathsf{MAC}.\mathsf{Gen},$$\mathsf{MAC}.\mathsf{Tag},$$\mathsf{MAC}.\mathsf{Vfy})$ consists of three algorithms: $\mathsf{MAC}.\mathsf{Gen}$,$\mathsf{MAC}.\mathsf{Tag}$ and $\mathsf{MAC}.\mathsf{Vfy}$ described below.

• $\mathsf{MAC}.\mathsf{Gen}\left(1^{\kappa }\right)\stackrel{\$}{\to }\mathsf{k}$. The non-deterministic key generation algorithm $\mathsf{MAC}.\mathsf{Gen}\left(\right)$ takes the security parameter $1^{\kappa }$ as the input and outputs the secret key $\mathsf{k}$.

• $\mathsf{MAC}.\mathsf{Tag}(\mathsf{k},m)\stackrel{\$}{\to }\mathsf{mTag}$. The (non-deterministic) message tagging algorithm $\mathsf{MAC}.\mathsf{Tag}\left(\right)$ takes the secret key $\mathsf{mTag}$ and a message m as the input and outputs the authentication tag $\mathsf{mTag}$.

• $\mathsf{MAC}.\mathsf{Vfy}(\mathsf{k},m,\mathsf{mTag})=b$. The deterministic tag verification algorithm $\mathsf{MAC}.\mathsf{Vfy}\left(\right)$ takes the MAC secret key $\mathsf{k}$, a message m and a tag $\mathsf{mTag}$ as input and outputs a boolean value b. b is $\mathsf{TRUE}$ if $\mathsf{mTag}$ is a valid MAC tag on m.

Hash functions are used for obtaining a digest of the input. The digest can be of fixed length or in a finite domain.

Definition 2 

(Collision-resistant Hash Function). A hash function $H:\mathcal{M}\to \mathcal{D}$ is collision-resistant if there exists a negligible function ${ϵ}_{\mathsf{coll}}\left(\right)$ such that for any algorithm $\mathcal{A}$ with running time bounded by $\mathsf{poly}\left(\kappa \right)$, it holds that

$\begin{array}{c}\hfill Pr\left[\begin{array}{c}(m_0,m_1)\leftarrow \mathcal{A}(1^{\kappa },H):\\ m_0\ne m_1\bigwedge H\left(m_0\right)=H\left(m_1\right)\end{array}\right]\le {ϵ}_{\mathsf{coll}}\left(\kappa \right),\end{array}$

where $\mathcal{M}$ is the message space, and $\mathcal{D}$ is the hash image space.

Pseudo-random function (PRF) can be used for key derivation as in TLS 1.3 [1]. PRF ensures that the output looks random if the secret key is not leaked.

Definition 3 

(Pseudo-random function, PRF). A pseudo-random function $\mathbb{F}=(\mathsf{FKGen},\mathsf{PRF})$ consists of two algorithms, $\mathsf{FKGen}$ and $\mathsf{PRF}$, described below.

• $\mathsf{FKGen}\left(1^{\kappa }\right)\stackrel{\$}{\to }\mathsf{k}$. The non-deterministic key generation algorithm $\mathsf{FKGen}\left(\right)$ takes the security parameter $1^{\kappa }$ as the input and outputs the secret key $\mathsf{k}$.

• $\mathsf{PRF}(\mathsf{k},x)=y$. The PRF evaluation algorithm $\mathsf{PRF}\left(\right)$ takes as the input the secret key $\mathsf{k}$ and a value x in the domain and outputs an image y.

The Schnorr signature scheme can be seen as a general template for (EC-)group-based signature. The most critical operation is the scalar-point multiplication. Note that the verification algorithm $\mathsf{SIG}.\mathsf{Vfy}$ of Schnorr needs two point multiplication, one on the base point G and one on the non-base point $\mathsf{pk}$. In contrast, the signing only needs one base point multiplication. In practice, base point multiplication has been optimized for each EC group, so it is usually much quicker than non-base point multiplication.

Definition 4 

(Schnorr signature scheme). Let ${\mathsf{H}}_2\left(\right):{\{0,1\}}^{\kappa }\to {\mathbb{Z}}_q$ be a collision-resistant cryptographic hash function. The Schnorr signature scheme $\mathsf{SIG}$ consists of three algorithms $(\mathsf{SIG}.\mathsf{Gen}$, $\mathsf{SIG}.\mathsf{Sign}$, $\mathsf{SIG}.\mathsf{Vfy})$ described below.

• $\mathsf{SIG}.\mathsf{Gen}\left(1^{\kappa }\right)\stackrel{\$}{\to }(\mathsf{params},\mathsf{pk},\mathsf{sk})$. The non-deterministic key generation algorithm $\mathsf{SIG}.\mathsf{Gen}\left(\right)$ takes the security parameter $1^{\kappa }$ as the input and outputs the public parameters $\mathsf{params}$, the public key $\mathsf{pk}$ and the corresponding private key $\mathsf{sk}$, where $\mathsf{params}=(\mathbb{G},G,{\mathsf{H}}_2\left(\right))$, G is the generator of group $\mathbb{G}$ of large prime order q, $\mathsf{pk}=x·G$, $\mathsf{sk}=x$ with $x\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|}$, and $\mathsf{H}\left(\right)$ maps any bit string to an integer in ${\mathbb{Z}}_q$.

• $\mathsf{SIG}.\mathsf{Sign}(\mathsf{sk},m)\stackrel{\$}{\to }\sigma$. This signing algorithm $\mathsf{SIG}.\mathsf{Sign}\left(\right)$ takes the private key $\mathsf{sk}$ and the message m as the input. It chooses $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$, computes $R=r·G$, $e={\mathsf{H}}_2\left(R\right|\left|m\right)$, and $\beta =r+e·\mathsf{sk}$. It outputs the signature $\sigma =(R,\beta )$.

• $\mathsf{SIG}.\mathsf{Vfy}(\mathsf{pk},m,\sigma )=b$. This verification algorithm $\mathsf{RingVrfy}\left(\right)$ takes a public key $\mathsf{pk}$, a message m and a signature $\sigma =(R,\beta )$ as input. It first computes $e^{\prime }=$${\mathsf{H}}_2\left(R\right|\left|m\right)$, then outputs $\mathsf{TRUE}$ if $\beta ·G=R+e^{\prime }·\mathsf{pk}$, and $\mathsf{FALSE}$ otherwise.

We refer the reader to standard cryptography literature, such as [34], for the security definition of all the cryptographic primitives above and Diffie–Hellman key exchange (DH).

Definition 5 

(Discrete logarithm, DL). Let $\mathsf{GGen}\left(1^{\kappa }\right)$ be a group generation algorithm which outputs $\mathsf{params}=(\mathbb{G},G,q)$, where $\mathbb{G}$ is the description of a cyclic group, with G as its generator and q as its order. The discrete logarithm (DL) assumption with respect to $\mathbb{G}$ states that the following quantity is negligible for any probabilistic polynomial time (PPT) adversary $\mathcal{A}$.

$\begin{array}{c}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{DL}}:=Pr\left[Y=x·G:Y\stackrel{\$}{\leftarrow }\mathbb{G};x\leftarrow \mathcal{A}(\mathsf{params},Y)\right]\end{array}$

The proof of Schnorr’s security or schemes that use group elements with hash usually relies on the hardness of the Discrete logarithm problem above. For proving security of AKE, we need the gap computational Diffie–Hellman Problem ($\mathsf{GCDH}$), which is defined as: given public parameter $\mathsf{params}$ and $(a·G,b·G)$ for $a,b\in {\mathbb{Z}}_q$, compute the element Z = $\left(ab\right)·G$ with the help of a Decisional Diffie–Hellman Oracle ${\mathcal{O}}_{\mathsf{ddh}}(·)$, i.e., ${\mathcal{O}}_{\mathsf{ddh}}(·)$ answers whether a given quadruple $(G,a·G,b·G,c·G)$ has $ab\equiv cmodq$.

Definition 6 

(Hardness of $\mathsf{GCDH}$). $\mathsf{GCDH}$ is hard with respect to $\mathbb{G}$, if for any PPT adversary $\mathcal{A}$, the following quantity is negligible.

$\begin{array}{c}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{GCDH}}:=Pr\left[Z=\left(ab\right)·G:a,b\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q;Z\leftarrow {\mathcal{A}}^{{\mathcal{O}}_{\mathsf{ddh}}(·)}(\mathsf{params},a·G,b·G)\right]\end{array}$

In this section, we have reviewed the most relevant cryptographic primitives and hard problems. In the next section, we show how to construct an efficient CL-SIG from them.

3. New Certificate-Less Signature with Two-Way Reconstructable Public Key

We construct an extended certificate-less signature (CL-SIG) as the starting point. Although signing and verification are not used in our CL-AKE protocol, the security of ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ simplifies the argument in the game-based framework.

Definition 7 

(CL-SIG with Two-way Reconstructable PK). A certificate-less signature scheme with a two-way reconstructable public key (CL-SIG-TRK) is a tuple of seven algorithms $(\mathsf{Setup},$$\mathsf{PPKey}-\mathsf{Extract},$$\mathsf{Set}-\mathsf{Private}-\mathsf{Key},$$\mathsf{Set}-\mathsf{Secret}-\mathsf{Value},$$\mathsf{Set}-\mathsf{Public}-\mathsf{Key},$ $\mathsf{Sign},$$\mathsf{Verify}$, $\mathsf{Reconst}-\mathsf{Pk})$ defined as follows.

• $\mathsf{Setup}\left(1^{\kappa }\right)\stackrel{\$}{\to }\left(\mathsf{params},\mathsf{msk}\right)$. The (non-deterministic) algorithm $\mathsf{Setup}\left(\right)$ takes in the security parameter $1^{\kappa }$ and outputs the system parameters $\mathsf{params}$ and the master key $\mathsf{msk}$.

• $\mathsf{Set}-\mathsf{Secret}-\mathsf{Value}(\mathsf{params},{\mathsf{PID}}_i)\stackrel{\$}{\to }(a_i,A_i)$. This algorithm outputs party i’s secret value $a_i$ and auxiliary information $A_i$ on input $\mathsf{params}$ and the identifier ${\mathsf{PID}}_i$.

• $\mathsf{PPKey}-\mathsf{Extract}(\mathsf{params},\mathsf{msk},{\mathsf{PID}}_i,A_i)\stackrel{\$}{\to }(s_i,$$B_i)$. This partial key extraction algorithm outputs party i’s partial private key $s_i$ and the partial public key $B_i$ on input $\mathsf{params}$, $\mathsf{msk}$, ${\mathsf{PID}}_i$ and $A_i$.

• $\mathsf{Set}-\mathsf{Public}-\mathsf{Key}(\mathsf{params},s_i,B_i,a_i)\to {\mathsf{pk}}_i$. This algorithm takes as input $\mathsf{params}$, $s_i$, $a_i$ and $B_i$, and outputs i’s public key ${\mathsf{pk}}_i$.

• $\mathsf{Reconst}-\mathsf{Pk}(\mathsf{params},{\mathsf{PID}}_i,B_i)\to {\mathsf{pk}}_i$. This public key reconstruction algorithm takes as input $\mathsf{params}$, identity ${\mathsf{PID}}_i$ and the partial public key $B_i$, and it outputs the complete public key ${\mathsf{pk}}_i$ of party i.

• $\mathsf{Sign}(\mathsf{params},{\mathsf{sk}}_i,m)\stackrel{\$}{\to }\sigma$. This algorithm takes $\mathsf{params}$, the private signing key ${\mathsf{sk}}_i$ and a valid message m as input and outputs a signature σ.

• $\mathsf{Verify}(\mathsf{params},{\mathsf{pk}}_i,{\mathsf{PID}}_i,m,\sigma )\to b$. This algorithm outputs a bit value $b\in \{\mathsf{TRUE},$$\mathsf{FALSE}\}$ on input ${\mathsf{pk}}_i$, ${\mathsf{PID}}_i$, m and a signature σ. The value b is $\mathsf{TRUE}$ if σ is a valid signature on m with respect to ${\mathsf{pk}}_i$ and ${\mathsf{PID}}_i$.

Algorithms and outputs in dashed boxes are the extensions to the syntax in [8]. In the original syntax, ${\mathsf{pk}}_i$ can only be computed by its owner with $\mathsf{Set}-\mathsf{Public}-\mathsf{Key}\left(\right)$. The extension $\mathsf{Reconst}-\mathsf{Pk}(\mathsf{params},{\mathsf{PID}}_i,B_i)$, allows anyone who knows $B_i$ and the KGC’s pubic key to reconstruct ${\mathsf{pk}}_i$. Thus, there are two ways to reconstruct the public key, giving space for more efficiency improvement in the CL-AKE construction.

The security game for $\mathsf{CL}-\mathsf{SIG}$ in [8] is an EUF-CMA game extended with queries in Table 2. In principle, Type I adversaries can replace public keys but cannot get KGC’s private key, while Type II adversaries can have the KGC’s private key but cannot replace public keys.

More specifically, let ${\mathsf{PID}}_j$ be the challenged party and $(m^{*},{\sigma }^{*})$ the forgery. Besides being forbidden to ask $\mathsf{getKeyKGC}\left(\right)$, the restrictions on a Type I adversary $\mathcal{A}$ are:

• $\mathcal{A}$ cannot query $\mathsf{PPKey}-\mathsf{Extract}\left({\mathsf{PID}}_j\right)$.

• For any ${\mathsf{PID}}_i$, $\mathcal{A}$ cannot query $\mathsf{getPrivateKey}\left({\mathsf{PID}}_i\right)$, if it has previously queried $\mathsf{ReplacePK}($${\mathsf{PID}}_i,{\mathsf{pk}}_i^{\prime })$.

• $\mathcal{A}$ cannot query $\mathsf{ReplacePK}({\mathsf{PID}}_j,{\mathsf{pk}}_j^{\prime })$ before submitting forgery, if it has previously asked $\mathsf{PPKey}-\mathsf{Extract}\left({\mathsf{PID}}_j\right)$.

• $\mathcal{A}$ has not queried $\mathsf{SIG}.\mathsf{Sign}({\mathsf{PID}}_j,m^{*})$ before submitting $(m^{*},{\sigma }^{*})$.

Besides being forbidden to ask $\mathsf{ReplacePK}{({\mathsf{PID}}_i,{\mathsf{pk}}_i)}^{\prime }$ for any i, the restrictions on a Type II adversary $\mathcal{A}$ are:

• $\mathcal{A}$ cannot ask $\mathsf{getPrivateKey}\left({\mathsf{PID}}_j\right)$.

• $\mathcal{A}$ has not queried $\mathsf{SIG}.\mathsf{Sign}({\mathsf{PID}}_j,m^{*})$ before submitting $(m^{*},{\sigma }^{*})$.

Our new CL-SIG-TRK ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ is in Figure 1, where $\mathsf{SIG}$ is the Schnorr signature scheme in Definition 4. The security of ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ is summarized in Theorem 1. We still stick to the original syntax of $\mathsf{Verify}\left(\right)$. On the other hand, the extension, $\mathsf{Reconst}-\mathsf{Pk}\left(\right)$, also provides more flexibility in the verification, as a signature $({\sigma }^{\prime },B_i)$ can now be verified with itself and the KGC public key ${\mathsf{pk}}_{\mathsf{KGC}}$. We will show how a receiver of the partial public key $B_i$ can check and use it efficiently in AKE in Section 5.

Theorem 1 

(Security of ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$). If the discrete logarithm problem is hard with respect to group $\mathbb{G}$, then the CL-SIG-TRK scheme ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ is existentially unforgeable against chosen message attack (EUF-CMA) in the presence of Type I and Type II adversaries in the random oracle model, where Type I and Type II adversaries have access to queries defined in [8].

More specifically, if there exists $\mathcal{S}$ against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$, then there exist DL problem solvers $\mathcal{D}$ and $\mathcal{U}$, such that

(1) $\begin{array}{cc}\hfill {\mathsf{Adv}}_{\mathcal{S},\mathsf{CL}-\mathsf{SIG}}\le & 2d·{\mathsf{Adv}}_{\mathsf{SIG}}+\sqrt[4]{{(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}^6·{\mathsf{Adv}}_{\mathcal{D},\mathbb{G}}^{\mathsf{DLP}}}\hfill \\ \hfill & +\sqrt[4]{\frac{3·(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}{\left|\mathbb{G}\right|}}+\frac{d^2+q_{{\mathsf{H}}_1}^2+2·q_{{\mathsf{H}}_2}^2+2}{\left|\mathbb{G}\right|}\hfill \\ \hfill \mathit{with}{\mathsf{Adv}}_{\mathsf{SIG}}\le & \sqrt[2]{(q_{{\mathsf{H}}_2}+q_{\mathsf{SIG}}+1)·{\mathsf{Adv}}_{\mathcal{U},\mathbb{G}}^{\mathsf{DLP}}}\hfill \\ \hfill & +\sqrt[2]{\frac{(q_{{\mathsf{H}}_2}+q_{\mathsf{SIG}}+1)·(q_{\mathsf{SIG}}+1)}{\left|\mathbb{G}\right|}},\hfill \end{array}$

where ${\mathsf{Adv}}_{\mathcal{S},\mathsf{CL}-\mathsf{SIG}}$ is the advantage of any PPT adversary $\mathcal{S}$ against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$, ${\mathsf{Adv}}_{\mathcal{D},\mathbb{G}}^{\mathsf{DLP}}$ and ${\mathsf{Adv}}_{\mathcal{U},\mathbb{G}}^{\mathsf{DLP}}$ the advantage of $\mathcal{D}$ and $\mathcal{U}$ against $\mathsf{DLP}$, respectively, ${\mathsf{Adv}}_{\mathsf{SIG}}$ the advantage of any PPT adversary against Schnorr Signature $\mathsf{SIG}$, d the maximal number of clients with distinct identifiers, $q_{{\mathsf{H}}_1}$ the number of queries to random oracle ${\mathsf{H}}_1$ used in ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$, $q_{{\mathsf{H}}_2}$ the number of queries to random oracle ${\mathsf{H}}_2$ used in Schnorr $\mathsf{SIG}$, and $q_{\mathsf{SIG}}$ the number of signing queries.

We defer the proof of Theorem 1 to Appendix A, as it relies on the multiple forking lemmma in [35] and is rather technical. Intuitively, the multiple-forking lemma helps us connect the CL-SIG security to the hardness of $\mathsf{DLP}$ (Definition 5).

From Theorem 1, we can have Corollary 1, which is necessary for proving the security of the user key registration protocol (see Figure 3 in Section 5). The proof of Corollary 1 is quite straight forward, as unforgeable CL-SIG implies unforgeable and non-replaceable key pairs.

Corollary 1. 

If the advantages of Type I and Type II adversaries against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ are upper-bounded by ${\mathsf{Adv}}_{\mathsf{CL}-\mathsf{SIG}}$, the probability that any public-private key pair $({\mathsf{pk}}_i,{\mathsf{sk}}_i)$ is forgeable or replaceable by Type I and Type II adversaries is also upper-bounded by ${\mathsf{Adv}}_{\mathsf{CL}-\mathsf{SIG}}$.

Now, we have all the necessary tools to construct a CL-AKE with forward secrecy [1].

4. Game-Based Security Model for CL-AKE

In this section, we define a security model for certificate-less AKE protocols. We assume each participant communicates through a public network, and the adversary controls all the data traffic. This setting is formalized in the execution environment.

4.1. Protocol Execution Environment

Let $\mathcal{SK}\in {\{0,1\}}^{\kappa }$ denote the session key space, and $\mathcal{K}$ is the pre-shared key space. Let $\{P_1,\dots ,P_{\ell }\}$ be the set of all parties for ℓ$\in \mathbb{N}$, where a potential participant $P_i$ has a long-term pre-shared key $\mathsf{K}\in \mathcal{K}$ that corresponds to its identity i.

Each $P_i$ can have a polynomial number of process oracles $\left\{{\pi }_i^s\right\}$, where $s\in \left[d\right]$ is an index with $d\in \mathbb{N}$. A unique session identifier $\mathsf{sid}$ labels a protocol session between a client and a server instance. Moreover, we assume that besides the access to long-term secrets, such as private keys, each oracle ${\pi }_i^s$ maintains a list of independent internal state variables as described in the following list (Table 3).

The internal state of each oracle ${\pi }_i^s$ is initialized as (${\mathsf{PID}}_i^s$, ${\Phi }_i^s$, ${\mathsf{sid}}_i^s$, ${\mathsf{K}}_i^s$, ${\mathsf{Eph}}_i^s$) = (∅, ∅, ∅, ∅, ∅), where ∅ denotes the empty string. We assume that the session key is assigned to the variable ${\mathsf{K}}_i^s$ such that ${\mathsf{K}}_i^s\ne \varnothing$ if each oracle completes the execution with an internal state ${\Phi }_i^s=\mathtt{accept}$.

4.2. Adversary Model

An active adversary $\mathcal{A}$ can interact with the execution environment by issuing the queries below. Queries in the dashed boxes are our extensions to the eCK model [3].

• $\mathsf{Send}({\pi }_i^s,m)$: $\mathcal{A}$ can use this query to send any message m of its choice to oracle ${\pi }_i^s$. The oracle will respond according to the protocol specification and its internal state. If m consists of a special symbol ⊤ ($m=\top$), then ${\pi }_i^s$ will respond with the first protocol message.

• $\mathsf{RegCorruptParty}(i,{\mathsf{sk}}_i,{\mathsf{pk}}_i)$ This query allows $\mathcal{A}$ to register a new party with ${\mathsf{sk}}_i,{\mathsf{pk}}_i$ given by $\mathcal{A}$. If party i already exists, then upon this query, all long-term key pairs will be replaced with ${\mathsf{sk}}_i,{\mathsf{pk}}_i$, and existing randomness and session keys holding by any ${\pi }_i^s$ will be erased. In any case, party i has ${\tau }_i=0$ once this query has been issued.

• $\mathsf{Corrupt}\left(i\right)$: The oracle ${\pi }_i^s$ responds with the long-term private keys of party $P_i$. If $\mathsf{Corrupt}\left(i\right)$ is the $\tau$-th query issued by $\mathcal{A}$, then we say that $P_i$ is $\tau$-corrupted. For parties that have never been corrupted, we define $\tau :=\infty$.

• $\mathsf{RevealKey}\left({\pi }_i^s\right)$: Oracle ${\pi }_i^s$ responds to this query with the contents of variable ${\mathsf{K}}_i^s$ to $\mathcal{A}$. This query models the attacks that the exposure of a session key should not be damaging to other sessions. (Note that we have ${\mathsf{K}}^s\ne \varnothing$ if and only if ${\Phi }_i^s=\mathtt{accept}$.)

• $\mathsf{RevealEph}\left({\pi }_i^s\right)$: Oracle ${\pi }_i^s$ responds with the contents of the ephemeral secret stored in variable ${\mathsf{Eph}}_i^s$.

• $\mathsf{Test}\left({\pi }_i^s\right)$: This query can be made at most once. It does not model attacks but functions as a judgment for whether $\mathcal{A}$’s attacks are successful. Oracle ${\pi }_i^s$ handles this query as follows. If the oracle has state ${\Phi }_i^s\ne \mathtt{accept}$, then it returns a failure symbol ⊥. If the oracle does not have access to the corresponding type of keys, it returns some failure symbol ⊥.

  Otherwise, it flips a fair coin b, and it returns ${\mathsf{K}}_b$, where ${\mathsf{K}}_0$ is the real ${\mathsf{K}}_i^s$ and ${\mathsf{K}}_1\stackrel{\$}{\leftarrow }\mathcal{K}$.

• $\mathsf{TestForge}(i,{\mathsf{sk}}_i^{\prime },{\mathsf{pk}}_i^{\prime })$ This query judges the result of an attack, the goal of which is to forge a valid key pair. The output is 1 if $\mathsf{checkKey}({\mathsf{sk}}_i^{\prime },$${\mathsf{pk}}_i^{\prime })=\mathsf{TRUE}$ and 0 otherwise, where $\mathsf{checkKey}\left(\right)$ is parameterized by concrete protocols.

4.3. Security Definitions

Let ${\mathsf{sid}}_i^s$∈$\mathcal{SID}$ denote the session identifier received by oracle ${\pi }_i^s$, where $\mathcal{SID}\subseteq {\{0,1\}}^{\mathsf{poly}\left(\kappa \right)}$, i.e., a set of binary strings of length $\mathsf{poly}\left(\kappa \right)$.

Definition 8 

(Partnering Using $\mathsf{sid}$). In the protocol execution described above, we say that ${\pi }_i^s$ (with (${\mathsf{PID}}_i^s$, ${\Phi }_i^s$, ${\mathsf{sid}}_i^s$)) and ${\pi }_j^t$ (with (${\mathsf{PID}}_t^j$, ${\Phi }_j^t$, ${\mathsf{sid}}_j^t$)) are partnered if the following hold for both oracles: (1) ${\mathsf{PID}}_i^s$ = j and ${\mathsf{PID}}_j^t$ = i; (2) ${\Phi }_i^s$ = accept and ${\Phi }_j^t$ = accept; (3) ${\mathsf{sid}}_i^s$ = ${\mathsf{sid}}_j^t$;

Definition 9 

(Registration Freshness). Let $\mathsf{TestForge}({\mathsf{PID}}_i,{\mathsf{pk}}_i^{\prime },{\mathsf{sk}}_i^{\prime })$ be the ${\tau }_1$-th query. We call an oracle ${\pi }_i^s$${\tau }_1$-reg-fresh if all the following conditions hold for the adversary $\mathcal{A}$.

• (No direct corruption) i is τ-corrupt with $\tau >{\tau }_1$.

• (No corrupt-and-replace) If ${\mathsf{pk}}_i^{\prime }={\mathsf{pk}}_j$ and ${\mathsf{pk}}_j$ is an honest generated public key, then j is ${\tau }^{\prime }$-corrupt with ${\tau }^{\prime }>{\tau }_1$.

• (Type 1) If the first $\mathsf{RegCorruptParty}\left(i\right)$ is the τ-th query with $\tau <\infty$, then $\mathsf{Server}$ is ${\tau }_S$-corrupt, ${\tau }_S>{\tau }_1$, where $\mathsf{Server}$ is the KGC,

• (Type 2) If $\mathsf{Corrupt}\left(\mathsf{Server}\right)$ is the ${\tau }_S$-th query of $\mathcal{A}$ with ${\tau }_S<{\tau }_1$, then $\mathcal{A}$ has not made any $\mathsf{RegCorruptParty}\left(i\right)$ before ${\tau }_S$.

Here, we define the security of the key pair registration protocol.

Definition 10 

(Secure Key Pair Registration). Let the KGC be party $\mathsf{S}$. We say that a key pair registration protocol Π is $(t,ϵ)$-secure, if for all adversaries $\mathcal{A}$ with running time bounded by t, for some function $ϵ=ϵ\left(\kappa \right)$, it holds that if $\mathcal{A}$ has issued a $\mathsf{TestForge}({\mathsf{PID}}_i,·,·)$-query as the ${\tau }_1$-th query to oracle ${\pi }_i^s$, every client oracle ${\pi }_i^s$ is ${\tau }_1$-reg-fresh, then the advantage ${\mathsf{Adv}}_{reg}$ is bounded by a function ϵ. More specifically,

${\mathsf{Adv}}_{reg}=Pr[\mathsf{TestForge}(i,{\mathsf{pk}}_i^{\prime },{\mathsf{sk}}_i^{\prime })=1:(i,{\mathsf{pk}}_i^{\prime },{\mathsf{sk}}_i^{\prime })\stackrel{\$}{\leftarrow }{\mathcal{A}}^{\mathcal{O}(·)}\left(1^{\kappa }\right)]\le ϵ,$

where $\mathcal{O}=\left\{\mathsf{Send}\right(),\mathsf{RegCorruptParty}(),\mathsf{Corrupt}(\left)\right\}$.

Definition 11 

(Session Oracle Freshness). Let ${\pi }_i^s$ be an accepting oracle held by a party $P_i$ with intended partner $P_j$. Meanwhile, let ${\pi }_j^t$ be an oracle (if it exists), such that ${\pi }_i^s$ and ${\pi }_j^t$ are partnered. Then the oracle ${\pi }_i^s$ is said to be ${\tau }_0$-fresh, if it is ${\tau }_0$-reg-fresh, and when the adversary $\mathcal{A}$ issues its ${\tau }_0$-th query to ${\pi }_i^s$ and NONE of the following conditions holds:

• $\mathcal{A}$ has either made a $\mathsf{RevealKey}\left({\pi }_i^s\right)$ query or a $\mathsf{RevealKey}\left({\pi }_j^t\right)$ query, (if ${\pi }_j^t$ exists);

• $P_i$ is ${\tau }_i$-corrupted with ${\tau }_i\le {\tau }_0$;

• $P_j$ is ${\tau }_i$-corrupted with ${\tau }_j\le {\tau }_0$, (if ${\pi }_j^t$ exists);

• if ${\pi }_j^t$ exists, it is NOT ${\tau }_0$-reg-fresh;

• $\mathcal{A}$ has either made both $\mathsf{RevealEph}\left({\pi }_i^s\right)$ and $\mathsf{Corrupt}\left(i\right)$ queries, or both $\mathsf{RevealEph}\left({\pi }_j^t\right)$ and $\mathsf{Corrupt}\left(j\right)$ (if ${\pi }_j^t$ exists).

Definition 12 

(Secure Authenticated Key Exchange). We say that an AKE protocol Π is $(t,ϵ)$-secure, if for all adversaries $\mathcal{A}$ with running time t, for some probability $ϵ=ϵ\left(\kappa \right)$, it holds that: when $\mathcal{A}$ returns $b^{\prime }$ such that $\mathcal{A}$ has issued a $\mathsf{Test}\left(\right)$-query as the ${\tau }_0$-th query to oracle ${\pi }_i^s$, and the client oracle ${\pi }_i^s$ is ${\tau }_0$-fresh and has a synchronized partner throughout the security game, then the advantage ${\mathsf{Adv}}_{ake}$ is bounded by a function ϵ. More specifically,

${\mathsf{Adv}}_{ake}=\left|Pr[b=b^{\prime }:b^{\prime }\leftarrow {\mathsf{Adv}}^{\mathcal{O}(·)}\left(1^{\kappa }\right)]-1/2\right|\le ϵ,$

where $\mathcal{O}=\left\{\mathsf{Send}\right(),\mathsf{RegCorruptParty}(),\mathsf{Corrupt}(),\mathsf{RevealKey}(),$$\mathsf{RevealEph}\left(\right),\mathsf{Test}\left(\right)\}$.

The model that we have discussed so far provides a unified framework to evaluate the new CL-AKE protocols. The freshness ensures that we are focusing on real threats, and the queries can be combined to emulate attacks such as replay and man-in-the-middle.

5. New Protocols for Certificate-Less Infrastructure

The canonical way to transform a certificate-based AKE to CL-AKE is to replace the signature with a CL-SIG. However, the efficiency of the result is sub-optimal due to redundant computation and the extra demand for randomness. For example, to sign a message with our CL-SIG, an extra randomness is needed for the Schnorr component (line 4 in $\mathsf{Sign}(\mathsf{params},{\mathsf{sk}}_i,m)$ in Figure 1), and point multiplications are needed for verification.

Our new CL-AKE protocols save the participants from any signature verification. $\mathsf{Reconst}-\mathsf{Pk}(\mathsf{params},{\mathsf{PID}}_i,B_i)$ in ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ (Figure 1) ensures that once Alice has a reliable ${\mathsf{pk}}_{\mathsf{KGC}}$$\in \mathsf{params}$, its peer Bob has to use a correct secret key with respect to $B_i$ and ${\mathsf{pk}}_{\mathsf{KGC}}$ in AKE (Figure 2), leading to optimal performance.

5.1. Client Key Registration

Initially, a client is provisioned with the KGC’s public keys ${\mathsf{ek}}_{\mathsf{KGC}},{\mathsf{pk}}_{\mathsf{KGC}}$ and its own encryption/decryption key pairs. A client can then register its key pair to a KGC, which also knows the client’s encryption key. Details of our new client key pair generation protocol (Protocol 2) can be found in Figure 3. The security is summarized in the following theorem, where $\mathsf{checkKey}$ for $\mathsf{TestForge}$ is defined as checking the discrete log relation ${\mathsf{sk}}_i^{\prime }·G={\mathsf{pk}}_i^{\prime }$.

Theorem 2 

(Security of Protocol 2). Assuming an authenticated channel, if the public encryption scheme ${\Pi }_{pke}$ is $\mathrm{IND}-\mathrm{CCA}$ secure and discrete logarithm problem is hard with respect to group $\mathbb{G}$, then Protocol 2 is secure in the sense of Definition 10 in the random oracle model. More specifically, for any PPT adversary ${\mathcal{A}}_{reg}$,

(2)$\begin{array}{c}\hfill {\mathsf{Adv}}_{reg}\le \frac{{(d·\ell )}^2}{\left|\mathbb{G}\right|}+{ϵ}_{{\mathsf{H}}_1}+{ϵ}_{\mathsf{PKE}}+{ϵ}_{\mathsf{CL}-\mathsf{SIG}},\end{array}$

where d is the maximal number of parties, ℓ is the maximal number of oracles owned by each party, $\mathbb{G}$ is the group and the range of the hash function $\mathsf{H}\left(\right)$, ${ϵ}_{\mathsf{H}}$ is the advantage against the hash function $\mathsf{H}\left(\right)$, ${ϵ}_{\mathsf{PKE}}$ is the advantage against ${\Pi }_{\mathsf{PKE}}$ in the $\mathrm{IND}-\mathrm{CCA}$ game, and ${ϵ}_{\mathsf{CL}-\mathsf{SIG}}$ is the advantage against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$.

Proof. 

We use a sequence of games [36] to argue $\mathcal{A}$’s advantage against Protocol 2. The term ${\mathsf{Adv}}_i$ means $\mathcal{A}$’s advantage in ${\mathsf{Game}}_{\mathsf{i}}$.

${\mathsf{Game}}_{\mathsf{0}}$. This is the original game, so we have

(3)$\begin{array}{c}\hfill {\mathsf{Adv}}_{reg}={\mathsf{Adv}}_0\end{array}$

${\mathsf{Game}}_{\mathsf{1}}$. We add an abort rule in this game. We abort the game if any collision of honestly generated randomness or any hash collision happens. The abort probability can be bounded by the term $\frac{{(d·\ell )}^2}{\left|\mathbb{G}\right|}+{ϵ}_{{\mathsf{H}}_1}$. Therefore, we have

(4)$\begin{array}{c}\hfill {\mathsf{Adv}}_0\le {\mathsf{Adv}}_1+\frac{{(d·\ell )}^2}{\left|\mathbb{G}\right|}+{ϵ}_{{\mathsf{H}}_1}.\end{array}$

Once the collisions have all been eliminated, from Corollary 1 we can have

(5)$\begin{array}{cc}\hfill {\mathsf{Adv}}_1& \le {ϵ}_{\mathsf{CL}-\mathsf{SIG}}\hfill \end{array}$

By combining the (in)equalities (3)–(5), we have (2) in Theorem 2.    □

5.2. Certificate-Less Authenticated Key Exchange

The certificate-less authenticated key exchange protocol (CL-AKE) with explicit authentication is presented in Figure 2. The correctness is trivial, and the three non-base point multiplications are for computing ${\mathsf{pk}}_i$ (or ${\mathsf{pk}}_j$) and $\mathsf{ms}$. Let $\mathsf{H}:{\{0,1\}}^{*}\to {\mathbb{Z}}_{\left|\mathbb{G}\right|}$ be a hash function modeled as a random oracle that maps any binary string to an integer in group ${\mathbb{Z}}_{\left|\mathbb{G}\right|}$.

Theorem 3 

(Security of Protocol 3). If the key pair registration scheme is secure, the $\mathsf{GCDH}$ problem is hard, and $\mathsf{PRF}$ and $\mathsf{MAC}$ are secure, then Protocol 3 is secure in the sense of Definition 12 in the random oracle model. More specifically, for any PPT adversary ${\mathcal{A}}_{ake}$,

(6)$\begin{array}{cc}\hfill {\mathsf{Adv}}_{ake}\le & {\mathsf{Adv}}_{reg}+\frac{{(d·\ell )}^2}{\left|\mathbb{G}\right|}+{ϵ}_{{\mathsf{H}}_1}+{ϵ}_{\mathsf{H}}\hfill \\ \hfill & +{(d·\ell )}^2·({ϵ}_{\mathsf{PRF}}+{ϵ}_{\mathsf{MAC}}+4·{ϵ}_{\mathsf{GCDH}}),\hfill \end{array}$

where d is the maximal number of parties, ℓ the maximal number of oracles owned by each party, $\mathbb{G}$ is the group for $\mathsf{CL}-\mathsf{SIG}$, ${ϵ}_{{\mathsf{H}}_1},{ϵ}_{\mathsf{H}}$ the advantages against hash functions ${\mathsf{H}}_1\left(\right)$ and $\mathsf{H}\left(\right)$, ${ϵ}_{\mathsf{PRF}}$ the advantage against the pseudo-random function $\mathsf{PRF}$, ${ϵ}_{\mathsf{MAC}}$ the advantage against $\mathsf{MAC}$, and ${ϵ}_{\mathsf{GCDH}}$ the advantage against the $\mathsf{GCDH}$ problem.

Proof. 

We use another sequence of games to bound $\mathcal{A}$’s advantage against Protocol 3. The term ${\mathsf{Adv}}_i$ denotes $\mathcal{A}$’s advantage in ${\mathsf{Game}}_{\mathsf{i}}$.

${\mathsf{Game}}_{\mathsf{0}}$. This is the original game, so we have

(7)$\begin{array}{c}\hfill {\mathsf{Adv}}_{ake}={\mathsf{Adv}}_0\end{array}$

${\mathsf{Game}}_{\mathsf{1}}$. We add an abort rule in this game. If any collision of honestly generated randomness happens, or any hash collision happens, we abort the game. The abort probability can be bounded by the term $\frac{{(d·\ell )}^2}{\left|\mathcal{N}\right|}+{ϵ}_{{\mathsf{H}}_1}+{ϵ}_{\mathsf{H}}$, Therefore we have

(8)$\begin{array}{c}\hfill {\mathsf{Adv}}_0\le {\mathsf{Adv}}_1+\frac{{(d·\ell )}^2}{\left|\mathcal{N}\right|}+{ϵ}_{{\mathsf{H}}_1}+{ϵ}_{\mathsf{H}}.\end{array}$

${\mathsf{Game}}_{\mathsf{2}}$. We add an abort rule here. If $\mathcal{A}$ successfully forges a key pair and uses in the first message in the transportation phase, prior to the corruption of any party, abort the game. This probability is bounded by ${\mathsf{Adv}}_{reg}$. Thus, we have

(9)$\begin{array}{c}\hfill {\mathsf{Adv}}_1\le {\mathsf{Adv}}_2+{\mathsf{Adv}}_{reg}\end{array}$

${\mathsf{Game}}_{\mathsf{3}}$. We add an abort rule here. Let the challenger first guess $\mathcal{A}$’s target $(i,s)$ and its peer $(j,t)$. If the guess is wrong, abort the game. Thus, we have

(10)$\begin{array}{c}\hfill {\mathsf{Adv}}_2\le {(d·\ell )}^2·{\mathsf{Adv}}_3\end{array}$

${\mathsf{Game}}_{\mathsf{4}}$. We replace $\mathsf{PRF}\left(\right)$ with a random oracle $\mathsf{RF}\left(\right)$. Distinguishing ${\mathsf{Game}}_{\mathsf{4}}$ from ${\mathsf{Game}}_{\mathsf{3}}$ implies the existence of another adversary against the security of $\mathsf{PRF}\left(\right)$. We now have

(11)$\begin{array}{c}\hfill {\mathsf{Adv}}_3\le {\mathsf{Adv}}_4+{ϵ}_{\mathsf{PRF}}\end{array}$

${\mathsf{Game}}_{\mathsf{5}}$. We add an abort rule here. If $\mathcal{A}$ successfully forges an $\mathsf{MAC}.{\mathsf{Tag}}_1$ or $\mathsf{MAC}.{\mathsf{Tag}}_2$ in the second or the last message in the transportation phase, prior to the corruption of the target party or its peer, abort the game. This probability is again bounded by ${ϵ}_{\mathsf{MAC}}$. Thus, we have

(12)$\begin{array}{c}\hfill {\mathsf{Adv}}_4\le {\mathsf{Adv}}_5+{ϵ}_{\mathsf{MAC}}\end{array}$

We use ${\mathsf{fresh}}_{··}\left({\pi }_i^s\right)$ to mark four (sub-)cases when the freshness of ${\pi }_i^s$ still holds, i.e., $\mathcal{A}$’s attack is non-trivial.

• ${\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)$: $\mathcal{A}$ has never queried both $\mathsf{Corrupt}\left(i\right)$ and $\mathsf{Corrupt}\left(j\right)$.

• ${\mathsf{fresh}}_{EE}\left({\pi }_i^s\right)$: $\mathcal{A}$ has never queried both $\mathsf{RevealEph}\left({\pi }_i^s\right)$ and $\mathsf{RevealEph}\left({\pi }_j^t\right)$.

• ${\mathsf{fresh}}_{EL}\left({\pi }_i^s\right)$: $\mathcal{A}$ has never queried both $\mathsf{RevealEph}\left({\pi }_i^s\right)$ and $\mathsf{Corrupt}\left(j\right)$.

• ${\mathsf{fresh}}_{LE}\left({\pi }_i^s\right)$: $\mathcal{A}$ has never queried both $\mathsf{Corrupt}\left(i\right)$ and $\mathsf{RevealEph}\left({\pi }_j^t\right)$.

It is straightforward to see that if none of the cases exist in ${\mathsf{Game}}_{\mathsf{5}}$, then $\mathcal{A}$’s attack is trivial. Let ${\mathsf{Adv}}_5^{\mathsf{fresh}..}$ denote $\mathcal{A}$’s advantage in ${\mathsf{Game}}_{\mathsf{5}}$ when ${\mathsf{fresh}}_{··}\left({\pi }_i^s\right)$ holds. We have from the union bound

(13)$\begin{array}{c}\hfill {\mathsf{Adv}}_5\le {\mathsf{Adv}}_5^{{\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)}+{\mathsf{Adv}}_5^{{\mathsf{fresh}}_{EL}\left({\pi }_i^s\right)}+{\mathsf{Adv}}_5^{{\mathsf{fresh}}_{LE}\left({\pi }_i^s\right)}+{\mathsf{Adv}}_5^{{\mathsf{fresh}}_{EE}\left({\pi }_i^s\right)}\end{array}$

We rewrite the computation of $\mathsf{ms}$ as

(14)

Observe that each of the four products on the right-hand side of (14) corresponds to one of the four fresh cases, and each fresh case allows a different strategy of embedding the $\mathsf{GCDH}$. Let ${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)}$ ${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{EE}\left({\pi }_i^s\right)}$ ${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{EL}\left({\pi }_i^s\right)}$ and ${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{LE}\left({\pi }_i^s\right)}$ be the game ${\mathsf{Game}}_{\mathsf{5}}$ when one of the four cases exist.

${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)}$. We claim that

(15)$\begin{array}{cc}\hfill & {\mathsf{Adv}}_5^{{\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)}\le {ϵ}_{\mathsf{GCDH}}\hfill \end{array}$

We show how to construct a $\mathsf{GCDH}$ solver $\mathcal{S}$ to prove (15). $\mathcal{S}$ chooses a random value ${\mathsf{K}}^{*}$ in the key space and program the random oracle $\mathsf{PRF}(·,W||"\mathsf{MAC}")$ with ${\mathsf{K}}^{*}$, where $W=B_i\left|\right|B_j\left|\right|{\mathsf{PID}}_i\left|\right|{\mathsf{PID}}_j\left|\right|X\left|\right|Y\left|\right|{\mathsf{params}}_i$ and all the variables are from the target session. Let $(\mathbb{G},A,B)$ be $\mathcal{S}$’s $\mathsf{GCDH}$ challenge. $\mathcal{S}$ sets $\underline{({\mathsf{pk}}_i,{\mathsf{pk}}_j)}$ to $(A,B)$, aborts the game when

• $\mathcal{A}$ queries the random oracle with a $\mathsf{ms}$ at the place of any PRF queries,

• and ${\mathcal{O}}_{DDH}(g,A,B,Z)=\mathsf{TRUE}$ where $Z=\mathsf{ms}-\mathsf{H}{\left(W\right)}^{2}x·Y-\mathsf{H}\left(W\right)x·{\mathsf{pk}}_j-\mathsf{H}\left(W\right)y·{\mathsf{pk}}_i$.

In other words, if the game aborts, $\mathcal{S}$ finds a solution to the $\mathsf{GCDH}$ instance.

As ${\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)$ guarantees that neither ${\mathsf{sk}}_i$ nor ${\mathsf{sk}}_j$ would be asked by $\mathcal{A}$, $\mathcal{S}$ can generate all other randomness including $(x,y)$ freely and simulate all the other $\mathsf{Corrupt}\left(\right)$, $\mathsf{RevealEph}\left(\right)$ and $\mathsf{RevealKey}\left(\right)$ queries perfectly for $\mathcal{A}$. The probability of aborting the game is thus upper bounded by ${ϵ}_{\mathsf{GCDH}}$.

On the other hand, if ${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{LL}\left({\pi }_i^s\right)}$ simulated by $\mathcal{S}$ does not abort, then $\mathcal{A}$ has never queried the random oracle with the correct value to compute the target session key. Due to the property of random oracle, $\mathcal{A}$ has zero advantage in distinguishing the random key ${\mathsf{K}}^{*}$.

${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{EE}\left({\pi }_i^s\right)}$. $\mathcal{S}$ embeds $(A,B)$ into $(X,Y)$, and aborts when ${\mathcal{O}}_{DDH}(g,A,$$B,Z)=\mathsf{TRUE}$ where $Z=\mathsf{H}{\left(W\right)}^{-2}·(\mathsf{ms}-{\mathsf{sk}}_j·{\mathsf{pk}}_i-{\mathsf{sk}}_j\mathsf{H}\left(W\right)·X-{\mathsf{sk}}_i\mathsf{H}\left(W\right)·Y)$. This abort means a $\mathsf{GCDH}$ solution of $(A,B)$ has been found.

(16)$\begin{array}{c}\hfill {\mathsf{Adv}}_5^{{\mathsf{fresh}}_{EE}\left({\pi }_i^s\right)}\le {ϵ}_{\mathsf{GCDH}}\end{array}$

${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{EL}\left({\pi }_i^s\right)}$. $\mathcal{S}$ embeds $(A,B)$ into $({\mathsf{pk}}_j,X)$, and aborts when ${\mathcal{O}}_{DDH}(g,A,$$B,Z)=\mathsf{TRUE}$ where $Z=\mathsf{H}{\left(W\right)}^{-1}·(\mathsf{ms}-{\mathsf{sk}}_i·{\mathsf{pk}}_j-\mathsf{H}{\left(W\right)}^{2}y·X-{\mathsf{sk}}_i\mathsf{H}\left(W\right)·Y)$. This abort means a $\mathsf{GCDH}$ solution of $(A,B)$ has been found.

(17)$\begin{array}{c}\hfill {\mathsf{Adv}}_5^{{\mathsf{fresh}}_{EL}\left({\pi }_i^s\right)}\le {ϵ}_{\mathsf{GCDH}}\end{array}$

${\mathsf{Game}}_{\mathsf{5}}^{{\mathsf{fresh}}_{LE}\left({\pi }_i^s\right)}$. Similar to the previous case, if $\mathcal{S}$ embeds $(A,B)$ into $(Y,{\mathsf{pk}}_i)$, it can also find a $\mathsf{GCDH}$ solution when the game aborts.

(18)$\begin{array}{c}\hfill {\mathsf{Adv}}_5^{{\mathsf{fresh}}_{LE}\left({\pi }_i^s\right)}\le {ϵ}_{\mathsf{GCDH}}\end{array}$

Now, we can conclude from the arguments above and (13) that

(19)$\begin{array}{c}\hfill {\mathsf{Adv}}_5\le 4·{ϵ}_{\mathsf{GCDH}}.\end{array}$

By combining the (in)equalities (7)–(19), we have proved (6).    □

6. Integration into TLS and Performance Evaluation

Since our solution is already asymptotically better than other provably secure ones (see Table 1), we only demonstrate its performance in real-world scenarios and compare with the original certificate-based TLS (TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256, henceforth TLS-DHE).

The two standard ways to integrate the Protocol 3 in Figure 2 are via the certificate type RawPublicKey [37] and via the PSK identities [38] (We merged mTag1 and mTag2 with the finish-messages in the TLS handshake.). When RawPublicKey is chosen, the TLS server sends ${\mathbf{M}}_{\mathbf{1}}$ in the (Server) Certificate message, and the TLS client sends ${\mathbf{M}}_{\mathbf{2}}$ in the (Client) Certificate message. When PSK identities is used, the TLS server sends ${\mathbf{M}}_{\mathbf{1}}$ in the ServerkeyExchange.psk_identity_hint field, and the TLS client sends ${\mathbf{M}}_{\mathbf{2}}$ in the ClientKeyExchange.psk_identity field.

6.1. Set Up

Opting for the PSK identifiers, we insert the encoded $\mathsf{PID}$, the EC group ID and auxiliary information into it. We implement Protocol 3 with the BouncyCastle library and OpenSSL (https://www.bouncycastle.org/ and https://www.openssl.org/, accessed on 8 September 2022) on the server, which runs Ubuntu 18.04.6 on 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80 GHz CPU with 16.0 GB RAM. Each client node is emulated with mbedTLS (https://github.com/Mbed-TLS/mbedtls) (accessed on 9 September 2022) on a STM32F107VCT6 (https://www.st.com/resource/en/datasheet/stm32f107vc.pdf) (accessed on 4 December 2023) board with 32-bit MCU and 64/256 KB Flash, which corresponds to a Class 2 constrained device [7]. For a fair comparison, we use the widely deployed EC curve NIST P-256 and a two-level certificate chain, i.e., the direct issuer of TLS certificates is trusted by both TLS peers.

6.2. Results

6.2.1. Computational Cost

Besides using absolute time, we measured the time consumption for the elementary functions with the base-point multiplication as a unit. We consider only the point multiplication, signature signing and verification to be elementary operations. Here, the cost of point addition, arithmetic operations and hash functions are ignored, as they are relatively negligible compared to the above operations.

We use ${\mathsf{t}}_{\mathsf{BPM}}$ to denote the time for computing one base point multiplication (BPM) and use ${\mathsf{t}}_{\mathsf{BPM}}$ as a unit.

• A non-base point multiplication (PM) costs 6 ${\mathsf{t}}_{\mathsf{BPM}}$. This difference comes from the optimization of base-point multiplication [39].

• A signing costs 2.5 ${\mathsf{t}}_{\mathsf{BPM}}$ and verification 8.5 ${\mathsf{t}}_{\mathsf{BPM}}$. This 6 ${\mathsf{t}}_{\mathsf{BPM}}$ difference comes exactly from the extra non-base point multiplication in the verification. Signing with ECDSA also needs extra operations in the integer group, so it is slower (2.5 ${\mathsf{t}}_{\mathsf{BPM}}$) than a simple base-point multiplication (1 ${\mathsf{t}}_{\mathsf{BPM}}$).

While the TLS with certificates needs $26.5 {\mathsf{t}}_{\mathsf{BPM}}$, this work needs only $19 {\mathsf{t}}_{\mathsf{BPM}}$, saving at least 28% local computation time for the cryptographic core. Details are provided in Table 4.

6.2.2. Communication Cost

In this part, we compare the communication cost between this work and TLS-DHE. We measure the communicated messages using the tool Wireshark (https://www.wireshark.org/) (accessed on 8 September 2022), and count the size of all TLS handshake messages (see Table 5). For one full handshake, TLS-DHE consumes about 2430 bytes, while this work consumes only about 840 bytes. That means our work reduces 65% of the payload.

6.2.3. Resource Consumption on the Constrained Client

The execution time is 2.09 s for Protocol 3 in the LAN setting (1 Gbps with 0.1 ms latency), saving 70% of the time compared to TLS-DHE with certificates.

Meanwhile, it is 13.8 KB for TLS-DHE, the maximal RAM consumption during key registration and Protocol 3 is 4.09 KB, making a considerable 70% reduction in RAM consumption. Whereas TLS-DHE consumes more than 150 KB, the binary of Protocol 3 consumes 48.32 KB in maximum in flash, i.e., a good reduction of 67% in storage can also be seen.

7. Conclusions and Future Work

Without using bilinear pairings, we construct practical certificate-less signature, key registration, and authenticated key exchange protocols with integration to TLS. To the best of our knowledge, our AKE protocols have the lowest number of point-multiplication among DH-based CL-AKE, while enjoying strong security in the eCK model.

We believe that the construction of practical post-quantum-secure CL-AKE can be pursued as meaningful future work, to design general compilers that can transform CL-SIG with two-way-reconstructable PK to CL-AKE, and to analyze the possible equivalence of game-based and universally composable security formalization [4].

Author Contributions

Conceptualization, L.D., Y.L. and L.L.; methodology, L.D., Y.L. and L.L.; software, L.L.; formal analysis, L.D. and Y.L.; data curation, L.L.; writing—original draft preparation, L.D.; writing—review and editing, Y.L. and L.L.; visualization, L.D. and L.L. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. Construction 1, the pairing-free CL-SIG-TRK construction [Forumla omitted. See PDF.]. Capital letters, such as A, B and T, represent EC group elements (points). Lowercase letters, such as a, b and s, represent integers in [Forumla omitted. See PDF.].

Figure 2. Protocol 3: Three-pass certificate-less AKE with mutual authentication.

Figure 3. Protocol 2, client key pair registration with [Forumla omitted. See PDF.].

Table 1

Comparison with other provably secure pairing-free (EC)DH-based CL-AKE. Proposals without security models, such as [18,20], are not included. BPM: base-point multiplication on each side; PM: non-base-point multiplication on each side.

	# BPM	# PM	Security Model
Yang and Tan [17]	1	10	dedicated, game-based, stage-separated
Song et al. [16]	1	7	dedicated, game-based, stage-separated
He et al. [19]	1	4	eCK for CL-AKA only
This work	1	3	extended eCK for AKE and key reg.

Table 2

Queries (adversary’s ability) in the $\mathsf{CL}-\mathsf{SIG}$ security game [8]. Notations are adapted to ours.

Query	Description
$\mathsf{PPKey}-\mathsf{Extract}\left({\mathsf{PID}}_i\right)$	return partial private/public keys
$\mathsf{ReplacePK}({\mathsf{PID}}_i,{\mathsf{pk}}_i^{\prime })$	replace the public key of ${\mathsf{PID}}_i$ with ${\mathsf{pk}}_i^{\prime }$
$\mathsf{getPrivateKey}\left({\mathsf{PID}}_i\right)$	get the private key of ${\mathsf{PID}}_i$
$\mathsf{getKeyKGC}\left(\right)$	return $\mathsf{msk}$
$\mathsf{SIG}.\mathsf{Sign}({\mathsf{PID}}_i,m)$	get ${\mathsf{PID}}_i$’s signature on m

Table 3

Internal states of oracles.

Variable	Description
${\mathsf{PID}}_i^s$	records the identities $\left\{j\right\}\subset \{1,\dots ,\ell \}$ of intended communication partners $\left\{P_j\right\}$
${\Phi }_i^s$	denotes ${\Phi }_i^s\in \{\mathtt{accept},\mathtt{reject}\}$
${\mathsf{sid}}_i^s$	denotes the session identifiers
${\mathsf{K}}_i^s$	records the session key ${\mathsf{K}}_i^s\in \mathcal{K}$
${\mathsf{Eph}}_i^s$	records the ephemeral secret used to compute the session key ${\mathsf{K}}_i^s$

Table 4

Computation cost. BPM: base-point scalar multiplication, PM: point scalar multiplication. Columns 2 to 4: number of operations on each side.

	BPM (1 ${\mathsf{t}}_{\mathsf{BPM}}$)	PM (6 ${\mathsf{t}}_{\mathsf{BPM}}$)	Sign (2.5 ${\mathsf{t}}_{\mathsf{BPM}}$)	Vrfy (8.5 ${\mathsf{t}}_{\mathsf{BPM}}$)	Total
TLS-DHE.	1	1	1	2	26.5 ${\mathsf{t}}_{\mathsf{BPM}}$
Protocol 3 TLS	1	3	0	0	19 ${\mathsf{t}}_{\mathsf{BPM}}$

Table 5

Communication cost comparison in bytes. ${}^{*}:$ Server Response includes Server Hello, Server Certificate, Server Key Exchange, Certificate Request and Server Hello Done.

Operation	Data${}_{\mathsf{TLS}-\mathsf{DHE}}$	Data${}_{\mathsf{Protocol}\mathsf{3}}$
Client Hello	309	106
Server Response ${}^{*}$	1092	421
Client Certificate	733	0
Client Key Exchange	119	266
Certificate Verify	128	0
Change Cipher Spec	50	50
Total	≈2430	≈840 ($35\%$)

Appendix A. Proof of EUF-CMA Security of ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$

Appendix A.1. Multiple-Forking Lemma

We recall the multiple-forking lemma introduced by Boldyreva et al. [35].

Lemma A1 

(Multiple-Forking Lemma, Lemma C.5 in [35]). Let $\alpha \in {\mathbb{Z}}^{+}$ be a fixed integer. Let $n\ge 1$ be an odd integer and S a set with no less than two elements. Let $\mathcal{B}\left(\right):{\{0,1\}}^{*}\times S^{\alpha }\to {\mathbb{Z}}^2\times {\{0,1\}}^{*}$, $(x,(s_1,\cdots ,s_{\alpha }))\mapsto (I,J,\Sigma )$ be a randomized algorithm, where I and J are integers with $0\le J\le I\le \alpha$. The multiple-forking algorithm ${\mathcal{MF}}_{\mathcal{B},n}$ associated to $\mathcal{B}$ and n is defined as in Figure A1 where $x\in {\{0,1\}}^{*}$.

Let $\mathsf{IGen}$ be a non-deterministic algorithm that takes no input and returns a binary string. Let $$\begin{array}{cc}\hfill \mathsf{accMf}=Pr[& I\ge 1,J\ge 1:x\stackrel{\$}{\leftarrow }\mathsf{IGen};(s_1,\cdots ,s_{\alpha })\stackrel{\$}{\leftarrow }{S}^{\alpha };\hfill \\ \hfill & (I,J,\Sigma )\stackrel{\$}{\leftarrow }\mathcal{B}\left((x,(s_1,\cdots ,s_{\alpha }))\right);]\hfill \\ \hfill \mathsf{frkMf}=Pr[& b=1:x\stackrel{\$}{\leftarrow }\mathsf{IGen};(b,\mathsf{RessultMF})\stackrel{\$}{\leftarrow }{\mathcal{MF}}_{\mathcal{B},n}\left(x\right)]\hfill \end{array}$$

Then (A1) $$\begin{array}{cc}\hfill \mathsf{frkMf}& \ge \mathsf{accMf}·\left(\frac{{\mathsf{accMf}}^n}{{\alpha }^{2n}}-\frac{n}{\left|S\right|}\right)\hfill \end{array}$$ (A2) $$\begin{array}{cc}\hfill \mathsf{accMf}& \le \sqrt[n+1]{{\alpha }^{2n}·\mathsf{frkMf}}+\sqrt[n+1]{\frac{n·{\alpha }^{2n}}{\left|S\right|}}\hfill \end{array}$$

This lemma allows forks to happen at two distinct positions I and J. When $n=1$, this lemma collapses to the generalized forking lemma [40], allowing forking at only one position.

Figure A1. The multiple-forking algorithm [Forumla omitted. See PDF.] associated to [Forumla omitted. See PDF.] in Lemma A1. We use [Forumla omitted. See PDF.] in the proof of Lemma A2.

Appendix A.2. Proof of Theorem 1

Here we prove Theorem 1 via proving Lemma A2 and Lemma A3. We use $\mathsf{CL}-\mathsf{SIG}$ adversaries to constructing DLP solvers and analyze with Lemma A1.

Lemma A2 

(${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ security against Type 1 adversary). If there exists an efficient Type I adversary against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ with advantage ${\mathsf{Adv}}_{\mathsf{CL}-\mathsf{SIG},1}$, then there exist a forger $\mathcal{S}$ with advantage ${\mathsf{Adv}}_{\mathsf{SIG}}$ against the Schnorr signature scheme, and a DLP solver $\mathcal{D}$ with advantage ${\mathsf{Adv}}_{\mathsf{DLP}}$ such that (A3)$$\begin{array}{cc}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{CL}-\mathsf{SIG},1}\le & d·{\mathsf{Adv}}_{\mathsf{SIG}}+\sqrt[4]{{(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}^6·{\mathsf{Adv}}_{\mathcal{D},\mathbb{G}}^{\mathsf{DLP}}}\hfill \\ \hfill & +\sqrt[4]{\frac{3·(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}{\left|\mathbb{G}\right|}}+\frac{d^2+q_{{\mathsf{H}}_1}^2+2·q_{{\mathsf{H}}_2}^2+2}{\left|\mathbb{G}\right|},\hfill \end{array}$$where d is the maximal number of clients with distinct identifiers, $q_{{\mathsf{H}}_1}$ and $q_{{\mathsf{H}}_2}$ are number of queries to random oracle ${\mathsf{H}}_1$ and ${\mathsf{H}}_2$, respectively.

Proof. 

We define the following events in the CL-SIG security experiments against a Type I adversaries $\mathcal{A}$, i.e., with $\mathsf{ReplacePK}\left(\right)$ but without KGC corruption. Let ${\mathsf{Adv}}_{\mathcal{A},I,\mathsf{CL}-\mathsf{SIG}}$ be the advantage of $\mathcal{A}$.

• ${\mathcal{E}}_1$: $\mathcal{A}$ outputs a forgery $(m,{\mathsf{pk}}_i,{\mathsf{PID}}_i,\sigma )$, where $\mathsf{Verify}(\mathsf{params},{\mathsf{pk}}_i,{\mathsf{PID}}_i,\sigma )=\mathsf{TRUE}$, ${\mathsf{pk}}_i$ has not been replaced, and m has not been queried to the signing oracle $\mathcal{O}({\mathsf{sk}}_i,·)$.

• ${\mathcal{E}}_2$: $\mathcal{A}$ outputs a forgery $(m,{\mathsf{pk}}_i^{\prime },{\mathsf{PID}}_i,\sigma )$, where $\mathsf{Verify}(\mathsf{params},{\mathsf{pk}}_i^{\prime },{\mathsf{PID}}_i,\sigma )=\mathsf{TRUE}$, and ${\mathsf{pk}}_i^{\prime }\ne {\mathsf{pk}}_i$ is an adversarial public key for ${\mathsf{PID}}_i$.

It is easy to see that (A4)$$\begin{array}{c}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{CL}-\mathsf{SIG},1}\le Pr[{\mathcal{E}}_1\cup {\mathcal{E}}_2]\le Pr\left[{\mathcal{E}}_1\right]+Pr\left[{\mathcal{E}}_2\right]\end{array}$$

To bound ${\mathsf{Adv}}_{\mathcal{A},I,\mathsf{CL}-\mathsf{SIG}}$, we first prove that (A5)$$\begin{array}{c}\hfill Pr\left[{\mathcal{E}}_1\right]\le d·{\mathsf{Adv}}_{\mathsf{SIG}},\end{array}$$ where d is the maximal number of parties, and ${\mathsf{Adv}}_{\mathsf{SIG}}$ is the advantage that any PPT adversary against the Schnorr signature scheme. We construct an adversary $\mathcal{S}$ against Schnorr signature from $\mathcal{A}$. The simulator $\mathcal{S}$ associates its challenge public key ${\mathsf{pk}}_i$ and the signing oracle $\mathcal{O}({\mathsf{sk}}_i,·)$ to party i. The master public-secret key $({\mathsf{pk}}_{\mathsf{KGC}},{\mathsf{sk}}_{\mathsf{KGC}})$ and all other honest key pairs are generated by $\mathcal{S}$. Signing and other key queries are handled faithfully for all ${\mathsf{PID}}_j,j\ne i$. For i, $\mathcal{S}$ prepares $B_i$, the partial private key $s_i$ and the user secret $a_i$ as follows.

• chooses random $h_i$ in the range of ${\mathsf{H}}_1$, compute $B_i={\mathsf{pk}}_i-h_i·{\mathsf{pk}}_{\mathsf{KGC}}$.

• program the random oracle ${\mathsf{H}}_1$ such that ${\mathsf{H}}_1({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_i\left|\right|B_i)=h_i$.

• If $\mathcal{A}$ queries for $s_i$, randomly choose a $b_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$ and compute $s_i=b_i+h_i·{\mathsf{sk}}_{\mathsf{KGC}}$.

• If $\mathcal{A}$ queries for $a_i$, randomly choose a $a_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$.

When $\mathcal{A}$ outputs a forgery $({\mathsf{PID}}_i,{\mathsf{pk}}_i,m,\sigma =({\sigma }^{\prime },B_i))$, $\mathcal{S}$ outputs a forgery $m,{\sigma }^{\prime }$ to its own challenger. Note that $\mathcal{A}$ cannot query both $a_i$ and $s_i$, if it does not fail trivially. So the simulation is indistinguishable from a real execution. The loss factor d is from guessing of the challenged party i. This completes the proof of (A5).

To bound $Pr\left[{\mathcal{E}}_2\right]$, first, we define an algorithm $\mathcal{B}$ relying on a ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ forger $\mathcal{A}$ that on inputs $(\mathsf{params},X)$ and $s_1,\cdots ,s_{\alpha }\in S$, returns a triple $(I,J,\Sigma )$ consisting of two integers $0\le J<I\le \alpha$ and a string $\Sigma$. Details follow.

• $\mathcal{B}$ gets a DLP challenge $(\mathbb{G},G,X)$ and a KGC identifier ${\mathsf{PID}}_{\mathsf{KGC}}$.

• $\mathcal{B}$ sets up the KGC public key ${\mathsf{pk}}_{\mathsf{KGC}}\leftarrow X$, the KGC identifier ${\mathsf{PID}}_{\mathsf{KGC}}$, CL-PKC parameters $\mathsf{params}\leftarrow (\mathbb{G},G,{\mathsf{PID}}_{\mathsf{KGC}},{\mathsf{pk}}_{\mathsf{KGC}})$. $\mathcal{B}$ also initializes two empty lists ${\mathcal{L}}_{{\mathsf{H}}_1}$ and ${\mathcal{L}}_{{\mathsf{H}}_2}$ to simulate the random oracles. Another empty list ${\mathcal{L}}_{\mathsf{aPK}}$ of replaced public keys is initialized by $\mathcal{B}$. $\mathcal{B}$ set up a flag $\mathsf{bad}\leftarrow \mathsf{FALSE}$.

• Preparation of simulated signing keys $\left\{\left({\mathsf{sk}}_j,B_j\right)\right\}$ for ${\left\{{\mathsf{PID}}_j\right\}}_{j=1,j\ne {\mathsf{PID}}_{\mathsf{KGC}}}^d$.

  • Choose random ${\mathsf{sk}}_j\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|}$, compute ${\mathsf{pk}}_j\leftarrow {\mathsf{sk}}_j·G$.

  • Choose random $h_j$ in the range of ${\mathsf{H}}_1\left(\right)$, compute $B_j={\mathsf{pk}}_j-h_j·{\mathsf{pk}}_{\mathsf{KGC}}$. If any ${\mathsf{sk}}_j$ collision happens, set $\mathsf{bad}=\mathsf{TRUE}$.

  • Program the random oracle ${\mathcal{O}}_{{\mathsf{H}}_1}\left(\right)$ such that ${\mathsf{H}}_1({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_j\left|\right|B_j)=h_j$, i.e., set ${\mathcal{L}}_{{\mathsf{H}}_1}({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_j\left|\right|B_j)$←$h_j$.

• $\mathcal{B}$ sends $\mathsf{params}$ to $\mathcal{A}$, chooses some randomness for $\mathcal{A}$, and prepares to answer the random oracle queries and others.

• Answer to ${\mathsf{H}}_1\left(s\right)$ queries, where s has the form ${\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_k\left|\right|B_k$.

  If ${\mathcal{L}}_{{\mathsf{H}}_1}\left(s\right)$ is defined, return ${\mathcal{L}}_{{\mathsf{H}}_1}\left(s\right)$ to $\mathcal{A}$. Otherwise, pick up $H\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|}$, define ${\mathcal{L}}_{{\mathsf{H}}_1}\left(s\right)\leftarrow H$, and return H.

• Answer to ${\mathsf{H}}_2\left(R\right|\left|m\right)$.

  If ${\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)$ is defined, return ${\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)$ to $\mathcal{A}$. Otherwise, pick up W$\stackrel{\$}{\leftarrow }$${\mathbb{Z}}_{\left|\mathbb{G}\right|}$, define ${\mathcal{L}}_{{\mathsf{H}}_1}\left(R\right|\left|m\right)\leftarrow W$, and return W.

• Answer to $\mathsf{PPKey}-\mathsf{Extract}\left({\mathsf{PID}}_j\right)$

  • If ${\mathsf{pk}}_j$ is not replaced, choose a $b_j\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$, compute $s_j=b_j+h_j·{\mathsf{sk}}_{\mathsf{KGC}}$, record and return $s_j$ to $\mathcal{A}$.

  • Otherwise, return ⊥.

• Answer to $\mathsf{ReplacePK}({\mathsf{PID}}_j,{\mathsf{pk}}_j)$ queries. Record $({\mathsf{PID}}_j,{\mathsf{pk}}_j)$ in ${\mathcal{L}}_{\mathsf{aPK}}$ and return “$\mathsf{OK}$” to $\mathcal{A}$.

• Answer to $\mathsf{getPrivateKey}\left({\mathsf{PID}}_j\right)$. Return ${\mathsf{sk}}_j$ if ${\mathsf{pk}}_j$ is not replaced, and ⊥ otherwise.

• Answer to $\mathsf{SIG}.\mathsf{Sign}({\mathsf{PID}}_j,m)$ queries.

  • If $({\mathsf{PID}}_j,{\mathsf{pk}}_j)$$\notin {\mathcal{L}}_{\mathsf{aPK}}$, retrieve the simulated signing key ${\mathsf{sk}}_j$.

    • –

      Choose $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|}$, compute $R\leftarrow r·G$, choose $h_m\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|}$.

    • –

      If ${\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)$ is defined, set $\mathsf{bad}=\mathsf{TRUE}$.

    • –

      Set ${\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)\leftarrow (h_m$, $\beta )$, where $\beta =r-h_m·{\mathsf{sk}}_j$, and return $(R,\beta )$ to $\mathcal{A}$.

  • Otherwise, return ⊥ to $\mathcal{A}$.

  We also count signing queries as ${\mathsf{H}}_2\left(\right)$ queries.

• If $\mathcal{A}$ submits a forgery $({\mathsf{PID}}_i,{\mathsf{pk}}_i^{*},m^{*},{\sigma }^{*})$, $\mathcal{B}$ parse ${\sigma }^{*}$ as $({\sigma }^{\prime },B_i^{*})$ and parse ${\sigma }^{\prime }$ as $(R,\beta )$.

  • $\mathcal{B}$ searches for $h_1={\mathcal{L}}_{{\mathsf{H}}_1}({\mathsf{PID}}_i\left|\right|{\mathsf{PID}}_{\mathsf{KGC}}\left|\right|B_i^{*})$, and $h_2={\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right||m^{*})$. If $h_1$ or $h_2$ is not defined, set $\mathsf{bad}=\mathsf{TRUE}$.

  • If ${\mathsf{pk}}_i\ne B_i^{*}+{\mathcal{L}}_{{\mathsf{H}}_1}({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_i\left|\right|B_i^{*})·X$, set $\mathsf{bad}=\mathsf{TRUE}$.

  If $\mathsf{bad}=\mathsf{FALSE}$, then $\mathcal{B}$ finally outputs $(I,J,\Sigma =\beta |\left|h_1\right|\left|h_2\right)$. Otherwise $\mathcal{B}$ outputs $(0,0,\perp )$.

Table A1

Variables in the proof.

Variable	Meaning
${\mathcal{L}}_{\mathsf{aPK}}$	a list of public keys registered by the adversary
${\mathcal{L}}_{{\mathsf{H}}_1}$	a list to simulate the random oracle ${\mathsf{H}}_1(·)$
${\mathcal{L}}_{{\mathsf{H}}_2}$	a list to simulate the random oracle ${\mathsf{H}}_2(·)$

We then use the multiple-forking algorithm ${\mathcal{MF}}_{\mathcal{B},3}$ associated to $\mathcal{B}$ and $n=3$ to construct a DL solver $\mathcal{D}$ as in Figure A2. Note that we do not require exact $b_i=b_i^{\prime }$ and $a_i=a_i^{\prime }$, but $(a_i+b_i)\equiv (a_i^{\prime }+b_i^{\prime })mod{\mathbb{Z}}_{\left|\mathbb{G}\right|}$ for the first fork. This critical forking point is observable by $\mathcal{B}$ in ${\mathcal{L}}_{{\mathsf{H}}_1}$ for the ${\mathsf{H}}_1(\cdots ||B_i)$ query, as $B_i=(a_i+b_i)·G$ is unique in $\mathbb{G}$. Simlilarly, the second fork can be observed for ${\mathsf{H}}_2\left(\right)$-queries on $R\left|\right|m^{*}$.

Figure A2. The DLP solving algorithm [Forumla omitted. See PDF.] from [Forumla omitted. See PDF.].

We now show that $\mathcal{D}$ solves the DLP for X in $\mathbb{G}$. If $b=1$, then there exist coins $\rho$ for $\mathcal{B}$, with $j>k\ge 1$ and $s_1,\cdots ,s_{\alpha },$$s_j^1,\cdots ,s_{\alpha }^1,$$s_k^2,\cdots ,s_{\alpha }^2,$ $s_j^3,\cdots ,s_{\alpha }^3,$$\in {\mathbb{Z}}_{\left|\mathbb{G}\right|}$ with $h_1=h_1^{\prime }=s_k\ne s_k^2=\widetilde{h_1}=\widehat{h_1}$, $h_2=s_j\ne s_j^1=h_2^{\prime }$ and $\widetilde{h_2}=s_j^2\ne s_j^3=\widehat{h_2}$. More specifically,

• (1)

  in the execution of $\mathcal{B}(\mathsf{params},s_1,\cdots ,s_{\alpha };\rho )$, $\mathcal{A}$ outputs a valid forgery $({\mathsf{PID}}_i,p{k}_i,$$m,$$((R,{\beta }_0),B_i))$, with $h_1={\mathcal{L}}_{{\mathsf{H}}_1}({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_i\left|\right|B_i)=s_k$, $h_2={\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)=s_j$.

• (2)

  in the execution of $\mathcal{B}(\mathsf{params},s_1,\cdots ,s_{j-1},s_j^1,\cdots ,s_{\alpha }^1;\rho )$, $\mathcal{A}$ outputs a valid forgery $({\mathsf{PID}}_i^{\prime },p{k}_i^{\prime },$$m^{\prime },$$((R^{\prime },{\beta }_1),B_i^{\prime }))$, with $h_1^{\prime }={\mathcal{L}}_{{\mathsf{H}}_1}({\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_i\left|\right|B_i^{\prime })=s_k$, $h_2^{\prime }={\mathcal{L}}_{{\mathsf{H}}_2}\left(R\right|\left|m\right)$$=s_j^1$, ${\mathsf{PID}}_{\mathsf{KGC}}^{\prime }\left|\right|{\mathsf{PID}}_i^{\prime }\left|\right|B_i^{\prime }={\mathsf{PID}}_{\mathsf{KGC}}\left|\right|{\mathsf{PID}}_i\left|\right|B_i$, and $R^{\prime }=R$.

• (3)

  in the execution of $\mathcal{B}(\mathsf{params},s_1,\cdots ,s_{k-1},s_k^2,\cdots ,s_{\alpha }^2;\rho )$, $\mathcal{A}$ outputs a valid forgery $(\widetilde{{\mathsf{PID}}_i},\widetilde{p{k}_i},$$\tilde{m},$$((\tilde{R},{\beta }_2),\widetilde{B_i}))$, with $\widetilde{h_1}={\mathcal{L}}_{{\mathsf{H}}_1}(\widetilde{{\mathsf{PID}}_{\mathsf{KGC}}}\left|\right|\widetilde{{\mathsf{PID}}_i}\left|\right|\widetilde{B_i})=s_k^2$, $\widetilde{h_2}={\mathcal{L}}_{{\mathsf{H}}_2}(\tilde{R}\left|\right|\tilde{m})$$=s_j^2$, and $\widetilde{B_i}=B_i$.

• (4)

  in the execution of $\mathcal{B}(\mathsf{params},s_1,\cdots ,s_{k-1},s_k^2,\cdots ,s_{j-1}^2,s_j^3,\cdots ,s_{\alpha }^3;\rho )$, $\mathcal{A}$ outputs a valid forgery $(\widehat{{\mathsf{PID}}_i},\widehat{p{k}_i},$$\widehat{m},$$((\widehat{R},{\beta }_2),\widehat{B_i}))$, with $\widehat{h_1}={\mathcal{L}}_{{\mathsf{H}}_1}(\widehat{{\mathsf{PID}}_{\mathsf{KGC}}}\left|\right|\widehat{{\mathsf{PID}}_i}\left|\right|$$\widehat{B_i})$$=s_k^2$, $\widehat{h_2}={\mathcal{L}}_{{\mathsf{H}}_2}(\widehat{R}\left|\right|\widehat{m})$$=s_j^3$, $\widehat{{\mathsf{PID}}_{\mathsf{KGC}}}\left|\right|\widehat{{\mathsf{PID}}_i}\left|\right|\widehat{B_i}=\widetilde{{\mathsf{PID}}_{\mathsf{KGC}}}\left|\right|\widetilde{{\mathsf{PID}}_i}\left|\right|B_i$, and $\widehat{R}=\tilde{R}$.

From (1) and (2), we have ${\mathsf{pk}}_i={\mathsf{pk}}_i^{\prime }=B_i+h_1·X$, ${\beta }_0·G=R+h_2·{\mathsf{pk}}_i$, and ${\beta }_1·G=R+h_2^{\prime }·{\mathsf{pk}}_i^{\prime }$ Since $h_2\ne h_2^{\prime }$, $(h_2-h_2^{\prime })$ is well-defined. So we have (A6)$$\begin{array}{c}\hfill ({\beta }_0-{\beta }_1){(h_2-h_2^{\prime })}^{-1}·G=B_i+h_1·X\end{array}$$

Similarly, from (3) and (4), we have (A7)$$\begin{array}{c}\hfill ({\beta }_2-{\beta }_3){(\widetilde{h_2}-\widehat{h_2})}^{-1}·G=B_i+\widetilde{h_1}·X\end{array}$$

Solving for X in (A6) and (A7), as $(h_1-\widetilde{h_1})$ is well-defined, we finally have (A8)$$\begin{array}{c}\hfill \left\{\left(({\beta }_0-{\beta }_1){(h_2-h_2^{\prime })}^{-1}-({\beta }_2-{\beta }_3){(\widetilde{h_2}-\widehat{h_2})}^{-1}\right){(h_1-\widetilde{h_1})}^{-1}\right\}·G=X\end{array}$$

Therefore, the output of $\mathcal{D}$ when $b=1$ as in Figure A2 is the $\mathsf{DLP}$ solution of X.

Let $q_{\mathsf{H}}=q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2}$, where $q_{{\mathsf{H}}_1}$ and $q_{{\mathsf{H}}_2}$ are the number of $\mathcal{A}$’s ${\mathsf{H}}_1\left(\right)$ and ${\mathsf{H}}_2\left(\right)$ queries, respectively. Let $\mathsf{bad}|{\mathcal{E}}_2$ be the event that $\mathcal{B}$ outputs $(0,0,\perp )$ when ${\mathcal{E}}_2$ happens. Then we have (A9)$$\begin{array}{c}\hfill Pr\left[\mathsf{bad}\right|{\mathcal{E}}_2]\le \frac{d^2+q_{{\mathsf{H}}_1}^2+2·q_{{\mathsf{H}}_2}^2+2}{\left|\mathbb{G}\right|}\end{array}$$

Let $\mathsf{IGen}$ be the algorithm that calls $\mathsf{Setup}\left(1^{\kappa }\right)$ for $(\mathsf{params},\mathsf{msk})$ and returns $\mathsf{params}=(\mathbb{G},G,{\mathsf{pk}}_{\mathsf{KGC}},{\mathsf{PID}}_{\mathsf{KGC}})$. Let $$\begin{array}{c}\hfill \mathsf{accMf}=Pr\left[\begin{array}{c}I\ge 1\wedge J\ge 1:\mathsf{params}\stackrel{\$}{\leftarrow }\mathsf{IGen}\left(1^{\kappa }\right);s_1\cdots s_{\alpha }\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\left|\mathbb{G}\right|};\\ (I,J,\sigma )\stackrel{\$}{\leftarrow }\mathcal{B}(\mathsf{params},s_1\cdots s_{\alpha });\end{array}\right]\end{array}$$

By applying (A2) in Lemma A1 for $n=3$ we have (A10)$$\begin{array}{cc}\hfill Pr\left[{\mathcal{E}}_2\right]& \le \mathsf{accMf}+Pr\left[\mathsf{bad}\right|{\mathcal{E}}_2]\hfill \\ \hfill & \le \sqrt[4]{q_{\mathsf{H}}^6·\mathsf{frkMf}}+\sqrt[4]{\frac{3·q_{\mathsf{H}}}{\left|\mathbb{G}\right|}}+Pr\left[\mathsf{bad}\right|{\mathcal{E}}_2]\hfill \\ \hfill & \le \sqrt[4]{{(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}^6·{\mathsf{Adv}}_{\mathcal{D},\mathbb{G}}^{\mathsf{DLP}}}+\sqrt[4]{\frac{3·(q_{{\mathsf{H}}_1}+q_{{\mathsf{H}}_2})}{\left|\mathbb{G}\right|}}+Pr\left[\mathsf{bad}\right|{\mathcal{E}}_2],\hfill \end{array}$$ where ${\mathsf{Adv}}_{\mathcal{D},\mathbb{G}}^{\mathsf{DLP}}$ is the advantage of $\mathcal{D}$ against $\mathsf{DLP}$ in $\mathbb{G}$. By combining (A4), (A5), (A9) and (A10), we get (A3) in Lemma A2. □

Lemma A3 

(${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ against Type II adversary). If there exists an efficient Type II adversary against ${\Pi }_{\mathsf{CL}-\mathsf{SIG}}$ with advantage ${\mathsf{Adv}}_{\mathsf{CL}-\mathsf{SIG},2}$, then there exists a forger $\mathcal{S}$ with advantage ${\mathsf{Adv}}_{\mathsf{SIG}}$ against the Schnorr signature scheme, such that (A11)$$\begin{array}{c}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{CL}-\mathsf{SIG},2}\le d·{\mathsf{Adv}}_{\mathsf{SIG}}\end{array}$$where d is the maximal number of clients with distinct identifiers.

Proof. 

Similar to the previous proof, we define two events such that (A12)$$\begin{array}{c}\hfill {\mathsf{Adv}}_{\mathcal{A},\mathsf{CL}-\mathsf{SIG},2}\le Pr[{\mathcal{E}}_3\cup {\mathcal{E}}_4]\le Pr\left[{\mathcal{E}}_3\right]+Pr\left[{\mathcal{E}}_4\right]\end{array}$$

• ${\mathcal{E}}_3$: $\mathcal{A}$ outputs a forgery $(m,{\mathsf{pk}}_i,{\mathsf{PID}}_i,\sigma )$, where $\mathsf{Verify}(\mathsf{params},{\mathsf{pk}}_i,{\mathsf{PID}}_i,\sigma )=\mathsf{TRUE}$, ${\mathsf{pk}}_i$ is the original public key of party ${\mathsf{PID}}_i$, and m has not been queried to the signing oracle $\mathcal{O}({\mathsf{sk}}_i,·)$.

• ${\mathcal{E}}_4$: $\mathcal{A}$ outputs a forgery $(m,{\mathsf{pk}}_i^{\prime },{\mathsf{PID}}_i,\sigma )$, where $\mathsf{Verify}(\mathsf{params},{\mathsf{pk}}_i^{\prime },{\mathsf{PID}}_i,\sigma )=\mathsf{TRUE}$, and ${\mathsf{pk}}_i^{\prime }\ne {\mathsf{pk}}_i$ is an adversarial public key for ${\mathsf{PID}}_i$.

If $\mathcal{A}$ does not fail automatically, then we construct an simulator ${\mathcal{S}}^{\prime }$ almost identical to $\mathcal{S}$ for event ${\mathcal{E}}_1$ in Lemma A2, and ${\mathcal{S}}^{\prime }$ can answer the extra $\mathsf{getKeyKGC}\left(\right)$ with the simulated $\mathsf{msk}$. So we have (A13)$$\begin{array}{c}\hfill Pr\left[{\mathcal{E}}_3\right]\le d·{\mathsf{Adv}}_{\mathsf{SIG}}\end{array}$$

The Type 2 adversary cannot replace public keys, so we have $Pr\left[{\mathcal{E}}_4\right]=0$. □

We use the advantage ${\mathsf{Adv}}_{\mathsf{SIG}}$ of attacking Schnorr signature scheme in Theorem 4.1 in [40] to finish the proof.

Lemma A4 

(Security of Schnorr Signature, from Theorem 4.1 in [40]). If there exist an efficient adversary against the Schnorr signature scheme ${\Pi }_{\mathsf{SIG}}$ with advantage ${\mathsf{Adv}}_{\mathsf{SIG}}$, then there exists a DLP solver $\mathcal{U}$ with advantage ${\mathsf{Adv}}_{\mathcal{U},\mathsf{DLP}}^{\mathsf{DLP}}$, such that (A14)$$\begin{array}{cc}\hfill {\mathsf{Adv}}_{\mathsf{SIG}}& \le \sqrt[2]{(q_{{\mathsf{H}}_2}+q_{\mathsf{SIG}}+1)·{\mathsf{Adv}}_{\mathcal{U},\mathbb{G}}^{\mathsf{DLP}}}+\sqrt[2]{\frac{(q_{{\mathsf{H}}_2}+q_{\mathsf{SIG}}+1)·(q_{\mathsf{SIG}}+1)}{\left|\mathbb{G}\right|}},\hfill \end{array}$$where $q_{H_2}$ is the number of random oracle queries for hash function ${\mathsf{H}}_2:{\{0,1\}}^{*}\to {\mathbb{Z}}_{\left|\mathbb{G}\right|}$, and $q_{\mathsf{SIG}}$ the number of signing queries.

By plugging (A14) into (A3) and (A11) and using union bound, we finally arrive at Theorem 1.

References

1. Rescorla, E. Internet Engineering Task Force. The Transport Layer Security (TLS) Protocol Version 1.3. 2018; Available online: https://tools.ietf.org/html/draft-ietf-tls-tls13-26 (accessed on 8 December 2023).

2. Bellare, M.; Rogaway, P. Entity Authentication and Key Distribution. Proceedings of the CRYPTO’93; Santa Barbara, CA, USA, 22–26 August 1994; Volume 773, pp. 232-249. [DOI: https://dx.doi.org/10.1007/3-540-48329-2_21]

3. LaMacchia, B.A.; Lauter, K.; Mityagin, A. Stronger Security of Authenticated Key Exchange. Proceedings of the ProvSec 2007; Wollongong, Australia, 1–2 November 2007; Susilo, W.; Liu, J.K.; Mu, Y. Volume 4784, pp. 1-16.

4. Canetti, R. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Cryptology ePrint Archive, Report 2000/067. 2000; Available online: https://ia.cr/2000/067 (accessed on 8 December 2023).

5. Jager, T.; Kohlar, F.; Schäge, S.; Schwenk, J. On the Security of TLS-DHE in the Standard Model. Proceedings of the CRYPTO 2012; Santa Barbara, CA, USA, 19–23 August 2012; Safavi-Naini, R.; Canetti, R. Volume 7417, pp. 273-293. [DOI: https://dx.doi.org/10.1007/978-3-642-32009-5_17]

6. Kiefer, F.; Manulis, M. Universally composable two-server PAKE. Proceedings of the International Conference on Information Security; Honolulu, HI, USA, 3–6 September 2016; Springer: Cham, Switzerland, 2016; pp. 147-166.

7. Bormann, C.; Ersue, M.; Keranen, A. Terminology for Constrained-Node Networks. RFC 7228 (Informational). 2014; Available online: https://datatracker.ietf.org/doc/html/rfc7228 (accessed on 8 December 2023).

8. Al-Riyami, S.S.; Paterson, K.G. Certificateless public key cryptography. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security; Taipei, Taiwan, 30 November–4 December 2003; Springer: Cham, Switzerland, 2003; pp. 452-473.

9. Crampton, J.; Lim, H.W.; Paterson, K.G.; Price, G. A certificate-free grid security infrastructure supporting password-based user authentication. Proceedings of the 6th Annual PKI R&D Workshop; Gaithersburg, MD, USA, 17–19 April 2007; pp. 103-118.

10. Taha, S.; Shen, X. A link-layer authentication and key agreement scheme for mobile public hotspots in NEMO based VANET. Proceedings of the 2012 IEEE Global Communications Conference (GLOBECOM); Anaheim, CA, USA, 3–7 December 2012; pp. 1004-1009.

11. Memon, I.; Mohammed, M.R.; Akhtar, R.; Memon, H.; Memon, M.H.; Shaikh, R.A. Design and implementation to authentication over a GSM system using certificate-less public key cryptography (CL-PKC). Wirel. Pers. Commun.; 2014; 79, pp. 661-686. [DOI: https://dx.doi.org/10.1007/s11277-014-1879-8]

12. Memon, I.; Hussain, I.; Akhtar, R.; Chen, G. Enhanced privacy and authentication: An efficient and secure anonymous communication for location based service using asymmetric cryptography scheme. Wirel. Pers. Commun.; 2015; 84, pp. 1487-1508. [DOI: https://dx.doi.org/10.1007/s11277-015-2699-1]

13. Balakrishnan, S.K.; Raj, V.J. Practical Implementation of a Secure Email System Using Certificateless Cryptography and Domain Name System. Int. J. Netw. Secur.; 2016; 18, pp. 99-107.

14. Bala, D.Q.; Maity, S.; Jena, S.K. A lightweight remote user authentication protocol for smart e-health networking environment. Proceedings of the 2017 International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC); Palladam, India, 10–11 February 2017; pp. 10-15.

15. Saeed, M.E.S.; Liu, Q.Y.; Tian, G.; Gao, B.; Li, F. Remote authentication schemes for wireless body area networks based on the Internet of Things. IEEE Internet Things J.; 2018; 5, pp. 4926-4944.

16. Song, J.; He, C.; Zhang, L.; Tang, S.; Zhang, H. Toward an RSU-unavailable lightweight certificateless key agreement scheme for VANETs. China Commun.; 2014; 11, pp. 93-103. [DOI: https://dx.doi.org/10.1109/CC.2014.6969774]

17. Yang, G.; Tan, C.H. Strongly Secure Certificateless Key Exchange without Pairing. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, ASIACCS ’11; Hong Kong, China, 22–24 March 2011; pp. 71-79.

18. Farouk, A.; Miri, A.; Fouad, M.M.; Abdelhafez, A.A. Efficient pairing-free, certificateless two-party authenticated key agreement protocol for grid computing. Proceedings of the 2014 Fourth International Conference on Digital Information and Communication Technology and Its Applications (DICTAP); Bangkok, Thailand, 6–8 May 2014; pp. 279-284.

19. He, D.; Padhye, S.; Chen, J. An efficient certificateless two-party authenticated key agreement protocol. Comput. Math. Appl.; 2012; 64, pp. 1914-1926. [DOI: https://dx.doi.org/10.1016/j.camwa.2012.03.044]

20. Safi, Q.G.K.; Luo, S.; Pan, L.; Liu, W.; Yan, G. Secure authentication framework for cloud-based toll payment message dissemination over ubiquitous VANETs. Pervasive Mob. Comput.; 2018; 48, pp. 43-58. [DOI: https://dx.doi.org/10.1016/j.pmcj.2018.05.004]

21. Boneh, D.; Boyen, X. Secure Identity Based Encryption Without Random Oracles. Proceedings of the CRYPTO 2004; Santa Barbara, CA, USA, 15–19 August 2004; Franklin, M. Volume 3152, pp. 443-459. [DOI: https://dx.doi.org/10.1007/978-3-540-28628-8_27]

22. Boneh, D.; Boyen, X.; Goh, E.J. Hierarchical Identity Based Encryption with Constant Size Ciphertext. Proceedings of the EUROCRYPT 2005; Aarhus, Denmark, 22–26 May 2005; Cramer, R. Volume 3494, pp. 440-456. [DOI: https://dx.doi.org/10.1007/11426639_26]

23. Lewko, A.B.; Waters, B. New Proof Methods for Attribute-Based Encryption: Achieving Full Security through Selective Techniques. Proceedings of the CRYPTO 2012; Santa Barbara, CA, USA, 19–23 August 2012; Safavi-Naini, R.; Canetti, R. Volume 7417, pp. 180-198. [DOI: https://dx.doi.org/10.1007/978-3-642-32009-5_12]

24. Debiao, H.; Jianhua, C.; Jin, H. An ID-based client authentication with key agreement protocol for mobile client–server environment on ECC with provable security. Inf. Fusion; 2012; 13, pp. 223-230. [DOI: https://dx.doi.org/10.1016/j.inffus.2011.01.001]

25. Yao, X.; Kong, H.; Liu, H.; Qiu, T.; Ning, H. An attribute credential based public key scheme for fog computing in digital manufacturing. IEEE Trans. Ind. Inform.; 2019; 15, pp. 2297-2307. [DOI: https://dx.doi.org/10.1109/TII.2019.2891079]

26. Galindo, D.; Morillo, P.; Ràfols, C. Breaking Yum and Lee generic constructions of certificate-less and certificate-based encryption schemes. Proceedings of the European Public Key Infrastructure Workshop; Turin, Italy, 19–20 June 2006; Springer: Cham, Switzerland, 2006; pp. 81-91.

27. Maity, S.; Hansdah, R.C. Certificate-less On-demand public key management (CLPKM) for self-organized MANETs. Proceedings of the International Conference on Information Systems Security; Guwahati, India, 15–19 December 2012; Springer: Cham, Switzerland, 2012; pp. 277-293.

28. Banerjee, U.; Chandrakasan, A.P. Efficient post-quantum TLS handshakes using identity-based key exchange from lattices. Proceedings of the ICC 2020—2020 IEEE International Conference on Communications (ICC); Virtual, 7–11 June 2020; pp. 1-6.

29. Li, H.; Wang, Y.; Fu, X.; Lan, C.; Wang, C.; Li, F.; Guo, H. PSCPAC: Post-quantum secure certificateless public auditing scheme in cloud storage. J. Inf. Secur. Appl.; 2021; 61, 102927. [DOI: https://dx.doi.org/10.1016/j.jisa.2021.102927]

30. Wei, G.; Fan, K.; Zhang, K.; Wang, H.; Li, H.; Yang, Y. Quantum-Safe Lattice-Based Certificateless Anonymous Authenticated Key Agreement for Internet of Things. IEEE Internet Things J.; 2023; Available online: https://ieeexplore.ieee.org/abstract/document/10285342 (accessed on 8 December 2023). [DOI: https://dx.doi.org/10.1109/JIOT.2023.3323275]

31. Li, L.; Xu, M. PVCLS-SI: Isogeny-based Certificateless Signature Scheme. Proceedings of the 2022 IEEE 10th International Conference on Information, Communication and Networks (ICICN); Zhangye, China, 19–22 August 2022; pp. 632-637.

32. Kumari, S.; Singh, M.; Singh, R.; Tewari, H. A post-quantum lattice based lightweight authentication and code-based hybrid encryption scheme for IoT devices. Comput. Netw.; 2022; 217, 109327. [DOI: https://dx.doi.org/10.1016/j.comnet.2022.109327]

33. Seyhan, K.; Nguyen, T.N.; Akleylek, S.; Cengiz, K. Lattice-based cryptosystems for the security of resource-constrained IoT devices in post-quantum world: A survey. Clust. Comput.; 2022; 25, pp. 1729-1748. [DOI: https://dx.doi.org/10.1007/s10586-021-03380-7]

34. Katz, J.; Lindell, Y. Introduction to Modern Cryptography; CRC Press: Boca Raton, FL, USA, 2014.

35. Boldyreva, A.; Palacio, A.; Warinschi, B. Secure proxy signature schemes for delegation of signing rights. J. Cryptol.; 2012; 25, pp. 57-115. [DOI: https://dx.doi.org/10.1007/s00145-010-9082-x]

36. Shoup, V. Sequences of Games: A Tool for Taming Complexity in Security Proofs. Cryptology Eprint Archive. 2004; Available online: https://eprint.iacr.org/2004/332 (accessed on 8 December 2023).

37. Wouters, P.; Tschofenig, H.; Gilmore, J.; Weiler, S.; Kivinen, T. Using Raw Public Keys in Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS). RFC 7250 (Proposed Standard). 2014; Available online: https://datatracker.ietf.org/doc/html/rfc7250 (accessed on 8 December 2023).

38. Eronen, P.; Tschofenig, H. Pre-Shared Key Ciphersuites for Transport Layer Security (TLS). RFC 4279 (Standards Track). 2005; Available online: https://datatracker.ietf.org/doc/html/rfc4279 (accessed on 8 December 2023).

39. Dimitrov, V.; Imbert, L.; Mishra, P.K. Efficient and secure elliptic curve point multiplication using double-base chains. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security; Chennai, India, 4–8 December 2005; pp. 59-78.

40. Bellare, M.; Neven, G. Multi-signatures in the plain public-Key model and a general forking lemma. Proceedings of the ACM CCS 2006; Alexandria, VA, USA, 30 October–3 November 2006; Juels, A.; Wright, R.N.; De Capitani di Vimercati, S. pp. 390-399. [DOI: https://dx.doi.org/10.1145/1180405.1180453]