# A Privacy-Preserving Exchange-Based Routing Protocol for Opportunistic Networks

Authors: Qingfeng Jiang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In opportunistic networks, nodes forward messages according to routing utility deduced from encounter information. When nodes simply communicate with real IDs, private information such as encounter time and location will be leaked. The private information can be preserved by anonymizing node real IDs, but ID anonymity will also prevent nodes from collecting real ID-based encounter information to compute routing utility. To address this problem, a privacy-preserving exchange-based routing protocol (PPERP) for opportunistic networks is proposed in this paper. In PPERP, nodes are classified into delivery nodes and nondelivery nodes. Two encountering nondelivery nodes exchange approximately equivalent anonymous encounter records. Then, when the exchanged encounter records are sent to a delivery node, it will compute the routing utilities to nondelivery nodes without knowing their real IDs. In PPERP, a node can directly compute its routing utility without relying on any trusted third party, so PPERP is suitable for opportunistic networks in which nodes usually are sparsely distributed and encounter opportunistically. Bilinear mapping technique is adopted to ensure the confidentiality, integrity, and nonrepudiation of encounter records. The security analysis and performance evaluation show that the proposed protocol is secure, efficient, and practical.


---

## Body

## 1. Introduction

Opportunistic networks [1] are one of the most interesting evolutions of MANETs. Nodes in opportunistic networks can communicate with each other even if there is no complete end-to-end path. Applications of opportunistic networks have been found in various scenarios, ranging from vehicular networks, environment monitoring, social networks, wildlife tracking, and disaster relief to remote health services and pocket switched networks. Because a complete end-to-end path does not exist in opportunistic networks, messages are delivered by the store-carry-and-forward technique, that is, forwarding nodes carry messages in a buffer until encountering the destination node.In order to effectively deliver messages, many utility-based routing protocols [2–10] have been proposed. In these utility-based routing protocols, message forwarding is stimulated when the utility of a node is smaller than the next-hop node. The routing utility usually is deduced from encounter information with real IDs. The encounter information includes encounter time, frequency, location, and even some social network status [6–10]. But the encounter information required for computing routing utility is privacy-sensitive and may be leaked. When the private information of a normal node is disclosed to a malicious node, the malicious node can analyze the encounter time or location of the normal node, then get the mobility pattern and launch attacks. So it is essential to preserve the encounter information in opportunistic networks routing. Now, some works about node anonymity [11, 12] are proposed to preserve the nodes’ private information. However, concealing such information in opportunistic networks routing is nontrivial as it is indispensable for computing routing utility. When the IDs are anonymized, two encountering nodes cannot effectively gather real ID-based encounter information to compute routing utility. This paradox poses a challenge: how to compute the routing utility in opportunistic networks routing while preserving the sensitive encounter information.To address the above problem, Chen et al. [13] propose a protocol FaceChange. But FaceChange only keeps ID anonymity when nodes encounter and postpone collecting the real ID-based encounter information to a moment. The real ID-based private encounter information will be leaked after two neighbor nodes disconnect with each other. Through the real ID-based encounter information, a malicious node can get another node’s mobility pattern. Our previous work [14] proposes a privacy-preserving protocol for utility-based routing (PPUR) to solve the above problem. But PPUR needs a trusted authority (TA) to compute the routing utility value so that nodes can obtain the utility value while preserving the privacy information. Overreliance on trusted TA is not suitable for opportunistic networks in many situations and has a single point failure at the same time. Therefore, a privacy-preserving exchange-based routing protocol (PPERP) in opportunistic networks is proposed in this paper. In PPERP, nodes are classified into delivery nodes and nondelivery nodes. Every node has a unique real ID, and a nondelivery node has some additional pseudo-IDs. The information of delivery nodes is public, and they communicate with real IDs, but nondelivery nodes communicate anonymously through pseudo-IDs to preserve their private information. When a delivery node and a nondelivery node encounter, they generate an anonymous encounter record including the nondelivery node’s pseudo-ID. When two nondelivery nodes encounter, they exchange approximately equivalent anonymous encounter records. Then, a delivery node can compute routing utilities to nondelivery nodes when receiving the exchanged encounter records, but it does not know their real IDs; therefore, the private information of nondelivery nodes is preserved. In addition, a node can directly compute its routing utility without relying on any trusted third party.The main contributions of this paper are the following threefold:(1)
First, a privacy-preserving exchange-based routing protocol (PPERP) in opportunistic networks is proposed. In PPERP, a node can collect node encounter records to compute the routing utility while preserving the private information of nondelivery nodes at the same time. The protocol is distributed, and a node can directly compute its routing utility without relying on any trusted third party, so it is suitable for opportunistic networks in which nodes usually are sparsely distributed and encounter opportunistically.(2)
Second, the confidentiality, integrity, and nonrepudiation of encounter record information are ensured through the bilinear mapping technique, and then the security analysis of anonymity is achieved.(3)
Third, extensive simulations and experiments are conducted to verify the efficiency of the protocol.The remainder of this paper is organized as follows. Section2 introduces the related works. Section 3 presents the system models and preliminaries. Section 4 describes the system design of the privacy-preserving protocol PPERP. Section 5 shows the performance evaluation. Section 6 is the conclusion.


## 2. Related Work

Privacy in opportunistic networks can be broadly classified into the following four categories [15, 16]: ID privacy [11, 12], location privacy [17–19], message content privacy [20–22], and relationships privacy [23–25].Le et al. [11] propose a privacy-preserving protocol PEON for opportunistic networks. In PEON, each relay node can only be aware of the next hop in the routing path and remains unaware of the identity of the source node. Ahmad et al. [12] propose a novel approach for secure and private communication by hiding the IDs of nodes using pseudonyms. The proposed approach guards against privacy attacks and delivers a high degree of anonymity even in the presence of compromised nodes in the network.For M-healthcare social networks, Zhou et al. [17] propose a patient-optimized privacy-preserving packet forwarding scheme POP to preserve the location privacy of the patients and decrease the privacy exposure when intermediate patients are compromised. Rashidibajgan et al. [18] propose a secure structure for opportunistic networks wherein nodes can decide to carry a message without knowledge about the sender, destination, and intermediate nodes. The privacy-preserving protocol provides location privacy for all nodes. Zhang et al. [19] propose a user collaboration privacy protection scheme with a threshold scheme and smart contract to cope with this privacy issue.Guo et al. [20] propose the PSaD, a privacy-preserving social-assisted content dissemination scheme in DTNs. In PSaD, mobile nodes disseminate their encrypted contents by each contact and let nodes that have the corresponding attributes decrypt the content. Srivastava et al. [21] propose a security design for DTNs using lattice-based cryptography. The security design successfully prevents various attacks at different layers of a DTN network. It fulfils confidentiality, privacy, and integrity very well. In remote rural areas without internet connectivity, it is hard to envisage the use of mHealth applications for remote patient monitoring. Yaacoub et al. [22] propose an approach that solves this problem by transmitting mHealth monitoring data using DTNs. It allows preserving the security and privacy of the patient’s data.Liang et al. [23] study user profile matching with privacy-preservation in mobile social networks and introduce a family of novel profile-matching protocols preventing user attribute values from disclosure. Miao et al. [24] propose a privacy-preserving probabilistic prediction-based pouting (4PR) protocol to hide the encounter probabilities of nodes. It compares the probability that at least one node in a community will encounter the destination node. Magaia et al. [25] propose an enhanced and efficient privacy-preserving routing protocol for vehicular delay-tolerant networks, which allows nodes to compute their similarity in a private manner.The above works are proposed to preserve nodes’ private information, but they cannot effectively gather encounter information to compute the utility value for utility-based routing. Chen et al. [13] propose a protocol FaceChange that can anonymize real IDs of neighbor nodes and collect encounter information to compute the real utility. The work FaceChange is similar to the work in this paper. But FaceChange only keeps node anonymity during the encounter and postpones the real ID-based encounter information collection to a moment. After two neighbor nodes disconnect, the real ID-based private encounter information will be leaked. A malicious node can deduce another node’s mobility pattern by analyzing the encounter information. But, in the PPERP protocol proposed in this paper, even if two nodes disconnect with each other, they can still compute the routing utility while preserving the sensitive private encounter information, so nodes’ mobility pattern is not disclosed. Our previous work [14] proposes a privacy-preserving protocol for utility-based routing (PPUR) to solve the above problem. But PPUR needs a TA to compute routing utility. Overreliance on trusted TA is not suitable for opportunistic networks in many situations and has a single point failure at the same time. However, the PPERP protocol in this paper is distributed, and a node can directly compute its routing utility value without relying on any trusted third party, so it is suitable for opportunistic networks in which nodes usually are sparsely distributed and encounter opportunistically.


## 3. Models and Preliminaries

### 3.1. Network Model

The system network model consists of TA, fixed network, and mobile nodes (Figure1).Figure 1
Network model.TA is a trusted authority server with both wireless capability and internet access. It is responsible for distributing public/private keys and generating IDs for mobile nodes, which can be conducted offline.Fixed network is composed of Internet and APs. Mobile nodes get public/private keys and IDs from TA when encountering APs and Internet.Mobile nodesN1–N8 are vehicles or pedestrians who can mutually communicate with each other and TA via wireless interfaces. In the model, nodes are classified into delivery nodes NT and nondelivery nodes N. A delivery node has a unique real ID. A nondelivery node has a unique real ID and some pseudo-IDs. Delivery nodes act as couriers to deliver messages to nondelivery nodes. The information of delivery nodes is public, and they communicate with real IDs, but the information of nondelivery nodes is privacy-sensitive to delivery nodes. Nondelivery nodes communicate anonymously through pseudo-IDs to preserve their private information. Messages are generated from a nondelivery source node and then relayed by some delivery nodes until to a nondelivery destination node.In the network model, it is assumed that a utility-based routing protocol is adopted. When encountering, nodeNi will send its messages to Nj if it has a larger utility to the destination node.


### 3.2. Attack Model

Assuming that some malicious nodes may launch passive and active attacks. Malicious nodes may eavesdrop on the underlying communications to get some relevant private information such as nodes’ IDs, encounter time, and location in the passive attacks. Malicious nodes may also take active actions to incur modification or damages to the received node encounter record information and then forward to other nodes in the active attacks. In addition, malicious nodes may also fabricate the pseudo-ID of a nondelivery node and encounter record information.


### 3.3. Pairing Technique

The proposed protocol is based on bilinear pairing. LetG1 be an additive cyclic group and G2 be a multiplicative cyclic group of the same order for some large prime q, that is, |G1| = |G2| = q. Let P be a generator of G1. It is further assumed that e^:G1 × G1⟶ G2 is an efficient admissible bilinear map with the following properties:(1)
Bilinear: for allP, Q∈G1 and all a, b∈Zq, e^ (aP, bQ) =  e^ (P, Q)ab(2)
Nondegenerate: the map does not send all pairs inG1 × G1 to the ID in G2. Since G1 and G2 are groups of prime order, this implies that if P is a generator of G1, then e^ (P, P) is a generator of G2(3)
Computable: there is an efficient algorithm to computee^ (P, Q) for any P, Q∈G1Such an admissible bilinear mape^ can be constructed by Weil or Tate pairing.


## 3.1. Network Model

The system network model consists of TA, fixed network, and mobile nodes (Figure1).Figure 1
Network model.TA is a trusted authority server with both wireless capability and internet access. It is responsible for distributing public/private keys and generating IDs for mobile nodes, which can be conducted offline.Fixed network is composed of Internet and APs. Mobile nodes get public/private keys and IDs from TA when encountering APs and Internet.Mobile nodesN1–N8 are vehicles or pedestrians who can mutually communicate with each other and TA via wireless interfaces. In the model, nodes are classified into delivery nodes NT and nondelivery nodes N. A delivery node has a unique real ID. A nondelivery node has a unique real ID and some pseudo-IDs. Delivery nodes act as couriers to deliver messages to nondelivery nodes. The information of delivery nodes is public, and they communicate with real IDs, but the information of nondelivery nodes is privacy-sensitive to delivery nodes. Nondelivery nodes communicate anonymously through pseudo-IDs to preserve their private information. Messages are generated from a nondelivery source node and then relayed by some delivery nodes until to a nondelivery destination node.In the network model, it is assumed that a utility-based routing protocol is adopted. When encountering, nodeNi will send its messages to Nj if it has a larger utility to the destination node.


## 3.2. Attack Model

Assuming that some malicious nodes may launch passive and active attacks. Malicious nodes may eavesdrop on the underlying communications to get some relevant private information such as nodes’ IDs, encounter time, and location in the passive attacks. Malicious nodes may also take active actions to incur modification or damages to the received node encounter record information and then forward to other nodes in the active attacks. In addition, malicious nodes may also fabricate the pseudo-ID of a nondelivery node and encounter record information.


## 3.3. Pairing Technique

The proposed protocol is based on bilinear pairing. LetG1 be an additive cyclic group and G2 be a multiplicative cyclic group of the same order for some large prime q, that is, |G1| = |G2| = q. Let P be a generator of G1. It is further assumed that e^:G1 × G1⟶ G2 is an efficient admissible bilinear map with the following properties:(1)
Bilinear: for allP, Q∈G1 and all a, b∈Zq, e^ (aP, bQ) =  e^ (P, Q)ab(2)
Nondegenerate: the map does not send all pairs inG1 × G1 to the ID in G2. Since G1 and G2 are groups of prime order, this implies that if P is a generator of G1, then e^ (P, P) is a generator of G2(3)
Computable: there is an efficient algorithm to computee^ (P, Q) for any P, Q∈G1Such an admissible bilinear mape^ can be constructed by Weil or Tate pairing.


## 4. System Design of PPERP

This section first describes the detailed system design of PPERP, which consists of system setup, generation of encounter records, exchange of encounter records, dissemination of exchanged encounter records, computation of routing utility, and message forwarding of encountering nodes. Then, the security analysis is achieved.The protocol flow chart is shown in Figure2. Assuming that two nodes Ni and Nj encounter, if a node is the delivery node and another is the nondelivery node, they first generate an encounter record that contains the information of node ID, encounter time, and so on. If nodes Ni and Nj are nondelivery nodes, they will exchange approximate equivalent anonymous encounter records to preserve the real IDs (Algorithm 1). Then nodes Ni and Nj transmit the records by the way of dissemination to make the exchanged encounter records reach the corresponding delivery nodes quickly (Algorithm 2). When exchanged encounter records are received by the delivery node, it decrypts exchanged encounter records and computes the approximate routing utilities to nondelivery nodes. At last, nodes Ni and Nj forward messages to the destination node according to their routing utilities (Algorithm 3 and 4).Figure 2
Protocol flow.The notations in this paper are listed in Table1.Table 1
Notations.
NotationsDefinitionsG1An additive cyclic group with orderqG2A multiplicative cyclic group with orderqe^A bilinear map:G1 × G1⟶G2ZqAn integer cyclic group with orderqPGenerator ofG1Enc( )Encryption with a symmetric cryptosystemH( )Collision-resistant hash functionNiReal ID of nondelivery nodeNiNiTReal ID of delivery nodeNiTPidiPseudo-ID of nondelivery nodeNiskiPrivate key of delivery nodeNiT or nondelivery node NiKeyijSession key of delivery nodeNiT and nondelivery node NjERijEncounter record of delivery nodeNiT and nondelivery node NjEERijExchanged encounter record (the new generated encounter record of nodesNiT and Nj, after Nj exchanging original encounter record with other nondelivery nodes)SigDigital signatureUijRouting utility of nodesNiT and NjUijE−kRouting utility of nodesNiT and Nj, after Nj exchanging encounter record with node NkAckSetAcknowledge sequence number set of exchanged encounter records received by delivery nodesEERSetExchanged encounter record set of a nondelivery nodeMessage SetSet of messages buffered in a node


### 4.1. System Setup

Given the security parameterk, TA generates bilinear parameters (q, P, G1, G2, and e^) with bilinear mapping technology. G1 and G2 are groups of order q; P is a generator; and e^: G1 × G1⟶G2 is a nondegenerated and efficiently computable bilinear map. TA generates master private key by random number s∈Zq∗ and computes corresponding public key Ppub = sP. A symmetric encryption algorithm Enc( ) AES and three collision-resistant hash functions H1, H2, and H3 are also chosen by TA, where H1:0,1∗⟶G1∗, H2: {0,1} ∗ ⟶ Zq, and H3: G1 ⟶ Zq. Finally, TA publishes system parameters (q, G1, G2, P, Ppub, e^, H1, H2, H3, and Enc( )) and keeps the master key s secret.When a delivery nodeNiT or nondelivery node Ni registers with the system, TA signs the real ID by master key s and generates an ID certificate, through which other nodes can verify the authenticity of real ID. TA also generates a set of pseudo-IDs, PIDi = {Pidi1, …, Pidik−1, Pidik}, for nondelivery node Ni. Pidik = Encs(Ni|| rik) is computed from Enc( ), master key s, and random number rik. For the simplicity of description, Pidi is used to represent Ni’s any unlinkable pseudo-ID∈PIDi in the paper. A nondelivery node chooses a different pseudo-ID after some time to anonymize the true ID. The public key of nondelivery node Ni with pseudo-ID Pidi is H1(Pidi), and the private key is ski = sH1(Pidi) generated by TA. Similarly, a delivery node NiT’s public key is H1(NiT), and the private key is sH1(NiT). The process above can be conducted offline.


### 4.2. Generation of Encounter Records

Nodes usually compute routing utility according to encounter record information, such as encounter time, visit frequency, geographic location even some social network information. Assuming that a delivery node and a nondelivery nodeNj encounter, they will generate an encounter record ERij as shown in Figure 3.Figure 3
Encounter record.In the encounter record ERij, Seq is the record serial number generated by delivery node NiT and is unique in the system; Pidj is the pseudo-ID of node Nj; tij1,…,tijn−1tijn are encounter time of nodes NiT and Nj (other information can also be chosen); SigNiT and SigPidj are digital signatures of NiT and Nj, respectively; and Keyij is the session key of nodes NiT and Nj.The session key Keyij is computed by(1)Keyij=e^ski,H1Pidj=e^H1N1T,ski=e^H1N1T,H1Pidjs.Keyij is used to encrypt ERij to ensure confidentiality. To ensure the integrity and nonrepudiation of encounter record ERij, an ID-based ElGamal signature scheme [26] is adopted. For m=Seq‖NiTPidjtij1…tijn−1tijn, the generation of SigPidj is as follows:(2)R=kP,where k∈Zq∗ is a random number from Zq∗.(3)S=H2mP+H3Rskjk−1,where k−1 is the inverse of k in Zq∗.(4)SigPidj=R,S.NodeNiT verifies the signature SigPidj by checking(5)e^R,S=e^P,PH2me^Ppub,H1PidjH3R.The correctness can be verified as follows:(6)e^R,S=e^kP,H2mP+H3Rskjk−1=e^P,PH2me^P,H1PidjH3Rs=e^P,PH2me^Ppub,H1PidjH3R.


### 4.3. Exchange of Encounter Records

If a nondelivery node directly tells its real ID to a delivery node, the delivery node will obtain the nondelivery node’s private information such as the encounter time and location according to encounter records. In order to preserve the real IDs, two encountering nondelivery nodes exchange approximate equivalent anonymous encounter records. Suppose that the encounter record of delivery nodeNiT and nondelivery node Nj is ERij and the record of delivery node NiT and nondelivery node Nk is ERik. When nondelivery nodes Nj and Nk encounter, they exchange their encounter records ERij and ERik as shown in Algorithm 1.Algorithm 1: Exchange of encounter records.
(1)
NodeNj computes the real utility Uij with NiT and the utility UijE−k after exchanging encounter records with node Nk(2)
NodeNk computes the real utility Uik with NiT and the utility UikE−j after exchanging encounter record with node Nj(3)
IfUijE−k−Uij≤ε && <sub> UikE−j−Uik≤ε,</sub> where 0 ≤ε≤ 1 is the error range specified then(4)
NodeNk sends its real ID to Nj (Figure 4(a))(5)
NodeNj inserts Nk to the encounter record ERij and then signs the record by equations (2)-(4), to generate an exchanged encounter record EERij (Figure 5)(6)
NodeNj sends one copy of EERij to Nk (Figure 4(a))(7)
NodeNj sends its real ID to Nk (Figure 4(b))(8)
NodeNk inserts Nj to encounter record ERik and then signs the record to generate an exchanged encounter record EERik (Figure 6)(9)
NodeNk sends one copy of EERik to Nj (Figure 4(b))(10)
end ifIn Algorithm 1,Nj and Nk compute the real utility and the utility after exchanging encounter record. The ID NiT is public, so Nj and Nk can directly compute the real utilities to NiT. If the difference between real utility and the utility after exchanging is in the error range specified, Nj and Nk will exchange encounter records.As shown in Figure4(a), node Nk sends its real ID to Nj. Nj inserts Nk to the encounter record ERij and generates an exchanged encounter record EERij and then sends one copy back to Nk. As shown in Figure 5, for m=Seq‖NiTPidjtij1…tijn−1tijnNk, Nj generates the digital signature SigPidj and then encrypts the encounter record information except for the record serial number Seq by the shared Keyij of NiT and Nj. The process of Nj sending its real ID to Nk and Nk generating the exchanged encounter record EERik (Figure 6) is the same as above.Figure 4
Exchange of encounter records betweenNj and Nk: (a) Nk sends its real ID to Nj and (b) Nj sends its real ID to Nk.
(a)(b)Figure 5
EERij.Figure 6
EERik.The main execution time of Algorithm 1 is to compute the routing utility after exchanging encounter records (lines 1–2). Routing utility is computed according to encounter timetij1…tijn−1tijn in the encounter record, so the time complexity is O(n).


### 4.4. Dissemination of Exchanged Encounter Records

To make the exchanged encounter records reach the delivery nodes quickly, nodes transmit the records by the way of dissemination. At the same time, each node sets an information acknowledge setAckSet that stores the sequence numbers of exchanged encounter records received by delivery nodes, to reduce repeated dissemination. Suppose that nondelivery nodes Nj and Nk encounter, the dissemination process of Nj is shown in Algorithm 2.Algorithm 2: Dissemination of exchanged encounter records.
(1)
Ack SetNewj=Ack SetOldj∪AckSetk(2)
for each ack Seq∈Ack SetNewj−Ack SetOldjdo(3)
for each exchanged encounter record eer∈EERSetjdo(4)
ifackSeq = = eer.Seqthen(5)
deleteeer from EERSetj(6)
end if(7)
end for(8)
end for(9)
for each exchanged encounter record eer∈EERSetkdo(10)
ifeer∉EERSetjthen(11)
addeer to EERSetj(12)
end if(13)
end forWhen nodeNj encounters Nk, it merges its acknowledge set Ack SetOldj with AckSetk of Nk and gets a new acknowledge set Ack SetNewj. According to Ack SetNewj, Nj deletes the acknowledged exchanged encounter record eer from exchanged encounter record set EERSetj. Then, for an exchanged encounter record eer in EERSetk, Nj will add one copy to its EERSetj if eer is not in. Through the process of dissemination, the exchanged encounter records will reach the delivery nodes quickly, which then can effectively compute the routing utility.Suppose that the maximum number of elements in setAckSet and EER Set is n. In Algorithm 2, the time complexity of line (1) is Onlogn+n if the elements are firstly sorted by quick sort and then merged. For lines (2–8), the time complexity is O(n2). In line (10), it needs to traverse through EERSetj to determine whether eer is in the set, so the time complexity is O(n). For lines (9–13), the time complexity is O(n2). The time complexity of Algorithm 2 is Onlogn+n+On2+On2=On2.Theorem 1.
The exchanged encounter records will reach a delivery node according to the sequence of records’ generation time.Proof:.
Suppose that the first encounter record of delivery nodeNiT and nondelivery node Nj is ERij1 and the encounter record of delivery node NiT and nondelivery node Nk is ERik. As shown in Algorithm 1, Nj exchanges encounter record ERij1 with Nk and gets an exchanged encounter record EERij1. Then Nj encounters the delivery node NiT again at time tm and generates the second encounter record ERij2. Nj exchanges ERij2 with node Nl (it also may be Nk) and gets an exchanged encounter record EERij2. Suppose the first exchanged encounter record EERij1 is delivered to NiT at time t1, and the second exchanged encounter record EERij2 is delivered to NiT at time t2. As seen from Algorithm 1, after exchanging the first encounter record, Nj will save EERij1 and send one copy to another node, so t1≤tm. In addition, tm<t2, so t1<t2.


### 4.5. Computation of Routing Utility

When the exchanged encounter record EERij of delivery node NiT and nondelivery node Nj with pseudo-ID Pidj is sent to NiT, NiT decrypts EERij with the shared secret key Keyij and obtains the encountered node ID Nk. As shown in Figure 5, according to key Keyij and the signature SigPidj in EERij, NiT believes that the real ID of Pidj is Nk (the real ID is Nj) and then computes the routing utility to node Nk. Similarly, when the exchanged encounter record EERik of delivery node NiT and nondelivery node Nk with pseudo-ID Pidk is sent to NiT, NiT decrypts EERik with the shared secret key Keyik to obtain the encountered node ID Nj. According to key Keyik and the signature in EERik, NiT believes that real ID of Pidk is Nj (the real ID is Nk) and then computes the routing utility to node Nj. Delivery node NiT computes the routing utility to node Nj according to (7) and (8) from PROPHET [2].(7)Uij=Uijold+1−Uijold×Uinit,0<Uinit≤1,where 0≤Uij≤1 is the new routing utility, Uijold is the routing utility before updated, and Uinit is an initialization constant. When the two nodes have not encountered each other for a certain time, they will update the utility value according to the following equation:(8)Uij=Uijold×γk,where γ∈0,1 is the aging constant and k is the number of time units that have lapsed since the last time the metric was aged.In the above process, delivery nodeNiT can compute the approximate routing utilities to nondelivery nodes Nj and Nk, but it does not know their real IDs, so the private information of Nj and Nk is preserved.


### 4.6. Message Forwarding of Encountering Nodes

When a delivery nodeNiT and a nondelivery node Nj encounter, as shown in Algorithm 3, Nj sends its messages to NiT which will deliver the messages to other nodes. For a message m in the messages set of NiT, if Nj is the destination node, it will show the real ID certificate signed by the master key s of TA to NiT. According to the real ID certificate, delivery node NiT sends the message m to nondelivery node Nj. In order to ensure the anonymity of a message destination node, a nondelivery node can choose a close friend node to exchange their real ID certificates, and they first receive messages for each other and then exchange the messages back.For lines (1–3), the time complexity isO(n). For lines (4–9), the time complexity is O(n). The total time complexity of Algorithm 3 is O(n).Algorithm 3: Message forwarding of delivery node NiT and nondelivery node Nj.
(1)
for each message m∈MessageSetjdo(2)
Nj sends m to NiT(3)
end for(4)
for each message m∈MessageSetido(5)
if the destination of m is Njthen(6)
Nj shows its real ID certificate to NiT(7)
NiT sends message m to Nj(8)
end if(9)
end forWhen two delivery nodesNiT and NjT encounter, as shown in Algorithm 4, they compare their routing utilities to the destination node of message m, and then m is forwarded to the delivery node with higher utility.For lines (1–5), the time complexity isO(n). For lines (6–10), the time complexity is O(n). The total time complexity of Algorithm 4 is O(n).Algorithm 4: Message forwarding of delivery nodes NiT and NjT.
(1)
for each message m∈MessageSeti, the destination node is Nkdo(2)
ifUjk>Uikthen(3)
NiT sends message m to NjT(4)
end if(5)
end for(6)
for each message m∈MessageSetj, the destination node is Nkdo(7)
ifUik>Ujkthen(8)
NjT sends message m to NiT(9)
end if(10)
end for


### 4.7. Security Analysis

#### 4.7.1. Passive Attack

Theorem 2.
PPERP can prevent malicious nodes from getting some relevant privacy information by eavesdropping on encounter record and ensure the data confidentiality and anonymity of nondelivery nodes.Proof: .
The encounter record ERij is encrypted by Keyij of nodes NiT and nondelivery node Nj. Dupont et al. [27] proved that this key agreement is secure in the random oracle model under the bilinear Diffie–Hellman (BDH) assumption [28] in G1, G2, and e^. Let G1 and G2 be two groups of prime order q. Let e^: G1 × G1 ⟶ G2 be an admissible bilinear map, and let P be a generator of G1. The BDH problem in <G1, G2, e^> is as follows: given <P, aP, bP, cP> for some a, b, c∈Zq∗, compute W = e^ (P, P)abc∈G2. An algorithm A has advantage ε solving BDH in <G1, G2, e^> if(9)PrAP,aP,bP,cP=e^P,Pabc≥ε,where the probability is over the random choice of a, b, and c in Zq∗, the random choice of P∈G1∗, and the random bits of A. If there is no efficient algorithm to solve the BDH problem for < G1, G2, e^>, they are considered to satisfy the BDH assumption.
Because of the hardness of the BDH assumption, the probability of the adversary being able to recover the session key Keyij is negligible. All nodes except NiT, Nj, and TA do not know Keyij, so the privacy information on the encounter record cannot be leaked to malicious nodes.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. Since master key s is secure, rik is randomly generated, so Pidi is unlinkable and the nondelivery node anonymity is kept in the process of generating encounter records. In the process of computation routing utility, when a delivery node NiT receives an exchanged encounter record EERij (Figure 5), the ID it obtained from EERij is not the real ID of nondelivery node Nj with pseudo-ID Pidj, so the nondelivery node anonymity is kept in this process. When receiving messages as destination nodes, a nondelivery node chooses a close friend node to exchange their real ID certificates, and they first receive messages for each other and then exchange the messages back, so the message destination node anonymity is ensured.


#### 4.7.2. Active Attack

Theorem 3.
PPERP can prevent malicious nodes from modifying or damaging the encounter record information and ensure the integrity, nonrepudiation of each encounter record.Proof:.
In equation (3), the summary of a record is generated by the collision-resistance hash function H2 that can prevent malicious nodes from modifying the encounter record information, so the integrity is ensured. In addition, as shown in Figure 3, the signature of the record is generated by two encountering nodes’ private keys. The security of the ID-based signature scheme resembles the generalized ElGamal signature scheme. Security of ElGamal signature relies on the discrete logarithm problem (DLP), which is hard. So the signature is secure and guarantees the nonrepudiation of encounter records.Theorem 4.
PPERP can prevent malicious nodes from fabricating pseudo-ID and encounter record information.Proof:.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. An attacker needs to know the master key s and random number rik in order to generate a valid pseudo-ID. However, master key s is only known by the TA, so it is hard for an attacker to get key s and generate a valid pseudo-ID. In addition, as shown in Figure 3, an encounter record is signed by the private keys of two encountering nodes. So any node cannot fabricate an encounter record alone without the private key of other nodes.


## 4.1. System Setup

Given the security parameterk, TA generates bilinear parameters (q, P, G1, G2, and e^) with bilinear mapping technology. G1 and G2 are groups of order q; P is a generator; and e^: G1 × G1⟶G2 is a nondegenerated and efficiently computable bilinear map. TA generates master private key by random number s∈Zq∗ and computes corresponding public key Ppub = sP. A symmetric encryption algorithm Enc( ) AES and three collision-resistant hash functions H1, H2, and H3 are also chosen by TA, where H1:0,1∗⟶G1∗, H2: {0,1} ∗ ⟶ Zq, and H3: G1 ⟶ Zq. Finally, TA publishes system parameters (q, G1, G2, P, Ppub, e^, H1, H2, H3, and Enc( )) and keeps the master key s secret.When a delivery nodeNiT or nondelivery node Ni registers with the system, TA signs the real ID by master key s and generates an ID certificate, through which other nodes can verify the authenticity of real ID. TA also generates a set of pseudo-IDs, PIDi = {Pidi1, …, Pidik−1, Pidik}, for nondelivery node Ni. Pidik = Encs(Ni|| rik) is computed from Enc( ), master key s, and random number rik. For the simplicity of description, Pidi is used to represent Ni’s any unlinkable pseudo-ID∈PIDi in the paper. A nondelivery node chooses a different pseudo-ID after some time to anonymize the true ID. The public key of nondelivery node Ni with pseudo-ID Pidi is H1(Pidi), and the private key is ski = sH1(Pidi) generated by TA. Similarly, a delivery node NiT’s public key is H1(NiT), and the private key is sH1(NiT). The process above can be conducted offline.


## 4.2. Generation of Encounter Records

Nodes usually compute routing utility according to encounter record information, such as encounter time, visit frequency, geographic location even some social network information. Assuming that a delivery node and a nondelivery nodeNj encounter, they will generate an encounter record ERij as shown in Figure 3.Figure 3
Encounter record.In the encounter record ERij, Seq is the record serial number generated by delivery node NiT and is unique in the system; Pidj is the pseudo-ID of node Nj; tij1,…,tijn−1tijn are encounter time of nodes NiT and Nj (other information can also be chosen); SigNiT and SigPidj are digital signatures of NiT and Nj, respectively; and Keyij is the session key of nodes NiT and Nj.The session key Keyij is computed by(1)Keyij=e^ski,H1Pidj=e^H1N1T,ski=e^H1N1T,H1Pidjs.Keyij is used to encrypt ERij to ensure confidentiality. To ensure the integrity and nonrepudiation of encounter record ERij, an ID-based ElGamal signature scheme [26] is adopted. For m=Seq‖NiTPidjtij1…tijn−1tijn, the generation of SigPidj is as follows:(2)R=kP,where k∈Zq∗ is a random number from Zq∗.(3)S=H2mP+H3Rskjk−1,where k−1 is the inverse of k in Zq∗.(4)SigPidj=R,S.NodeNiT verifies the signature SigPidj by checking(5)e^R,S=e^P,PH2me^Ppub,H1PidjH3R.The correctness can be verified as follows:(6)e^R,S=e^kP,H2mP+H3Rskjk−1=e^P,PH2me^P,H1PidjH3Rs=e^P,PH2me^Ppub,H1PidjH3R.


## 4.3. Exchange of Encounter Records

If a nondelivery node directly tells its real ID to a delivery node, the delivery node will obtain the nondelivery node’s private information such as the encounter time and location according to encounter records. In order to preserve the real IDs, two encountering nondelivery nodes exchange approximate equivalent anonymous encounter records. Suppose that the encounter record of delivery nodeNiT and nondelivery node Nj is ERij and the record of delivery node NiT and nondelivery node Nk is ERik. When nondelivery nodes Nj and Nk encounter, they exchange their encounter records ERij and ERik as shown in Algorithm 1.Algorithm 1: Exchange of encounter records.
(1)
NodeNj computes the real utility Uij with NiT and the utility UijE−k after exchanging encounter records with node Nk(2)
NodeNk computes the real utility Uik with NiT and the utility UikE−j after exchanging encounter record with node Nj(3)
IfUijE−k−Uij≤ε && <sub> UikE−j−Uik≤ε,</sub> where 0 ≤ε≤ 1 is the error range specified then(4)
NodeNk sends its real ID to Nj (Figure 4(a))(5)
NodeNj inserts Nk to the encounter record ERij and then signs the record by equations (2)-(4), to generate an exchanged encounter record EERij (Figure 5)(6)
NodeNj sends one copy of EERij to Nk (Figure 4(a))(7)
NodeNj sends its real ID to Nk (Figure 4(b))(8)
NodeNk inserts Nj to encounter record ERik and then signs the record to generate an exchanged encounter record EERik (Figure 6)(9)
NodeNk sends one copy of EERik to Nj (Figure 4(b))(10)
end ifIn Algorithm 1,Nj and Nk compute the real utility and the utility after exchanging encounter record. The ID NiT is public, so Nj and Nk can directly compute the real utilities to NiT. If the difference between real utility and the utility after exchanging is in the error range specified, Nj and Nk will exchange encounter records.As shown in Figure4(a), node Nk sends its real ID to Nj. Nj inserts Nk to the encounter record ERij and generates an exchanged encounter record EERij and then sends one copy back to Nk. As shown in Figure 5, for m=Seq‖NiTPidjtij1…tijn−1tijnNk, Nj generates the digital signature SigPidj and then encrypts the encounter record information except for the record serial number Seq by the shared Keyij of NiT and Nj. The process of Nj sending its real ID to Nk and Nk generating the exchanged encounter record EERik (Figure 6) is the same as above.Figure 4
Exchange of encounter records betweenNj and Nk: (a) Nk sends its real ID to Nj and (b) Nj sends its real ID to Nk.
(a)(b)Figure 5
EERij.Figure 6
EERik.The main execution time of Algorithm 1 is to compute the routing utility after exchanging encounter records (lines 1–2). Routing utility is computed according to encounter timetij1…tijn−1tijn in the encounter record, so the time complexity is O(n).


## 4.4. Dissemination of Exchanged Encounter Records

To make the exchanged encounter records reach the delivery nodes quickly, nodes transmit the records by the way of dissemination. At the same time, each node sets an information acknowledge setAckSet that stores the sequence numbers of exchanged encounter records received by delivery nodes, to reduce repeated dissemination. Suppose that nondelivery nodes Nj and Nk encounter, the dissemination process of Nj is shown in Algorithm 2.Algorithm 2: Dissemination of exchanged encounter records.
(1)
Ack SetNewj=Ack SetOldj∪AckSetk(2)
for each ack Seq∈Ack SetNewj−Ack SetOldjdo(3)
for each exchanged encounter record eer∈EERSetjdo(4)
ifackSeq = = eer.Seqthen(5)
deleteeer from EERSetj(6)
end if(7)
end for(8)
end for(9)
for each exchanged encounter record eer∈EERSetkdo(10)
ifeer∉EERSetjthen(11)
addeer to EERSetj(12)
end if(13)
end forWhen nodeNj encounters Nk, it merges its acknowledge set Ack SetOldj with AckSetk of Nk and gets a new acknowledge set Ack SetNewj. According to Ack SetNewj, Nj deletes the acknowledged exchanged encounter record eer from exchanged encounter record set EERSetj. Then, for an exchanged encounter record eer in EERSetk, Nj will add one copy to its EERSetj if eer is not in. Through the process of dissemination, the exchanged encounter records will reach the delivery nodes quickly, which then can effectively compute the routing utility.Suppose that the maximum number of elements in setAckSet and EER Set is n. In Algorithm 2, the time complexity of line (1) is Onlogn+n if the elements are firstly sorted by quick sort and then merged. For lines (2–8), the time complexity is O(n2). In line (10), it needs to traverse through EERSetj to determine whether eer is in the set, so the time complexity is O(n). For lines (9–13), the time complexity is O(n2). The time complexity of Algorithm 2 is Onlogn+n+On2+On2=On2.Theorem 1.
The exchanged encounter records will reach a delivery node according to the sequence of records’ generation time.Proof:.
Suppose that the first encounter record of delivery nodeNiT and nondelivery node Nj is ERij1 and the encounter record of delivery node NiT and nondelivery node Nk is ERik. As shown in Algorithm 1, Nj exchanges encounter record ERij1 with Nk and gets an exchanged encounter record EERij1. Then Nj encounters the delivery node NiT again at time tm and generates the second encounter record ERij2. Nj exchanges ERij2 with node Nl (it also may be Nk) and gets an exchanged encounter record EERij2. Suppose the first exchanged encounter record EERij1 is delivered to NiT at time t1, and the second exchanged encounter record EERij2 is delivered to NiT at time t2. As seen from Algorithm 1, after exchanging the first encounter record, Nj will save EERij1 and send one copy to another node, so t1≤tm. In addition, tm<t2, so t1<t2.


## 4.5. Computation of Routing Utility

When the exchanged encounter record EERij of delivery node NiT and nondelivery node Nj with pseudo-ID Pidj is sent to NiT, NiT decrypts EERij with the shared secret key Keyij and obtains the encountered node ID Nk. As shown in Figure 5, according to key Keyij and the signature SigPidj in EERij, NiT believes that the real ID of Pidj is Nk (the real ID is Nj) and then computes the routing utility to node Nk. Similarly, when the exchanged encounter record EERik of delivery node NiT and nondelivery node Nk with pseudo-ID Pidk is sent to NiT, NiT decrypts EERik with the shared secret key Keyik to obtain the encountered node ID Nj. According to key Keyik and the signature in EERik, NiT believes that real ID of Pidk is Nj (the real ID is Nk) and then computes the routing utility to node Nj. Delivery node NiT computes the routing utility to node Nj according to (7) and (8) from PROPHET [2].(7)Uij=Uijold+1−Uijold×Uinit,0<Uinit≤1,where 0≤Uij≤1 is the new routing utility, Uijold is the routing utility before updated, and Uinit is an initialization constant. When the two nodes have not encountered each other for a certain time, they will update the utility value according to the following equation:(8)Uij=Uijold×γk,where γ∈0,1 is the aging constant and k is the number of time units that have lapsed since the last time the metric was aged.In the above process, delivery nodeNiT can compute the approximate routing utilities to nondelivery nodes Nj and Nk, but it does not know their real IDs, so the private information of Nj and Nk is preserved.


## 4.6. Message Forwarding of Encountering Nodes

When a delivery nodeNiT and a nondelivery node Nj encounter, as shown in Algorithm 3, Nj sends its messages to NiT which will deliver the messages to other nodes. For a message m in the messages set of NiT, if Nj is the destination node, it will show the real ID certificate signed by the master key s of TA to NiT. According to the real ID certificate, delivery node NiT sends the message m to nondelivery node Nj. In order to ensure the anonymity of a message destination node, a nondelivery node can choose a close friend node to exchange their real ID certificates, and they first receive messages for each other and then exchange the messages back.For lines (1–3), the time complexity isO(n). For lines (4–9), the time complexity is O(n). The total time complexity of Algorithm 3 is O(n).Algorithm 3: Message forwarding of delivery node NiT and nondelivery node Nj.
(1)
for each message m∈MessageSetjdo(2)
Nj sends m to NiT(3)
end for(4)
for each message m∈MessageSetido(5)
if the destination of m is Njthen(6)
Nj shows its real ID certificate to NiT(7)
NiT sends message m to Nj(8)
end if(9)
end forWhen two delivery nodesNiT and NjT encounter, as shown in Algorithm 4, they compare their routing utilities to the destination node of message m, and then m is forwarded to the delivery node with higher utility.For lines (1–5), the time complexity isO(n). For lines (6–10), the time complexity is O(n). The total time complexity of Algorithm 4 is O(n).Algorithm 4: Message forwarding of delivery nodes NiT and NjT.
(1)
for each message m∈MessageSeti, the destination node is Nkdo(2)
ifUjk>Uikthen(3)
NiT sends message m to NjT(4)
end if(5)
end for(6)
for each message m∈MessageSetj, the destination node is Nkdo(7)
ifUik>Ujkthen(8)
NjT sends message m to NiT(9)
end if(10)
end for


## 4.7. Security Analysis

### 4.7.1. Passive Attack

Theorem 2.
PPERP can prevent malicious nodes from getting some relevant privacy information by eavesdropping on encounter record and ensure the data confidentiality and anonymity of nondelivery nodes.Proof: .
The encounter record ERij is encrypted by Keyij of nodes NiT and nondelivery node Nj. Dupont et al. [27] proved that this key agreement is secure in the random oracle model under the bilinear Diffie–Hellman (BDH) assumption [28] in G1, G2, and e^. Let G1 and G2 be two groups of prime order q. Let e^: G1 × G1 ⟶ G2 be an admissible bilinear map, and let P be a generator of G1. The BDH problem in <G1, G2, e^> is as follows: given <P, aP, bP, cP> for some a, b, c∈Zq∗, compute W = e^ (P, P)abc∈G2. An algorithm A has advantage ε solving BDH in <G1, G2, e^> if(9)PrAP,aP,bP,cP=e^P,Pabc≥ε,where the probability is over the random choice of a, b, and c in Zq∗, the random choice of P∈G1∗, and the random bits of A. If there is no efficient algorithm to solve the BDH problem for < G1, G2, e^>, they are considered to satisfy the BDH assumption.
Because of the hardness of the BDH assumption, the probability of the adversary being able to recover the session key Keyij is negligible. All nodes except NiT, Nj, and TA do not know Keyij, so the privacy information on the encounter record cannot be leaked to malicious nodes.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. Since master key s is secure, rik is randomly generated, so Pidi is unlinkable and the nondelivery node anonymity is kept in the process of generating encounter records. In the process of computation routing utility, when a delivery node NiT receives an exchanged encounter record EERij (Figure 5), the ID it obtained from EERij is not the real ID of nondelivery node Nj with pseudo-ID Pidj, so the nondelivery node anonymity is kept in this process. When receiving messages as destination nodes, a nondelivery node chooses a close friend node to exchange their real ID certificates, and they first receive messages for each other and then exchange the messages back, so the message destination node anonymity is ensured.


### 4.7.2. Active Attack

Theorem 3.
PPERP can prevent malicious nodes from modifying or damaging the encounter record information and ensure the integrity, nonrepudiation of each encounter record.Proof:.
In equation (3), the summary of a record is generated by the collision-resistance hash function H2 that can prevent malicious nodes from modifying the encounter record information, so the integrity is ensured. In addition, as shown in Figure 3, the signature of the record is generated by two encountering nodes’ private keys. The security of the ID-based signature scheme resembles the generalized ElGamal signature scheme. Security of ElGamal signature relies on the discrete logarithm problem (DLP), which is hard. So the signature is secure and guarantees the nonrepudiation of encounter records.Theorem 4.
PPERP can prevent malicious nodes from fabricating pseudo-ID and encounter record information.Proof:.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. An attacker needs to know the master key s and random number rik in order to generate a valid pseudo-ID. However, master key s is only known by the TA, so it is hard for an attacker to get key s and generate a valid pseudo-ID. In addition, as shown in Figure 3, an encounter record is signed by the private keys of two encountering nodes. So any node cannot fabricate an encounter record alone without the private key of other nodes.


## 4.7.1. Passive Attack

Theorem 2.
PPERP can prevent malicious nodes from getting some relevant privacy information by eavesdropping on encounter record and ensure the data confidentiality and anonymity of nondelivery nodes.Proof: .
The encounter record ERij is encrypted by Keyij of nodes NiT and nondelivery node Nj. Dupont et al. [27] proved that this key agreement is secure in the random oracle model under the bilinear Diffie–Hellman (BDH) assumption [28] in G1, G2, and e^. Let G1 and G2 be two groups of prime order q. Let e^: G1 × G1 ⟶ G2 be an admissible bilinear map, and let P be a generator of G1. The BDH problem in <G1, G2, e^> is as follows: given <P, aP, bP, cP> for some a, b, c∈Zq∗, compute W = e^ (P, P)abc∈G2. An algorithm A has advantage ε solving BDH in <G1, G2, e^> if(9)PrAP,aP,bP,cP=e^P,Pabc≥ε,where the probability is over the random choice of a, b, and c in Zq∗, the random choice of P∈G1∗, and the random bits of A. If there is no efficient algorithm to solve the BDH problem for < G1, G2, e^>, they are considered to satisfy the BDH assumption.
Because of the hardness of the BDH assumption, the probability of the adversary being able to recover the session key Keyij is negligible. All nodes except NiT, Nj, and TA do not know Keyij, so the privacy information on the encounter record cannot be leaked to malicious nodes.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. Since master key s is secure, rik is randomly generated, so Pidi is unlinkable and the nondelivery node anonymity is kept in the process of generating encounter records. In the process of computation routing utility, when a delivery node NiT receives an exchanged encounter record EERij (Figure 5), the ID it obtained from EERij is not the real ID of nondelivery node Nj with pseudo-ID Pidj, so the nondelivery node anonymity is kept in this process. When receiving messages as destination nodes, a nondelivery node chooses a close friend node to exchange their real ID certificates, and they first receive messages for each other and then exchange the messages back, so the message destination node anonymity is ensured.


## 4.7.2. Active Attack

Theorem 3.
PPERP can prevent malicious nodes from modifying or damaging the encounter record information and ensure the integrity, nonrepudiation of each encounter record.Proof:.
In equation (3), the summary of a record is generated by the collision-resistance hash function H2 that can prevent malicious nodes from modifying the encounter record information, so the integrity is ensured. In addition, as shown in Figure 3, the signature of the record is generated by two encountering nodes’ private keys. The security of the ID-based signature scheme resembles the generalized ElGamal signature scheme. Security of ElGamal signature relies on the discrete logarithm problem (DLP), which is hard. So the signature is secure and guarantees the nonrepudiation of encounter records.Theorem 4.
PPERP can prevent malicious nodes from fabricating pseudo-ID and encounter record information.Proof:.
The pseudo-IDPidik = Encs(Ni|| rik) of a nondelivery node Ni is computed from Enc( ), master key s, and random number rik. An attacker needs to know the master key s and random number rik in order to generate a valid pseudo-ID. However, master key s is only known by the TA, so it is hard for an attacker to get key s and generate a valid pseudo-ID. In addition, as shown in Figure 3, an encounter record is signed by the private keys of two encountering nodes. So any node cannot fabricate an encounter record alone without the private key of other nodes.


## 5. Performance Evaluation

This section evaluates the performance of PPERP. Firstly, the computational and storage cost is discussed. Then the effectiveness of PPERP is further demonstrated with extensive simulations.


### 5.1. Efficiency Analysis

Pairing-Based Cryptography (0.5.14) library [29] is used to implement the simulation on the computational and storage cost. The bilinear map e^ is Tate pairing. Two security parameters are used, a 160-bit Solinas prime q = 2159 + 2107 + 1 and a 512-bit prime p = 12qr − 1 (for some r large enough to make p the correct size). Such bit-length configurations of q and p can deliver a comparable level of security to 1,024 bit RSA cryptography. The “type A” curve from Pairing-Based Cryptography is used for experiments. The elliptic curve E is y2 = x3 + x. For the experiments, a laptop is used with an Intel dual-core 2.4 GHz CPU and 4 GB RAM under the platform Ubuntu 12.04. All the timing reported below are averaged over 50 randomized runs. Table 2 lists the main time-consuming operations used in the protocol.Table 2
Main time-consuming operations and computational cost.
Operations NotationsDefinitionsTime (ms)TeTime for pairing operation4.744TPMulTime for a point scalar multiplication operation inG13.398TPAddTime for a point addition operation inG10.013TETime for exponentiation operation inG20.607TMulTime for multiplication of two elements inG20.004TInvTime for inversion operation inZq∗0.003TH1Time for the MapToPoint hash operationH1:0,1∗⟶G1∗0.7848TH2Time for general hash operationH20.001TH3Time for general hash operationH30.001TEncTime for the symmetric encryption operation Enc( )0.039


#### 5.1.1. Computational Cost

The computational cost of generating encounter records, verifying the signature, and exchanging encounter records is considered. As shown in (1), the computation time for a node to generate the session key Keyij is 1TH1 + 1Te. The time for encrypting an encounter record is TEnc. As shown in (2), the time for generating R in the signature is 1TPMul. As shown in (3), the time for generating S in the signature is 1TH2 + 1TH3 + 3TPMul + 1TInv + 1TPAdd. So, as shown in Figure 3, the total computational cost of generating an encounter record is 1TH1 + 1Te + TEnc + (1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd × 2. According to Table 2, the time is 32.788 ms.As shown in (5), the computational cost of verifying a signature is 1TH1 + 1TH2 + 1TH3 + 3Te + 2TE + 1TMul. The cost of computing H1(Pidj) is precomputed in the above process of generating an encounter record. The cost of computing e^P,P is fixed and can also be precomputed. Therefore, the computational cost can be reduced to 1TH2 + 1TH3 + 2Te + 2TE + 1TMul. According to Table 2, the time is 10.708 ms.As shown in Figure5, the session key Keyij is precomputed in the process of generating an encounter record, so the total computational cost of exchanging encounter records is 1TEnc + 1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd. According to Table 2, the time is 13.649 ms.


#### 5.1.2. Storage Cost

Each element inG1 is 512 bit in length, so in the signature of the encounter record, the size of R and S are all 64 bytes. The storage cost of a total signature is 128 bytes. Suppose that the size of every other item in the encounter record is 4 bytes, then as shown in Figure 3, the total storage cost of an encounter record is 4 + 4+4 + 4 ∗ n + 128 + 128 = 4 ∗ n + 268 bytes. As shown in Figure 5, an exchanged encounter record has one more ID Nk and one less signature than the original encounter record, so the storage cost is 4 + 4+4 + 4 ∗ n+4 + 128 = 4 ∗ n + 144 bytes.


### 5.2. Simulation Analysis

PPERP is implemented on the ONE simulator [30]. There are 2 APs and 40 mobile nodes that contain 20 delivery nodes and 20 nondelivery nodes. The mobility model is ShortestPathMapBasedMovement model, where a node selects the shortest distance path through Dijkstra algorithm. Message generation interval is 4–8 s; buffer size is 20 MB; TTL is 60 minutes; message size is 200–300 KB; movement speed is 2–6 m/s; data speed is 250 KB/s; the area is 4,500∗3,400 m2; simulation time is 104,000 s; warm-up time is 4,000 s; and the error range ε in Algorithm 1 is 0.1.PPERP is compared with the PROPHET [2], FaceChange [13], and PPUR [14] routing protocols to evaluate its performance. In PROPHET, each node maintains its future encounter probabilities with other nodes based on previous records to guide packet routing. PROPHET is the original routing scheme without privacy-preserving and the baseline for other routing protocols.The protocol performance is evaluated by the metrics of delivery ratio, delay, and overhead ratio. The delivery ratio is the percentage of messages delivered successfully among the total messages. The delivery ratio denotes how many messages can be successfully delivered to the destination. The average delay is the average time for a message to be successfully delivered. Delivery delay denotes how quickly the messages can be delivered to the destination node. The overhead ratio is the ratio of forwarding number to the successfully delivered messages number. The overhead ratio denotes the average forwarding times of a delivered message.


#### 5.2.1. Effects of Buffer Size

Figure7 shows the delivery ratio for various buffer sizes. For all protocols, the delivery ratio increases when the buffer size increases. This is for the reason that more messages can be carried by nodes with larger buffers and finally delivered to the destination node. The delivery ratios of FaceChange, PPUR, and PPERP are slightly smaller than PROPHET. This is because there is a delay for nodes collecting encounter records, and nodes cannot update the routing utility quickly enough, which will cause the success ratio smaller. In FaceChange, a node only selects some limited trusted relay nodes to relay encounter records. In PPUR, nodes can deliver encounter records to TA and obtain routing utility only when encountering the AP. Therefore, the encounter records in FaceChange and PPUR cannot deliver as quickly as PPERP, leading to the delivery ratio smaller.Figure 7
Delivery ratio for varying buffer size.Figure8 shows the delay as a function of buffer size. When having a larger buffer, nodes get more chances to successfully deliver messages with a larger delay, so the delivery delay increases when the buffer becomes larger. The average delay of PROPHET is the largest. The delay of PPERP is smaller than PROPHET and PPUR. The delay of PPERP is slightly larger than FaceChange because more messages having larger delays are received by the destination node as seen in Figure 7.Figure 8
Delivery delay for varying buffer size.Figure9 shows the overhead ratio for various buffer sizes. As more messages are successfully forwarded to the destination node, the overhead ratio decreases as buffer size increases. The overhead ratio of PROPHET is the largest. The overhead ratio of PPERP is smaller than PPUR and PROPHET. As the message forwarding number is small, the overhead ratio of FaceChange is the smallest.Figure 9
Overhead ratio for varying buffer size.


#### 5.2.2. Effects of TTL

Figure10 shows the delivery ratio for various TTLs. As the message with longer TTL has a greater opportunity to be received by the destination node, the delivery ratio increases when the TTL becomes larger. The delivery ratio of PPERP is larger than PPUR and FaceChange. The delivery ratio of PPERP is smaller than PROPHET, as nodes can update their utility values only when receiving exchanged encounter records.Figure 10
Delivery ratio for varying TTL.Figure11 shows the delivery delay for various TTLs. Nodes can buffer and deliver more messages with longer delivery delay as the TTL increases, so delay increases when TTL becomes larger. The delay of PPERP is slightly larger than FaceChange but smaller than PPUR and PROPHET.Figure 11
Delivery delay for varying TTL.Figure12 shows the overhead ratio for various TTLs. The overhead ratio will decrease, as more messages are successfully delivered when TTL increases. The overhead ratio of the PPERP protocol is smaller than PROPHET and PPUR. The overhead ratio of FaceChange is the smallest.Figure 12
Overhead ratio for varying TTL.From above, it can be seen that the delivery ratio of PPERP is larger than PPUR and FaceChange. PPERP also achieves similar performance as the original PROPHET, which explains that the introduction of the proposed privacy-preserving scheme does not affect the performance significantly.


## 5.1. Efficiency Analysis

Pairing-Based Cryptography (0.5.14) library [29] is used to implement the simulation on the computational and storage cost. The bilinear map e^ is Tate pairing. Two security parameters are used, a 160-bit Solinas prime q = 2159 + 2107 + 1 and a 512-bit prime p = 12qr − 1 (for some r large enough to make p the correct size). Such bit-length configurations of q and p can deliver a comparable level of security to 1,024 bit RSA cryptography. The “type A” curve from Pairing-Based Cryptography is used for experiments. The elliptic curve E is y2 = x3 + x. For the experiments, a laptop is used with an Intel dual-core 2.4 GHz CPU and 4 GB RAM under the platform Ubuntu 12.04. All the timing reported below are averaged over 50 randomized runs. Table 2 lists the main time-consuming operations used in the protocol.Table 2
Main time-consuming operations and computational cost.
Operations NotationsDefinitionsTime (ms)TeTime for pairing operation4.744TPMulTime for a point scalar multiplication operation inG13.398TPAddTime for a point addition operation inG10.013TETime for exponentiation operation inG20.607TMulTime for multiplication of two elements inG20.004TInvTime for inversion operation inZq∗0.003TH1Time for the MapToPoint hash operationH1:0,1∗⟶G1∗0.7848TH2Time for general hash operationH20.001TH3Time for general hash operationH30.001TEncTime for the symmetric encryption operation Enc( )0.039


### 5.1.1. Computational Cost

The computational cost of generating encounter records, verifying the signature, and exchanging encounter records is considered. As shown in (1), the computation time for a node to generate the session key Keyij is 1TH1 + 1Te. The time for encrypting an encounter record is TEnc. As shown in (2), the time for generating R in the signature is 1TPMul. As shown in (3), the time for generating S in the signature is 1TH2 + 1TH3 + 3TPMul + 1TInv + 1TPAdd. So, as shown in Figure 3, the total computational cost of generating an encounter record is 1TH1 + 1Te + TEnc + (1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd × 2. According to Table 2, the time is 32.788 ms.As shown in (5), the computational cost of verifying a signature is 1TH1 + 1TH2 + 1TH3 + 3Te + 2TE + 1TMul. The cost of computing H1(Pidj) is precomputed in the above process of generating an encounter record. The cost of computing e^P,P is fixed and can also be precomputed. Therefore, the computational cost can be reduced to 1TH2 + 1TH3 + 2Te + 2TE + 1TMul. According to Table 2, the time is 10.708 ms.As shown in Figure5, the session key Keyij is precomputed in the process of generating an encounter record, so the total computational cost of exchanging encounter records is 1TEnc + 1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd. According to Table 2, the time is 13.649 ms.


### 5.1.2. Storage Cost

Each element inG1 is 512 bit in length, so in the signature of the encounter record, the size of R and S are all 64 bytes. The storage cost of a total signature is 128 bytes. Suppose that the size of every other item in the encounter record is 4 bytes, then as shown in Figure 3, the total storage cost of an encounter record is 4 + 4+4 + 4 ∗ n + 128 + 128 = 4 ∗ n + 268 bytes. As shown in Figure 5, an exchanged encounter record has one more ID Nk and one less signature than the original encounter record, so the storage cost is 4 + 4+4 + 4 ∗ n+4 + 128 = 4 ∗ n + 144 bytes.


## 5.1.1. Computational Cost

The computational cost of generating encounter records, verifying the signature, and exchanging encounter records is considered. As shown in (1), the computation time for a node to generate the session key Keyij is 1TH1 + 1Te. The time for encrypting an encounter record is TEnc. As shown in (2), the time for generating R in the signature is 1TPMul. As shown in (3), the time for generating S in the signature is 1TH2 + 1TH3 + 3TPMul + 1TInv + 1TPAdd. So, as shown in Figure 3, the total computational cost of generating an encounter record is 1TH1 + 1Te + TEnc + (1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd × 2. According to Table 2, the time is 32.788 ms.As shown in (5), the computational cost of verifying a signature is 1TH1 + 1TH2 + 1TH3 + 3Te + 2TE + 1TMul. The cost of computing H1(Pidj) is precomputed in the above process of generating an encounter record. The cost of computing e^P,P is fixed and can also be precomputed. Therefore, the computational cost can be reduced to 1TH2 + 1TH3 + 2Te + 2TE + 1TMul. According to Table 2, the time is 10.708 ms.As shown in Figure5, the session key Keyij is precomputed in the process of generating an encounter record, so the total computational cost of exchanging encounter records is 1TEnc + 1TH2 + 1TH3 + 4TPMul + 1TInv + 1TPAdd. According to Table 2, the time is 13.649 ms.


## 5.1.2. Storage Cost

Each element inG1 is 512 bit in length, so in the signature of the encounter record, the size of R and S are all 64 bytes. The storage cost of a total signature is 128 bytes. Suppose that the size of every other item in the encounter record is 4 bytes, then as shown in Figure 3, the total storage cost of an encounter record is 4 + 4+4 + 4 ∗ n + 128 + 128 = 4 ∗ n + 268 bytes. As shown in Figure 5, an exchanged encounter record has one more ID Nk and one less signature than the original encounter record, so the storage cost is 4 + 4+4 + 4 ∗ n+4 + 128 = 4 ∗ n + 144 bytes.


## 5.2. Simulation Analysis

PPERP is implemented on the ONE simulator [30]. There are 2 APs and 40 mobile nodes that contain 20 delivery nodes and 20 nondelivery nodes. The mobility model is ShortestPathMapBasedMovement model, where a node selects the shortest distance path through Dijkstra algorithm. Message generation interval is 4–8 s; buffer size is 20 MB; TTL is 60 minutes; message size is 200–300 KB; movement speed is 2–6 m/s; data speed is 250 KB/s; the area is 4,500∗3,400 m2; simulation time is 104,000 s; warm-up time is 4,000 s; and the error range ε in Algorithm 1 is 0.1.PPERP is compared with the PROPHET [2], FaceChange [13], and PPUR [14] routing protocols to evaluate its performance. In PROPHET, each node maintains its future encounter probabilities with other nodes based on previous records to guide packet routing. PROPHET is the original routing scheme without privacy-preserving and the baseline for other routing protocols.The protocol performance is evaluated by the metrics of delivery ratio, delay, and overhead ratio. The delivery ratio is the percentage of messages delivered successfully among the total messages. The delivery ratio denotes how many messages can be successfully delivered to the destination. The average delay is the average time for a message to be successfully delivered. Delivery delay denotes how quickly the messages can be delivered to the destination node. The overhead ratio is the ratio of forwarding number to the successfully delivered messages number. The overhead ratio denotes the average forwarding times of a delivered message.


### 5.2.1. Effects of Buffer Size

Figure7 shows the delivery ratio for various buffer sizes. For all protocols, the delivery ratio increases when the buffer size increases. This is for the reason that more messages can be carried by nodes with larger buffers and finally delivered to the destination node. The delivery ratios of FaceChange, PPUR, and PPERP are slightly smaller than PROPHET. This is because there is a delay for nodes collecting encounter records, and nodes cannot update the routing utility quickly enough, which will cause the success ratio smaller. In FaceChange, a node only selects some limited trusted relay nodes to relay encounter records. In PPUR, nodes can deliver encounter records to TA and obtain routing utility only when encountering the AP. Therefore, the encounter records in FaceChange and PPUR cannot deliver as quickly as PPERP, leading to the delivery ratio smaller.Figure 7
Delivery ratio for varying buffer size.Figure8 shows the delay as a function of buffer size. When having a larger buffer, nodes get more chances to successfully deliver messages with a larger delay, so the delivery delay increases when the buffer becomes larger. The average delay of PROPHET is the largest. The delay of PPERP is smaller than PROPHET and PPUR. The delay of PPERP is slightly larger than FaceChange because more messages having larger delays are received by the destination node as seen in Figure 7.Figure 8
Delivery delay for varying buffer size.Figure9 shows the overhead ratio for various buffer sizes. As more messages are successfully forwarded to the destination node, the overhead ratio decreases as buffer size increases. The overhead ratio of PROPHET is the largest. The overhead ratio of PPERP is smaller than PPUR and PROPHET. As the message forwarding number is small, the overhead ratio of FaceChange is the smallest.Figure 9
Overhead ratio for varying buffer size.


### 5.2.2. Effects of TTL

Figure10 shows the delivery ratio for various TTLs. As the message with longer TTL has a greater opportunity to be received by the destination node, the delivery ratio increases when the TTL becomes larger. The delivery ratio of PPERP is larger than PPUR and FaceChange. The delivery ratio of PPERP is smaller than PROPHET, as nodes can update their utility values only when receiving exchanged encounter records.Figure 10
Delivery ratio for varying TTL.Figure11 shows the delivery delay for various TTLs. Nodes can buffer and deliver more messages with longer delivery delay as the TTL increases, so delay increases when TTL becomes larger. The delay of PPERP is slightly larger than FaceChange but smaller than PPUR and PROPHET.Figure 11
Delivery delay for varying TTL.Figure12 shows the overhead ratio for various TTLs. The overhead ratio will decrease, as more messages are successfully delivered when TTL increases. The overhead ratio of the PPERP protocol is smaller than PROPHET and PPUR. The overhead ratio of FaceChange is the smallest.Figure 12
Overhead ratio for varying TTL.From above, it can be seen that the delivery ratio of PPERP is larger than PPUR and FaceChange. PPERP also achieves similar performance as the original PROPHET, which explains that the introduction of the proposed privacy-preserving scheme does not affect the performance significantly.


## 5.2.1. Effects of Buffer Size

Figure7 shows the delivery ratio for various buffer sizes. For all protocols, the delivery ratio increases when the buffer size increases. This is for the reason that more messages can be carried by nodes with larger buffers and finally delivered to the destination node. The delivery ratios of FaceChange, PPUR, and PPERP are slightly smaller than PROPHET. This is because there is a delay for nodes collecting encounter records, and nodes cannot update the routing utility quickly enough, which will cause the success ratio smaller. In FaceChange, a node only selects some limited trusted relay nodes to relay encounter records. In PPUR, nodes can deliver encounter records to TA and obtain routing utility only when encountering the AP. Therefore, the encounter records in FaceChange and PPUR cannot deliver as quickly as PPERP, leading to the delivery ratio smaller.Figure 7
Delivery ratio for varying buffer size.Figure8 shows the delay as a function of buffer size. When having a larger buffer, nodes get more chances to successfully deliver messages with a larger delay, so the delivery delay increases when the buffer becomes larger. The average delay of PROPHET is the largest. The delay of PPERP is smaller than PROPHET and PPUR. The delay of PPERP is slightly larger than FaceChange because more messages having larger delays are received by the destination node as seen in Figure 7.Figure 8
Delivery delay for varying buffer size.Figure9 shows the overhead ratio for various buffer sizes. As more messages are successfully forwarded to the destination node, the overhead ratio decreases as buffer size increases. The overhead ratio of PROPHET is the largest. The overhead ratio of PPERP is smaller than PPUR and PROPHET. As the message forwarding number is small, the overhead ratio of FaceChange is the smallest.Figure 9
Overhead ratio for varying buffer size.


## 5.2.2. Effects of TTL

Figure10 shows the delivery ratio for various TTLs. As the message with longer TTL has a greater opportunity to be received by the destination node, the delivery ratio increases when the TTL becomes larger. The delivery ratio of PPERP is larger than PPUR and FaceChange. The delivery ratio of PPERP is smaller than PROPHET, as nodes can update their utility values only when receiving exchanged encounter records.Figure 10
Delivery ratio for varying TTL.Figure11 shows the delivery delay for various TTLs. Nodes can buffer and deliver more messages with longer delivery delay as the TTL increases, so delay increases when TTL becomes larger. The delay of PPERP is slightly larger than FaceChange but smaller than PPUR and PROPHET.Figure 11
Delivery delay for varying TTL.Figure12 shows the overhead ratio for various TTLs. The overhead ratio will decrease, as more messages are successfully delivered when TTL increases. The overhead ratio of the PPERP protocol is smaller than PROPHET and PPUR. The overhead ratio of FaceChange is the smallest.Figure 12
Overhead ratio for varying TTL.From above, it can be seen that the delivery ratio of PPERP is larger than PPUR and FaceChange. PPERP also achieves similar performance as the original PROPHET, which explains that the introduction of the proposed privacy-preserving scheme does not affect the performance significantly.


## 6. Conclusions

A privacy-preserving exchange-based protocol PPERP for utility-based routing in opportunistic networks is proposed in this paper. PPERP can preserve nodes’ private information and collect encounter records to compute routing utility without relying on any trusted third party. In addition, the bilinear mapping technique is adopted to ensure the confidentiality, integrity, and nonrepudiation of encounter records. The effectiveness and efficiency of PPERP have also been verified by simulations. Compared with other routing protocols, PPERP can achieve a similar performance as the original PROPHET, which has no privacy-preserving, and get larger delivery ratio than FaceChange and PPUR. In addition, the real ID-based private encounter information in FaceChange will be leaked after two neighbor nodes disconnect. However, in the PPERP protocol, the sensitive private encounter information is preserved even if two nodes disconnect with each other. PPUR needs a TA to compute routing utility. But the PPERP protocol is distributed, and a node can directly compute its routing utility value without relying on any trusted third party. Now, this work focuses on preserving the private information of nondelivery nodes. It is planned to devise a privacy-preserving opportunistic networks routing protocol that can preserve the private information of all nodes at the same time.



---

*Source: 6815911-2022-04-09.xml*