# A Privacy Preserving Authentication Scheme for Heterogeneous Industrial Internet of Things

Authors: Zuowen Tan; Jintao Jiao; Mengjiang Yu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Nowadays, the industrial Internet of Things (IIoT) is playing a promising role in the optimization of industrial systems. IIoT devices generate a great amount of data that could be used for different applications. Due to the untrusted nature of machine-to-machine (M2M) communication channels, data authenticity and integrity are an important issue that must be addressed. Especially, it is challenging to deal with the privacy disclosure that the heterogeneity of IIoT brings about. In this paper, we propose a privacy-preserving scheme for authenticity in heterogeneous IIoT systems. Our authentication schemes support many kinds of IIoT devices with multicryptographic configurations such as RSA-based, DL-based, ECC-based, and lattice-based cryptosystems. We provide the formalized proof of the unforgeability and privacy of the proposed schemes in the random oracle model. The experimental simulation demonstrates that the proposed schemes are feasible in the heterogeneous IIoT environment.


---

## Body

## 1. Introduction

With the great increment of smart devices, the Internet of Things (IoT) has made tremendous changes in the way people live. Smart devices in the IoT can connect with each other and exchange information with each other. Among all fields of the IoT, the industrial IoT (IIoT) is the most important one [1]. IIoT has the characteristics of real-time, automation, information interconnection, and so on. By introducing many kinds of sensors, wireless communications, artificial intelligence, and other technologies into the industrial production process, IIoT has greatly improved productivity and quality. Meanwhile, the production costs and resource consumption are reduced, and the intelligence degree of the traditional industry has been promoted to a higher level. Despite its great convenience, one of the major obstacles to widely adopting IIoT is its security risks [2]. Since the IIoT is a network with highly coupled heterogeneous devices, the industries are mostly concerned with the integrity and authenticity of the data which is generated and transmitted by the IIoT devices. In most cases, the IIoT data are transmitted via a public channel. These data are easily intercepted by the adversary. Hence, it is essential to ensure that the data are from legal devices, and the data are not tampered with by a malicious adversary.Signature schemes are usually used to ensure integrity and authenticity. Nevertheless, since the nature of the existing signature schemes is homogeneous, most of them can only provide data authenticity in a single cryptosystem. Due to the heterogeneity of IIoT, multiple cryptographic systems are always applied for data authenticity [3, 4], and such cryptographic systems are usually based on RSA, DL, and ECC. In addition, due to the consideration of postquantum security, a cryptographic system based on lattice has already been implemented in IIoT [5]. On the other hand, the privacy of the data sender in IIoT is very important under many circumstances. If the public key is used to verify the validity of the signature, the privacy of the sender’s identity will be leaked.


### 1.1. Motivation

Due to the complexity of practical network architecture in the IIoT environment, it is urgent to design an authentication scheme for the heterogeneous IIoT systems with distinct cryptosystems. Li et al. [6] proposed the SAMA scheme which considers the situation that the devices in IIoT use the same cryptographic configuration. However, it is quite possible that devices in IIoT networks may use different kinds of cryptographic systems. In order to remove this limitation, Wei et al. [7] propose an improved authentication scheme with different system parameters (hereafter, called improved SAMA). However, the improved SAMA scheme only considers the RSA nodes and DL nodes. In fact, there are more devices that adopt other cryptosystems, such as the elliptical cryptosystem. In recent years, more and more attention is paid to postquantum cryptographic algorithms. The threat from quantum computers will emerge in the future, so antiquantum attack cryptographic algorithms have attracted great attention [8]. Some researchers such as Paul and Guerin [9] and Zhang et al. [10] have already conducted a lot of research on postquantum cryptography to secure IIoT. Among the existed postquantum cryptographies, lattice-based cryptography brings the advantage of high-security guarantees and performance efficiency.In addition, privacy is another major concern in IIoT [11]. To the best of our knowledge, privacy issues in IIoT have not been treated very well in the existing literature, which is a potentially fatal threat. When the IIoT devices transmit data through communication channels, the adversaries could intercept the messages and reveal the identities of the devices.Motived by the above limitations, we propose novel message authentication schemes with more kinds of nodes compared with the improved SAMA scheme. Our scheme allows the devices in the IIoT to use RSA-based systems, ElGamal-based systems, ECC-based systems, and quantum cryptography. We also consider the privacy preservation of the IIoT devices while the scheme can provide data authenticity. In order to achieve these two goals at the same time, we chose the ring signature to design the authentication schemes in the heterogeneous IIoT environment.


### 1.2. Contribution

We construct novel authentication schemes over a multicryptosystem (hereafter, called ASMC) for the heterogeneous IIoT environment. The main contributions of this paper are as follows:(1)
We propose two ASMC schemes that support heterogeneous devices with multicryptographic configurations such as RSA-based, DL-based, ECC-based, and lattice-based cryptosystems. This solution brings greater flexibility to the authentication for heterogeneous IIoT. Moreover, the ASMC scheme can provide the devices with strong privacy protection.(2)
Based on the hardness assumption of the complex problem, we give the proof of unforgeability against adaptive chosen-message-and-chosen-ring attacks and privacy under the random oracle model.(3)
The IIoT devices only need to do lightweight signing operations online; some expensive operations can be preprocessed offline. So, even if there are lattice-based nodes that may need more computation power, our schemes are still suitable for the IIoT environment.


### 1.3. Related Work

In order to achieve data authenticity [12], researchers have conducted a lot of related works.In these years, considerable efforts have been paid for the authentication scheme for the resource constrained devices. Bali and Kumar [13] proposed secure clustering for efficient data dissemination among vehicles, and a trust metric was presented by considering various transmission characteristics of vehicles. He et al. [14] proposed a privacy-preserving data aggregation scheme for the smart grid against internal attacks. Bordel et al. [15] applied watermarking and physically unclonable functions to their scheme which can authenticate data in the IoT system, and the scheme is also suitable for 5G networks. Roy et al. [16] proposed a lightweight authentication scheme based on cryptographic hash, bitwise, and fuzzy extractor functions. Peng et al. [17] proposed a mechanism called verifiable query layer (VQL) which can work effectively and guarantee data authenticity. Jain and Prabhakar [18] constructed a system to ensure authenticity and integrity of data in a dynamic database where the server could be untrusted. Challa et al. [19] designed a scheme between a smart meter and a cloud server, and they also give the security and cost analysis of the scheme.At the same time, the digital signature schemes are usually used to ensure data authenticity for the devices that need to transmit data to each other. Ring signature is one of the important cryptographic primitives which can provide both message authentication and the anonymity of the actual signer. The first ring signature scheme was designed by Rivest et al. [20] in 2001. Any member in the ring can anonymously sign a message, and any receiver can verify the authenticity of the signature. Herranz [21] proposed a ring signature scheme based on RSA. In 2008, Ren and [22] introduced a ring signature scheme based on the ElGamal signature. Recently, some lattice-based ring signature schemes against quantum attacks have been proposed. Liu et al. [23] proposed a lattice-based ring signature that is proven secure against chosen-message attacks. Mundhe et al. [24] proposed a lattice-based ring signature that can provide identity privacy and location privacy. Ren et al. [25] proposed a lattice-based linkable ring signature scheme based on the Borromean ring signature.


### 1.4. Paper Organization

The remaining paper is organized as follows: in Section2, we present some preliminaries. Section 3 introduces the threat model and security model. Section 4 constructs our ASMC schemes and gives its security analysis. In Section 5, we compare the proposed protocols with the relevant improved SAMA scheme in terms of computation cost and communication overhead. Finally, Section 6 concludes this paper.


## 1.1. Motivation

Due to the complexity of practical network architecture in the IIoT environment, it is urgent to design an authentication scheme for the heterogeneous IIoT systems with distinct cryptosystems. Li et al. [6] proposed the SAMA scheme which considers the situation that the devices in IIoT use the same cryptographic configuration. However, it is quite possible that devices in IIoT networks may use different kinds of cryptographic systems. In order to remove this limitation, Wei et al. [7] propose an improved authentication scheme with different system parameters (hereafter, called improved SAMA). However, the improved SAMA scheme only considers the RSA nodes and DL nodes. In fact, there are more devices that adopt other cryptosystems, such as the elliptical cryptosystem. In recent years, more and more attention is paid to postquantum cryptographic algorithms. The threat from quantum computers will emerge in the future, so antiquantum attack cryptographic algorithms have attracted great attention [8]. Some researchers such as Paul and Guerin [9] and Zhang et al. [10] have already conducted a lot of research on postquantum cryptography to secure IIoT. Among the existed postquantum cryptographies, lattice-based cryptography brings the advantage of high-security guarantees and performance efficiency.In addition, privacy is another major concern in IIoT [11]. To the best of our knowledge, privacy issues in IIoT have not been treated very well in the existing literature, which is a potentially fatal threat. When the IIoT devices transmit data through communication channels, the adversaries could intercept the messages and reveal the identities of the devices.Motived by the above limitations, we propose novel message authentication schemes with more kinds of nodes compared with the improved SAMA scheme. Our scheme allows the devices in the IIoT to use RSA-based systems, ElGamal-based systems, ECC-based systems, and quantum cryptography. We also consider the privacy preservation of the IIoT devices while the scheme can provide data authenticity. In order to achieve these two goals at the same time, we chose the ring signature to design the authentication schemes in the heterogeneous IIoT environment.


## 1.2. Contribution

We construct novel authentication schemes over a multicryptosystem (hereafter, called ASMC) for the heterogeneous IIoT environment. The main contributions of this paper are as follows:(1)
We propose two ASMC schemes that support heterogeneous devices with multicryptographic configurations such as RSA-based, DL-based, ECC-based, and lattice-based cryptosystems. This solution brings greater flexibility to the authentication for heterogeneous IIoT. Moreover, the ASMC scheme can provide the devices with strong privacy protection.(2)
Based on the hardness assumption of the complex problem, we give the proof of unforgeability against adaptive chosen-message-and-chosen-ring attacks and privacy under the random oracle model.(3)
The IIoT devices only need to do lightweight signing operations online; some expensive operations can be preprocessed offline. So, even if there are lattice-based nodes that may need more computation power, our schemes are still suitable for the IIoT environment.


## 1.3. Related Work

In order to achieve data authenticity [12], researchers have conducted a lot of related works.In these years, considerable efforts have been paid for the authentication scheme for the resource constrained devices. Bali and Kumar [13] proposed secure clustering for efficient data dissemination among vehicles, and a trust metric was presented by considering various transmission characteristics of vehicles. He et al. [14] proposed a privacy-preserving data aggregation scheme for the smart grid against internal attacks. Bordel et al. [15] applied watermarking and physically unclonable functions to their scheme which can authenticate data in the IoT system, and the scheme is also suitable for 5G networks. Roy et al. [16] proposed a lightweight authentication scheme based on cryptographic hash, bitwise, and fuzzy extractor functions. Peng et al. [17] proposed a mechanism called verifiable query layer (VQL) which can work effectively and guarantee data authenticity. Jain and Prabhakar [18] constructed a system to ensure authenticity and integrity of data in a dynamic database where the server could be untrusted. Challa et al. [19] designed a scheme between a smart meter and a cloud server, and they also give the security and cost analysis of the scheme.At the same time, the digital signature schemes are usually used to ensure data authenticity for the devices that need to transmit data to each other. Ring signature is one of the important cryptographic primitives which can provide both message authentication and the anonymity of the actual signer. The first ring signature scheme was designed by Rivest et al. [20] in 2001. Any member in the ring can anonymously sign a message, and any receiver can verify the authenticity of the signature. Herranz [21] proposed a ring signature scheme based on RSA. In 2008, Ren and [22] introduced a ring signature scheme based on the ElGamal signature. Recently, some lattice-based ring signature schemes against quantum attacks have been proposed. Liu et al. [23] proposed a lattice-based ring signature that is proven secure against chosen-message attacks. Mundhe et al. [24] proposed a lattice-based ring signature that can provide identity privacy and location privacy. Ren et al. [25] proposed a lattice-based linkable ring signature scheme based on the Borromean ring signature.


## 1.4. Paper Organization

The remaining paper is organized as follows: in Section2, we present some preliminaries. Section 3 introduces the threat model and security model. Section 4 constructs our ASMC schemes and gives its security analysis. In Section 5, we compare the proposed protocols with the relevant improved SAMA scheme in terms of computation cost and communication overhead. Finally, Section 6 concludes this paper.


## 2. Preliminaries

In this section, we will briefly review some cryptographic assumptions. Table1 lists the notations used throughout this paper. Preliminaries.Table 1
The list of notations.
NotationsDescriptionskSystem security parameterPPPublic system parametersdi/eiPrivate/public key of theith RSA nodeNiModule of theith RSA nodexi/yiPrivate/public key of theith DL nodeGDLMultiplicative cyclic group of prime orderpgGenerator of the groupGDLki/KiPrivate/public key of theith ECC nodep,qTwo great primesFpFinite field of prime order pGECa cyclic group of all points on the elliptic curve ECGGenerator ofGECnECThe prime order ofGECxEC⋅Thex-coordinate of an elliptic curve pointl^i/L^iPrivate/public key of theith lattice nodeDThe quotient polynomial ringZqLatticex/xnLattice+1x←$Sis a uniformly random sample drawn from a setS


### 2.1. Elliptic Curve overFp

Letp be an odd prime with p≡3mod8. An elliptic curve EC over Fp is defined by the equation y2=x3+ax+b, where a,b∈Fp, and Δ=4a3+27b20≡modp. The set Gec consists of all points x,y, x∈Fp, y∈Fp, which satisfy the above equation, together with an additional point O called the point at infinity.


### 2.2. Complexity Assumptions

DLP: Given a finite cyclic groupGdl, a generator g of Gdl, and an element h, the DLP is to find the integer a, 0≤a≤Gdl−1, such that h=ga.ECDLP: Given an elliptic curveEC defined over a finite field Fp, a point P of order n in Gec, and a point Q that is a multiple of P, the ECDLP is to find the integer l∈0,nec−1, such that Q=lP.SVP (shortest vector problem): Given a monic polynomialf and a lattice L corresponding to an ideal in the ring Zx/f, for γ≥1, the SVPγL is to find an element g∈L such that g∞≤γλ1, where λ1 is the shortest length of a nonzero vector in L [26].Lyubashevsky and Micciancio [27] introduced a family of collision-resistant hash functions based on the worst-case hardness of standard lattice problems over ideal lattices.For any integerz and Dh⊆D, let HD,Dh,m=ha^:a^∈Dz be the family of functions such that for any b^∈Dhz, ha^b^=a^·b^=∑i∈zaibi, where a^=a1,…,az, b^=b1,…,bz, z=1,…,z, and all the operations aibi are performed in the quotient polynomial ring D.Given an elementha^∈HD,Dh,z, the collision problem Colha^,Dh of lattice-based hash function is to find distinct elements b^1 and b^2 in Dhz such that ha^b^1=ha^b^2. The function family HD,Dh,m is collision-resistant when the input domain is suitably chosen in Dhz⊂Dz.Theorem 1 (Hardness of collision-resistant hash function [27]).
LetD be the ring ZqLatticex/xnLattice+1 for nLattice a power of two. Define the set Dh=y∈D:y∞≤d for some integer d. Let HD,Dh,z be a hash function family as the above definition such that z>logqLattice/log2d and qLattice≥4dznLattice1.5lognLattice. If there is a polynomial-time algorithm that solves Colha^,Dh for random ha^∈HD,Dh,z with some non-negligible probability, then there is a polynomial-time algorithm that can solve SVPγL for every lattice corresponding to an ideal in D, where γ=16dznlog2nLattice.
In this paper, we setd=znLattice1.5lognLattice+nLatticelognLattice. The setting ensures that the conditions required by the above theorem are verified, and finding collisions for HD,Dh,z implies an algorithm for breaking SVP in the case over ideal lattices for polynomial gaps.


### 2.3. Statistical Distance

Statistical distance is a measure of the difference between two probability distributions [28]. Let X and X′ be two random variables over a countable set S. The statistical distance between X and X′ is defined by(1)△X,X′=12∑x∈SPrX=x−PrX′=x.


## 2.1. Elliptic Curve overFp

Letp be an odd prime with p≡3mod8. An elliptic curve EC over Fp is defined by the equation y2=x3+ax+b, where a,b∈Fp, and Δ=4a3+27b20≡modp. The set Gec consists of all points x,y, x∈Fp, y∈Fp, which satisfy the above equation, together with an additional point O called the point at infinity.


## 2.2. Complexity Assumptions

DLP: Given a finite cyclic groupGdl, a generator g of Gdl, and an element h, the DLP is to find the integer a, 0≤a≤Gdl−1, such that h=ga.ECDLP: Given an elliptic curveEC defined over a finite field Fp, a point P of order n in Gec, and a point Q that is a multiple of P, the ECDLP is to find the integer l∈0,nec−1, such that Q=lP.SVP (shortest vector problem): Given a monic polynomialf and a lattice L corresponding to an ideal in the ring Zx/f, for γ≥1, the SVPγL is to find an element g∈L such that g∞≤γλ1, where λ1 is the shortest length of a nonzero vector in L [26].Lyubashevsky and Micciancio [27] introduced a family of collision-resistant hash functions based on the worst-case hardness of standard lattice problems over ideal lattices.For any integerz and Dh⊆D, let HD,Dh,m=ha^:a^∈Dz be the family of functions such that for any b^∈Dhz, ha^b^=a^·b^=∑i∈zaibi, where a^=a1,…,az, b^=b1,…,bz, z=1,…,z, and all the operations aibi are performed in the quotient polynomial ring D.Given an elementha^∈HD,Dh,z, the collision problem Colha^,Dh of lattice-based hash function is to find distinct elements b^1 and b^2 in Dhz such that ha^b^1=ha^b^2. The function family HD,Dh,m is collision-resistant when the input domain is suitably chosen in Dhz⊂Dz.Theorem 1 (Hardness of collision-resistant hash function [27]).
LetD be the ring ZqLatticex/xnLattice+1 for nLattice a power of two. Define the set Dh=y∈D:y∞≤d for some integer d. Let HD,Dh,z be a hash function family as the above definition such that z>logqLattice/log2d and qLattice≥4dznLattice1.5lognLattice. If there is a polynomial-time algorithm that solves Colha^,Dh for random ha^∈HD,Dh,z with some non-negligible probability, then there is a polynomial-time algorithm that can solve SVPγL for every lattice corresponding to an ideal in D, where γ=16dznlog2nLattice.
In this paper, we setd=znLattice1.5lognLattice+nLatticelognLattice. The setting ensures that the conditions required by the above theorem are verified, and finding collisions for HD,Dh,z implies an algorithm for breaking SVP in the case over ideal lattices for polynomial gaps.


## 2.3. Statistical Distance

Statistical distance is a measure of the difference between two probability distributions [28]. Let X and X′ be two random variables over a countable set S. The statistical distance between X and X′ is defined by(1)△X,X′=12∑x∈SPrX=x−PrX′=x.


## 3. System Model

This section gives a brief discussion of the network, threat, and security model of the proposed scheme. We assume that the IIoT is heterogeneous, and the devices may use different cryptographic systems, and a privacy-preserving authentication scheme (ASMC) based on ring signature over a multicryptosystem is proposed under such circumstance.


### 3.1. Network Model

In the proposed ASMC scheme, we consider the network model with cloud data centers for the IIoT device authenticity and privacy. The network model is shown in Figure1. Specifically, we consider an IIoT network where the devices may be deployed by different workshops or different factories for collecting many types of data. Hence, these devices may use various system parameters. We assume that all the system parameters, public, and private keys have been stored in the devices before they are deployed. After the deployment, devices will collect data and transmit the data to the cloud data centers.Figure 1
Network model.


### 3.2. Attack Model

The IIoT devices connect with each other via an insecure channel. During the data transmitting process, an adversary can eavesdrop, intercept, and modify the transmitted data of both devices. So, the IIoT devices are vulnerable to various attacks. We apply the Dolev–Yao (DY) attack model [29] in the presented scheme, and there are two types of adversaries in the system.(1)
Passive adversaryA can eavesdrop on the data transmitted in the public channel, such as collecting the messages sent by the IIoT devices. Then, the adversary may analyze the intercepted message and try to reveal the content of the message and identify the real data sender. Since one type of IIoT device always generates a specific kind of data, thus the kind of data implies the type of device. So, the disclosure of the message type may leak the sender’s privacy such as identity.(2)
Active adversaryA may actively launch different attacks which include man-in-the-middle, brute force attack, data injection, and so on. A can intercept and modify the messages during data transmission or inject fake messages into the data channel. An IIoT device may be corrupted and controlled by an active adversary. When an IIoT device is compromised, the adversary can access all the secret information of the device.


### 3.3. Security Model

In IIoT, many devices transmit data via the insecure channels. In order to mitigate the various types of attacks launched by the passive adversary and active adversary, the ASMC schemes aim at providing the message transmitted with authenticity, integrity, and privacy.The message authenticity and integrity require that a message is sent by a legal device and has not been altered by any other devices. This security goal is guaranteed by the unforgeability of the underlying ring signature scheme in ASMC. Privacy protection requires that the identity and other private information of the message sender is well protected. The anonymity of the underlying ring signature scheme in ASCM can meet the requirement of privacy. So, the security goals of the ASMC scheme are unforgeability and anonymity.Unforgeability. The property means that it is difficult forA to forge a valid signature of an honest ring member in the ASMC scheme. The security model allows the adversary to mount the following two attacks:(1)
Adaptive chosen-message attack:A can acquire the signature of a message chosen by the adversary in the forge attack phase.(2)
Adaptive chosen-ring attack:A can choose the ring members and acquire a signature regarding the chosen ring.In the security model,A is allowed to make the following oracle queries: Add, Crpt, Sign, and Hash (for details, see the proof of Theorem 2). Now, we can define the unforgeability.Definition 1.
Existential unforgeability against adaptive chosen-message-and-ring attack (EUF-ACMRA): an ASMC scheme is said to satisfy the existential unforgeability against the adaptive chosen-message-and-ring attack if no probabilistic polynomial-time adversary has a non-negligible advantageAdvunforge/ASMC,Ak in the experiment Expunforge/ASMC,Ak as defined in Table 2, where the advantage of the adversary A is defined by(2)AdvASMC,Aunforgek=PrExpASMC,Aunforgek=1.
Anonymity. This property indicates that the ASMC scheme will not reveal the identity of the real data sender.Table 2
Experiments of unforgeability and anonymity.
ExperimentExpunforge/ASMC,AkInitialization:List←∅; MList←∅; SList←∅, public parameters PP is generated.Quary1:A makes oracle queries Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ repeatedly.Challenge:A chooses The message m′ and ring R′ to challenge.Ifpki∈R′ , i,ski,pki∈List, and i∈MList, then return 0.Quary2:A continues to make queries on Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ as phase Quary1, but he is not permitted to make query on the oracle Crpt with any i that pki∈R′ or the oracle Sign with R′,∗,m′.Forge:A outputs a forged signature R′,m′,σ′.IfVerifyPP,R′,m′,σ′=accpeted, then return 1, else return 0.ExperimentExpanony/ASMC,AkInitialization:List←∅; MList←∅; SList←∅, public parameters PP is generated.Quary1:A makes oracle queries Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ repeatedly.Challenge:A chooses identities i0,i1 and a message m′, and call oracle Chbi0,i1,m′. Then, A obtains a signature R′,m′,σb where b∈0,1.Quary2:A continues to make queries on Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ as phase Quary1 except the query Crpt with any i that pki∈R′ or Sign with R′,∗,m′.Guess:A makes a guess of b denoted by d according to the signature R′,m′,σb.Return the valued.Definition 2.
Anonymity
For the ASMC scheme, we define the advantage of any probabilistic polynomial-time adversaryA in the experiment Expanony/ASMC,Ak as defined in Table 2, and an ASMC scheme is said to provide the anonymity of the actual signer if the advantage GI=u,vSSu,v'/SS′≥1/qhqh+1 is negligible for any A with a security parameter k, with querying oracles Add, Reg, Crpt, Sign, Chb, and Hash (for details, see the proof of Theorem 4).(3)AdvASMC,Aanonyk=2PrExpASMC,Aanonyk=b−1.


## 3.1. Network Model

In the proposed ASMC scheme, we consider the network model with cloud data centers for the IIoT device authenticity and privacy. The network model is shown in Figure1. Specifically, we consider an IIoT network where the devices may be deployed by different workshops or different factories for collecting many types of data. Hence, these devices may use various system parameters. We assume that all the system parameters, public, and private keys have been stored in the devices before they are deployed. After the deployment, devices will collect data and transmit the data to the cloud data centers.Figure 1
Network model.


## 3.2. Attack Model

The IIoT devices connect with each other via an insecure channel. During the data transmitting process, an adversary can eavesdrop, intercept, and modify the transmitted data of both devices. So, the IIoT devices are vulnerable to various attacks. We apply the Dolev–Yao (DY) attack model [29] in the presented scheme, and there are two types of adversaries in the system.(1)
Passive adversaryA can eavesdrop on the data transmitted in the public channel, such as collecting the messages sent by the IIoT devices. Then, the adversary may analyze the intercepted message and try to reveal the content of the message and identify the real data sender. Since one type of IIoT device always generates a specific kind of data, thus the kind of data implies the type of device. So, the disclosure of the message type may leak the sender’s privacy such as identity.(2)
Active adversaryA may actively launch different attacks which include man-in-the-middle, brute force attack, data injection, and so on. A can intercept and modify the messages during data transmission or inject fake messages into the data channel. An IIoT device may be corrupted and controlled by an active adversary. When an IIoT device is compromised, the adversary can access all the secret information of the device.


## 3.3. Security Model

In IIoT, many devices transmit data via the insecure channels. In order to mitigate the various types of attacks launched by the passive adversary and active adversary, the ASMC schemes aim at providing the message transmitted with authenticity, integrity, and privacy.The message authenticity and integrity require that a message is sent by a legal device and has not been altered by any other devices. This security goal is guaranteed by the unforgeability of the underlying ring signature scheme in ASMC. Privacy protection requires that the identity and other private information of the message sender is well protected. The anonymity of the underlying ring signature scheme in ASCM can meet the requirement of privacy. So, the security goals of the ASMC scheme are unforgeability and anonymity.Unforgeability. The property means that it is difficult forA to forge a valid signature of an honest ring member in the ASMC scheme. The security model allows the adversary to mount the following two attacks:(1)
Adaptive chosen-message attack:A can acquire the signature of a message chosen by the adversary in the forge attack phase.(2)
Adaptive chosen-ring attack:A can choose the ring members and acquire a signature regarding the chosen ring.In the security model,A is allowed to make the following oracle queries: Add, Crpt, Sign, and Hash (for details, see the proof of Theorem 2). Now, we can define the unforgeability.Definition 1.
Existential unforgeability against adaptive chosen-message-and-ring attack (EUF-ACMRA): an ASMC scheme is said to satisfy the existential unforgeability against the adaptive chosen-message-and-ring attack if no probabilistic polynomial-time adversary has a non-negligible advantageAdvunforge/ASMC,Ak in the experiment Expunforge/ASMC,Ak as defined in Table 2, where the advantage of the adversary A is defined by(2)AdvASMC,Aunforgek=PrExpASMC,Aunforgek=1.
Anonymity. This property indicates that the ASMC scheme will not reveal the identity of the real data sender.Table 2
Experiments of unforgeability and anonymity.
ExperimentExpunforge/ASMC,AkInitialization:List←∅; MList←∅; SList←∅, public parameters PP is generated.Quary1:A makes oracle queries Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ repeatedly.Challenge:A chooses The message m′ and ring R′ to challenge.Ifpki∈R′ , i,ski,pki∈List, and i∈MList, then return 0.Quary2:A continues to make queries on Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ as phase Quary1, but he is not permitted to make query on the oracle Crpt with any i that pki∈R′ or the oracle Sign with R′,∗,m′.Forge:A outputs a forged signature R′,m′,σ′.IfVerifyPP,R′,m′,σ′=accpeted, then return 1, else return 0.ExperimentExpanony/ASMC,AkInitialization:List←∅; MList←∅; SList←∅, public parameters PP is generated.Quary1:A makes oracle queries Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ repeatedly.Challenge:A chooses identities i0,i1 and a message m′, and call oracle Chbi0,i1,m′. Then, A obtains a signature R′,m′,σb where b∈0,1.Quary2:A continues to make queries on Add⋅, Reg⋅, Crpt⋅, Sgin⋅, and Hash⋅ as phase Quary1 except the query Crpt with any i that pki∈R′ or Sign with R′,∗,m′.Guess:A makes a guess of b denoted by d according to the signature R′,m′,σb.Return the valued.Definition 2.
Anonymity
For the ASMC scheme, we define the advantage of any probabilistic polynomial-time adversaryA in the experiment Expanony/ASMC,Ak as defined in Table 2, and an ASMC scheme is said to provide the anonymity of the actual signer if the advantage GI=u,vSSu,v'/SS′≥1/qhqh+1 is negligible for any A with a security parameter k, with querying oracles Add, Reg, Crpt, Sign, Chb, and Hash (for details, see the proof of Theorem 4).(3)AdvASMC,Aanonyk=2PrExpASMC,Aanonyk=b−1.


## 4. 4. Our Authentication Scheme over Multicryptosystem

In the following section, we construct two ASMC schemes, corresponding to two situations, respectively, adjacent nodes using the same cryptographic system as shown in Figure2 and the mixture of distinct cryptosystem nodes as shown in Figure 3.Figure 2
Adjacent nodes using the same cryptographic system.Figure 3
A mixture of distinct cryptosystem nodes.


### 4.1. ASMC for Adjacent Nodes Using the Same Cryptosystem

In order to provide the legitimacy of one’s identity, the signature schemes based on RSA, DL (discrete logarithm), ECC (elliptic curve), and lattice are mostly used at present. For simplicity, we make the assumptions that each node in the IIoT system can use only one type of these four schemes. For adjacent nodes using the same cryptosystem, the ASMC scheme is composed of the following phases.For clarity, we assume that the number of each type of cryptosystem nodes in the system isn. The ring R consists of n RSA nodes (with indices from 1 to n), t DL nodes (with indices from n+1 to 2n), n ECC nodes (with indices from 2n+1 to 3n), and n lattice nodes (with indices from 3n+1 to 4n).Setup1k. KGC generates GDL,g,p for DL nodes, GEC,G,nEC for ECC nodes, and D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D. The parameters PP denote the system public parameters. The hash functions are HDL:0,1∗⟶Zp, HEC:0,1∗⟶ZnEC, and HLattice:0,1∗⟶Zq.KeyGenPP. After the KeyGen is executed, each node i will be equipped with ski,pki. Specially, the key pairs are generated as follows.Each RSA nodei has a private key ski=di,Ni and a public key pki=ei,Ni. A hash function HRSA:0,1∗⟶ZNmin is also generated, where Nmin=minN1,N2,…,Nn.Similarly, each DL nodei has a private key ski=xi and a public key pki=yi, where xi is chosen randomly from 2,p−2 and yi=gxi. Each ECC node i has a private key ski=ki and a public key pki=Ki, where ki←$ZnEC∗ and Ki=kiG.For the lattice nodei, the system generates a vector l1,l2,…,lz←$Dz . If none of the vector component is invertible, then it regenerates the vector. Otherwise, set l^i=l1,l2,…,lz as the node’s private key. Let lj be any of the invertible vector components. Then, the system generates L1,L2,…,Lj−1,Lj+1,…,Lz←$Dz−1 and Lj=l−1/jS−∑k=1,k≠jzlkLk∈D. The public key is L^i=L1,L2,…,Lz. We have(4)hL^il^i=∑alaLa=S.RSignPP,R,ski,m. Suppose that the node j in the ring wants to generate a ring signature. The generation of a ring signature consists of the offline-sign and online-sign phases.Offline-Sign.For any RSA nodei≠j in R, select si∈ZNi∗ and compute vi=sieimodNi.For any DL nodei≠j in R, select si∈2,p−2 and compute vi=gsimodp.For any ECC nodei≠j in R, select si∈Znec∗ and compute vi=siG.For any lattice nodei≠j in R, select s^i∈Dz and compute vi=hL^is^i.Online-Sign.According to the kind of the node, the real signerj generates the ring signature about the message m as shown in the following steps:(1)
Signing by an RSA node(1)
Nodej chooses a random number α∈ZNj∗ and computes cj+1=HRSAR,m,α.(2)
Fori=j+1,…,n−1, Node i computes(5)ci+1=HRSAR,m,ci+vimodNi,(3)
Noden computes ct+1=HDLR,m,ct+vtmodNn.(4)
Fori=n+1,…,2n−1, Node i computes(6)ci+1=HDLR,m,viyicimodp.(5)
Node2n computes(7)c2n+1=HECR,m,v2ny2nc2nmodp.(6)
Fori=2n+1,…,3n−1, Node i computes(8)ci+1=HECR,m,xECvi+ciKimodnEC.(7)
Node3n computes(9)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(8)
Fori=3n+1,…,4n−1, Node i computes(10)ci+1=HLatticeR,m,vi+ciS.(9)
Node4n computes c1=HRSAR,m,v4n+c4nS.(10)
Fori=1,…,j−1, Node i computes(11)ci+1=HRSAR,m,ci+vimodNi.(11)
Nodej computes sj=α−cjdj.(2)
Signing by a DL node(1)
Nodej chooses randomly β∈2,p−2, and Node i computes(12)cj+1=HDLR,m,gβmodp.(2)
Fori=j+1,…,2n−1, Node i computes(13)ci+1=HDLR,m,viyicimodp.(3)
Node2n computes(14)c2n+1=HECR,m,v2ny2nc2nmodp.(4)
Fori=2n+1,…,3n−1, Node i computes(15)ci+1=HECR,m,xECvi+ciKimodnEC.(5)
Node3n computes(16)c3t+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(6)
Fori=3n+1,…,4n−1, Node i computes(17)ci+1=HLatticeR,m,vi+ciS.(7)
Node4n computes c1=HRSAR,m,v4n+c4nS.(8)
Fori=1,…,n−1, Node i computes(18)ci+1=HRSAR,m,ci+vimodNi.(9)
Noden computes(19)cn+1=HDLR,m,cn+vnmodNn.(10)
Fori=n+1,…,j−1, Node i computes(20)ci+1=HDLR,m,viyicimodp.(11)
Nodej computes sj=β−cjxjmodp.(3)
Signing by an ECC node(1)
Nodej chooses randomly γ∈ZnEC∗, and it computes(21)cj+1=HECR,m,xECγGmodnEC.(2)
Fori=j+1,…,3n−1, Node i computes(22)ci+1=HECR,m,xECvi+ciKimodnEC.(3)
Node3n computes(23)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(4)
Fori=3n+1,…,4n−1, Node i computes(24)ci+1=HLatticeR,m,vi+ciS.(5)
Node4n computes c1=HRSAR,m,v4n+c4nS.(6)
Fori=1,…,n−1, Node i computes(25)ci+1=HRSAR,m,ci+vimodNi.(7)
Noden computes(26)cn+1=HDLR,m,cn+vnmodNn.(8)
Fori=n+1,…,2n−1, Node i computes(27)ci+1=HDLR,m,viyicimodp.(9)
Node2n computes(28)c2n+1=HECR,m,v2ny2nc2nmodp.(10)
Fori=2n,…,j−1, Node i computes(29)ci+1=HECR,m,xECvi+ciKimodnEC.(11)
Nodej computes sj=γ−cjkjmodnEC.(4)
Signing by a lattice node(1)
Nodej chooses randomly δ^∈Dz, and it computes(30)cj+1=hL^jδ^^.(2)
Fori=j+1,…,4n−1, computes(31)ci+1=HLatticeR,m,vi+ciS.(3)
Node4n computes c1=HRSAR,m,v4n+c4nS.(4)
Fori=1,…,t−1, computes(32)ci+1=HRSAR,m,ci+vimodNi.(5)
Noden computes(33)cn+1=HDLR,m,cn+vnmodNn.(6)
Fori=n+1,…,2n−1, Node i computes(34)ci+1=HDLR,m,viyicimodp.(7)
Node2n computes(35)c2n+1=HECR,m,v2ny2nc2nmodp.(8)
Fori=2n,…,3n−1, Node i computes(36)ci+1=HECR,m,xECvi+ciKimodnEC.(9)
Node3n computes(37)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(10)
Fori=3n+1,…,j−1, Node i computes(38)ci+1=HLatticeR,m,vi+ciS.(11)
Nodej computes s^j=δ^−cjl^j.Letσ=c1,s1,…,s4n. Then, the final ring signature on the message m is R,m,σ.(39)VerifyPP,R,m,σ.Once receiving an ASMC signatureR,m,σ, one can check the authenticity and integrity regarding m as follows:(1)
Fori=1,…,n−1, the verifier computes(40)ci+1=HRSAR,m,ci+sieimodNi.(2)
The verifier computescn+1=HDLR,m,cn+snenmodNn.(3)
Fori=n+1,…,2n−1, the verifier computes(41)ci+1=HDLR,m,gsiyicimodp.(4)
The verifier computesc2n+1=HECR,m,gs2ny2nc2nmodp.(5)
Fori=2n+1,…,3n−1, the verifier computes(42)ci+1=HECR,m,xECsiG+ciKimodnEC.(6)
The verifier computes(43)c3n+1=HLatticeR,m,xECs3nG+c3nK3nmodnEC.(7)
Fori=3n+1,…,4n−1, the verifier computes(44)ci+1=HLatticeR,m,hL^is^i+ciS.(8)
The verifier computesc1′=HRSAR,m,hL^4ns^4n+c4nS.Ifc1=c1′, the signature R,m,σ is valid. Otherwise, it is invalid.


### 4.2. ASMC for the Mixture of Distinct Cryptosystem Nodes

In this case, we assume that the ring includes RSA nodes, DL nodes, ECC nodes, and lattice nodes, and they are mixed as shown in Figure3. Now, the ASMC scheme for a mixture of distinct cryptosystems is different from the ASMC scheme for the first case, especially in the RSign and Verify phase.Setup1k and KeyGenPP are the same as those ones of ASMC in the first case.(45)RSignPP,R,ski,m.The Offline-Sign in the case is the same as the Offline-Sign in the first case. Here, we only give the description of Online-Sign.Online-Sign.Step 1.
Initialization.
If Nodej is an RSA, DL, ECC, or lattice node, it randomly chooses α∈ZNj∗, β∈2,p−2, γ∈ZnEC∗ or δ^∈Dz, respectively. Then, Node j computes(46)wj=α,Nodejis a RSA nodegβmodp,Nodejis a DL nodexECγGmodnEC,Nodejis an ECC nodehL^jδ^,Nodejis a Lattice node.
Next, Nodej computes(47)cj+1=HRSAR,m,wj,Nodej+1is a RSA nodeHDLR,m,wj,Nodej+1is a DL nodeHECR,m,wj,Nodej+1is  n ECC nodeHLatticeR,m,wj,Nodej+1is a Lattice node.Step 2.
Forward the sequence.
Fori=j+1,…,n,1,…j−1, Node i computes(48)wi=ci+vimodNi,Nodeiis a RSA nodeviyicimodp,Nodeiis a DL nodexECvi+ciKimodnEC,Nodeiis an ECC nodevi+ciS,Nodeiis a Lattice node.
Next, it computesci+1 with the same manner as above cj+1.Step 3.
Form the ring. Finally, Nodej computes(49)sj=α−cjdj,Nodejis a RSA nodeβ−cjxjmodp,Nodejis a DL nodeγ−cjkjmodnEC,Nodejis an ECC nodeδ^−cjl^j,Nodejis a Lattice node.
Letσ=c1,s1,…,sn. Then, the ring signature on the message m is R,m,σ.(50)VerifyPP,R,m,σ.
Upon receiving an ASMC signatureR,m,σ, the receiver can check the authenticity and integrity regarding m by verifying the signature as follows.
The verifier computeswi′ and ci+1' as the same as wi and ci+1 in the online phase. Finally, it computes(51)c1′=HRSAR,m,wn′,Node1is a RSA nodeHDLR,m,wn′,Node1is a DL nodeHECR,m,wn′,Node1is an ECC nodeHLatticeR,m,wn′,Node1is a Lattice node.
Ifc1′=c1, the verifier believes the authenticity and integrity of the received message. Otherwise, it outputs ⊥.


## 4.1. ASMC for Adjacent Nodes Using the Same Cryptosystem

In order to provide the legitimacy of one’s identity, the signature schemes based on RSA, DL (discrete logarithm), ECC (elliptic curve), and lattice are mostly used at present. For simplicity, we make the assumptions that each node in the IIoT system can use only one type of these four schemes. For adjacent nodes using the same cryptosystem, the ASMC scheme is composed of the following phases.For clarity, we assume that the number of each type of cryptosystem nodes in the system isn. The ring R consists of n RSA nodes (with indices from 1 to n), t DL nodes (with indices from n+1 to 2n), n ECC nodes (with indices from 2n+1 to 3n), and n lattice nodes (with indices from 3n+1 to 4n).Setup1k. KGC generates GDL,g,p for DL nodes, GEC,G,nEC for ECC nodes, and D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D. The parameters PP denote the system public parameters. The hash functions are HDL:0,1∗⟶Zp, HEC:0,1∗⟶ZnEC, and HLattice:0,1∗⟶Zq.KeyGenPP. After the KeyGen is executed, each node i will be equipped with ski,pki. Specially, the key pairs are generated as follows.Each RSA nodei has a private key ski=di,Ni and a public key pki=ei,Ni. A hash function HRSA:0,1∗⟶ZNmin is also generated, where Nmin=minN1,N2,…,Nn.Similarly, each DL nodei has a private key ski=xi and a public key pki=yi, where xi is chosen randomly from 2,p−2 and yi=gxi. Each ECC node i has a private key ski=ki and a public key pki=Ki, where ki←$ZnEC∗ and Ki=kiG.For the lattice nodei, the system generates a vector l1,l2,…,lz←$Dz . If none of the vector component is invertible, then it regenerates the vector. Otherwise, set l^i=l1,l2,…,lz as the node’s private key. Let lj be any of the invertible vector components. Then, the system generates L1,L2,…,Lj−1,Lj+1,…,Lz←$Dz−1 and Lj=l−1/jS−∑k=1,k≠jzlkLk∈D. The public key is L^i=L1,L2,…,Lz. We have(4)hL^il^i=∑alaLa=S.RSignPP,R,ski,m. Suppose that the node j in the ring wants to generate a ring signature. The generation of a ring signature consists of the offline-sign and online-sign phases.Offline-Sign.For any RSA nodei≠j in R, select si∈ZNi∗ and compute vi=sieimodNi.For any DL nodei≠j in R, select si∈2,p−2 and compute vi=gsimodp.For any ECC nodei≠j in R, select si∈Znec∗ and compute vi=siG.For any lattice nodei≠j in R, select s^i∈Dz and compute vi=hL^is^i.Online-Sign.According to the kind of the node, the real signerj generates the ring signature about the message m as shown in the following steps:(1)
Signing by an RSA node(1)
Nodej chooses a random number α∈ZNj∗ and computes cj+1=HRSAR,m,α.(2)
Fori=j+1,…,n−1, Node i computes(5)ci+1=HRSAR,m,ci+vimodNi,(3)
Noden computes ct+1=HDLR,m,ct+vtmodNn.(4)
Fori=n+1,…,2n−1, Node i computes(6)ci+1=HDLR,m,viyicimodp.(5)
Node2n computes(7)c2n+1=HECR,m,v2ny2nc2nmodp.(6)
Fori=2n+1,…,3n−1, Node i computes(8)ci+1=HECR,m,xECvi+ciKimodnEC.(7)
Node3n computes(9)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(8)
Fori=3n+1,…,4n−1, Node i computes(10)ci+1=HLatticeR,m,vi+ciS.(9)
Node4n computes c1=HRSAR,m,v4n+c4nS.(10)
Fori=1,…,j−1, Node i computes(11)ci+1=HRSAR,m,ci+vimodNi.(11)
Nodej computes sj=α−cjdj.(2)
Signing by a DL node(1)
Nodej chooses randomly β∈2,p−2, and Node i computes(12)cj+1=HDLR,m,gβmodp.(2)
Fori=j+1,…,2n−1, Node i computes(13)ci+1=HDLR,m,viyicimodp.(3)
Node2n computes(14)c2n+1=HECR,m,v2ny2nc2nmodp.(4)
Fori=2n+1,…,3n−1, Node i computes(15)ci+1=HECR,m,xECvi+ciKimodnEC.(5)
Node3n computes(16)c3t+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(6)
Fori=3n+1,…,4n−1, Node i computes(17)ci+1=HLatticeR,m,vi+ciS.(7)
Node4n computes c1=HRSAR,m,v4n+c4nS.(8)
Fori=1,…,n−1, Node i computes(18)ci+1=HRSAR,m,ci+vimodNi.(9)
Noden computes(19)cn+1=HDLR,m,cn+vnmodNn.(10)
Fori=n+1,…,j−1, Node i computes(20)ci+1=HDLR,m,viyicimodp.(11)
Nodej computes sj=β−cjxjmodp.(3)
Signing by an ECC node(1)
Nodej chooses randomly γ∈ZnEC∗, and it computes(21)cj+1=HECR,m,xECγGmodnEC.(2)
Fori=j+1,…,3n−1, Node i computes(22)ci+1=HECR,m,xECvi+ciKimodnEC.(3)
Node3n computes(23)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(4)
Fori=3n+1,…,4n−1, Node i computes(24)ci+1=HLatticeR,m,vi+ciS.(5)
Node4n computes c1=HRSAR,m,v4n+c4nS.(6)
Fori=1,…,n−1, Node i computes(25)ci+1=HRSAR,m,ci+vimodNi.(7)
Noden computes(26)cn+1=HDLR,m,cn+vnmodNn.(8)
Fori=n+1,…,2n−1, Node i computes(27)ci+1=HDLR,m,viyicimodp.(9)
Node2n computes(28)c2n+1=HECR,m,v2ny2nc2nmodp.(10)
Fori=2n,…,j−1, Node i computes(29)ci+1=HECR,m,xECvi+ciKimodnEC.(11)
Nodej computes sj=γ−cjkjmodnEC.(4)
Signing by a lattice node(1)
Nodej chooses randomly δ^∈Dz, and it computes(30)cj+1=hL^jδ^^.(2)
Fori=j+1,…,4n−1, computes(31)ci+1=HLatticeR,m,vi+ciS.(3)
Node4n computes c1=HRSAR,m,v4n+c4nS.(4)
Fori=1,…,t−1, computes(32)ci+1=HRSAR,m,ci+vimodNi.(5)
Noden computes(33)cn+1=HDLR,m,cn+vnmodNn.(6)
Fori=n+1,…,2n−1, Node i computes(34)ci+1=HDLR,m,viyicimodp.(7)
Node2n computes(35)c2n+1=HECR,m,v2ny2nc2nmodp.(8)
Fori=2n,…,3n−1, Node i computes(36)ci+1=HECR,m,xECvi+ciKimodnEC.(9)
Node3n computes(37)c3n+1=HLatticeR,m,xECv3n+c3nK3nmodnEC.(10)
Fori=3n+1,…,j−1, Node i computes(38)ci+1=HLatticeR,m,vi+ciS.(11)
Nodej computes s^j=δ^−cjl^j.Letσ=c1,s1,…,s4n. Then, the final ring signature on the message m is R,m,σ.(39)VerifyPP,R,m,σ.Once receiving an ASMC signatureR,m,σ, one can check the authenticity and integrity regarding m as follows:(1)
Fori=1,…,n−1, the verifier computes(40)ci+1=HRSAR,m,ci+sieimodNi.(2)
The verifier computescn+1=HDLR,m,cn+snenmodNn.(3)
Fori=n+1,…,2n−1, the verifier computes(41)ci+1=HDLR,m,gsiyicimodp.(4)
The verifier computesc2n+1=HECR,m,gs2ny2nc2nmodp.(5)
Fori=2n+1,…,3n−1, the verifier computes(42)ci+1=HECR,m,xECsiG+ciKimodnEC.(6)
The verifier computes(43)c3n+1=HLatticeR,m,xECs3nG+c3nK3nmodnEC.(7)
Fori=3n+1,…,4n−1, the verifier computes(44)ci+1=HLatticeR,m,hL^is^i+ciS.(8)
The verifier computesc1′=HRSAR,m,hL^4ns^4n+c4nS.Ifc1=c1′, the signature R,m,σ is valid. Otherwise, it is invalid.


## 4.2. ASMC for the Mixture of Distinct Cryptosystem Nodes

In this case, we assume that the ring includes RSA nodes, DL nodes, ECC nodes, and lattice nodes, and they are mixed as shown in Figure3. Now, the ASMC scheme for a mixture of distinct cryptosystems is different from the ASMC scheme for the first case, especially in the RSign and Verify phase.Setup1k and KeyGenPP are the same as those ones of ASMC in the first case.(45)RSignPP,R,ski,m.The Offline-Sign in the case is the same as the Offline-Sign in the first case. Here, we only give the description of Online-Sign.Online-Sign.Step 1.
Initialization.
If Nodej is an RSA, DL, ECC, or lattice node, it randomly chooses α∈ZNj∗, β∈2,p−2, γ∈ZnEC∗ or δ^∈Dz, respectively. Then, Node j computes(46)wj=α,Nodejis a RSA nodegβmodp,Nodejis a DL nodexECγGmodnEC,Nodejis an ECC nodehL^jδ^,Nodejis a Lattice node.
Next, Nodej computes(47)cj+1=HRSAR,m,wj,Nodej+1is a RSA nodeHDLR,m,wj,Nodej+1is a DL nodeHECR,m,wj,Nodej+1is  n ECC nodeHLatticeR,m,wj,Nodej+1is a Lattice node.Step 2.
Forward the sequence.
Fori=j+1,…,n,1,…j−1, Node i computes(48)wi=ci+vimodNi,Nodeiis a RSA nodeviyicimodp,Nodeiis a DL nodexECvi+ciKimodnEC,Nodeiis an ECC nodevi+ciS,Nodeiis a Lattice node.
Next, it computesci+1 with the same manner as above cj+1.Step 3.
Form the ring. Finally, Nodej computes(49)sj=α−cjdj,Nodejis a RSA nodeβ−cjxjmodp,Nodejis a DL nodeγ−cjkjmodnEC,Nodejis an ECC nodeδ^−cjl^j,Nodejis a Lattice node.
Letσ=c1,s1,…,sn. Then, the ring signature on the message m is R,m,σ.(50)VerifyPP,R,m,σ.
Upon receiving an ASMC signatureR,m,σ, the receiver can check the authenticity and integrity regarding m by verifying the signature as follows.
The verifier computeswi′ and ci+1' as the same as wi and ci+1 in the online phase. Finally, it computes(51)c1′=HRSAR,m,wn′,Node1is a RSA nodeHDLR,m,wn′,Node1is a DL nodeHECR,m,wn′,Node1is an ECC nodeHLatticeR,m,wn′,Node1is a Lattice node.
Ifc1′=c1, the verifier believes the authenticity and integrity of the received message. Otherwise, it outputs ⊥.


## 5. Security Analysis of Our Scheme

### 5.1. Message Authenticity and Integrity Analysis

The proposed ASMC scheme guarantees the message authenticity and integrity, due to the underlying ring signature being existentially unforgeable against adaptive chosen-message- and-chosen-ring attacks.Our ring signature scheme is an extension of the 1-out-of-n signature scheme proposed by Abe et al. [30]. The theorems of Abe et al. [30] show that if all the nodes in the ring use the same type of cryptosystems such as the RSA-type, DL-type, or ECC-type, the ring signature scheme is unforgeable.However, Abe et al. [30] did not consider the lattice-type cryptosystem. In the following section, we will show that the ring signature is existentially unforgeable if all the nodes in the ring are lattice nodes.Theorem 2.
If aτ,ε,qs,qh-adversary A exists in the ASMC scheme for all the nodes in the ring being lattice nodes, a η,μ-simulator S can find two vectors s^i and s^i′ such that hL^il^i=hL^il^i′ with the probability at least μ and the cost time at most η for at least one node i in R. Here, η<32qh2+4/p·τ and μ>9/100 on the condition that ϵ>8qh2/q and q>2qhqs, where q is the order of the quotient polynomial ring D.Proof.
For simplicity, the hash functionHLattice⋅ is written as H⋅. Thus, H⋅ can be treated as that uses Qj=Rj,mj,wj as jth query and returns HRj,mj,wj, where Rj is a set of public keys. The experiment Expunforge/ASMC,Ak. is carried out as follows.
Initialization The simulator S starts the unforgeable experiment with List←∅, MList←∅, SList←∅, and HList←∅.
SetupS generates D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D.
Query1A makes queries on Add, Reg, Crpt, Sign, and hash oracle H with S repeatedly. These oracles can make responses as follows.
Addi If i,∗,∗∈List, return ⊥, otherwise generate.
l^i=l1,l2,…,lz←$Dz,L^i,ski=l^i,pki=L^i, add i,ski,pki into List and return pki
Regi,pki If i,∗,∗∈List, return ⊥, otherwise set pki as the public key of signer with identity i, add i,⋅,pki to List and identity i to MList, finally returns pki.
Crpti If i,ski,pki∉List, return ⊥, otherwise add identity i into MList and return ski.
HR,m,w If R,m,w,v∈HList, return v, else uniformly choose v from Zq, add R,m,w,v into HList and return v.
SignR,k,m If R,k,m,σ∈SList, return σ, else generate the signature as follows.
For any memberi in the ring R including k, if i,∗,∗∉List, return ⊥. Otherwise, there are two cases.(1)
Ifk,skk,∗∈List, call the RSignR,skk,m algorithm to create a signature σ(2)
Ifk,skk,∗∉List, do the following four steps:Step 4.
Choosec1←$Zq.Step 5.
Fori=1,…,n, select s^i←$Dz, compute wi=hL^is^i+ciS, where S is part of system public parameters PP, and then we compute ci+1=HRj,mj,wi ifi≠Rj.Step 6.
Assignc1 to the value of HRj,mj,wn and add Rj,mj,wn,c1 into HList.Step 7.
Form the signature asσ=c1,s^1,…,s^n.
Finally, we return signatureR,m,σ and add R,k,m,σ into SList.
ChallengeA chooses the message m′ and ring R′=pk1′,…,pkn′ that he wants to challenge. For any member k′ in the ring R′, if k′,skk′,pkk′∈List and k′∈MList) or R′,∗,m′,∗∈SList, return ⊥, otherwise continue to carry on the next phase.
Query2A queries Add, Reg, Crpt, Sign, and hash oracle H the same as the phase, Query1, but he is not allowed to query Crpt with anyone in the ring R′ and Sign with R′,k′,m'.
Forge Finally, after those phases above, A returns a forged signature σ′ for the ring R′.
The oracleSign⋅ fails if inconsistencies of H⋅ emerge in Step-3. The probability is at most qh/q where q is the order of the quotient polynomial ring D. So, Sign⋅ can succeed qs times with probability greater than 1−qh/qqs≥1−qhqs/q.
LetΘ,Ω be the view given to the signing oracle and A. Let SS be a set of Θ,Ω,H with which A is successful in forge. For the success probability of A restricted by Θ,Ω, and H, we have PrΘ,Ω,H∈SS≥ϵ. Let R,m,c1,s1,…,sn be a forged signature that A outputs. We define wi=hL^is^i+ciS and ci+1=HR,m,wi for i=1,…,n. Due to the ideal randomness of H, there exist queries Qj=R,m,wi with probability at least 1−1/q, for i=1,…,n. Let SS′ be a subset of SS. Then, we have(52)PrΘ,Ω,H∈SS′≥1−qhqsq1−1qϵ.
Letϵ'=1−qhqs/q1−1/qϵ. Since the queries form a ring, there exists at least one k∈1,…,n such that Qu=R,m,wk and Qv=R,m,wk−1 with u<v. Then, k is between the gap of query order. Let u,v be a gap index. Note that u=v happens only if n=1. We will classify SS′ by the gap indices. Let SSu,v' be a class which yields gap indices u,v. Hence, there are at most 2/qh+1/qh=qhqh+1/2 classes. By invoking A with randomly chosen Θ,Ω,H at most t1=1/ϵ' times, S can find at least one Θ,Ω,H∈SSu,v' for a gap index u,v with probability 1−exp−1≥3/5.
LetGI=u,vSSu,v'/SS′≥1/qhqh+1 and B=Θ,Ω,H∈SSu,v'u,v∈GI. Then, it holds that PrB|SS′≥1/2. Due to the heavy-row lemma [31], Θ,Ω,H that yields the successful run of A is in B with probability at least 1/2. We split H as H−,ck where H− corresponds to the answers to all queries except for Qv answered with ck. Due to the heavy-row lemma [31], again, with probability at least 1/2, Θ,Ω,H− satisfies Prck′Θ,Ω,H−,ck′∈SSu,v'≥ϵ'/2qhqh+1. We assume ϵ>8qh2/q and q>2qhqs. It holds that ϵ'/2qhqh+1>1/q.
By runningA up to t2=ϵ'/2qhqh+1>1/q−1 times with Θ,Ω,H− obtained in the first successful run and randomly chosen ck′≠ck, then with probability at least 3/5, S finds at least one ck′ such that Θ,Ω,H−,ck′∈SSu,v'. Since Qu happens before Qv, wi will not change. Therefore, S gets two distinct tuples s^k,ck,l^k and s^k′,ck′,l^k that satisfies hL^ks^k+ckS=hL^ks^k′+ck′S. Then, we will have hL^ks^k−s^k′/ck′−ck=S=hL^kl^k. Thus, a collision of the lattice-based hash function has been found. The overall success probability is μ>3/5,1/2,1/2,3/5=9/100, and the number of invocations of A is(53)t1+t2<1ϵ'+4qhqh+1ϵ'<4ε+4⋅4⋅2qh2ε=32qh2+4ε.
By applying the similar technique in [30], with the mixture case of multi-type cryptosystems, we have Theorem 3.Theorem 3.
With regard to the ring,R consists of the public keys of n nodes, if a τ,ε,qs,qh-adversary A does exist, a η,μ-simulator S is allowed to interact with A who can make queries on the hash oracles up to qh times and the signing oracle up to qs times, and then S can compute vdmodNmin for v←$1,…,Nmin with probability greater than μ≥ 3/5 and running time η≤4qh2/ετ or compute the discrete-logarithm of y∈R such that y=gx with probability μ≥9/100 and running time η≤32qh2+4/ετ or compute elliptic-curve-discrete-logarithm k of K∈R such that K=kG with probability μ≥9/100 and running time η≤32qh2+4/ετ or compute and finds two vectors s^ and s^' such that hL^s^=hL^s^' with probability μ≥9/100 and running time η≤32qh2+4/ετ.So, the proposed ASMC ring signature with the mixture case of multi-type cryptosystems is existentially unforgeable against adaptive chosen-message and chosen-ring attacks.By combining the proofs of the theorems in [30] and Theorem 2, we can easily get the proof of Theorem 3. Now, we omit the detailed proof.2. Privacy analysis. The privacy of the proposed ASMC schemes can be guaranteed by the anonymity of the ring signature scheme.Theorem 4.
(Anonymity). For b∈0,1, let Xb,R,skib,m be the signature of a member ib in the ring R about message m in the proposed ASMC schemes. With a probabilistic polynomial-time turning machine, the statistical distance (as defined in Eq. 1) between the two signatures generated by signer i0 and signer i1 holds ΔX0,R,ski0,m,X1,R,ski1,m≤1/gk for any polynomial g and sufficiently large k under the random oracle model.Proof.
Here, we will prove that the statistical distance between two signaturesX0,PP,R,ski0,m,X1,PP,R,ski1,m is negligible. There is a simulator S and an adversary A in ExpASMC,Aanony−bk. Assume that A is granted the ability to access the security key of any member in the ring, and A is allowed to query S with the oracles Add, Reg, Crpt, Sign, Chb, and hash oracles. The anonymity experiment ExpMEMA,Aanony−bk is carried out asfollows.
Initialization The anonymity experiment starts with List←∅, MList←∅, SList←∅HListRSA←∅, HListDL←∅, HListEC←∅, and HListLattice←∅.
SetupS generates Gdl,g,p for DL nodes, GEC,G,nEC for ECC nodes, and D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D. The generated parameters are considered as public parameters PP.
Query 1A makes queries on Add, Reg, Crpt, Sign, and hash oracles repeatedly. S makes responses about the oracle queries as follows.
Addi: if i,∗,∗∈List, return ⊥, otherwise generate ski,pki, add i,ski,pki into List, and return pki.
HashRSAm: if m,v∈HListRSA, return v, else uniformly choose v from ZNmin, add m,v into HListRSA, and return v.
HashDLm, HashECm, and HashLatticem are handled similarly as HashRSAm. v is chosen randomly from the legal domain, and the m,v pair is added into the corresponding oracle list HListDL, HListEC, or HListLattice.
SignR,k,m: If R,k,m,σ∈SList, return σ, else generate the signature as follows.
For any memberi in the ring R including k, if i,∗,∗∉List, return ⊥. Otherwise, there are two cases.(1)
Ifk,skk,∗∈List, call the RSign algorithm to create a signature σ.(2)
If Node 1 is an RSA, DL, ECC, or lattice node andk,skk,∗∉List, it randomly chooses c1 from ZNmin, Zp, ZnEC, or Zq, respectively, and generate si, vi, wi , ci+1 with the same manner as the ASMC scheme.
Lastly, program hash oracle as(54)HashRSAR,m,wn=c1,if Node1is a RSA nodeHashDLR,m,wn=c1,if Node1is a DL nodeHashECR,m,wn=c1,if Node1is an ECC nodeHashLatticeR,m,wn=c1,if Node1is a Lattice node.
Form the signature asσ=c1,s1,…,sn and add R,k,m,σ into SList.
Finally, return the signature.R,m,σ, Reg⋅ and Crpt⋅ are handled the same as in Theorem 2.
ChallengeA chooses two identities i0,i1, and message m′, the Chb oracle is handled as follows.
-Chbi0,i1,m′ If i0,ski0,pki0 or i1,ski1,pki1∉List, return ⊥. Otherwise, we generate a ring R′ which contains the public keys of i0 and the public key of i1. If R′,ib,m′,∗∈SList, return ⊥. Otherwise, we generate a signature by calling SignR′,ib,m′ where b∈0,1. Finally return the signature R′,m′,σb. Note that the triple R′,ib,m′,σb is also added to the list SList.
Query 2 The adversary A queries Add, Reg, Crpt, Sign, and hash oracles in the same way as in Query 1, but he is not allowed to query about Crpt with any k in the ring R′ or Sign with R′,m′.
Finally,A returns a guess of bit b according to the signature R′,m′,σb from Chbi0,i1,m′.
Since the pairR′,m′ of the two signatures R′,m′,σ0 and R′,m′,σ1 are the same as each other, we will omit it when we measure the statistical distance between XR′,m′,σ0 and XR′,m′,σ1. Set the σ=c1,s1,…,sn as a vector of n+1 coordinates. Thus, each coordinate is independent of each other. For clarity, σ0 and σ1 are written as c1′,s1′,…,si0',…,si1',…,sn′ and c1'′,s1'′,…,si0'′,…,si1'′,…,sn'′. All the signature coordinates except for si0' of i0 are directly chosen uniformly from the domains defined in the ASMC scheme (here, we refer the domain as domain A, but the meaning of domain A for distinct kinds of nodes is different), while si1'′ of signature i1 is not directly chosen from the domain A. We set λ=minNmin,q,nEC,p, λ′=maxNmax,q,nEC,p. The distance between XR′,m′,σ0 and XR′,m′,σ1 is(55)△XR′,m′,σ0,XR′,m′,σ1=∑c1,si∈A,i∈1,…,nPrXR′,m′,σ0=c1,s1,…,si0,…,si1,…,sn−PrXR′,m′,σ1=c1,s1,…,si0,…,si1,…,sn=∑c1,si∈A,i∈1,…,nPrc1,Prs1,…,si0−1,si0+1,…,si1−1,si1+1,…,sn|Prsi0|si0−1,Prsi1−Prsi0,Prsi1|si1−1|=∑c1,si∈A,i∈1,…,nPrc1,∏i=1i≠i0,i1tPrsi,|Prsi0|si0−1,Prsi1−Prsi0,Prsi1|si1−1|≤λ′λt−1λ'2λ2−λ2λ'2=λ′λn−1λ′λ+λλ′λ'2−λ2λλ′≤2λ′λtλ′λ2−1=2λ′λtλ′λ+1λ′λ−1≤4λ′λn+1λ′λ−1,
The variablesα,β,γ,δ^ are used in the real signer’s secure value sib computation, and they are generated uniformly as α←$ZNj, β←$Zp, γ←$Zn, and δ^←$Dz. So, sib can still be considered a uniform chosen variable. c1 is generated by HashRSA,HashDL,HashEC,HashLattice random oracles with uniform distributions as HashRSA:0,1∗⟶ZNmin, HashDL:0,1∗⟶Zp, HashEC:0,1∗⟶Zn, HashLattice:0,1∗⟶Zq. So, we have Equation (2).
If the security parameterk is larger enough, λ′/λ−1≤g′k for any polynomial g′, and 4λ′/λn+1 will have an upper bound. Then, we have △XR′,m′,σ0,XR′,m′,σ1≤gk for any polynomial g and sufficiently large k.


## 5.1. Message Authenticity and Integrity Analysis

The proposed ASMC scheme guarantees the message authenticity and integrity, due to the underlying ring signature being existentially unforgeable against adaptive chosen-message- and-chosen-ring attacks.Our ring signature scheme is an extension of the 1-out-of-n signature scheme proposed by Abe et al. [30]. The theorems of Abe et al. [30] show that if all the nodes in the ring use the same type of cryptosystems such as the RSA-type, DL-type, or ECC-type, the ring signature scheme is unforgeable.However, Abe et al. [30] did not consider the lattice-type cryptosystem. In the following section, we will show that the ring signature is existentially unforgeable if all the nodes in the ring are lattice nodes.Theorem 2.
If aτ,ε,qs,qh-adversary A exists in the ASMC scheme for all the nodes in the ring being lattice nodes, a η,μ-simulator S can find two vectors s^i and s^i′ such that hL^il^i=hL^il^i′ with the probability at least μ and the cost time at most η for at least one node i in R. Here, η<32qh2+4/p·τ and μ>9/100 on the condition that ϵ>8qh2/q and q>2qhqs, where q is the order of the quotient polynomial ring D.Proof.
For simplicity, the hash functionHLattice⋅ is written as H⋅. Thus, H⋅ can be treated as that uses Qj=Rj,mj,wj as jth query and returns HRj,mj,wj, where Rj is a set of public keys. The experiment Expunforge/ASMC,Ak. is carried out as follows.
Initialization The simulator S starts the unforgeable experiment with List←∅, MList←∅, SList←∅, and HList←∅.
SetupS generates D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D.
Query1A makes queries on Add, Reg, Crpt, Sign, and hash oracle H with S repeatedly. These oracles can make responses as follows.
Addi If i,∗,∗∈List, return ⊥, otherwise generate.
l^i=l1,l2,…,lz←$Dz,L^i,ski=l^i,pki=L^i, add i,ski,pki into List and return pki
Regi,pki If i,∗,∗∈List, return ⊥, otherwise set pki as the public key of signer with identity i, add i,⋅,pki to List and identity i to MList, finally returns pki.
Crpti If i,ski,pki∉List, return ⊥, otherwise add identity i into MList and return ski.
HR,m,w If R,m,w,v∈HList, return v, else uniformly choose v from Zq, add R,m,w,v into HList and return v.
SignR,k,m If R,k,m,σ∈SList, return σ, else generate the signature as follows.
For any memberi in the ring R including k, if i,∗,∗∉List, return ⊥. Otherwise, there are two cases.(1)
Ifk,skk,∗∈List, call the RSignR,skk,m algorithm to create a signature σ(2)
Ifk,skk,∗∉List, do the following four steps:Step 4.
Choosec1←$Zq.Step 5.
Fori=1,…,n, select s^i←$Dz, compute wi=hL^is^i+ciS, where S is part of system public parameters PP, and then we compute ci+1=HRj,mj,wi ifi≠Rj.Step 6.
Assignc1 to the value of HRj,mj,wn and add Rj,mj,wn,c1 into HList.Step 7.
Form the signature asσ=c1,s^1,…,s^n.
Finally, we return signatureR,m,σ and add R,k,m,σ into SList.
ChallengeA chooses the message m′ and ring R′=pk1′,…,pkn′ that he wants to challenge. For any member k′ in the ring R′, if k′,skk′,pkk′∈List and k′∈MList) or R′,∗,m′,∗∈SList, return ⊥, otherwise continue to carry on the next phase.
Query2A queries Add, Reg, Crpt, Sign, and hash oracle H the same as the phase, Query1, but he is not allowed to query Crpt with anyone in the ring R′ and Sign with R′,k′,m'.
Forge Finally, after those phases above, A returns a forged signature σ′ for the ring R′.
The oracleSign⋅ fails if inconsistencies of H⋅ emerge in Step-3. The probability is at most qh/q where q is the order of the quotient polynomial ring D. So, Sign⋅ can succeed qs times with probability greater than 1−qh/qqs≥1−qhqs/q.
LetΘ,Ω be the view given to the signing oracle and A. Let SS be a set of Θ,Ω,H with which A is successful in forge. For the success probability of A restricted by Θ,Ω, and H, we have PrΘ,Ω,H∈SS≥ϵ. Let R,m,c1,s1,…,sn be a forged signature that A outputs. We define wi=hL^is^i+ciS and ci+1=HR,m,wi for i=1,…,n. Due to the ideal randomness of H, there exist queries Qj=R,m,wi with probability at least 1−1/q, for i=1,…,n. Let SS′ be a subset of SS. Then, we have(52)PrΘ,Ω,H∈SS′≥1−qhqsq1−1qϵ.
Letϵ'=1−qhqs/q1−1/qϵ. Since the queries form a ring, there exists at least one k∈1,…,n such that Qu=R,m,wk and Qv=R,m,wk−1 with u<v. Then, k is between the gap of query order. Let u,v be a gap index. Note that u=v happens only if n=1. We will classify SS′ by the gap indices. Let SSu,v' be a class which yields gap indices u,v. Hence, there are at most 2/qh+1/qh=qhqh+1/2 classes. By invoking A with randomly chosen Θ,Ω,H at most t1=1/ϵ' times, S can find at least one Θ,Ω,H∈SSu,v' for a gap index u,v with probability 1−exp−1≥3/5.
LetGI=u,vSSu,v'/SS′≥1/qhqh+1 and B=Θ,Ω,H∈SSu,v'u,v∈GI. Then, it holds that PrB|SS′≥1/2. Due to the heavy-row lemma [31], Θ,Ω,H that yields the successful run of A is in B with probability at least 1/2. We split H as H−,ck where H− corresponds to the answers to all queries except for Qv answered with ck. Due to the heavy-row lemma [31], again, with probability at least 1/2, Θ,Ω,H− satisfies Prck′Θ,Ω,H−,ck′∈SSu,v'≥ϵ'/2qhqh+1. We assume ϵ>8qh2/q and q>2qhqs. It holds that ϵ'/2qhqh+1>1/q.
By runningA up to t2=ϵ'/2qhqh+1>1/q−1 times with Θ,Ω,H− obtained in the first successful run and randomly chosen ck′≠ck, then with probability at least 3/5, S finds at least one ck′ such that Θ,Ω,H−,ck′∈SSu,v'. Since Qu happens before Qv, wi will not change. Therefore, S gets two distinct tuples s^k,ck,l^k and s^k′,ck′,l^k that satisfies hL^ks^k+ckS=hL^ks^k′+ck′S. Then, we will have hL^ks^k−s^k′/ck′−ck=S=hL^kl^k. Thus, a collision of the lattice-based hash function has been found. The overall success probability is μ>3/5,1/2,1/2,3/5=9/100, and the number of invocations of A is(53)t1+t2<1ϵ'+4qhqh+1ϵ'<4ε+4⋅4⋅2qh2ε=32qh2+4ε.
By applying the similar technique in [30], with the mixture case of multi-type cryptosystems, we have Theorem 3.Theorem 3.
With regard to the ring,R consists of the public keys of n nodes, if a τ,ε,qs,qh-adversary A does exist, a η,μ-simulator S is allowed to interact with A who can make queries on the hash oracles up to qh times and the signing oracle up to qs times, and then S can compute vdmodNmin for v←$1,…,Nmin with probability greater than μ≥ 3/5 and running time η≤4qh2/ετ or compute the discrete-logarithm of y∈R such that y=gx with probability μ≥9/100 and running time η≤32qh2+4/ετ or compute elliptic-curve-discrete-logarithm k of K∈R such that K=kG with probability μ≥9/100 and running time η≤32qh2+4/ετ or compute and finds two vectors s^ and s^' such that hL^s^=hL^s^' with probability μ≥9/100 and running time η≤32qh2+4/ετ.So, the proposed ASMC ring signature with the mixture case of multi-type cryptosystems is existentially unforgeable against adaptive chosen-message and chosen-ring attacks.By combining the proofs of the theorems in [30] and Theorem 2, we can easily get the proof of Theorem 3. Now, we omit the detailed proof.2. Privacy analysis. The privacy of the proposed ASMC schemes can be guaranteed by the anonymity of the ring signature scheme.Theorem 4.
(Anonymity). For b∈0,1, let Xb,R,skib,m be the signature of a member ib in the ring R about message m in the proposed ASMC schemes. With a probabilistic polynomial-time turning machine, the statistical distance (as defined in Eq. 1) between the two signatures generated by signer i0 and signer i1 holds ΔX0,R,ski0,m,X1,R,ski1,m≤1/gk for any polynomial g and sufficiently large k under the random oracle model.Proof.
Here, we will prove that the statistical distance between two signaturesX0,PP,R,ski0,m,X1,PP,R,ski1,m is negligible. There is a simulator S and an adversary A in ExpASMC,Aanony−bk. Assume that A is granted the ability to access the security key of any member in the ring, and A is allowed to query S with the oracles Add, Reg, Crpt, Sign, Chb, and hash oracles. The anonymity experiment ExpMEMA,Aanony−bk is carried out asfollows.
Initialization The anonymity experiment starts with List←∅, MList←∅, SList←∅HListRSA←∅, HListDL←∅, HListEC←∅, and HListLattice←∅.
SetupS generates Gdl,g,p for DL nodes, GEC,G,nEC for ECC nodes, and D,S,q for lattice nodes, where S is a nonzero element chosen randomly from D. The generated parameters are considered as public parameters PP.
Query 1A makes queries on Add, Reg, Crpt, Sign, and hash oracles repeatedly. S makes responses about the oracle queries as follows.
Addi: if i,∗,∗∈List, return ⊥, otherwise generate ski,pki, add i,ski,pki into List, and return pki.
HashRSAm: if m,v∈HListRSA, return v, else uniformly choose v from ZNmin, add m,v into HListRSA, and return v.
HashDLm, HashECm, and HashLatticem are handled similarly as HashRSAm. v is chosen randomly from the legal domain, and the m,v pair is added into the corresponding oracle list HListDL, HListEC, or HListLattice.
SignR,k,m: If R,k,m,σ∈SList, return σ, else generate the signature as follows.
For any memberi in the ring R including k, if i,∗,∗∉List, return ⊥. Otherwise, there are two cases.(1)
Ifk,skk,∗∈List, call the RSign algorithm to create a signature σ.(2)
If Node 1 is an RSA, DL, ECC, or lattice node andk,skk,∗∉List, it randomly chooses c1 from ZNmin, Zp, ZnEC, or Zq, respectively, and generate si, vi, wi , ci+1 with the same manner as the ASMC scheme.
Lastly, program hash oracle as(54)HashRSAR,m,wn=c1,if Node1is a RSA nodeHashDLR,m,wn=c1,if Node1is a DL nodeHashECR,m,wn=c1,if Node1is an ECC nodeHashLatticeR,m,wn=c1,if Node1is a Lattice node.
Form the signature asσ=c1,s1,…,sn and add R,k,m,σ into SList.
Finally, return the signature.R,m,σ, Reg⋅ and Crpt⋅ are handled the same as in Theorem 2.
ChallengeA chooses two identities i0,i1, and message m′, the Chb oracle is handled as follows.
-Chbi0,i1,m′ If i0,ski0,pki0 or i1,ski1,pki1∉List, return ⊥. Otherwise, we generate a ring R′ which contains the public keys of i0 and the public key of i1. If R′,ib,m′,∗∈SList, return ⊥. Otherwise, we generate a signature by calling SignR′,ib,m′ where b∈0,1. Finally return the signature R′,m′,σb. Note that the triple R′,ib,m′,σb is also added to the list SList.
Query 2 The adversary A queries Add, Reg, Crpt, Sign, and hash oracles in the same way as in Query 1, but he is not allowed to query about Crpt with any k in the ring R′ or Sign with R′,m′.
Finally,A returns a guess of bit b according to the signature R′,m′,σb from Chbi0,i1,m′.
Since the pairR′,m′ of the two signatures R′,m′,σ0 and R′,m′,σ1 are the same as each other, we will omit it when we measure the statistical distance between XR′,m′,σ0 and XR′,m′,σ1. Set the σ=c1,s1,…,sn as a vector of n+1 coordinates. Thus, each coordinate is independent of each other. For clarity, σ0 and σ1 are written as c1′,s1′,…,si0',…,si1',…,sn′ and c1'′,s1'′,…,si0'′,…,si1'′,…,sn'′. All the signature coordinates except for si0' of i0 are directly chosen uniformly from the domains defined in the ASMC scheme (here, we refer the domain as domain A, but the meaning of domain A for distinct kinds of nodes is different), while si1'′ of signature i1 is not directly chosen from the domain A. We set λ=minNmin,q,nEC,p, λ′=maxNmax,q,nEC,p. The distance between XR′,m′,σ0 and XR′,m′,σ1 is(55)△XR′,m′,σ0,XR′,m′,σ1=∑c1,si∈A,i∈1,…,nPrXR′,m′,σ0=c1,s1,…,si0,…,si1,…,sn−PrXR′,m′,σ1=c1,s1,…,si0,…,si1,…,sn=∑c1,si∈A,i∈1,…,nPrc1,Prs1,…,si0−1,si0+1,…,si1−1,si1+1,…,sn|Prsi0|si0−1,Prsi1−Prsi0,Prsi1|si1−1|=∑c1,si∈A,i∈1,…,nPrc1,∏i=1i≠i0,i1tPrsi,|Prsi0|si0−1,Prsi1−Prsi0,Prsi1|si1−1|≤λ′λt−1λ'2λ2−λ2λ'2=λ′λn−1λ′λ+λλ′λ'2−λ2λλ′≤2λ′λtλ′λ2−1=2λ′λtλ′λ+1λ′λ−1≤4λ′λn+1λ′λ−1,
The variablesα,β,γ,δ^ are used in the real signer’s secure value sib computation, and they are generated uniformly as α←$ZNj, β←$Zp, γ←$Zn, and δ^←$Dz. So, sib can still be considered a uniform chosen variable. c1 is generated by HashRSA,HashDL,HashEC,HashLattice random oracles with uniform distributions as HashRSA:0,1∗⟶ZNmin, HashDL:0,1∗⟶Zp, HashEC:0,1∗⟶Zn, HashLattice:0,1∗⟶Zq. So, we have Equation (2).
If the security parameterk is larger enough, λ′/λ−1≤g′k for any polynomial g′, and 4λ′/λn+1 will have an upper bound. Then, we have △XR′,m′,σ0,XR′,m′,σ1≤gk for any polynomial g and sufficiently large k.


## 6. Efficiency Analysis and Experimental Results

In this section, we will give an analysis of the computation cost and the communication overhead of the proposed schemes. To the best of our knowledge, there is no other heterogeneous IIoT authentication system in the literature that supports multiple cryptosystems except for Sun’s authentication scheme which supports two different cryptosystems. So, we just compare the scheme proposed by Wei et al. [7] with our schemes.Table3 gives the comparison of the computation costs of the proposed ASMC schemes and the scheme proposed by Wei et al. [7]. For the sake of fairness, we assume that the number of nodes in the two schemes is the same. Each ring has n nodes. Furthermore, we assume that the proportion of each type of node in the two schemes is the same. Specifically, there are n/2 RSA nodes and n/2 DL nodes in [7], while there are n/4 RSA nodes, n/4 DL nodes, n/4 ECC nodes, and n/4 Lattice nodes in our scheme.Table 3
The comparison of computational cost.
SchemeOffline-signOnline-signVerificationWei et al. [7] (RSA signer)n/2SR+SD−SRSR+n/2SDn/2VR+VDWei et al. [7] (DL signer)n/2SR+SD−SDn/2SDn/2VR+VDOur scheme (RSA signer)n/4SR+SD+SE+SL−SRSR+n/4SD+SEn/4SR+SD+SE+SLOur scheme (DL signer)n/4SR+SD+SE+SL−SDn/4SD+SEn/4SR+SD+SE+SLOur scheme (ECC signer)n/4SR+SD+SE+SL−SEn/4SD+SEn/4SR+SD+SE+SLOur scheme (lattice signer)n/4SR+SD+SE+SL−SLn/4SD+SEn/4SR+SD+SE+SLLetSR and VR denote the signature generation and verification exponentiation operations carried out by an RSA node. Similarly, let SD and VD denote the signing and verification exponentiation operations carried out by a DL node. Let SE and VE represent the signing and verification elliptic curve multiplication operations carried out by an ECC node. Let SL and VL represent the signing and verification polynomial multiplication operations carried out by a lattice node.Table4 gives the comparison of the communication overhead between Wei et al. [7] and our ASMC scheme. GRSA is the size of a random number in the signature chosen by the RSA node, while GDL and GEC are the size of random numbers chosen by the DL node and ECC node, respectively. G is the size of the generator of the quotient polynomial ring D, and z is the number of polynomials contained in one vector which is chosen by the lattice node. We set the security level as 1024-bit RSA, 1024-bit DL, 160-bit ECC. As for lattice nodes, we choose nlattice  = 256, z=16 and set qlattice to a 16bit prime number, and we note that the meaning of those symbols is the same as in Theorem 1. As the size of zG is much bigger than the others, so the communication overhead of our ASMC scheme is higher than the scheme of Wei et al. [7], as shown in Table 4. Considering that the communication overhead of lattice-based signatures is generally larger than that of other type signatures, even the communication overhead of our ASMC scheme is several times of Wei et al. [7], it is still acceptable compared with other lattice-based ring signature schemes. When the number of signing nodes is 20, the communication overhead of our ASMC scheme is 42.5 K bytes, while the communication overhead of other lattice-based ring signature schemes is basically of the same order of magnitude as ours or even larger. For instance, the communication overhead of SALRS proposed by Liu et al. [32] is 53.6k with 16 ring members.Table 4
The comparison of communication overhead.
SchemeCommunication overheadNo. of bits (n = 20)Wei et al. [7]n/2GRSA+GDL+GRSA12,864Our schemen/4GRSA+GDL+GEC+zG+GRSA339,744Table5 gives the simulation experiments’ computation time based on different values of n on a PC. The configuration is Intel Core i7-8550 CPU@2.00 GHz and 16 GB RAM with Window 10 operating system. The signature is generated by using the NTL [33]. The computational time of every operation is calculated as the average time of 10 executions. Our simulation is based on the architecture of adjacent nodes using the same cryptographic system. Since the actual operations remain the same in the architecture of a mixture of distinct cryptosystem nodes, so the results of the two architectures shown in Figures 2 and 3 are similar.Table 5
The computation time (msec.).
PhaseValue of nReal signer typeRSADLECCLatticeWei et al. [7]Our schemeWei et al. [7]Our schemeWei et al. [7]Our schemeWei et al. [7]Our schemeOffline sign2041.5232.2735.4628.38-30.23-30.514076.6560.0765.4556.07-55.74-51.9260119.0993.7100.8784.18-81.55-79.0980141.44121.98141.76102.86-104.46-108.53100195.26158.78156.01129.93-129.53-134.18200358.72310.94348.34245.6-290.21-262.25Online sign2031.6523.1523.7220.42-21.63-22.454058.5144.8746.540.82-43.18-43.186089.9665.7468.8452.39-56.91-63.680145.03106.08111.1199.56-106.99-109.41100181.17138.96174.66130.69-140.93-144.23200284.59207.31228.58194.36-203.27-205.16Verify20113.8487.47DL76.4-82.21-89.1740140.9987.57104.4580.86-76.15-91.8360205.48132.88109.05128.2-121.5-132.5980331.99224.39168.86207.82-197.29-220.03100389.37319.81251.03269.04-289.02-299.06200687.8492.57325.09400.02-390.87-433.24Figure 4
Computational cost for Online-Sign.Figures4–6 show the computation time of a different number of signing nodes in the phase Offline-Sign, Online-Sign, and verification, respectively. From the experiment results, we can see that the computational cost of our ASMC scheme is lower than that of [7], and the computational cost difference between the two schemes increases with the number of signing nodes.Figure 5
Computational cost for Offline-Sign.


## 7. Conclusion

In this paper, we proposed two novel privacy-preserving message Figure6 authentication schemes that allow IIoT devices to use different security systems and parameters. Our AMSC schemes can support four kinds of nodes. Analysis shows that the ASMC schemes can provide the authentication and integrity of the message and the anonymity of the message senders.Figure 6
Computational cost for verification.



---

*Source: 9919089-2022-10-17.xml*