Mul-IBS: a multivariate identity-based signature scheme compatible with IoT-based NDN architecture

Abstract

It has been forty years since the TCP/IP protocol blueprint, which is the core of the modern worldwide Internet, was published. Over this long period, technology has made rapid progress. These advancements are slowly putting pressure and new demands on the underlying network architecture design. Therefore, there was a need for innovations that could handle the increasing demands of new technologies like IoT while ensuring secrecy and privacy. It is how named data networking (NDN) came into the picture. NDN enables robust data distribution with interest-based content retrieval and a leave-copy-everywhere caching policy. Even though NDN has surfaced as a future envisioned and decisive machinery for data distribution in IoT, it suffers from new data security challenges like content poisoning attacks. In this attack, an attacker attempts to introduce poisoned content with an invalid signature into the network. Given the circumstances, there is a need for a cost-effective signature scheme, requiring inexpensive computing resources and fast when implemented. An identity-based signature scheme (IBS) is the natural choice to address this problem. Herein, we present an IBS, namely Mul-IBS relying on multivariate public key cryptography (MPKC), which leads the race among the post-quantum cryptography contenders. A 5-pass identification scheme accompanying a safe and secure signature scheme based on MPKC works as key ingredients of our design. Our Mul-IBS attains optimal master public key size, master secret key size, and user’s secret key size in the context of multivariate identity-based signatures. The proposed scheme Mul-IBS is proven to be secure in the model, existential unforgeability under chosen-message and chosen identity attack (uf-cma), contingent upon the fact that Multivariate Quadratic (MQ) problem is NP-hard. The proposed design Mul-IBS can be utilized as a crucial cryptographic building block to build a robust and resilient IoT-based NDN architecture.

1 Introduction

The currently used host-centric nature of the network architecture is not fit for IoT-based systems due to hurdles like high latency, inadequate address spacing, and caching. A novel network architecture model called named data networking (NDN) [11, 30] is swiftly gaining popularity to ensure efficient content distribution. NDN is decorated with features like a leave copy everywhere (LCE) caching policy and name-based routing, making it ideal for content distribution among IoT devices. To cut a long story short, a network dispatches and transfers data. Designing a network architecture becomes a pivotal task as it describes and explains how these bits of data will be dispatched in the real world. Any network design should address the core question of what namespaces are used for data transfer. Currently used TCP/IP protocol architecture [22] uses a namespace design where locations are named. It is very similar to a telephone network where each telephone is assigned a phone number. In TCP/IP network protocol, these phone numbers are replaced by IP addresses. In short, TCP/IP is a location-based, host-centric, point-to-point communication model. NDN uses an entirely different namespace design. In an NDN-based network architecture, data bits are named themselves. Let John be a client interested in some content, say $\mathsf{\Gamma }$. His interest request is transferred to the original publisher of the content. Due to the LCE caching policy, the response sent by the publisher is cached by the intermediate routers for future use. In the future, if another user, Michael, displays interest in the same content $\mathsf{\Gamma }$, then local routers will serve the interest request of Michael instead of forwarding it again to the publisher. This way, the network’s overall efficiency increases as contents are provided locally from the caches to users. It also enhances the response time since the content request must not be dispatched to the original broadcaster of the content (Fig. 1).

Fig. 1

Caching policy and routing in NDN architecture

In NDN, security is built into the data itself rather than a function of where or how it is obtained. Even though NDN has surfaced as a future envisioned and decisive machinery for data distribution in IoT, it suffers from new data security challenges. A content poisoning attack is the most prevalent among all the major hurdles. In this attack, an attacker attempts to introduce poisoned content with an invalid signature into the network. A possible solution to mitigate the network from a content poisoning attack is to append a signature of the contents to every data package. The circumstances demand a cost-effective identity-based signature (IBS).

In 1984, Shamir [26] put forward the concept of the first IBS. The key idea behind IBS is that a user’s public key can be directly derived from its identity, such as names and email addresses, instead of randomly generated keys. This removes the requirement for digital certificates for linking public keys with identities. In the identity-based setting, a trusted secret key generator or key distribution center $\textsf{SKG}$ derives users’ secret keys from a master secret key and issues the secret keys to the respective users. Note that the master secret key is only known to the $\textsf{SKG}$. As the SKG generates and holds the secret key for all users, a malicious SKG can sell the users’ secret keys or do the signature on behalf of users. This is known as the key escrow problem. This property demands that $\textsf{SKG}$ has to be trusted; otherwise, it can misuse its power. In contrast to IBS, the traditional PKI does not allow CA to get information about users’ secret keys. Thus, from the security perspective, inherent key escrow property is a major drawback of IBS, unlike traditional PKI. However, a similar kind of fraud is possible in PKI. For instance, a fake certificate can be generated by a cheating CA for a public key of which it knows the corresponding secret key. As a consequence, the CA can generate valid signatures. Note that the victim may try to prove his honesty by revealing his original certificate to a judge. However, it is impossible to prevent the CA from requesting that the user register two public keys. The escrow feature is not a serious issue in the signature scheme as opposed to the encryption scheme, where the $\textsf{SKG}$ can decrypt ciphertexts associated with any of its users. Still, a limited form of key escrow property inherently appears in identity-based and PKI-based signatures. Almost all currently used IBS schemes rely on challenging classical problems [13, 14, 23]. Unfortunately, these IBS schemes will become obsolete once quantum computers enter the market. This is since Shor’s algorithm [28] can be employed to break these classical challenging problems in polynomial time. It makes the requirements of finding an alternative solution, i.e., quantum computer-resistant IBS, which falls under post-quantum cryptography (PQC) [1]. In the last two decades, PQC has become a new direction of research to overcome the threat of Shor’s algorithm.

Since 2013, a working group of the National Institute of Standards and Technologies (NIST) has studied the standardization of Post-Quantum cryptography. The European Telecommunications Standards Institute (ETSI) also organizes a regular Quantum-Safe-Crypto Workshop. Apart from lattice-based, code-based, isogeny-based and hash-based cryptosystems, multivariate cryptography is one of the leading candidates for PQC. Mathematical operations used in multivariate cryptographic schemes are elementary. The most used mathematical operations are addition and multiplications over finite fields. This makes them fast and efficient, making them suitable for low-cost devices [3, 4]. A system of multivariate polynomials works as the public key of an MPKC. The security of MPKC stands on the fact MQ problem is NP-Hard [9, 18]. In the current state of art, there are several practical multivariate encryption and signature schemes such as MI [16], HFE [17], UOV [12], Rainbow [8], and Gui [21]. However, there is a deficiency of signature schemes with special properties such as IBS. Thus, the development of secure and efficient multivariate IBS becomes an exciting direction of research work. The first multivariate IBS, namely IBUOV, was proposed by Shen et al. [27]. They employed standard UOV [12] as building blocks of their construction. In the following, Luyen [15] designed a multivariate IBS by modifying UOV, and Rainbow [8] using the technique of Sakumoto et al. [24]. Recently, Chen et al. [5] developed a general construction of multivariate IBS that is compatible with any MPKC.

1.1 Our contribution

The unprecedented advancements that the Internet has made over the last few decades have put much pressure and placed new demands on the underlying network architecture design. The situation demands new ingenious ideas to handle the requirements of modern technologies like IoT while ensuring secrecy and privacy. These circumstances manifested a novel network architecture design, Named Data Networking (NDN), enabling robust data distribution with interest-based content retrieval and a leave-copy-everywhere caching policy. Although NDN-based architecture brings significant advantages to IoT, it has to fight against shortcomings. One of the most prevalent ones is content poisoning attacks. In this attack, an attacker attempts to introduce poisoned content with an invalid signature into the network. Hence, a growing need for a cost-effective signature scheme requires inexpensive computing resources and rapidity when implemented. An IBS is a natural choice to address this problem. Almost all the existing IBS rely upon the intractability of challenging classical problems. Such as discrete logarithms or number factorization. However, these IBS will become outdated once a quantum computer comes into the picture. This demands an IBS that is post-quantum-safe.

Herein, we propose the multivariate-based IBS, namely Mul-IBS, which offers resistance against attacks by quantum computers. We utilize a multivariate signature scheme along with a 5-pass identification scheme [24] as the cryptographic building blocks of Mul-IBS. The Mul-IBS involves four algorithms: (i) Setup, (ii) Extract, (iii) Signature Generation, and (iv) Signature Verification. On the input security parameter $\kappa$, the $\textsf{SKG}$ runs $\textsf{Setup}$ to generate Mpk and Msk. It publishes Mpk as a master public key and keeps with itself Msk as a master secret key. In the following, the $\textsf{SKG}$ produces user’s secret key $\textbf{u}_{ID}$ by running $\textsf{Extract}$ for an user with identity $ID\in \{0,1\}^*$. Given a message $\textsf{Mg}\in \{0,1\}^*$, a user having identity $ID\in \{0,1\}^*$ and signing key $\textbf{u}_{ID}$, runs $\mathsf{Signature~Generation}$, to produce a signature $\theta$. In order to validate the correctness of the signature $\theta$, a verifier runs $\mathsf{Signature~Verification}$ on input $(Mpk,\textsf{Mg},\theta ,ID)$. Size of Mpk and Msk is, respectively, $\frac{m(n+2)(n+1)}{2}$ and $n^2+m^2+c$ field ($\mathbb {F}_q$) elements, where c is the size of the central map and, m and n are the number of equations and the number of variables of the public polynomial of the underlying MQ-based signature scheme, respectively. Identity of user and secret key sizes are m and n field ($\mathbb {F}_q$) elements, respectively. The signature size is 2$\alpha$ $|\textsf{Commit}|$+ $\alpha (m+2n)$-$\mathbb {F}_q$ elements, $\alpha$ being the number of rounds needed for the underlying identification protocol. Luyen [15] claimed that the authors of [27] selected wrong parameters with the corresponding desired security level, as well as evaluated the wrong corresponding key sizes. While, in our scheme, we have correctly chosen the parameters. Moreover, IBS of [27] does not achieve uf-cma security, unlike ours. The IBS of [15] is similar to PKI, where each user has a different public key and $\textsf{SKG}$ needs to link the user’s public key with the user’s identity by providing a digital certificate. In other words, the work of [15] seems to be attaching a certificate to a non-identity-based signature. In contrast to the work of [15], we do not require any such digital certificate for linking the user’s public key with the user’s identity. In the IBS of [5], the master public key ${\overline{F}}$ is a function of user’s identity $ID_u=(z_1,\ldots ,z_d)$. Thus, if a verifier wants to verify the signature produced by a user with identity $ID_u$, then he first needs to evaluate the expression of the master public key ${\overline{F}}$ for the user’s identity $ID_u$. Thereby, it increases the computation complexity of the verifier. In comparison, our scheme does not have this issue, as the master public of our IBS is not a function of the user’s identity. Similar to [15], our signature scheme is provable secure since it attains uf-cma security. While, [5] is not provable secure. The most attractive point of our scheme is that it performs better over [5, 15, 27] given the sizes of the master public key, user’s secret key size, and Msk. The size of the signature of Mul-IBS is less than that of [15, 27]. Our scheme is ideally suited for an IoT-based NDN network where a lightweight IBS is needed for building a resilient network system.

2 Organization

The paper is structured as follows. Basic preliminaries are described in Sect. 3. We give the construction of our IBS in Sect. 4. Security analysis of our scheme is discussed in Sect. 5 followed by efficiency analysis in Sect. 6. Application of Mul-IBS in IoT-Based NDN Architecture is provided in Sect. 7. Finally, we conclude the paper in Sect. 8.

3 Preliminaries

We first give some basic notations. Throughout the paper, $\kappa$ represents “security parameter”, $x\in _R S$ denote that “x is chosen uniformly at random from a set S”, finite field with q elements is denoted by $\mathbb {F}_q$, $\mathbb {F}_{q^{\eta }}$ represent an extension field of $\mathbb {F}_q$ of degree $\eta$ and $(\mathbb {F}_{q})^{\eta }=\{\textbf{y}=(y_1,\ldots ,y_{\eta })|y_i\in \mathbb {F}_{q}~\hbox {for}~i=1,\ldots ,{\eta }\}$ is a vector space.

3.1 Hardness assumption

Our proposed design Mul-IBS rests its security on the hardness of MQ problem. The problem is expressed as:

Definition 3.1

Given a system $\mathcal {Q} = (q_{(1)}(\rho _1,\dots ,\rho _n) ,\dots ,q_{(m)}(\rho _1,\dots , \rho _n))$ of m quadratic equations in variables $(\rho _1,\dots ,\rho _n)$, find a n tuple $(\bar{\rho }_1 ,\dots , \bar{\rho }_n)$ such that

$$\begin{aligned} q_{(1)}(\bar{\rho }_1,\dots ,\bar{\rho }_n ) = \dots = q_{(m)}(\bar{\rho }_1,\dots ,\bar{\rho }_n ) = 0. \end{aligned}$$

3.2 Multivariate identification scheme [25]

A multivariate identification scheme makes use of a randomly chosen MQ system $\mathcal {P} : \mathbb {F}_q^n \rightarrow \mathbb {F}_q^m$. The security of a multivariate identification scheme is contingent on the presumption that the MQ problem is hard. Suppose a user, Alice desires to identify herself to another user Bob. Alice is also called the prover, and Bob, whom Alice tries to convince, is called the verifier. Now, Alice wants to exhibit to Bob that he understands how to compute $\textbf{u}$, a solution of $\mathcal {P}(\textbf{x})=\textbf{k}$ without disclosing any details about $\textbf{u}$. Such a scheme can be constructed using the technique of zero-knowledge proof (ZKP). Presuming the existence of a computationally binding and statistically hiding commitment scheme $\textsf{Commit}$, Sakumoto et al. [25] constructed a 5-pass identification scheme for the knowledge of $\textbf{u}$. To construct a ZKP of knowledge of $\textbf{u}$, the authors of [25] defined a function called the polar form of $\mathcal {P}$ which is mathematically formulated as $\mathcal {G}(\mathbf {\gamma _1},\mathbf {\gamma _2}) =\mathcal {P}(\mathbf {\gamma _1}+\mathbf {\gamma _2})-\mathcal {P}(\mathbf {\gamma _1}) -\mathcal {P}(\mathbf {\gamma _2})$. The detailed construction and correctness of the 5-pass identification protocol of Sakumoto et. al can be found in [25].

In the general setting, the polar form ( [7], Definition 2.1.2) of a multivariate system $\mathcal {P}$ is defined as $\mathcal {G}(\mathbf {\gamma _1},\mathbf {\gamma _2}) =\mathcal {P}(\mathbf {\gamma _1}+\mathbf {\gamma _2})-\mathcal {P}(\mathbf {\gamma _1}) -\mathcal {P}(\mathbf {\gamma _2})+\mathcal {P}(0)$. The authors of [25] assumed that the system $\mathcal {P}$ has no constant terms; therefore, the term $\mathcal {P}(0)$ vanishes. We tweaked the 5-pass identification scheme of [25] a little by modifying the polar form originally utilized in the [25]. For our purpose, we use the general version of $\mathcal {G}$, i.e., $\mathcal {G}(\mathbf {\gamma _1},\mathbf {\gamma _2})=\mathcal {P}(\mathbf {\gamma _1} +\mathbf {\gamma _2})-\mathcal {P}(\mathbf {\gamma _1})-\mathcal {P}(\mathbf {\gamma _2})+\mathcal {P}(0)$. The modified 5-pass identification scheme is given in Fig. 2. The only change we made is that we assume that the public polynomial may have constant terms (unlike [25]). Therefore, an additional term $\mathcal {P}(0)$ is added. We now give the correctness of the modified 5-pass identification scheme by proving that the following equalities (refer to Fig. 2):

• If chal=0, then Res=$\textbf{f}_0$. The verifier has the knowledge of $\textbf{f}_0, \textbf{g}_1, \textbf{h}_1$. In addition, verifier has $\textit{e}$ and the public polynomial $\mathcal {P}$. Therefore, he can easily compute $\mathbf{f_0}, { e}\textbf{f}_0-\textbf{g}_1$ and ${ e}\mathcal {P}(\textbf{f}_0)-\textbf{h}_1$ to correctly verifier the equality $c_0{\mathop {=}\limits ^{?}}\textsf{Commit}(\mathbf{f_0}, { e}\textbf{f}_0-\textbf{g}_1,{ e}\mathcal {P}(\textbf{f}_0)-\textbf{h}_1)$

• If chal=1, then Res=$\textbf{f}_1$. The verifier has the knowledge of $\textbf{f}_1, \textbf{g}_1, \textbf{h}_1$. In addition, verifier has $\textit{e}$ and the public polynomial $\mathcal {P}$. We have,

  $$\begin{aligned}&{ e}(\textbf{k}-\mathcal {P}(\textbf{f}_1)+\mathcal {P}(0))-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)-\textbf{h}_1\\&={ e}(\textbf{k}-\mathcal {P}(\textbf{f}_1)+\mathcal {P}(0))-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)- { e} \mathcal {P}(\textbf{f}_0)+\textbf{h}_0 \hbox { }\\&={ e}{} \textbf{k}-{ e}\mathcal {P}(\textbf{f}_1)+ { e}\mathcal {P}(0)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)- { e} \mathcal {P}(\textbf{f}_0)+\textbf{h}_0 \\&={ e}{} \textbf{k}-{ e}\mathcal {P}(\textbf{f}_1) - { e} \mathcal {P}(\textbf{f}_0)+ { e}\mathcal {P}(0)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0 \\&={ e}\mathcal {P}(\textbf{u})-{ e}\mathcal {P}(\textbf{f}_1) - { e} \mathcal {P}(\textbf{f}_0)+ { e}\mathcal {P}(0)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0\\&={ e}\mathcal {P}(\textbf{f}_0 +\textbf{f}_1)-{ e}\mathcal {P}(\textbf{f}_1) - { e} \mathcal {P}(\textbf{f}_0)+ { e}\mathcal {P}(0)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0\\&={ e}\mathcal {G}(\textbf{f}_0+\textbf{f}_1)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0\\&=\mathcal {G}({ e}{} \textbf{f}_0+\textbf{f}_1)-\mathcal {G}(\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0\\&=\mathcal {G}({ e}{} \textbf{f}_0-\textbf{g}_1, \textbf{f}_1)+\textbf{h}_0\\&=\mathcal {G}(\textbf{g}_0, \textbf{f}_1)+\textbf{h}_0\\ \end{aligned}$$

  Therefore, the verifier can correctly compute $\textsf{Commit}(\textbf{f}_1,\mathcal {G}(\textbf{g}_0, \textbf{f}_1)+\textbf{h}_0)$ and verify the equality $c_1{\mathop {=}\limits ^{?}}\textsf{Commit}(\textbf{f}_1,\mathcal {G}(\textbf{g}_0, \textbf{f}_1)+\textbf{h}_0)$.

Assume that $\textsf{SE}$ denotes the soundness error of the scheme; then, we have $\textsf{SE}=1/2 +1/2q$. To achieve the desired security level and reduce impersonation probability, we need to execute the protocol in multiple rounds. The numbers of rounds required to reach the security level of l is given by $\alpha =\left\lceil \frac{l}{\log _2(\textsf{SE})}\right\rceil$.

Fig. 2

Modified version of 5-pass identification protocol of [25]. The only change is that we assume that the public polynomial may have constant terms. Therefore, an additional term $\mathcal {P}(0)$ is added

3.3 General construction of identity-based signature (IBS) [19]

An identity-based signature (IBS) scheme consists of the four algorithms: $\textsf{Setup}$, $\textsf{Extract}$, $\mathsf{Signature~Generation}$ and $\mathsf{Signature~Verification}$:

• $\textsf{Setup} (1^{\kappa })$: On input the security parameter $\kappa$, the secret key generator or key distribution center $\textsf{SKG}$ generates master public key-secret key pair (Mpk, Msk).

• $\textsf{Extract}({ Msk},ID)$: On input Msk and an identity $ID\in \{0,1\}^*$, the $\textsf{SKG}$ runs $\textsf{Extract}$ algorithm for generating the signing key ${\textbf {u}}_{ID}$ corresponding to the user having identity ID.

• $\mathsf{Signature~Generation}({\textbf {u}}_{ID},\textsf{Mg})$: On input ${\textbf {u}}_{ID}$ and message $\textsf{Mg}\in \{0,1\}^*$, the user with identity ID runs $\mathsf{Signature~Generation}$ to generate a signature $\theta$ of $\textsf{Mg}$.

• $\textsf{SignatureVerification}({ Mpk}, \textsf{Mg},\theta , ID)$: On input ${ Mpk}, \textsf{Mg},\theta , ID$, the verifier runs $\mathsf{Signature~Verification}$ to check the correctness of the message-signature pair . If it is a valid pair corresponding to the identity ID, then $\mathsf{Signature~Verification}$ outputs 1; otherwise, outputs 0.

3.4 Existential unforgeability under chosen-message and chosen-identity attack (uf-cma) [10]

The notion of uf-cma is considered as the standard security notion for an IBS. It is defined by a “game”, or an experiment, run between a forger $\textsf{FG}$ and a challenger $\textsf{CH}$. Let us consider an IBS that consists of the algorithms $\textsf{Setup}$, $\textsf{Extract}$, $\mathsf{Signature~Generation}$ and $\mathsf{Signature~Verification}$. Then, the experiment $\textsf{Ex}^{\hbox {uf-cma}}_{IBS(1^{\kappa })}$ is described below:

• The $\textsf{CH}$ runs $\textsf{Setup}(1^{\kappa })$ to generate (Mpk, Msk) and sends Mpk to $\textsf{FG}$.

• The $\textsf{FG}$ adaptively makes a number of following queries to $\textsf{CH}$:

  $\textsf{Extract}\hbox {-}\textsf{query}:$:

  For any $ID\in \{0,1\}^*$, the $\textsf{FG}$ can ask the corresponding secret key to the $\textsf{CH}$. In order to give response, the $\textsf{CH}$ runs $\textsf{Extract}(Msk,ID)$ to extract the secret key $\textbf{u}_{ID}$ and sends it to the $\textsf{FG}$.

  $\textsf{Sign}\hbox {-}\mathsf{query:}$:

  For any $ID\in \{0,1\}^*$ and message $\textsf{Mg}$, the $\textsf{FG}$ can ask the corresponding signature to the $\textsf{CH}$. In order to give response, the $\textsf{CH}$ first runs $\textsf{Extract}(Msk,ID)$ to extract the secret key $\textbf{u}_{ID}$ and then, runs the $\mathsf{Signature~Generation}(\textbf{u}_{ID},\textsf{Mg})$ to get the signature $\theta$, which is sent to $\textsf{FG}$.

• The $\textsf{FG}$ outputs an identity $ID^*$, message $\textsf{Mg}^*$ and a signature $\theta ^*$.

The $\textsf{FG}$ will win the game, i.e., output of the experiment $\textsf{Ex}^{\hbox {uf-cma}}_{IBS(1^{\kappa })}$ will be 1 if $\mathsf{Signature~Verification}(Mpk,\textsf{Mg}^*,\theta ^*,ID^*)=1$ and $\textsf{FG}$ has neither made any $\textsf{Extract}\hbox {-}\textsf{query}$ on $ID^*$ nor made any $\textsf{Sign}\hbox {-}\textsf{query}$ on $(ID^*,\textsf{Mg}^*)$. We denote the advantage or the success probabilityof $\textsf{FG}$ by $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf-cma}}_{IBS(1^{\kappa })}}$ which is defined as $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf-cma}}_{IBS(1^{\kappa })}}$ $=\textsf{Prob}[\textsf{Ex}^{\hbox {uf-cma}}_{IBS(1^{\kappa })}=1]$ $=\textsf{Prob}[\textsf{FG}~wins~the~game]$.

Definition 3.2

An IBS is said to be uf-cma secure if$\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{uf-cma}_{IBS(1^{\kappa })}}$ is negligible in security parameter $\kappa$ for any probabilistic polynomial time (PPT) forger $\textsf{FG}$ who is allowed to make at most $Q_e$ (polynomial time) $\mathsf{Extract-query}$ and $Q_s$ (polynomial time) $\mathsf{Sign-query}$.

4 Proposed multivariate identity-based signature (Mul-IBS)

In this section, we present the multivariate-based IBS, namely Mul-IBS. We take advantage of a multivariate signature scheme together with 5-pass identification scheme as fundamental blocks of our proposed design. We make use of the technique by Hülsing et al. [6] of transforming identification scheme into a signature scheme. The Mul-IBS consists of four algorithms: (i) Setup, (ii) Extract, (iii) Signature Generation, and (iv) Signature Verification. On the input of $\kappa$ (security parameter), the secret key generator $\textsf{SKG}$ runs $\textsf{Setup}$ to produce master public key Mpk and mater secret key Msk. During $\textsf{Extract}$, the $\textsf{SKG}$ generates clients secret key $\textbf{u}_{ID}$ for a client having identity $ID\in \{0,1\}^*$. Given a message $\textsf{Mg}\in \{0,1\}^*$, the algorithm $\mathsf{Signature~Generation}$ is run by a client having identity $ID\in \{0,1\}^*$ and signing key $\textbf{u}_{ID}$ to produce a signature $\theta$. A verifier runs $\mathsf{Signature~Verification}$ on input $(Mpk,\textsf{Mg},\theta ,ID)$ to validate the correctness of the signature $\theta$. A computationally binding and statistically hiding commitment scheme $\textsf{Commit}$ is employed in our Mul-IBS. Refer to Fig. 3 for a workflow diagram of our proposed design.

Protocol 4.1

Mul-IBS

$\textsf{Setup} (1^{\kappa })$:

: The secret key generator $\textsf{SKG}$ runs the algorithm $\mathsf{Key ~Gen}$ on input $1^{\kappa }$ for the underlying MQ-based signature scheme in order to generate master public key $Mpk=\mathcal {P}=S\circ F\circ T:\mathbb {F}_q^n\rightarrow \mathbb {F}_q^m$ and master secret key $Msk=\{S,F,T\}$.

$\textsf{Extract}({ Msk}, ID)$:

: Given Msk and an identity $ID\in \{0,1\}^*$ of an user, the $\textsf{SKG}$

• 1. derives $\textbf{k}_{ID}\in \mathbb {F}_q^m$ by computing $\textsf{Hash}(ID)=\textbf{k}_{ID}$ for some cryptographically secure collision-resistant hash function $\textsf{Hash}:\{0,1\}^*\rightarrow \mathbb {F}_q^m$,

• 2. evaluates $\textbf{u}_{ID}=\mathcal {P}^{-1}({\textbf{k}}_{ID})\in \mathbb {F}_q^n$ using $Msk=\{S,F,T\}$,

• 3. sends $\textbf{u}_{ID}$ as the secret key to the user with identity ID.

$\mathsf{Signature~Generation}({\textbf{u}}_{ID},\textsf{Mg})$: The user with identity ID makes a signature over a message $\textsf{Mg}\in \{0,1\}^*$ with the signing key ${\textbf{u}}_{ID}$ as follows:

• 1. Computes $\textbf{a}=\textsf{Hash}_1(\mathcal {P}||\textsf{Mg})$ using cryptographically secure collision-resistant hash function $\textsf{Hash}_1:\{0,1\}^*\rightarrow \mathbb {F}_q^{m}$.

• 2. Selects $\textbf{f}_{0,1},\ldots ,\textbf{f}_{0,\alpha },\textbf{g}_{0,1},\ldots ,\textbf{g}_{0,\alpha }, \in _R \mathbb {F}_q^{n}, \textbf{h}_{0,1},\ldots ,\textbf{h}_{0,\alpha }\in _R \mathbb {F}_q^{m}$ and for $j=1,\ldots ,\alpha$,

• (a) writes $\textbf{f}_{1,j}={\textbf{u}}_{ID}-\textbf{f}_{0,j}$,

• (b) evaluates $\beta _{0,j}=\textsf{Commit}(\textbf{f}_{0,j},\textbf{g}_{0,j},\textbf{h}_{0,j})$, $\beta _{1,j}=\textsf{Commit}(\textbf{f}_{1,j},\mathcal {G}(\textbf{g}_{0,j},\textbf{f}_{1,j})+\textbf{h}_{0,j})$.

• 3. Sets $\textsf{COMM}=(\beta _{0,1},\beta _{1,1},\ldots ,\beta _{0,\alpha },\beta _{1,\alpha })$

• 4. Computes challenges $\textsf{Hash}_2(\textbf{a}||\textsf{COMM}) =(\delta _1,\ldots ,\delta _{\alpha })\in \mathbb {F}_q^{\alpha }$ for cryptographically secure collision-resistant hash function $\textsf{Hash}_2:\{0,1\}^*\rightarrow \mathbb {F}_q^{\alpha }$.

• 5. Evaluates $\textbf{g}_{1,j}=\delta _j\textbf{f}_{0,j}-\textbf{g}_{0,j}$ and $\textbf{h}_{1,j}=\delta _j{\mathcal {P}}(\textbf{f}_{0,j})-\textbf{h}_{0,j}$ for $j=1,\ldots ,\alpha$.

• 6. Writes $\textsf{Res}_1=(\textbf{g}_{1,1},\textbf{h}_{1,1}\ldots , \textbf{g}_{1,\alpha },\textbf{h}_{1,\alpha })$.

• 7. Computes challenges $\textsf{Hash}_3(\textbf{a}||\textsf{COMM}||\textsf{Res}_1)=(\gamma _1,\ldots ,\gamma _{\alpha })\in \{0,1\}^{\alpha }$ using cryptographically secure collision-resistant hash function $\textsf{Hash}_3:\{0,1\}^*\rightarrow \{0,1\}^{\alpha }$.

• 8. Sets $\textsf{Res}_2=(\textbf{f}_{\gamma _1,1}\ldots ,\textbf{f}_{\gamma _{\alpha },\alpha })$.

• 9. Outputs the signature as $\theta =(\textsf{COMM},\textsf{Res}_1,\textsf{Res}_2)$.

Length of the signature is . If the stipulated security level is l, then the number of rounds, $\alpha$, of the underlying identification scheme is given by

$$\begin{aligned} \alpha \ge \frac{l}{\log _2(1/2+1/2q)}. \end{aligned}$$

$\mathsf{Signature~Verification}(Mpk,\textsf{Mg},\theta ,ID$: The verifier performs the following steps to check the validity of the message-signature pair $(\textsf{Mg},\theta ))$ with respect to the user with identity ID:

• 1. Computes $\textsf{Hash}(ID)=\textbf{k}_{ID}$.

• 2. Evaluates $\textbf{a}=\textsf{Hash}_1(\mathcal {P}||\textsf{Mg})$ and derives challenges $(\delta _1,\ldots ,\delta _{\alpha })=\textsf{Hash}_2(\textbf{a}||\textsf{COMM})\in \mathbb {F}_q^{\alpha }$ and $(\gamma _1,\ldots ,\gamma _{\alpha })=\textsf{Hash}_3(\textbf{a}||\textsf{COMM}||\textsf{Res}_1)\in \{0,1\}^{\alpha }$ utilizing $\textbf{a}$, $\textsf{COMM}$ and $\textsf{Resp}_1$.

• 3. Parses $\textsf{COMM}$ into $(\beta _{0,1},\beta _{1,1},\ldots ,\beta _{0,\alpha },\beta _{1,\alpha })$, $\textsf{Res}_1$ into $(\textbf{g}_{1,1},\textbf{h}_{1,1}\ldots , \textbf{g}_{1,\alpha },\textbf{h}_{1,\alpha })$ and $\textsf{Res}_2$ into $(\textbf{f}_{{\gamma }_1,1},\ldots ,\textbf{f}_{{\gamma }_{\alpha },\alpha })$.

• 4. In order to check that $\textbf{f}_{{\gamma }_j,j}$ is correct response to $\gamma _j$ with respect to $\textsf{COMM}$, $\textbf{g}_{1,j}$ and $\textbf{h}_{1,j}$, verifies the following equalities for each $j=1,\ldots ,\alpha$:

• (a) if $\gamma _j=0$ then

  $$\begin{aligned} \beta _{0,j}{\mathop {=}\limits ^{?}}\textsf{Commit}(\textbf{f}_{{\gamma }_j,j},\delta _j\textbf{f}_{{\gamma }_j,j}-\textbf{g}_{1,j}, \delta _j{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j}) -\textbf{h}_{1,j}) \end{aligned}$$

• (b) for $\gamma _j=1$,

$$\begin{aligned}{} & {} \beta _{1,j}{\mathop {=}\limits ^{?}}\textsf{Commit}(\textbf{f}_{{\gamma }_j,j},\delta _j(\textbf{k}_{ID}-{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j})+ {\mathcal {P}}(\textbf{0})) \\ {}{} & {} - \mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{{\gamma }_j,j})-\textbf{h}_{1,j}) \end{aligned}$$

• 5. The message-signature pair $(\textsf{Mg},\theta )$ is accepted, i.e., $\mathsf{Signature~Verification}(Mpk,\textsf{Mg},\theta ,ID)=1$ if all the equalities hold, otherwise rejected, i.e., $\mathsf{Signature~Verification}(Mpk,\textsf{Mg},\theta ,ID)=0$.

Correctness: We now give the correctness of the Mul-IBS by proving that the following equalities in the step 4 of $\mathsf{Signature~ Verification}$ algorithm hold:

$$\begin{aligned}{} & {} \hbox {for}~ \gamma _j=0,\nonumber \\{} & {} \beta _{0,j}=\textsf{Commit}(\textbf{f}_{{\gamma }_j,j},\delta _j\textbf{f}_{{\gamma }_j,j}\nonumber \\{} & {} -\textbf{g}_{1,j},\delta _j{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j}) -\textbf{h}_{1,j})\nonumber \\{} & {} \\{} & {} \hbox {for}~\gamma _j=1,\nonumber \\{} & {} \beta _{1,j}=\textsf{Commit}(\textbf{f}_{{\gamma }_j,j},\delta _j(\textbf{k}_{ID}-{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j})+ {\mathcal {P}}(\textbf{0}))\nonumber \\{} & {} -\mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{{\gamma }_j,j})-\textbf{h}_{1,j}),\nonumber \\{} & {} \end{aligned}$$

(4.1)

where $j=1,\ldots ,\alpha$. Let us consider the following two cases:

• Case I: Suppose $\gamma _j=0$. Then $\textbf{f}_{{\gamma }_j,j}=\textbf{f}_{0,j}$. Therefore, $\delta _j\textbf{f}_{{\gamma }_j,j}-\textbf{g}_{1,j}=,\delta _j\textbf{f}_{0,j}-\textbf{g}_{1,j}=\textbf{g}_{0,j}$ and $\delta _j{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j})-\textbf{h}_{1,j}= \delta _j{\mathcal {P}}(\textbf{f}_{0,j})-\textbf{h}_{1,j}=\textbf{h}_{0,j}$. Hence, we may conclude that for each $j=1,\ldots ,\alpha$, the Eq. 4.1 holds.

• Case II: Let $\gamma _j=1$. Then, $\textbf{f}_{{\gamma }_j,j}=\textbf{f}_{1,j}$. Therefore,

  $$\begin{aligned}{} & {} \delta _j(\textbf{k}_{ID}-{\mathcal {P}}(\textbf{f}_{{\gamma }_j,j})+ {\mathcal {P}}(\textbf{0}))- \mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{{\gamma }_j,j})-\textbf{h}_{1,j}\nonumber \\{} & {} =\delta _j({\mathcal {P}}({\textbf{u}}_{ID})-{\mathcal {P}}(\textbf{f}_{1,j})+ {\mathcal {P}}(\textbf{0}))- \mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{1,j})-\textbf{h}_{1,j}\nonumber \\{} & {} =\delta _j({\mathcal {P}}(\textbf{f}_{0,j}+\textbf{f}_{1,j})-{\mathcal {P}}(\textbf{f}_{1,j})+ {\mathcal {P}}(\textbf{0}))\nonumber \\{} & {} -\mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{1,j})-\textbf{h}_{1,j}~\hbox {since}~ {\textbf{u}}_{ID}\nonumber \\{} & {} =\textbf{f}_{0,j}+\textbf{f}_{1,j}\nonumber \\{} & {} =\delta _j({\mathcal {P}}(\textbf{f}_{0,j})+\mathcal {G}(\textbf{f}_{0,j},\textbf{f}_{1,j}))- \mathcal {G}(\textbf{g}_{1,j},\textbf{f}_{1,j})-\textbf{h}_{1,j}\nonumber \\{} & {} =\mathcal {G}(\delta _j\textbf{f}_{0,j}-\textbf{g}_{1,j},\textbf{f}_{1,j}) +\delta _j{\mathcal {P}}(\textbf{f}_{0,j})-\textbf{h}_{1,j}\nonumber \\{} & {} =\mathcal {G}(\textbf{g}_{0,j},\textbf{f}_{1,j})+\textbf{h}_{0,j}\nonumber \end{aligned}$$

  (4.2)

Thus, for each $j=1,\ldots ,\alpha$, the Eq. 4.2 holds.

Fig. 3

Workflow diagram of Mul-IBS

5 Security

Theorem 5.1

The proposed Mul-IBS is uf-cma secure in the random oracle model under the hardness of MQ problem, if

• (i) the commitment scheme $\textsf{Commit}$ is computationally binding and perfectly hiding,

• (ii) the hash functions $\textsf{Hash}$, $\textsf{Hash}_1$, $\textsf{Hash}_2$ and $\textsf{Hash}_3$ are designed as random oracles.

Proof

We now show that the proposed Mul-IBS possesses uf-cma security under the hardness of the MQ assumption by the method of contradiction. Let us consider a forger $\textsf{FG}$ with non-negligible success probability in the uf-cma game for Mul-IBS. We will prove that it is possible to design an oracle machine ${\mathcal {O}}^\textsf{FG}$ for solving the MQ problem by using $\textsf{FG}$ and managing outputs of the random oracles $\textsf{Hash}$, $\textsf{Hash}_1$, $\textsf{Hash}_2$ and $\textsf{Hash}_3$ in a series of games $\textbf{Game}_0,\ldots ,\textbf{Game}_6$. Here $\textbf{Game}_i$ slightly modifies $\textbf{Game}_{i-1}$ for $i=1,\ldots ,6$. In the game $\textbf{Game}_i$, $\textsf{Prob}[\textbf{Game}_i]$ is considered as $\textsf{FG}$’s success probability $\textsf{FG}$.

$\textbf{Game}_0:$:

$\textbf{Game}_0$ corresponds to uf-cma game for Mul-IBS. Thereby, $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}}$ $=\textsf{Prob}[\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}=1]=\textsf{Prob}[\textbf{Game}_0]$

$\textbf{Game}_1:$:

It is identical to $\textbf{Game}_0$, except that during $\textsf{Extract}\hbox {-}\textsf{query}$, ${\mathcal {O}}^\textsf{FG}$ substitutes the output of the random oracle $\textsf{Hash}$ query of $ID\in \{0,1\}^*$ by $\textbf{k}=P(\textbf{u})\in \mathbb {F}_q^{m}$ and the corresponding secret key by $\textbf{u}$ for randomly chosen $\textbf{u}\in \mathbb {F}_q^n$. Note that if $|\textsf{Prob}[\textbf{Game}_1]-\textsf{Prob}[\textbf{Game}_0]|$ is non-negligible, then $\textsf{FG}$ can be utilized for distinguishing $\textsf{Hash}$’s output distributions, which is impossible. Consequently, there exists negligible function $\epsilon _1(\kappa )$ such that $|\textsf{Prob}[\textbf{Game}_1]-\textsf{Prob}[\textbf{Game}_0]|=\epsilon _1(\kappa )$.

$\textbf{Game}_2:$:

$\textbf{Game}_2$ is analogues to $\textbf{Game}_1$ apart from the fact that during $\textsf{Sign}\hbox {-}\textsf{query}$, the oracle ${\mathcal {O}}^\textsf{FG}$ replaces the output of $\textsf{Hash}$ of $ID\in \{0,1\}^*$ by $\textbf{k}=P(\textbf{u})\in \mathbb {F}_q^{m}$ and the signature by $\sigma$ which is generated using secret key $\textbf{u}$ for the system $\textbf{k}=P(\textbf{u})$. Note that one may use $\textsf{FG}$ for distinguishing $\textsf{Hash}$’s distributions if $|\textsf{Prob}[\textbf{Game}_2]-\textsf{Prob}[\textbf{Game}_1|$ is non-negligible. This is impossible. As a consequence, $|\textsf{Prob}[\textbf{Game}_2]-\textsf{Prob}[\textbf{Game}_1]|=\epsilon _2(\kappa )$, where $\epsilon _2(\kappa )$ is a negligible function.

$\textbf{Game}_3:$:

It is equivalent to $\textbf{Game}_2$ excepting ${\mathcal {O}}^\textsf{FG}$ substitutes $\textsf{Hash}_1$’s output by randomly chosen bit-string. Note that one may use $\textsf{FG}$ for distinguishing $\textsf{Hash}_1$’s distributions if $|\textsf{Prob}[\textbf{Game}_3]-\textsf{Prob}[\textbf{Game}_2|$ is non-negligible. This is impossible. Note that if $|\textsf{Prob}[\textbf{Game}_3]-\textsf{Prob}[\textbf{Game}_2]|$ is non-negligible then $\textsf{FG}$ may be utilized for distinguishing $\textsf{Hash}_1$’s output distributions, which is impossible. Thus, there exists negligible function $\epsilon _3(\kappa )$ such that $|\textsf{Prob}[\textbf{Game}_3]-\textsf{Prob}[\textbf{Game}_2]|=\epsilon _3(\kappa )$.

$\textbf{Game}_4:$:

$\textbf{Game}_4$ is identical to $\textbf{Game}_3$ apart from the fact that ${\mathcal {O}}^\textsf{FG}$ replaces $\textsf{Hash}_2$’s output by randomly selected element from $\mathbb {F}_q^{\alpha }$. Note that one can utilize $\textsf{FG}$ for distinguishing $\textsf{Hash}_2$’s distributions if $|\textsf{Prob}[\textbf{Game}_4]-\textsf{Prob}[\textbf{Game}_3|$ is non-negligible. This is impossible. Thereby, for some non-negligible function $\epsilon _4(\kappa )$, we can write $|\textsf{Prob}[\textbf{Game}_4]-\textsf{Prob}[\textbf{Game}_3]|=\epsilon _4(\kappa )$.

$\textbf{Game}_5:$:

It is analogues to $\textbf{Game}_4$ excepting ${\mathcal {O}}^\textsf{FG}$ substitutes $\textsf{Hash}_3$’s output by randomly chosen $\alpha$-length bit-string. Note that if $|\textsf{Prob}[\textbf{Game}_5]-\textsf{Prob}[\textbf{Game}_4]|$ is non-negligible, then $\textsf{FG}$ can be utilized for distinguishing $\textsf{Hash}_3$’s output distributions, which is impossible. As a consequence, there exists some negligible function $\epsilon _5(\kappa )$ such that $|\textsf{Prob}[\textbf{Game}_5]-\textsf{Prob}[\textbf{Game}_4]|=\epsilon _5(\kappa )$.

$\textbf{Game}_6:$:

$\textbf{Game}_2$ identical to $\textbf{Game}_5$ excepting ${\mathcal {O}}^\textsf{FG}$ replaces $\textsf{Hash}$ query on $ID^*$ using randomly chosen $\textbf{k}^*\in \mathbb {F}_q^{m}$, the output of $\textsf{Hash}_1$ by randomly selected bit-string, $\textsf{Hash}_2$’s output by randomly chosen element from $\mathbb {F}_q^{\alpha }$ and $\textsf{Hash}_3$’s using $\alpha$-length randomly selected bit-string. We can argue that $|\textsf{Prob}[\textbf{Game}_6]-\textsf{Prob}[\textbf{Game}_5]|=\epsilon _6(\kappa )$ (negligible function) by taking into account the arguments of $\textbf{Game}_2$, $\textbf{Game}_3$, $\textbf{Game}_4$ and $\textbf{Game}_5$, we can argue that $|\textsf{Prob}[\textbf{Game}_6]-\textsf{Prob}[\textbf{Game}_5]|=\epsilon _6(\kappa )$ for some negligible function $\epsilon _6(\kappa )$.

Therefore,

$$\begin{aligned}{} & {} |\textsf{Prob}[\textbf{Game}_6]-\textsf{Prob}[\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}=1]| \nonumber \\{} & {} =|\textsf{Prob}[\textbf{Game}_6]-\textsf{Prob}[\textbf{Game}_0]|\\{} & {} \le |\textsf{Prob}[\textbf{Game}_6]-\textsf{Prob}[\textbf{Game}_5]| \nonumber \\{} & {} +|\textsf{Prob}[\textbf{Game}_5]-\textsf{Prob}[\textbf{Game}_4]|\\{} & {} +|\textsf{Prob}[\textbf{Game}_4]-\textsf{Prob}[\textbf{Game}_3]| \nonumber \\{} & {} +|\textsf{Prob}[\textbf{Game}_3]-\textsf{Prob}[\textbf{Game}_2]|\\{} & {} +|\textsf{Prob}[\textbf{Game}_2]-\textsf{Prob}[\textbf{Game}_1]| \nonumber \\{} & {} +|\textsf{Prob}[\textbf{Game}_1]-\textsf{Prob}[\textbf{Game}_0]|\\{} & {} =\epsilon _6(\kappa )+\epsilon _5(\kappa ) \nonumber \\{} & {} +\epsilon _4(\kappa )+\epsilon _3(\kappa )+\epsilon _2(\kappa ) \epsilon _1(\kappa )=\rho (\kappa ) (\hbox {negligible function})), \end{aligned}$$

Thereby, $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}}$ $=\textsf{Prob}[\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}=1]$ is identical to $\textsf{Prob}[\textbf{Game}_6]$ of $\textsf{FG}$ in the game $\textbf{Game}_6$. Hence, $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf{-}cma}}_{Mul\hbox {-}IBS(1^{\kappa })}}$ is non-negligible implies $\textsf{Prob}[\textbf{Game}_6]$ non-negligible.

If possible, let $\textsf{Prob}[\textbf{Game}_6]$ be non-negligible. We now prove that ${\mathcal {O}}^\textsf{FG}$ can easily solve the MQ problem by finding a solution $\textbf{u}^*$ of the system $\textbf{k}^*=P(\textbf{x})$ with the help $\textsf{FG}$.

• 1. The oracle machine ${\mathcal {O}}^\textsf{FG}$ generates four valid transcripts $(\textsf{COMM}, \Delta ^{(i)},\textsf{Res}^{(i)}_1,{\Gamma }^{(j)},\textsf{Res}^{(i,j)}_2)_{\{i,j=0,1\}}$ with the help of $\textsf{FG}$ and controlling the output of random oracles $\textsf{Hash}$, $\textsf{Hash}_1$, $\textsf{Hash}_2$ and $\textsf{Hash}_3$, where

  $$\begin{aligned}{} & {} \textsf{COMM}=(\beta _{0,1},\beta _{1,1},\ldots ,\beta _{0,\alpha },\beta _{1,\alpha })\nonumber \\{} & {} \Delta ^{(i)}=\{\delta ^{(i)}_1,\ldots ,\delta ^{(i)}_{\alpha }\} ~\hbox {with}~\delta ^{(0)}_{l}\ne \delta ^{(1)}_{\alpha } ~\hbox {for}~l=1,\ldots ,\alpha \nonumber \\{} & {} \textsf{Res}^{(i)}_1 =(\textbf{g}^{(i)}_{1,1},\textbf{h}^{(i)}_{1,1},\ldots ,\textbf{g}^{(i)}_{1,\alpha }, \textbf{h}^{(i)}_{1,\alpha })\nonumber \\{} & {} {\Gamma }^{(j)}=(\gamma ^{(j)}_1,\ldots ,\gamma ^{(j)}_{\alpha }) ~\hbox {with}~ \gamma ^{(j)}_l\nonumber \\{} & {} =j\in \{0,1\} ~\hbox {for}~ l=1,\ldots ,\alpha \nonumber \\{} & {} \textsf{Res}^{(i,j)}_2=(\textbf{f}_{j,1}^{(i)},\ldots ,\textbf{f}_{j,\alpha }^{(i)})\nonumber \end{aligned}$$

  (5.1)

• 2. Note that for $l=1,\ldots ,\alpha$,

  $$\begin{aligned}{} & {} \beta _{0,l}=\textsf{Commit}\left( \textbf{f}^{(0)}_{0,l},~\delta ^{(0)}_{l}\textbf{f}^{(0)}_{0,l}-\textbf{g}^{(0)}_{1,l},~ \delta ^{(0)}_{l}{\mathcal {P}}(\textbf{f}^{(0)}_{0,l})-\textbf{h}^{(0)}_{1,l}\right) \nonumber \\{} & {} =\textsf{Commit}\left( \textbf{f}^{(1)}_{0,l},~\delta ^{(1)}_{l}\textbf{f}^{(1)}_{0,l}-\textbf{g}^{(1)}_{1,l},~ \delta ^{(1)}_l{\mathcal {P}}(\textbf{f}^{(1)}_{0,l})-\textbf{h}^{(1)}_{1,\rho }\right) \\{} & {} \beta _{1,l}=\textsf{Commit}\left( \textbf{f}^{(0)}_{1,l},~ \delta ^{(0)}_{l}(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,l})+{\mathcal {P}}(\textbf{0})) \right. \nonumber \\{} & {} \left. -\mathcal {G}(\textbf{g}^{(0)}_{1,l},\textbf{f}^{(0)}_{1,l})-\textbf{h}^{(0)}_{1,l}\right) \nonumber \\{} & {} =\textsf{Commit}\left( \textbf{f}^{(1)}_{1,l},~ \delta ^{(1)}_{l}(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(1)}_{1,l})+{\mathcal {P}}(\textbf{0})) \right. \nonumber \\{} & {} \left. -\mathcal {G}(\textbf{g}^{(1)}_{1,l},\textbf{f}^{(1)}_{1,l})-\textbf{h}^{(1)}_{1,l}\right) \end{aligned}$$

  (5.2)

• 3. Using the computationally binding property of the commitment scheme $\textsf{Comit}$, we argue that the arguments of $\textsf{Commit}$ for $\beta _{0,l}$ are equal in 5.2. Similarly, the arguments of $\textsf{Commit}$ for $\beta _{1,l}$ are equal in 5.2 due to the binding property of $\textsf{Commit}$. Thus, we have

  $$\begin{aligned}{} & {} \textbf{f}^{(0)}_{0,l}=\textbf{f}^{(1)}_{0,l} \end{aligned}$$

  (5.3)
  $$\begin{aligned}{} & {} \delta ^{(0)}_{l}\textbf{f}^{(0)}_{0,l}-\textbf{g}^{(0)}_{1,l} =\delta ^{(1)}_{l}\textbf{f}^{(1)}_{0,l}-\textbf{g}^{(1)}_{1,l} \end{aligned}$$

  (5.4)
  $$\begin{aligned}{} & {} \delta ^{(0)}_{l}{\mathcal {P}}(\textbf{f}^{(0)}_{0,l})-\textbf{h}^{(0)}_{1,l} = \delta ^{(1)}_l{\mathcal {P}}(\textbf{f}^{(1)}_{0,l})-\textbf{h}^{(1)}_{1,l} \end{aligned}$$

  (5.5)
  $$\begin{aligned}{} & {} \textbf{f}^{(0)}_{1,l}=\textbf{f}^{(1)}_{1,l} \end{aligned}$$

  (5.6)
  $$\begin{aligned}{} & {} \delta ^{(0)}_{l}(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,l})+{\mathcal {P}}(\textbf{0})) -\mathcal {G}(\textbf{g}^{(0)}_{1,l},\textbf{f}^{(0)}_{1,l})-\textbf{h}^{(0)}_{1,l}\nonumber \\{} & {} =\delta ^{(1)}_{l}(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(1)}_{1,l})+{\mathcal {P}}(\textbf{0})) -\mathcal {G}(\textbf{g}^{(1)}_{1,l},\textbf{f}^{(1)}_{1,l})-\textbf{h}^{(1)}_{1,l} \nonumber \\ \end{aligned}$$

  (5.7)

• 4. From Eqs. 5.6 and 5.7,

  $$\begin{aligned}{} & {} (\delta ^{(0)}_{l}-\delta ^{(1)}_{l})(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,l})+ {\mathcal {P}}(\textbf{0}))\nonumber \\{} & {} =\mathcal {G}(\textbf{g}^{(0)}_{1,l},\textbf{f}^{(0)}_{1,l}) -\mathcal {G}(\textbf{g}^{(1)}_{1,l},\textbf{f}^{(1)}_{1,l}) +\textbf{h}^{(0)}_{1,l}-\textbf{h}^{(1)}_{1,l}\nonumber \\{} & {} \Rightarrow (\delta ^{(0)}_{l}-\delta ^{(1)}_{l})(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,\rho }) +{\mathcal {P}}(\textbf{0})) \nonumber \\{} & {} =\mathcal {G}(\textbf{g}^{(0)}_{1,l}-\textbf{g}^{(1)}_{1,l},\textbf{f}^{(0)}_{1,l}) +\textbf{h}^{(0)}_{1,l}-\textbf{h}^{(1)}_{1,l} \end{aligned}$$

  (5.8)

• 5. From 5.3, 5.4, 5.5 and 5.8

  $$\begin{aligned}{} & {} (\delta ^{(0)}_{l}-\delta ^{(1)}_{l})(\textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,l}) +{\mathcal {P}}(\textbf{0})) \nonumber \\{} & {} =\mathcal {G}((\delta ^{(0)}_{l}-\delta ^{(1)}_{l})\textbf{f}^{(0)}_{0,l},\textbf{f}^{(0)}_{1,l}) +(\delta ^{(0)}_{l}-\delta ^{(1)}_{l}){\mathcal {P}}(\textbf{f}^{(0)}_{0,l})~\\{} & {} \Rightarrow \textbf{k}^*-{\mathcal {P}}(\textbf{f}^{(0)}_{1,l})+{\mathcal {P}}(\textbf{0}) \nonumber \\{} & {} =\mathcal {G}(\textbf{f}^{(0)}_{0,l},\textbf{f}^{(0)}_{1,l})+{\mathcal {P}}(\textbf{f}^{(0)}_{0,l}) ~\hbox {since}~\delta ^{(0)}_{l}\ne \delta ^{(1)}_{l}\\{} & {} \Rightarrow \textbf{k}^*={\mathcal {P}}(\textbf{f}^{(0)}_{1,l}) +\mathcal {G}(\textbf{f}^{(0)}_{0,l},\textbf{f}^{(0)}_{1,l}) +{\mathcal {P}}(\textbf{f}^{(0)}_{0,l})-{\mathcal {P}}(\textbf{0})\\{} & {} ={\mathcal {P}}(\textbf{f}^{(0)}_{0,l}+\textbf{f}^{(0)}_{1,l}) \end{aligned}$$

• 6. Hence, the oracle machine ${\mathcal {O}}^\textsf{FG}$ extracts a solution $\textbf{f}^{(0)}_{0,l}+\textbf{f}^{(0)}_{1,l}$ of $\textbf{k}^*=\overline{\mathcal {P}}(x)$

Thus, $\textsf{Prob}[\textbf{Game}_6]$ is non-negligible implies ${\mathcal {O}}^\textsf{FG}$ is able to determine a solution of the MQ problem $\textbf{k}^*=\overline{\mathcal {P}}(x)$. It contradicts the assumption that MQ problem is NP-hard. Consequently, $\textsf{Prob}[\textbf{Game}_6]$ is negligible, which ensures $\textsf{Adv}_\textsf{FG}^{\textsf{Ex}^{\hbox {uf-cma}}_{Mul\hbox {-}IBS(1^{\kappa })}}$ $=\textsf{Prob}[\textsf{Ex}^{\hbox {uf-cma}}_{Mul\hbox {-}IBS(1^{\kappa })}=1]$ is negligible. Therefore, we conclude that the proposed Mul-IBS is uf-cma secure. $\square$

6 Efficiency analysis

In this part, we discuss our scheme’s communication, storage and computation complexity. Size of Mpk and Msk are, respectively, $\frac{m(n+2)(n+1)}{2}$ and $n^2+m^2+c$ field ($\mathbb {F}_q$) elements, c being the size of the central map. The user’s identity and secret key sizes are m and n field ($\mathbb {F}_q$) elements, respectively. Moreover, the signature size is 2$\alpha$ $|\textsf{Commit}|$+ $\alpha (m+2n)$-$\mathbb {F}_q$ elements. The round complexity of our scheme is 2, one for $\textsf{Extract}$ algorithm to send the user’s secret key and one for $\mathsf{Signature~Generation}$ algorithm to send the signature. The signer evaluates the system $\mathcal {P}$ $3\alpha$ times for the computation of $\mathcal {G}$ in $\beta _{1,j}$ and $\alpha$ times for the computation of $\textbf{h}_{1,j}$. While the verifier needs to compute the system $\mathcal {P}$ around $(1+4)\alpha /2$, i.e., $2.5\alpha$ times. Thus, the total number of executions of the system $\mathcal {P}$ is approximately $6.5\alpha$. To evaluate the system $\mathcal {P}$, one has to perform $m(n^4+n)$ modulo multiplications. Therefore, we require total $\alpha (n^4+n)$ modulo multiplications for signature generation and verification.

We direct to Table 1 for a comparative summary of the proposed design with multivariate IBS in the current state of the art in terms of signature size, master public key (verification key) size, signer’s secret key size, user’s identity size, and master secret key size for 128-bit security level over GF(256). Let us write Mul-IBS-Rainbow $(q,v,o_1,o_2,\alpha )$ for denoting that Rainbow with parameter $(q,v,o_1,o_2,\alpha )$ is used in our scheme and Mul-IBS-UOV $(q,o,v,\alpha )$ for denoting that UOV with parameter $(q,o,v,\alpha )$ is used in our scheme. Here, $\alpha$ denotes the number of rounds. Using the result stated in Sect. 3.2, we may choose the number of rounds for a 128-bit security level over GF(256) as 129. We follow [20] for selecting parameters of the underlying signature in our scheme. While, for the existing schemes [5, 15, 27], we follow their respective parameter representations. We instantiate the output lengths of the commitment scheme with SHA3-256 in our Mul-IBS. However, one may use a weaker commitment scheme to reduce the signature size.

Table 1 Comparison for 128-bit security level over GF(256)

We compare the time complexity of Mul-IBS in terms of signature generation and verification time for 80-bit security level over the field GF(256). We implemented Mul-IBS in SageMath¹ The hardware configuration is a workspace with an Intel Core i7-8700 3.20GHz processor with 8GB of RAM and a 64-bit operating system. We make use of Rainbow with parameters (256, 18, 17, 9) [20] as the underlying multivariate signature scheme. Results are summarized in Table 2.

Table 2 Comparison of time complexity for 80-bit security level over GF(256)

Table 3 List of notations and symbols used in the article

Remark

We want to point out that our proposed design is a generic IBS. Any secure multivariate signature scheme can be used to instantiate the protocol Mul-IBS . If in future, the multivariate signature scheme employed to instantiate Mul-IBS becomes insecure, it can be very easily replaced by some other secure MQ-signature scheme. In short, the proposed design is not based on the internal structure of the multivariate signature scheme (like Rainbow, UOV, etc.). The multivariate signature scheme is only used to generate the key pair ${\mathcal {P}, (\mathcal {S},\mathcal {F},\mathcal {T})}$. The recent key recovery attack [2] on Rainbow renders all the instantiation based on Rainbow insecure. To circumvent the attack, we can either choose different set of parameters or replace Rainbow by some other multivariate signature scheme.

7 Application of Mul-IBS in IoT-Based NDN Architecture

In this section, we will see how Mul-IBS can be employed in IoT-based NDN architecture to prevent content poisoning attacks. First, we briefly describe the content poisoning attack (refer to Fig. 4). Let Michael be a client who is interested in some content, say $\mathsf{\Gamma }$. His interest request (shown by black arrow) is transferred to the original publisher of the content. Due to the LCE caching policy, the response sent by the publisher (indicated by green color) is cached by the intermediate routers for future use (here Router-D, Router-E, and Router-C). Suppose an adversary takes charge of the Router-C and introduces poisoned content with a counterfeit signature. Suppose another user, John, tied up with Router-C, exhibits interest (shown by yellow color) for $\Gamma$. In that case, the local router (Router-C) will serve the interest of John instead of forwarding it again to the publisher. But since the content cached in Router-C is poisoned, John will receive the maligned copy of $\Gamma$. In addition to that, Router-A and Router-B will also store the poisonous content due to the LCE caching policy of NDN.

Fig. 4

Content poisoning attack in IoT-based NDN systems

Now, we will see how Mul-IBS can be employed in IoT-based NDN architecture to prevent content poisoning attacks. In the first step, content providers and users submit their identities to the network executive to complete the registration process. Network-executive generates public and secret keys for the users and providers using Extract. Suppose a user named Michael displays his interest in some content, say $\mathsf{\Delta }$. As soon as the interest request is received, routers in NDN dispatch the particular interest to the content publisher. After receiving the interest, the content provider uses a cryptographically secure hash like SHA3-256 on $\Delta$ to get the checksum (chk). In the following, the content publisher uses his secret key to generate a digital signature for chk with the help of the algorithm Signature Generation. After that, the requested content is distributed to the user along with the provider’s signature sign-chk and checksum chk. NDN architecture follows a leave copy everywhere (LCE) caching policy. Therefore, content requested by Michael, i.e., $\mathsf{\Delta }$, is stored in router-C, Router-D, and Router-E caches. Now, imagine a situation where an attacker $\mathsf{\mathcal {Z}}$ poisoned $\mathsf{\Delta }$ in Router-C. Suppose John also displays his interest for $\mathsf{\Delta }$, and his interest request is obtained at Router-C. Since at Router-C, $\mathsf{\Delta }$ is already poisoned by $\mathsf{\mathcal {Z}}$, a poisoned copy will be received by John. If John wants to ensure whether he has received the right content, he proceeds as follows. First, he asks the network executive for the original provider’s public key. With the help of the public key of the broadcaster, John attempts to verify the signature sign-chk using Signature Verification. If the Signature Verification outputs 1, then John concludes that the content provider is registered with NE and authentic.

Post-authentication, if John wishes to confirm the integrity of $\mathsf{\Delta }$, he uses secure hash SHA3-256 on $\mathsf{\Delta }$ to obtain $\mathsf{chk_1}$. If chk is equal to $\mathsf{chk_1}$, John concludes that received content $\mathsf{\Delta }$ is not poisoned. In case chk is not equal to $\mathsf{chk_1}$, John concludes that content has been poisoned. To remove the poisoned content from the network, John proceeds as follows. Using a secure multivariate encryption scheme like ABC [29], and the public key of the original content publisher, John encrypts the poisoned $\mathsf{\Delta }$ and $\mathsf{chk_1}$ and dispatch it to the publisher. Broadcaster decrypts with the help of his secret key and compares $\mathsf{chk, chk_1 }$. In the end, the publisher disseminates a message regarding the poisoned content, which is then removed from the caches of the router. Mul-IBS, being a very lightweight signature scheme, is ideal for IoT systems. It mitigates the threat of content poisoning with solid security guarantees and with modest and inexpensive computing resources. Verifying a signature generated by Mul-IBS requires only doing field multiplications and additions. Due to this low verification overhead, our proposed design addresses the threat of content poisoning with low latency. The lightweight nature of Mul-IBS also ensures that caches remain clean from invalid content. The proposed design Mul-IBS can be utilized as a key cryptographic building block to build a robust and resilient IoT-based NDN architecture. Our scheme is provably secure in the random oracle model. It is built on the hardness assumption of the MQ problem; thus, it also provides safety against attacks by quantum computers. Mul-IBS presents an economical yet efficient solution for resource-constrained IoT networks.

8 Conclusion

In this paper, we constructed a provably secure multivariate IBS, namely Mul-IBS utilizing a secure MPKC signature scheme accompanying a 5-pass identification scheme of [25] as its building blocks. Our construction performs better over the existing multivariate IBS in terms of master public key size, user secret key size, and master secret key size. In contrast to [5, 27], our scheme achieves uf-cma security using random oracles. Mathematical operations used in multivariate cryptographic schemes are elementary, and the most used mathematical operations are addition and multiplications over finite fields. Hence, Mul-IBS is very fast and inexpensive. The Mul-IBS, a very lightweight signature scheme, is ideal for IoT systems. It mitigates the threat of content poisoning with strong security guarantees and modest and inexpensive computing resources. The lightweight nature of Mul-IBS also ensures that caches remain clean from invalid content. The proposed design Mul-IBS can be utilized as a key cryptographic building block to build a robust and resilient IoT-based NDN system.