# Certificateless Network Coding Ring Signature Scheme

Authors: Huifang Yu; Weike Wang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Traditional certificateless ring signature is not suitable for the network coding environment. In this view, a new certificateless network coding ring signature (CL-NCRS) is devised by using the techniques of multisource network coding and certificateless ring signature. Network coding is a kind of information interaction technology and can improve system robustness and save wireless network resources. CL-NCRS satisfies the unforgeability and unconditional anonymity; moreover, it has relatively higher communication and computational efficiency.


---

## Body

## 1. Introduction

Network coding is a kind of information interaction technology with the functions of routing and coding and has large information throughput and good robustness. If the nodes encode the messages in a certain mode instead of forwarding them, the network structure can obtain maximum transmission efficiency in theory [1]. In 2002, Cai and Yeung proposed the first network coding security model [2]; the source nodes must understand the internal structure of network, and the edge set may be eavesdropped. Zhou and Xu [3] proposed an antipollution network coding cipher algorithm using homomorphic digital signature which can determine the attackers’ location and so can resist the pollution attacks in time. Yu and Li [4] proposed single source network coding homomorphic signature scheme by using the generation identifier and homomorphic hash function, it reduces the communication overhead and saves network resources, and it can resist the intrageneration and intergeneration pollutions. Wang et al. [5] proposed the hybrid network coding scheme that can resist data pollution attacks, label pollution attacks, and intergenerational pollution attacks. Abovementioned network coding schemes are only suitable for single source network coding. Multisource network coding is much more complex. Niu et al. [6] proposed the antipollution multisource network coding cipher algorithm. Li and Mei [7] proposed homomorphic signature scheme using the generation identifier which can prevent the replay attacks and use the linear operation to reduce the node computing requirement. Network coding signature schemes in [8–10] can effectively prevent the forgery attacks, but the computation overhead in signature and verification phases is high. Li et al. [11] proposed new network coding signature by using homomorphism to solve the problem of identity authentication in multisource network coding.In ring signature, there is no group administrator and all members in the ring have the same status. A user represents a group of users to sign the message with their own private key. The ring signer can sign the message on behalf of a group of users in completely anonymous way; when the verifier receives the signature, the verifier only knows that the signer comes from a ring but does not know who is the real signer; therefore, it also enhances the privacy of the signer. Ring signature overcomes the defect of excessive authority of the group administrator in group signature. Traditional certificateless ring signature is not appropriate to multisource network coding; it is worth devising an antipollution and certificateless ring signature scheme.In this paper, on the basis of homomorphic hash function and ring signature theory [12, 13], an efficient and certificateless network coding ring signature (CL-NCRS) is devised. In CL-NCRS, the source node generates a ring signature for each message vector by using the private key, and the intermediate node linearly combines the received messages and directly generates the ring signature of the combination message by using the homomorphic hash function. CL-NCRS has the unconditional anonymity and UF-CMA security (unforgeability against adaptive message-chosen attacks) [14, 15], and it can defense the pollution attacks.


## 2. Preliminaries

### 2.1. Multisource Network Coding Model

In multisource network coding, each source node can send multiple messages and a unified index. AssumeG=M,E is a multisource network, then M is the node set and E is the edge set. As shown in Figure 1, the source node set is denoted by S=s1,…,sm⊂M, and the destination node set is denoted by T=t1,…,tk⊂M.Figure 1
Transmission model for multisource network coding.Each messagevi∈v1,…,vm is composed of n elements in finite field F which can be regarded as a vector in n-dimensional vector space V/F, where Vi=vi,1,…,vi,n,1≤i≤m. If w=w1,…,wn is the message sent on any side of the multicast network, the linear combination of l messages received by the intermediate node can be expressed as(1)w=∑j=1lαjwj.The coding coefficient vectorα=α1,...,αl is called the local coding vector; then the message W on one side of message transmission can also be expressed by the linear combination of original message Vi1≤i≤m:(2)W=∑i=1mβiVi,where β=β1,…,βm is called the global coding vector. If the receiving node ti receives m linearly independent messages w1,…,wm and the global coding vector is β1,...,βm, the original message V1,…,Vm can be recovered in the following way:(3)W1⋮Wm=GtiV1⋮VmGti=β1,…,βm−1.Since the receivedm messages are linearly independent and the matrix Gti is full rank and invertible, then the original message (V1, …, Vm) is obtained by the following method:(4)V1⋮Vm=Gti−1W1⋮Wm.In order to facilitate the decoding of the destination node, the global coding vectorβi and the message can be transmitted together. The extended original message can be regarded as a vector in the m + n dimension vector space V′/F:(5)vi=vi,1,…,vi,n,0,…,0,1,0,…,0∈Fm+n,1≤i≤m.That is to say,(6)W=∑i=1mβiVi=β1V1+β2V2+…+βmVm=β1v1,1,…,β1v1,n,β1,0,…,0+β2v2,1,…,β2v2,n,0,β2,…,0+⋯+βmvm,1,…,βmvm,n,0,0,…,βm=β1v1,1+β2v2,1+⋯+βmvm,1,…,β1v1,n+β2v2,n+⋯+βmvm,n,β1,β2,…,βm=∑i=1mβivi,1,…,∑i=1mβivi,n,β1,β2,…,βm=∑i=1mwi,1,…,∑i=1mwi,n,∑i=1mβi,1,∑i=1mβi,2,…,∑i=1mβi,m.Hence, the encoded message can be represented asWi=wi,1,…,wi,n,βi,1,βi,2,…,βi,m=wi,1,…,wi,m+n.


### 2.2. Homomorphic Hash Function

The trusted third party (TTP) generates a hash parameter setG=p,q,r⟶, where p and q are two large primes and satisfy the condition q|p − 1. Parameter r⟶ is a row vector of 1×m+n which is randomly composed of all elements with order q in Zq:(7)r⟶=1,…,m+n,rip≡1modp,ri∈Zpand1≤i≤m+n.Homomorphism verification of the hash function: for message vectorWi=w1,…,wm+n received by any node in network, we have(8)H2w⟶=∏j=1m+nrjwjmodp.


### 2.3. Bilinear Map

G1 and G2 are multiplicative cyclic groups with order q, where G1=g=gk|k=0,1,…. e:G1×G1⟶G2 is a bilinear map with three properties: (1) ega,h′b=eg,h′ab for any aandb∈Zq and gandh′∈G1; (2) eg,g≠1; (3) there exists an efficient algorithm to calculate eg,h′ for any gandh′∈G1.


### 2.4. DL Problem

Given a finite cyclic groupG=g=gk|k=0,1,…, where g is a generator of group G, n=G. For a∈0,n and g∈G, it is easy to calculate h=ga. Given g and h∈G, the discrete logarithm (DL) problem is to find a0≤a≤n such that h=ga.


### 2.5. Flowchart of CLRS

In this section, we show the working process of a certificateless ring signature (CLRS) by Figure2.Figure 2
Flowchart of working process of CLRS.


## 2.1. Multisource Network Coding Model

In multisource network coding, each source node can send multiple messages and a unified index. AssumeG=M,E is a multisource network, then M is the node set and E is the edge set. As shown in Figure 1, the source node set is denoted by S=s1,…,sm⊂M, and the destination node set is denoted by T=t1,…,tk⊂M.Figure 1
Transmission model for multisource network coding.Each messagevi∈v1,…,vm is composed of n elements in finite field F which can be regarded as a vector in n-dimensional vector space V/F, where Vi=vi,1,…,vi,n,1≤i≤m. If w=w1,…,wn is the message sent on any side of the multicast network, the linear combination of l messages received by the intermediate node can be expressed as(1)w=∑j=1lαjwj.The coding coefficient vectorα=α1,...,αl is called the local coding vector; then the message W on one side of message transmission can also be expressed by the linear combination of original message Vi1≤i≤m:(2)W=∑i=1mβiVi,where β=β1,…,βm is called the global coding vector. If the receiving node ti receives m linearly independent messages w1,…,wm and the global coding vector is β1,...,βm, the original message V1,…,Vm can be recovered in the following way:(3)W1⋮Wm=GtiV1⋮VmGti=β1,…,βm−1.Since the receivedm messages are linearly independent and the matrix Gti is full rank and invertible, then the original message (V1, …, Vm) is obtained by the following method:(4)V1⋮Vm=Gti−1W1⋮Wm.In order to facilitate the decoding of the destination node, the global coding vectorβi and the message can be transmitted together. The extended original message can be regarded as a vector in the m + n dimension vector space V′/F:(5)vi=vi,1,…,vi,n,0,…,0,1,0,…,0∈Fm+n,1≤i≤m.That is to say,(6)W=∑i=1mβiVi=β1V1+β2V2+…+βmVm=β1v1,1,…,β1v1,n,β1,0,…,0+β2v2,1,…,β2v2,n,0,β2,…,0+⋯+βmvm,1,…,βmvm,n,0,0,…,βm=β1v1,1+β2v2,1+⋯+βmvm,1,…,β1v1,n+β2v2,n+⋯+βmvm,n,β1,β2,…,βm=∑i=1mβivi,1,…,∑i=1mβivi,n,β1,β2,…,βm=∑i=1mwi,1,…,∑i=1mwi,n,∑i=1mβi,1,∑i=1mβi,2,…,∑i=1mβi,m.Hence, the encoded message can be represented asWi=wi,1,…,wi,n,βi,1,βi,2,…,βi,m=wi,1,…,wi,m+n.


## 2.2. Homomorphic Hash Function

The trusted third party (TTP) generates a hash parameter setG=p,q,r⟶, where p and q are two large primes and satisfy the condition q|p − 1. Parameter r⟶ is a row vector of 1×m+n which is randomly composed of all elements with order q in Zq:(7)r⟶=1,…,m+n,rip≡1modp,ri∈Zpand1≤i≤m+n.Homomorphism verification of the hash function: for message vectorWi=w1,…,wm+n received by any node in network, we have(8)H2w⟶=∏j=1m+nrjwjmodp.


## 2.3. Bilinear Map

G1 and G2 are multiplicative cyclic groups with order q, where G1=g=gk|k=0,1,…. e:G1×G1⟶G2 is a bilinear map with three properties: (1) ega,h′b=eg,h′ab for any aandb∈Zq and gandh′∈G1; (2) eg,g≠1; (3) there exists an efficient algorithm to calculate eg,h′ for any gandh′∈G1.


## 2.4. DL Problem

Given a finite cyclic groupG=g=gk|k=0,1,…, where g is a generator of group G, n=G. For a∈0,n and g∈G, it is easy to calculate h=ga. Given g and h∈G, the discrete logarithm (DL) problem is to find a0≤a≤n such that h=ga.


## 2.5. Flowchart of CLRS

In this section, we show the working process of a certificateless ring signature (CLRS) by Figure2.Figure 2
Flowchart of working process of CLRS.


## 3. Formal Definition

### 3.1. Algorithm Definition

A certificateless network coding ring signature (CL-NCRS) scheme is defined as follows.Setup: input a security parameter 1k; this algorithm outputs the master key x and a set ϕ of the system parameter.Extract: inputϕ and a user’s identity IDi; this algorithm outputs this the corresponding partial private key Di.KeyGen: inputϕ and a user’s identity IDi; this algorithm outputs this user’s secret value xi and public key Yi.Ring signature: inputϕ, the master key x, the message v⟶j, the partial private key Di, the secret value xi, and the public key Yi; this algorithm outputs a signature σ⟶.Combine: input the coding vectorα⟶=α1,…,αl and the message vector w⟶1,…,w⟶l; this algorithm outputs a combined message vector w⟶ and the corresponding signature σ.Verification: inputϕ, σ⟶, the signer’s identity IDi, the public key Yi, and the message v⟶j. If the verification equation is true, the verifier accepts the signature and stops the game otherwise.


### 3.2. Security Model

In this section, the UF-CMA security model of CL-NCRS is in terms of the gameG1 (G2) between the challenger B and adversary A1 (A2) is discussed [16].Public key queries:A1 (A2) queries a public key for the identity IDi; B returns a public key.Partial private key queries:A1 (A2) queries a partial private key for the identity IDi; B returns a partial private key.Secret value queries:A1 (A2) queries a secret value for the identity IDi; B returns a secret value.Public key replacement:A1 replaces the previous Yi with a new public key Yi′ chosen in a suitable range.Ring signature queries:A1 (A2) submits a signature query for a message. B returns a signature σ by calling the signature algorithm.Combination queries:A1 (A2) submits a combination query. B returns a combination signature.Verification queries:A1 (A2) submit a verification query. If the verification equation holds, B outputs a plaintext and otherwise stops the game.Finally,A1 (A2) outputs a forged signature. In queries, A1 should not request the full private key of identity IDs; A2 cannot query the private key of identity IDs. In addition, the forged signature should not be returned by any signcryption oracle. A1 (A2) wins the G1 (G2) if the result of unsigncryption is not the symbol ⊥. We define the advantage of A1 (A2) as the probability which it wins the game G1 (G2).Definition 1 (unforgeability).
A CL-NCRS is UF-CMA secure if no probabilistic polynomial time adversaryA1 (A2) wins in the G1 (G2) with nonnegligent advantage.


## 3.1. Algorithm Definition

A certificateless network coding ring signature (CL-NCRS) scheme is defined as follows.Setup: input a security parameter 1k; this algorithm outputs the master key x and a set ϕ of the system parameter.Extract: inputϕ and a user’s identity IDi; this algorithm outputs this the corresponding partial private key Di.KeyGen: inputϕ and a user’s identity IDi; this algorithm outputs this user’s secret value xi and public key Yi.Ring signature: inputϕ, the master key x, the message v⟶j, the partial private key Di, the secret value xi, and the public key Yi; this algorithm outputs a signature σ⟶.Combine: input the coding vectorα⟶=α1,…,αl and the message vector w⟶1,…,w⟶l; this algorithm outputs a combined message vector w⟶ and the corresponding signature σ.Verification: inputϕ, σ⟶, the signer’s identity IDi, the public key Yi, and the message v⟶j. If the verification equation is true, the verifier accepts the signature and stops the game otherwise.


## 3.2. Security Model

In this section, the UF-CMA security model of CL-NCRS is in terms of the gameG1 (G2) between the challenger B and adversary A1 (A2) is discussed [16].Public key queries:A1 (A2) queries a public key for the identity IDi; B returns a public key.Partial private key queries:A1 (A2) queries a partial private key for the identity IDi; B returns a partial private key.Secret value queries:A1 (A2) queries a secret value for the identity IDi; B returns a secret value.Public key replacement:A1 replaces the previous Yi with a new public key Yi′ chosen in a suitable range.Ring signature queries:A1 (A2) submits a signature query for a message. B returns a signature σ by calling the signature algorithm.Combination queries:A1 (A2) submits a combination query. B returns a combination signature.Verification queries:A1 (A2) submit a verification query. If the verification equation holds, B outputs a plaintext and otherwise stops the game.Finally,A1 (A2) outputs a forged signature. In queries, A1 should not request the full private key of identity IDs; A2 cannot query the private key of identity IDs. In addition, the forged signature should not be returned by any signcryption oracle. A1 (A2) wins the G1 (G2) if the result of unsigncryption is not the symbol ⊥. We define the advantage of A1 (A2) as the probability which it wins the game G1 (G2).Definition 1 (unforgeability).
A CL-NCRS is UF-CMA secure if no probabilistic polynomial time adversaryA1 (A2) wins in the G1 (G2) with nonnegligent advantage.


## 4. Concrete Instance of CL-NCRS

### 4.1. Setup

In the setup algorithm,G1 and G2 are two multiplicative cyclic groups with order q; g is a generator of group G1; e:G1×G1⟶G2 is a bilinear map, as shown in Section 2.3; H1:0,1∗⟶G1 and H2:0,1∗⟶Zq∗ are one-way hash functions. KGC (Key Generator Center) chooses a master key x from Zq∗ and calculates the system public key Y = gx. Finally, KGC keeps the master key x secret but publishes a set ϕ=G1,G2,Y,g,q,e,H1,H2 of system parameter.


### 4.2. Extract

In the extraction algorithm, KGC calculates a user’s partial private keyDi = Qix, where Qi = H1 (IDi) and IDi is the identity of user. Then, KGC sends Di to the user.


### 4.3. KeyGen

In the key generation algorithm, a user withIDi chooses xi from Zq∗ as a secret value and calculates the corresponding public key Yi=gxi. The full private key of this user is (xi, Di).


### 4.4. Ring Signature

In this algorithm,IDs is the identity of ring signer IDs∈ID1,…,IDc, the full private key of the ring signer is (xs, Ds), the public key of the ring signer is Ys, and v⟶∈0,1∗ is a message. Relevant operation steps are carried out as follows:(1)
Forj = 1, 2, …, c (j ≠ s), ring signer randomly selects aj∈Zq∗ and calculates σj=YiYaj(2)
Ring signer calculatesη=H2v⟶(3)
Ring signer calculatesσs=DsηQsxs/∏j=1,j≠scσj(4)
Ring signer outputs a ring signature of messagev⟶: σ⟶us=σ1us,…,σcus which is recorded as σ⟶=σ1,…,σc for convenience


### 4.5. Combine

Given the local coding vectorα⟶=α1,…,αl, the message vector received by intermediate nodes w⟶1,…,w⟶l, and its corresponding ring signature σ⟶1,…,σ⟶l. If the combined message vector is w⟶=∑j=1lαjw⟶j, then the generation process of signature σ⟶=σ1,…,σc relevant to w⟶ is σj=∏i=1lσi,jαi, where σi,j1≤i≤mand1≤j≤c represents the j-th element of σ⟶i. Then, the combined signature can be expressed as follows:(9)σ=∏i=1lσiαi.


### 4.6. Verification

Given the public keysY1,…,Yc∈G1, message v⟶, and ring signature σ⟶=σ1,…,σc, the destination codes calculate η=H2v⟶ firstly. If the verification equality eQs,YηYs=∏j=1ceσj,g holds, this means that σ⟶=σ1,…,σc is valid and invalid otherwise.


## 4.1. Setup

In the setup algorithm,G1 and G2 are two multiplicative cyclic groups with order q; g is a generator of group G1; e:G1×G1⟶G2 is a bilinear map, as shown in Section 2.3; H1:0,1∗⟶G1 and H2:0,1∗⟶Zq∗ are one-way hash functions. KGC (Key Generator Center) chooses a master key x from Zq∗ and calculates the system public key Y = gx. Finally, KGC keeps the master key x secret but publishes a set ϕ=G1,G2,Y,g,q,e,H1,H2 of system parameter.


## 4.2. Extract

In the extraction algorithm, KGC calculates a user’s partial private keyDi = Qix, where Qi = H1 (IDi) and IDi is the identity of user. Then, KGC sends Di to the user.


## 4.3. KeyGen

In the key generation algorithm, a user withIDi chooses xi from Zq∗ as a secret value and calculates the corresponding public key Yi=gxi. The full private key of this user is (xi, Di).


## 4.4. Ring Signature

In this algorithm,IDs is the identity of ring signer IDs∈ID1,…,IDc, the full private key of the ring signer is (xs, Ds), the public key of the ring signer is Ys, and v⟶∈0,1∗ is a message. Relevant operation steps are carried out as follows:(1)
Forj = 1, 2, …, c (j ≠ s), ring signer randomly selects aj∈Zq∗ and calculates σj=YiYaj(2)
Ring signer calculatesη=H2v⟶(3)
Ring signer calculatesσs=DsηQsxs/∏j=1,j≠scσj(4)
Ring signer outputs a ring signature of messagev⟶: σ⟶us=σ1us,…,σcus which is recorded as σ⟶=σ1,…,σc for convenience


## 4.5. Combine

Given the local coding vectorα⟶=α1,…,αl, the message vector received by intermediate nodes w⟶1,…,w⟶l, and its corresponding ring signature σ⟶1,…,σ⟶l. If the combined message vector is w⟶=∑j=1lαjw⟶j, then the generation process of signature σ⟶=σ1,…,σc relevant to w⟶ is σj=∏i=1lσi,jαi, where σi,j1≤i≤mand1≤j≤c represents the j-th element of σ⟶i. Then, the combined signature can be expressed as follows:(9)σ=∏i=1lσiαi.


## 4.6. Verification

Given the public keysY1,…,Yc∈G1, message v⟶, and ring signature σ⟶=σ1,…,σc, the destination codes calculate η=H2v⟶ firstly. If the verification equality eQs,YηYs=∏j=1ceσj,g holds, this means that σ⟶=σ1,…,σc is valid and invalid otherwise.


## 5. Correctness Analysis

### 5.1. Signature Verification

After receiving a ring signatureσ⟶=σ1,…,σc, the receiver calculates η=H2v⟶ and then verifies the following equality:(10)eQs,YηYs=∏j=1ceσj,g.The verification process of above equality is as follows:(11)∏j=1ceσj,g=∏j=1,j≠sceσj,g⋅eσs,g=∏j=1,j≠sceYiYaj,g⋅eDsηQsxs,ge∏j=1,j≠scYiYaj,g=e∏j=1,j≠scYiYaj,g⋅eDsηQsxs,ge∏j=1,j≠scYiYaj,g=eQs,YηYs.


### 5.2. Combination Verification

Given the messagev⟶1,…,v⟶m and global coding vector β⟶=β1,…,βm, the message vector w⟶=∑j=1mβjv⟶j1≤j≤m is received by the intermediate nodes and the signature corresponds to the message vector w⟶ is σ⟶=σ1,…,σc In the verification phase, eQs,YηjYs=∏i=1ceσi,g holds, where ηj=H2v⟶j.In the multisource network coding environment, the intermediate nodes combine the messages from different source nodes and form a combination signature. Each source nodesi has a unique identifier ui∈u1,...,uc, the global coding vector of each source node user is expressed as βju1,…,βjuc, respectively. In order to distinguish the possible combination of the same message vector, the message vector is expressed as w⟶=∑j=1m∑k=1dβjukv⟶j1≤j≤m.Ring signature of message vectorw⟶ can be expressed as σ⟶=∏j=1m∏k=1dσjukβjuk, and then, the i-th component in ring signature can be expressed as σ⟶i=∏j=1m∏k=1dσjukβjuk,1≤i≤c, where σj,iuk denotes the i-th component of ring signature σ⟶juk. Then, the verification process of the equality eQs,YηjYs=∏i=1ceσi,g is as follows:(12)∏i=1ceσi,g=∏i=1ce∏j=1m∏k=1dσj,iukβjuk,g=∏j=1m∏k=1de∏i=1cσj,iuk,gβjuk=∏j=1m∏k=1d∏i=1ceσj,iuk,gβjuk.Then, the verification equalityeQs,YηYs=∏j=1ceσjus,g holds and the verification of message v⟶j can be denoted as eQs,YηYs=∏i=1ceσj,ius,g, and the verification process of this equality is shown as follows:(13)∏j=1m∏k=1c∏i=1ceσj,iuk,gβjuk=∏j=1m∏k=1ceQs,YηjYsβjuk=∏j=1meQs,Yηj∑k=1cβjukYs=∏j=1meQs,YηjβjYs=e∏j=1mQs,YηjβjYs=eQs,YηYs.


## 5.1. Signature Verification

After receiving a ring signatureσ⟶=σ1,…,σc, the receiver calculates η=H2v⟶ and then verifies the following equality:(10)eQs,YηYs=∏j=1ceσj,g.The verification process of above equality is as follows:(11)∏j=1ceσj,g=∏j=1,j≠sceσj,g⋅eσs,g=∏j=1,j≠sceYiYaj,g⋅eDsηQsxs,ge∏j=1,j≠scYiYaj,g=e∏j=1,j≠scYiYaj,g⋅eDsηQsxs,ge∏j=1,j≠scYiYaj,g=eQs,YηYs.


## 5.2. Combination Verification

Given the messagev⟶1,…,v⟶m and global coding vector β⟶=β1,…,βm, the message vector w⟶=∑j=1mβjv⟶j1≤j≤m is received by the intermediate nodes and the signature corresponds to the message vector w⟶ is σ⟶=σ1,…,σc In the verification phase, eQs,YηjYs=∏i=1ceσi,g holds, where ηj=H2v⟶j.In the multisource network coding environment, the intermediate nodes combine the messages from different source nodes and form a combination signature. Each source nodesi has a unique identifier ui∈u1,...,uc, the global coding vector of each source node user is expressed as βju1,…,βjuc, respectively. In order to distinguish the possible combination of the same message vector, the message vector is expressed as w⟶=∑j=1m∑k=1dβjukv⟶j1≤j≤m.Ring signature of message vectorw⟶ can be expressed as σ⟶=∏j=1m∏k=1dσjukβjuk, and then, the i-th component in ring signature can be expressed as σ⟶i=∏j=1m∏k=1dσjukβjuk,1≤i≤c, where σj,iuk denotes the i-th component of ring signature σ⟶juk. Then, the verification process of the equality eQs,YηjYs=∏i=1ceσi,g is as follows:(12)∏i=1ceσi,g=∏i=1ce∏j=1m∏k=1dσj,iukβjuk,g=∏j=1m∏k=1de∏i=1cσj,iuk,gβjuk=∏j=1m∏k=1d∏i=1ceσj,iuk,gβjuk.Then, the verification equalityeQs,YηYs=∏j=1ceσjus,g holds and the verification of message v⟶j can be denoted as eQs,YηYs=∏i=1ceσj,ius,g, and the verification process of this equality is shown as follows:(13)∏j=1m∏k=1c∏i=1ceσj,iuk,gβjuk=∏j=1m∏k=1ceQs,YηjYsβjuk=∏j=1meQs,Yηj∑k=1cβjukYs=∏j=1meQs,YηjβjYs=e∏j=1mQs,YηjβjYs=eQs,YηYs.


## 6. Security Analysis

In CL-NCRS, no external attacker can obtain any message signature without the members’ private key. CL-NCRS is vulnerable to two types of adversaries:A1 and A2. Here, A1 is a malicious user who can change the public key of any user but cannot know the master key of the system; A2 is a malicious KGC who knows the master key of the system but cannot change any user’s public key and provide the security proof of existential unforgeability, unconditional anonymity, and antipollution attacks under adaptive chosen-plaintext attacks.Theorem 1.
In the random oracle model, if a probabilistic polynomial time adversaryA1 can break the UF-CMA-I security of CL-NCRS with probability ε, then there must exist an algorithm B to solve the discrete logarithm (DL) problem with probability ε′ (qp, qs, and qr are the query times of partial private key, secret value, and public key replacement, respectively), where ε′≥ε/eqs+qp+qr.Proof.
Given a discrete logarithm random instanceg,ga∈G1, the aim of the challenger B is to use the adversary A1 as a subroutine to obtain the value of a. B selects a challenge identity ID∗ and maintains the initially empty lists L1,L2,L3,L4,andL5 which represent the H1 query list, the H2 query list, the public key query list, the signature query list, and the combination query list, respectively. At first, B runs the setup algorithm to obtain the system parameter ϕ=G1,G2,Y=ga,g,q,e,H1,H2 and then sends ϕ to A1, where a acts as the master key of system and is unknown to B. Then, A1 adaptively carries out a series of polynomial bounded queries as follows.
Public key queries:A1 queries a public key for the identity IDi. B returns Yi to A1 and adds U,IDi,Yi,xi,− into the list L3.
H1 queries: A1 queries the H1 oracle for the identity IDi. If the relevant content already exists in the list L1, B returns hi as answer; otherwise, B returns Qi←gλi and adds U,IDi,−,Qi,λis into the list L1, where λi is a random from Zq∗.
H2 queries: A1 queries the H2 oracle for the identity IDi. If the corresponding query result already exists in the list L2, B returns h2 as the answer; otherwise, B returns a random number h2 from Zq∗ and adds U,IDi,v⟶,h2 into the list L2.
Partial private key queries:A1 queries a partial private key for the identity IDi. B responds as follows: (1) if IDi=ID∗, B fails and terminates the game; (2) if IDi≠ID∗, B returns Di←Yλi to A1 and updates the list L3 with U,IDi,Yi,xi,Di.
Secret value queries:A1 queries a secret value for the identity IDi. If IDi≠ID∗, B outputs the secret value xi from the list L3; otherwise, B fails and terminates the game.
Public key replacement:A1 chooses Yi′ to replace the public key of the identity IDi. If IDi=ID∗, B fails and terminates the game; otherwise, B updates list L3 with U,IDi,Yi′,−.
Ring signature queries:A1 submits a ring signature query. If IDs≠ID∗ and the public key of identity IDi is not replaced, B returns a signature by running ring signature algorithm. If IDs=ID∗ and the public key of identity IDi has been replaced, B responds as follows:(1)
B randomly selects aj∈Zq∗ to calculate σj=YiYaj1≤j≤candj≠s and η=H2v⟶(2)
B calculates σs=YηλsYsλs/∏j=1,j≠scσj and adds v⟶,U,IDi,aj,η,σj,σs into the list L4(3)
B returns σ⟶us=σ1us,…,σcus
Combination queries:A1 submits a combination query. B calculates the combination message vectors w⟶=∑j=1lαjw⟶j, and the signature of w⟶ is σj=∏i=1lσi,jαi, where σi,j1≤i≤mand1≤j≤c represents the j-th element of σ⟶i. Finally, B returns the combination signature σ=∏i=1lσiαi to A1 and stores α⟶,w⟶,σ in the list L5. Note that α⟶=α1,…,αl is the local coding vector; w⟶1,…,w⟶l are the message vectors, and σ⟶1,…,σ⟶l are the ring signatures.
Verification queries:A1 submits a verification query. If eQs,YηYs=∏j=1ceσjus,g holds, B outputs a valid ring signature and terminates the game otherwise.
After a series of adaptive queries,A1 outputs a forgery v⟶∗,U,ID∗,aj∗,η∗,σj∗,σs∗ to B. A1 does not know the private key of any member in the ring. In the probabilistic polynomial time, two valid signatures are generated as follows:(14)σs=DsηQsxs∏j=1,j≠scYiYaj,σs=Ds∗η∗Qs∗xs∗∏j=1,j≠scYi∗Yaj∗.
Then, the solutiona of DL problem instance can be obtained via the above equalities:(15)a=∑j=1,j≠sclogYiYi∗−1+λs∗xs∗−λsxsλsη−λs∗η∗−∑j=1,j≠scaj−aj∗.
Referring to the probability analysis in [16], we obtain that the probability ε′≥ε/eqs+qp+qr of B in solving the discrete logarithm problem in polynomial time is negligible. Hence, A1 cannot break the UF-CMA-I security of CL-NCRS.Theorem 2.
In the random oracle model, if a probabilistic polynomial time adversaryA2 can break the UF-CMA-II security of CL-NCRS with probability ε then, there must exist an algorithm B to solve the discrete logarithm (DL) problem with probability ε′ (qs is the query time relevant to the secret value oracle), where ε′≥ε/eqs.Proof.
Given a discrete logarithm random instanceg,ga∈G1, the purpose of B is to use the adversary A1 as a subroutine to obtain the value of a. L1,L2,L3,L4,andL5 store the values of the query and answer of various random oracles. At first, B runs the initialization algorithm to obtain ϕ=G1,G2,Y=gx,g,q,e,H1,H2 and then sends ϕ and x to A2. Then, A2 carries out a series of queries in an adaptive way. Note that the H1 and H2 oracle queries and answers are as those in Theorem 1.
Public key queries:A2 queries a public key for the identity IDi. B returns Yi←gxi to A2 as the answer and adds U,IDi,Yi,xi,− to the list L3 if IDi≠ID∗; otherwise, B returns Yi←ga to A2 as the answer and adds U,IDi,Yi,−,− to the list L3.
Partial private key queries:A2 queries a partial private key for the identity IDi. B responds as follows: (1) if IDi=ID∗, B fails and terminates the game; (2) if IDi≠ID∗ and there is a query value, B returns Di←gxλi to A2.
Secret value queries:A2 queries a secret value for the identity IDi. B calls the public key oracle and returns a secret value xi if IDi≠ID∗ and terminates the game otherwise.
Ring signature queries: for a ring signature query,B returns a signature to A2 by calling the ring signature algorithm if IDs≠ID∗; otherwise, B responds as follows:(1)
B randomly selects aj∈Zq∗ to calculate σj=YiYaj1≤j≤candj≠s and η=H2v⟶(2)
B calculates σs=gηxλsYiλs/∏j=1,j≠scσj and adds v⟶,U,IDi,aj,η,σj,σs into the list L4(3)
B returns σ⟶us=σ1us,…,σcus
Combination queries:A2 issues a combination query. Note that σ⟶1,…,σ⟶l are the ring signatures. B calculates the combination message vector w⟶=∑j=1lαjw⟶j, where α⟶=α1,…,αl is the local coding vector and w⟶1,…,w⟶l are the message vectors. σj=∏i=1lσi,jαi is the signature of w⟶, where σi,j1≤i≤mand1≤j≤c represents the j-th element of σ⟶i. Finally, B returns a combination signature σ=∏i=1lσiαi to A2 and stores α⟶,w⟶,σ in the list L5.
Verification queries:A2 submits a verification query. B outputs a valid ring signature if eQs,YηYs=∏j=1ceσj,g and terminates the game otherwise.
After a sequence of adaptive queries,A2 outputs a forgery v⟶∗,U,ID∗,aj∗,η∗,σj∗,σs∗ to B. A2 does not know the private key of any member in the ring. In the probabilistic polynomial time, two valid signatures are obtained as follows:(16)σs=DsηQsxs∏j=1,j≠scYiYaj,σs=Ds∗η∗Qs∗xs∗∏j=1,j≠scYi∗Yaj∗.
Then, the solutiona of the discrete logarithm problem can be obtained by the above two signatures:(17)a=∑j=1,j≠sclogYiYi∗−1+xλs∗η∗−λsη∑j=1,j≠scaj−aj∗λs−λs∗.
Referring to the probability analysis in [16], the probability of B in solving the discrete logarithm problem in the probabilistic polynomial time is negligible. Hence, A2 cannot break the UF-CMA-II security of CL-NCRS.Theorem 3.
CL-NCRS can resist the pollution attacks in the multisource network coding environment.Proof.
In CL-NCRS, if the adversary attempts to forge a ring signature, it must obtain a ring signer’s private key by solving the discrete logarithm problem. As we know, it is computationally infeasible to solve the discrete logarithm problem. If the adversary wants to forge a valid signature, the forger has to perform the following operations:(1)
The forger attempts to sign a forged message directly. In the ring signature algorithm of CL-NCRS, it is needful to use the signer’s private key andaj∈Zq∗1≤j≤candj≠s to sign the message. Obtaining the private key from the ring signer’s public key is equivalent to solving the discrete logarithm problem; and it is also equivalent to solving the discrete logarithm problem to obtain aj from a signature.(2)
The forger tried to obtain a valid signature by exhaustive search. Assume that the length of an element in ring signature isn and the number of ring members is m, then the size of ring signature is n×m. For example, if n is 256 bit on the elliptic curve, the size of ring signature is 256 ×m, and it is difficult to solve the discrete logarithm of 1589 bit [17]. Obviously, it is impossible to obtain a valid ring signature.Theorem 4.
CL-NCRS can satisfy the unconditional anonymity of ring signers.
A CL-NCRS can meet the unconditional anonymity [18–20]: no attacker can obtain the private key of all possible signers in illegal ways.Proof.
Given a signature setσ⟶=σ1,…,σc of identity set L=ID1,…,IDn and the corresponding public key set PK=PK1,…,PKn, IDs of the real signer in the ring and ξ is the probability of ring signature σ⟶=σ1,…,σc.
For the adversary, sinceajj≠sandaj≠1 is randomly chosen from Zq∗, then the probability of selecting a1,a2,…,as−1,as+1,…,ac in turn is(18)1q−1×1q−2×⋯×1q−c+1.
Forσs=DsηQsxs/∏j=1,j≠scYiYaj, the probability of selecting all a1,a2,…,ac in turn is(19)ξ=1q×1q−2×⋯×1q−c+1×1q−c.
Here,ξ has nothing to do with the identity of the ring signer. If the adversary obtains the private keys of all users in the ring and even if the verifier can verify the ring signature, the probability of inferring the identity of the real ring signer from valid signature is less than 1/c. It is obvious that CL-NCRS satisfies the unconditional anonymity of the real signer.


## 7. Performance Analysis

In this section, we provide the performance comparison between CL-NCRS and relevant schemes [15, 21, 22]. Table 1 shows the comparison of the relevant features of several schemes. According to the analysis, it is found that Chen’s scheme and Zhao’s scheme are not suitable for the network coding environment. Table 2 shows the time complexity of main cryptography operations [4]. Table 3 shows the comparison case of several schemes, where l is the output length of bilinear pairing. From the comparison of signature length in Table 3, it can be seen that the computational complexity of CL-NCRS is relatively lower.Table 1
Feature comparison of several schemes.
ReferenceUnforgeabilityUnconditional anonymityPublic key cryptosystemIs it suitable for network coding?Chen’s scheme√√Identity-basedNoZhao’s scheme√√Identity-basedNoYu’s scheme××Identity-basedYesCL-NCRS scheme√√CertificatelessYesTable 2
The time complexity of cryptographic operations.
Cryptographic operationsTime (ms)Time to perform an exponential operation:Cme0.83Time to perform a scalar multiplication:Cmul0.75Time to perform a hash operation:Cmtp1.18Time to perform a bilinear operation:Cpar2.75Table 3
Computational efficiency comparison of several schemes.
ReferenceSignature lengthSignature time (ms)Verification time (ms)Total time (ms)Chen’s schemeO (l2n−1n lb n)(2n + 1) Cmul + 2nCmtp2Cpar + 4nCmul + nCmtp3Cpar + (6n + 1) Cmul + (3n + 1) Cmtp + CmeZhao’s schemeO (l2n−1n2lb n)(4n + 2) Cme2nCpar + (2n + 3) Cme(2n + 1) Cpar + (6n + 5) Cme + 2Cmtp + nCmulYu’s schemeO (l2nn2lb n)2nCme + 2nCmul + Cmtp(2n + 1) Cme + Cmtp + (n + 2) Cpar(5n + 2) Cme + 2nCmul + 5Cmtp + (n + 2) CparCL-NCRS schemeO (2n−1n lb n)(n + 2) Cme + 2Cmtp + nCmul2Cpar + (n + 4) Cme + 3Cmtp + nCmul3Cpar + (2n + 7) Cme + 7Cmtp + 2nCmulSimulation curves of time-consuming signature of several schemes are shown in Figure3. Simulation curves of time-consuming verification of several schemes are shown in Figure 4. The simulation curve of total algorithm time of several schemes is shown in Figure 5. Because two comparison schemes are not suitable for the network coding environment, for the convenience, we omit the network coding combination phase. The number of ring members n is 10, 20, 30, 40, and 50. Experiment results show that the running time of different schemes increases linearly with the increase of the number of ring members. As shown in Figure 3, in the signature phase, the growth rate of CL-NCRS is relatively slower than that of other schemes. As seen from Figure 4, the computational efficiency of CL-NCRS is the highest. In terms of total time in Figure 5, CL-NCRS takes the least time. In addition, the computational cost of other schemes is relatively high. Hence, CL-NCRS is the good cryptography scheme with short communication length and high computation efficiency.Figure 3
Comparison of signature time.Figure 4
Comparison of verification time.Figure 5
Total time comparison of several schemes.


## 8. Conclusion

Based on the certificateless ring signature and homomorphic hash function, a new certificateless network coding ring signature (CL-NCRS) is proposed. CL-NCRS satisfies the unforgeability against adaptive chosen-message attacks and unconditional anonymity of the real ring signer. CL-NCRS can resist the pollution attacks in the network coding environment and has the characteristics of low computation complexity and strong robustness. The limitation of this scheme is that it requires to send the message in undistorted ways.



---

*Source: 8029644-2021-07-01.xml*