# A Rational Exchange Protocol under Asymmetric Information in Wireless Sensor Networks

Authors: Zhen Lv; Changgen Peng; Yanguo Peng; Junwei Zhang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

P2P network is one of the most extensive network frameworks for wireless sensor network (WSN) in Internet of Things (IoT). The peers in WSN are rational and often free ride to save power of electricity and calculation, due to the fact that the usability is of great variability and unpredictability. Such a phenomenon tremendously reduces the quality of service (QoS) in WSN. Rational exchange protocol aims at promoting QoS and guaranteeing security and fairness. However, existing schemes have taken only complete information into account, which is not up to realistic environment. The peers in realistic environment indeed possess incomplete information, which is, however, still not thoroughly investigated so far. In this paper, under asymmetric information (a typical incomplete information), an entropy based incentive model is well designed based on Markov model and QoS evaluation model to help peers cooperate in WSNs. A concrete utility function with entropy is constructed to evaluate decision utility in P2P network. Finally, an entropy based rational exchange protocol is proposed based on the presented incentive model and concrete utility function, with analysis of correctness, security, fairness, and robustness, respectively. The proposed protocol can facilitate rational peers positively and sensibly participating in services and prevent free riding for rational peers. Hence, it further promotes QoS and guarantees security and fairness simultaneously in WSNs.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) contains massive static and dynamic wireless sensors that extremely lack electricity and calculation. Due to that, sensors are highly willing to intentionally free ride [1–4] for better efficiency selfishly. Especially, in P2P network, which is one of the most extensive network frameworks for WSNs, peers (i.e., wireless sensors) are rational in fact. Rational peers make decisions to maximize their own benefit first and tremendously reduce the quality of service (QoS) of WSNs. To prevent free riding of rational peers and promote QoS, rational protocols have been widely investigated in security community [5–8].Rational cryptography is a fresh and important branch in cryptographic research field, where rational exchange protocol is compatible and applicable for WSNs. Rational exchange protocol, which promotes peers to positively provide various services (data transmitting, data sharing, data distributing, etc.), aims at promoting QoS in WSNs. Simultaneously, rational exchange protocol guarantees both security and fairness for peers in WSNs, which are practical and necessary requirement in realistic environments.Existing rational exchange protocols have been widely investigated since they were proposed by Syverson [9] in 1998. After that, extensive research work has been done under complete information [10–14], which means that each peer in WSN is fully aware of characteristics of participants, strategic space, and utility function about others. In realistic environments, however, the information is not always available (type, reputation, QoS, etc.), in which information is incomplete. A typical phenomenon is under asymmetric information [15], where, between two communicating peers, one possesses private information while the other is not aware of that. Unfortunately, rational exchange protocol under asymmetric information is not well considered so far and should be investigated thoroughly.We focus on, in this paper, proposing a rational exchange protocol with security and fairness under asymmetric information. Also, it is applied in wireless sensor networks aiming at promoting QoS of peers. The dominating contributions are as follows.(1)
To quantify utilities of participants, a dynamic game model with entropy is presented. In such a model, the utility for participants can be quantitatively analyzed. Furthermore, a selective basis of strategies in a game is explicitly provided (Section2.1).(2)
Under asymmetric information, a Markov-based entropy function and a QoS evaluation model are designed. A utility function with entropy is further concreted to measure fairness of rational exchange protocol (Section3).(3)
A concrete rational exchange protocol under asymmetric information is presented with through analysis of correctness, security, fairness, and robustness. Additionally, the proposed utility function with entropy is simulated and appropriateness is declared (Section4).The rest of this paper is organized as follows. Section2 introduces the problem definition and preliminaries. Under asymmetric information, Section 3 presents a utility function with entropy based on Markov-based entropy function and QoS evaluation model. The concrete rational exchange protocol is proposed in Section 4 with thorough analysis. The simulation of utility function with entropy is presented in Section 5. Finally, the related work is summarized in Section 6 and this paper is concluded in Section 7.


## 2. Problem Definition and Preliminaries

In this section, we formally define a dynamic game model in which a utility function with entropy can be derived. Following that, a rational exchange protocol is formalized.For facile understanding, the primary notations are listed in Table1.Table 1
Primary notations.
Notation Meaning P,Pi Set of participants and participant. n Number of participants inP. inf Exchanging Information. A Set of optional actions. H• Mixed strategy entropy function. T Participant’s contribution value. c Unitary cost for participating in an exchange. wij Credit that participantPj rates Pi. Z Participant’s number of positive feedbacks. U Utility. T Transfer matrix of participant’s type. R Possibility matrix of service for all participants. PUB Bulletin board. E(),D() Asymmetric encryption and decryption functions. E^(),D^() Symmetric encryption and decryption functions. ωx Weakly secret bit commitment function. PK,SK,k Public key, private key, and session key.


### 2.1. Definition of Dynamic Game with Entropy

In this section, a dynamic game model with entropy is introduced to pave the way to quantify utilities of participants.Definition 1 (dynamic game model with entropy).
A dynamic game model with entropy contains a seven-tupleP,Q,IiPi∈P,A,fp,≥iPi∈P,Hi•Pi∈P, where the elements are formally defined as follows. (i)
P is a set of participants, in which pi is a participant.(ii)
Q is a set of sequences of actions containing all participants’ actions. A sequence consists of participant’s specific actions in a dynamic game. Q satisfies the following characteristics.
(1)
The empty sequence is∅∈Q.(2)
If a sequence of actionsq satisfies that q=ajj=1w∈Q and 0<v<w∈N∗, then q′=ajj=1v∈Q holds.(3)
If anyv∈N∗ and q′=ajj=1v∈Q holds, then the infinite sequence of actions q=ajj=1∞∈Q holds.(iii)
(Ii)Pi∈P is participant Pi’s information set denoting the previous information of other participants in a game. An information set is formally denoted as IiPi∈P=x1,x2,…,xm, where xi is the previous m action sequences of the other participants and the corresponding probability distribution is px1,px2,…,pxm such that ∑i=1mpxi=1.(iv)
A is a set of optional actions, in which A=∪Ai and Ai is the optional actions of participant Pi.(v)
fp is a participant function, to determine the next participant of nonterminal sequence of actions.(vi)
≥iPi∈P is a preference relation for participant Pi under a set of mixed strategies. Generally, the utility function Uiq of participant Pi is the preference. The preference relation q∗≥iq means that Uiq∗≥Uiq and q∗ is the willing action sequence for participant Pi.(vii)
Hi•Pi∈P is a mixed strategy entropy function for participant Pi. It is a probability distribution function of strategies on IiPi∈P. Given the round number r of a game, the entropy function of participant Pi in rth round is Hir=-∑pxilog⁡p(xi), in which Hi•=∑r=1NHir≥0 is the total entropy of participant Pi during a whole game.So far, we define a novel dynamic game model to analyze the rational exchange protocol that will be proposed in the following.


### 2.2. Definition of Rational Exchange Protocol

In this paper, rational exchange protocol is thoroughly investigated under two participants. Such a protocol can be facilely generalized into multiple participants in theory.Definition 2 (rational exchange protocol with entropy).
A rational exchange protocol with entropy contains a five-tupleHX∣Y,PA,PB,PUB,π, in which HX∣Y is a conditional entropy, PA and PB are the participants, PUB is a bulletin board, and π is the concrete exchange protocol. Additionally, π is formally defined as follows. (i)
Setup: generate the secret and public keys for PA and PB and other public parameters.(ii)
Rational exchange: participants PA and PB own information infA and infB, respectively. PA and PB rationally exchange their information, which means that PA and PB correctly get infB and infA, respectively, or get nothing.A rational exchange protocol must satisfy the following four pivotal requirements.Correctness. Such a requirement provides a guarantee that, when π is finished, PA and PB can successfully exchange infA and infB. Additionally, both PA and PB receive the positive feedbacks and credits that are defined later, in time.Security. Both infA and infB must be prevented from adversary’s cracking. That means there is no illegal participant that can derive anything from encrypted information during the exchange. Additionally, such a protocol can not reveal anything valuable during interactive processes.Fairness. Since all participants are rational and aim at maximizing their own benefit, a rational exchange protocol is fair when the expected utilities for all the participants are maximized.Robustness. The protocol is steady. That means even when the protocol is destabilized or interrupted, the fairness is still satisfied.


## 2.1. Definition of Dynamic Game with Entropy

In this section, a dynamic game model with entropy is introduced to pave the way to quantify utilities of participants.Definition 1 (dynamic game model with entropy).
A dynamic game model with entropy contains a seven-tupleP,Q,IiPi∈P,A,fp,≥iPi∈P,Hi•Pi∈P, where the elements are formally defined as follows. (i)
P is a set of participants, in which pi is a participant.(ii)
Q is a set of sequences of actions containing all participants’ actions. A sequence consists of participant’s specific actions in a dynamic game. Q satisfies the following characteristics.
(1)
The empty sequence is∅∈Q.(2)
If a sequence of actionsq satisfies that q=ajj=1w∈Q and 0<v<w∈N∗, then q′=ajj=1v∈Q holds.(3)
If anyv∈N∗ and q′=ajj=1v∈Q holds, then the infinite sequence of actions q=ajj=1∞∈Q holds.(iii)
(Ii)Pi∈P is participant Pi’s information set denoting the previous information of other participants in a game. An information set is formally denoted as IiPi∈P=x1,x2,…,xm, where xi is the previous m action sequences of the other participants and the corresponding probability distribution is px1,px2,…,pxm such that ∑i=1mpxi=1.(iv)
A is a set of optional actions, in which A=∪Ai and Ai is the optional actions of participant Pi.(v)
fp is a participant function, to determine the next participant of nonterminal sequence of actions.(vi)
≥iPi∈P is a preference relation for participant Pi under a set of mixed strategies. Generally, the utility function Uiq of participant Pi is the preference. The preference relation q∗≥iq means that Uiq∗≥Uiq and q∗ is the willing action sequence for participant Pi.(vii)
Hi•Pi∈P is a mixed strategy entropy function for participant Pi. It is a probability distribution function of strategies on IiPi∈P. Given the round number r of a game, the entropy function of participant Pi in rth round is Hir=-∑pxilog⁡p(xi), in which Hi•=∑r=1NHir≥0 is the total entropy of participant Pi during a whole game.So far, we define a novel dynamic game model to analyze the rational exchange protocol that will be proposed in the following.


## 2.2. Definition of Rational Exchange Protocol

In this paper, rational exchange protocol is thoroughly investigated under two participants. Such a protocol can be facilely generalized into multiple participants in theory.Definition 2 (rational exchange protocol with entropy).
A rational exchange protocol with entropy contains a five-tupleHX∣Y,PA,PB,PUB,π, in which HX∣Y is a conditional entropy, PA and PB are the participants, PUB is a bulletin board, and π is the concrete exchange protocol. Additionally, π is formally defined as follows. (i)
Setup: generate the secret and public keys for PA and PB and other public parameters.(ii)
Rational exchange: participants PA and PB own information infA and infB, respectively. PA and PB rationally exchange their information, which means that PA and PB correctly get infB and infA, respectively, or get nothing.A rational exchange protocol must satisfy the following four pivotal requirements.Correctness. Such a requirement provides a guarantee that, when π is finished, PA and PB can successfully exchange infA and infB. Additionally, both PA and PB receive the positive feedbacks and credits that are defined later, in time.Security. Both infA and infB must be prevented from adversary’s cracking. That means there is no illegal participant that can derive anything from encrypted information during the exchange. Additionally, such a protocol can not reveal anything valuable during interactive processes.Fairness. Since all participants are rational and aim at maximizing their own benefit, a rational exchange protocol is fair when the expected utilities for all the participants are maximized.Robustness. The protocol is steady. That means even when the protocol is destabilized or interrupted, the fairness is still satisfied.


## 3. Utility Function with Entropy under Asymmetric Information

Before designing and representing a formal rational exchange protocol, a utility function capability for the dynamic game model with entropy is proposed in this section. Specifically, a Markov-based entropy function and a QoS evaluation model under asymmetric information are sequentially designed. Based on both of them, a utility function with entropy is concreted under asymmetric information.


### 3.1. Markov-Based Entropy Function

Under asymmetric information, participant does not completely know, before exchanging information, about other participants’ a priori information (i.e., participant’s type). Additionally, participant’s status relies only on the last past status. Hence, we introduce Markov chain to evaluate participant’s information entropy.Participants in our model are categorized into four types according to the contribution of participant in the system.(i)
Positive: such a participant provides service with a higher probability (e.g., p≥80%). Here, positive participant’s QoS is preferable. He can transfer to be ordinary.(ii)
Ordinary: such a participant provides service with a moderate probability (e.g., 50%≤p<80%). He can transfer to be positive or negative.(iii)
Negative: such a participant provides service with a lower probability (e.g., 0%<p<50%). He can transfer to be ordinary or outside.(iv)
Outside: such a participant does not provide any service (e.g., p=0%) and does always free ride. He can transfer to be only negative.In the transfer, each participant stays in a specific type with a specific probability and each transfer occurs with a specific probability too. The transfer between participants with different types is illustrated in Figure1.Figure 1
The transfer types for participants.The constraint rules for participant’s action are as follows.(1)
Allow participant to be outside when he first participates in a game.(2)
Every other period with timet>0, the mechanism figures out the distribution of all participants’ types.By following the above constraints, every period, the probabilityRij for participant Pj serving participant Pi is estimated based on Markov chain. Based on the distribution in Step(2), the transfer matrix P4×4 of participants’ types can be resolved. Specifically, at jth period, the transfer matrix is Pj=P0•Pj, and the steady-state vector D is derived by resolving a system of linear equations D=D•P. Here, D=dii=1,2,3,4. The probability of service is Rij=D•gT, where g=gii=1,2,3,4 is the vector containing all membership functions corresponding to all participants’ types (i.e., by embedding membership functions, the values of probabilities that participant provides service can be estimated in advance; thus, participant will be further convinced of his decision). In our construction, gi (1≤i≤4) stands for the tendency of maintaining a specific type (positive, ordinary, negative, and outside) for a participant. Finally, the probability matrix of service for all participants is Rn×n=Rij, where 1≤i,j≤n.According to the analysis of Shannon entropy and perceptive information, when a system achieves steady,Pi’s total quantity of services coming from other participants is Hi=-∑j=1nRijln⁡Rij, where i≠j. From the aspect of expectation, Hi is larger; also Pi’s willingness to participate in exchanging information is stronger. The expectation for the whole system is H=∑Pi∈PHi, which is changing with periods.The ultimate entropyH∞ of m-orderly discrete information source with memory is the m-orderly conditional entropy for a steady system. That means H∞=limn→∞HXn∣X1…Xn-1=HXm+1∣X1…Xm=Hm+1, in which Hm+1=-∑i=1n∑j=1nRijln⁡Rij. The ultimate entropy H∞ weighs the average quantity of information of all symbols that the information source sends. That means all the participants in an exchange protocol achieve steady.


### 3.2. QoS Evaluation Model under Asymmetric Information

Asymmetric information is a typically incomplete information. It means that, in an exchange protocol, a participant’s information is complete, and the other’s is incomplete. The former is advantageous participant, and the latter is disadvantageous participant. A rational participant makes decision through observing information that other participants reveal and deducing other participants’ actions, in order to make his own expected utility maximum.In this section, a deducing method is presented to turn asymmetric information into weakened-symmetric information. Based on that, a QoS evaluation model under asymmetric information is proposed for guaranteeing disadvantage and advantageous participants’ fairness simultaneously.For a disadvantageous participant (i.e., receiver) and an advantageous participant (i.e., sender) in a rational exchange protocol, the receiver derives a random variableY about the exchanging information according to his own prior knowledge. The realistic information X is estimated by Y. In such a case, HX∣Y is the uncertainty of X on the condition that Y is known. Here, let HX be the prior uncertainty and HX∣Y be the posterior uncertainty. The mutual information entropy is HX;Y=HX-HX∣Y, which stands for the average quantity of information that is derived from Y about X. If HX∣Y→0, then HX;Y→HX and asymmetry of two participants is removed. The random variable Y can be corrected according to Bayes rules with exchanging information. The transform process is shown in Figure 2.Figure 2
The transform process from asymmetric information to symmetric information.LetHq•=HX be the quantity of exchanging information that the receiver does not know. To overcome the asymmetry of information, in fact, the receiver corrects service quantity by Bayes probability principle px∣y=py∣xpx/py with other participants’ valuation about the exchanging information and derives the posterior probability distribution π^q.Definition 3 (QoS evaluation mechanism).
In a QoS evaluation mechanism, a list is maintained along with a whole rational exchange protocol. For participantPi, the element in the list contains a three-tuple Pi,Zi,RPi. Here, Pi is the unique identifier, Zi is the number of positive feedbacks, RPi=∪l=1mAil,δil,wijPj∈P\Pi is the set of records for lth round, in which Ail is the set of lth round actions, δil is the comment about quality of information in lth round, and wijPj∈P\Pi is the vector of credits for lth round information exchange.
Specifically, the list above is maintained at a bulletin board. Afterlth round exchange between sender PS and receiver PR, the following steps are carried out. (1)
PR comments on such an exchange and uploads δSl to the bulletin board. The bulletin board records actions in this exchange as ASl.(2)
PR rates the quality of the exchanged information as wSR and uploads it to the bulletin board.(3)
PR can make a positive feedback by setting ZS=ZS+1 if wSR is greater than a threshold and a negative feedback by setting ZS=ZS-1 if wSR is smaller than a threshold.(4)
If there are multiple receiversPj∈P\PR (1≤j≤m) in the system, Pj rates the quality of the exchanged information as wSj and makes a positive feedback for the other participants who make a consistent credit wSj.By embedding such a QoS evaluation mechanism, all participants are further more willing to really evaluate the quality of exchanged information, in order to maximize credit and number of positive feedbacks. It is vital to measure participant’s long-term utility.


### 3.3. Utility Function with Entropy

By comprehensive consideration of long-term utility and short-term utilities, the utility function with entropy is proposed for participantPi.(1)Ui=-ciTi+Hi∑j=1nwij+ln⁡ZiTi.Here,ci is the unitary cost for participating in an exchange and obtaining a unitary contribution value. Ti=α∑j=1nRij is the contribution value in which the contribution weight α falls in 0,1.In the equation,wij reflects short-term benefit and Zi reflects long-term benefit for participant. In fact, in realistic scenarios, short-term benefit is more crucial than long-term benefit. In order to respond to such a correlation, it is necessary to take the logarithm of Zi in the equation. By logarithm, the protocol is able to prevent participants with long-term benefit doing one-time deceive and provides rational fair from a new point of view. Through the combination of both, the utility function is more practical than others proposed in existing schemes.Additionally, the product of information entropyHi, which is the quantization of QoS, and ∑j=1nwij+ln⁡Zi constitutes the unitary revenue. Furthermore, Ti multiplied by Hi∑j=1nwij+ln⁡Zi is Pi’s revenue. According to the definition, ciTi is the cost in total. Hence, the eventual utility for participant Pi is formalized and quantized by (1).


## 3.1. Markov-Based Entropy Function

Under asymmetric information, participant does not completely know, before exchanging information, about other participants’ a priori information (i.e., participant’s type). Additionally, participant’s status relies only on the last past status. Hence, we introduce Markov chain to evaluate participant’s information entropy.Participants in our model are categorized into four types according to the contribution of participant in the system.(i)
Positive: such a participant provides service with a higher probability (e.g., p≥80%). Here, positive participant’s QoS is preferable. He can transfer to be ordinary.(ii)
Ordinary: such a participant provides service with a moderate probability (e.g., 50%≤p<80%). He can transfer to be positive or negative.(iii)
Negative: such a participant provides service with a lower probability (e.g., 0%<p<50%). He can transfer to be ordinary or outside.(iv)
Outside: such a participant does not provide any service (e.g., p=0%) and does always free ride. He can transfer to be only negative.In the transfer, each participant stays in a specific type with a specific probability and each transfer occurs with a specific probability too. The transfer between participants with different types is illustrated in Figure1.Figure 1
The transfer types for participants.The constraint rules for participant’s action are as follows.(1)
Allow participant to be outside when he first participates in a game.(2)
Every other period with timet>0, the mechanism figures out the distribution of all participants’ types.By following the above constraints, every period, the probabilityRij for participant Pj serving participant Pi is estimated based on Markov chain. Based on the distribution in Step(2), the transfer matrix P4×4 of participants’ types can be resolved. Specifically, at jth period, the transfer matrix is Pj=P0•Pj, and the steady-state vector D is derived by resolving a system of linear equations D=D•P. Here, D=dii=1,2,3,4. The probability of service is Rij=D•gT, where g=gii=1,2,3,4 is the vector containing all membership functions corresponding to all participants’ types (i.e., by embedding membership functions, the values of probabilities that participant provides service can be estimated in advance; thus, participant will be further convinced of his decision). In our construction, gi (1≤i≤4) stands for the tendency of maintaining a specific type (positive, ordinary, negative, and outside) for a participant. Finally, the probability matrix of service for all participants is Rn×n=Rij, where 1≤i,j≤n.According to the analysis of Shannon entropy and perceptive information, when a system achieves steady,Pi’s total quantity of services coming from other participants is Hi=-∑j=1nRijln⁡Rij, where i≠j. From the aspect of expectation, Hi is larger; also Pi’s willingness to participate in exchanging information is stronger. The expectation for the whole system is H=∑Pi∈PHi, which is changing with periods.The ultimate entropyH∞ of m-orderly discrete information source with memory is the m-orderly conditional entropy for a steady system. That means H∞=limn→∞HXn∣X1…Xn-1=HXm+1∣X1…Xm=Hm+1, in which Hm+1=-∑i=1n∑j=1nRijln⁡Rij. The ultimate entropy H∞ weighs the average quantity of information of all symbols that the information source sends. That means all the participants in an exchange protocol achieve steady.


## 3.2. QoS Evaluation Model under Asymmetric Information

Asymmetric information is a typically incomplete information. It means that, in an exchange protocol, a participant’s information is complete, and the other’s is incomplete. The former is advantageous participant, and the latter is disadvantageous participant. A rational participant makes decision through observing information that other participants reveal and deducing other participants’ actions, in order to make his own expected utility maximum.In this section, a deducing method is presented to turn asymmetric information into weakened-symmetric information. Based on that, a QoS evaluation model under asymmetric information is proposed for guaranteeing disadvantage and advantageous participants’ fairness simultaneously.For a disadvantageous participant (i.e., receiver) and an advantageous participant (i.e., sender) in a rational exchange protocol, the receiver derives a random variableY about the exchanging information according to his own prior knowledge. The realistic information X is estimated by Y. In such a case, HX∣Y is the uncertainty of X on the condition that Y is known. Here, let HX be the prior uncertainty and HX∣Y be the posterior uncertainty. The mutual information entropy is HX;Y=HX-HX∣Y, which stands for the average quantity of information that is derived from Y about X. If HX∣Y→0, then HX;Y→HX and asymmetry of two participants is removed. The random variable Y can be corrected according to Bayes rules with exchanging information. The transform process is shown in Figure 2.Figure 2
The transform process from asymmetric information to symmetric information.LetHq•=HX be the quantity of exchanging information that the receiver does not know. To overcome the asymmetry of information, in fact, the receiver corrects service quantity by Bayes probability principle px∣y=py∣xpx/py with other participants’ valuation about the exchanging information and derives the posterior probability distribution π^q.Definition 3 (QoS evaluation mechanism).
In a QoS evaluation mechanism, a list is maintained along with a whole rational exchange protocol. For participantPi, the element in the list contains a three-tuple Pi,Zi,RPi. Here, Pi is the unique identifier, Zi is the number of positive feedbacks, RPi=∪l=1mAil,δil,wijPj∈P\Pi is the set of records for lth round, in which Ail is the set of lth round actions, δil is the comment about quality of information in lth round, and wijPj∈P\Pi is the vector of credits for lth round information exchange.
Specifically, the list above is maintained at a bulletin board. Afterlth round exchange between sender PS and receiver PR, the following steps are carried out. (1)
PR comments on such an exchange and uploads δSl to the bulletin board. The bulletin board records actions in this exchange as ASl.(2)
PR rates the quality of the exchanged information as wSR and uploads it to the bulletin board.(3)
PR can make a positive feedback by setting ZS=ZS+1 if wSR is greater than a threshold and a negative feedback by setting ZS=ZS-1 if wSR is smaller than a threshold.(4)
If there are multiple receiversPj∈P\PR (1≤j≤m) in the system, Pj rates the quality of the exchanged information as wSj and makes a positive feedback for the other participants who make a consistent credit wSj.By embedding such a QoS evaluation mechanism, all participants are further more willing to really evaluate the quality of exchanged information, in order to maximize credit and number of positive feedbacks. It is vital to measure participant’s long-term utility.


## 3.3. Utility Function with Entropy

By comprehensive consideration of long-term utility and short-term utilities, the utility function with entropy is proposed for participantPi.(1)Ui=-ciTi+Hi∑j=1nwij+ln⁡ZiTi.Here,ci is the unitary cost for participating in an exchange and obtaining a unitary contribution value. Ti=α∑j=1nRij is the contribution value in which the contribution weight α falls in 0,1.In the equation,wij reflects short-term benefit and Zi reflects long-term benefit for participant. In fact, in realistic scenarios, short-term benefit is more crucial than long-term benefit. In order to respond to such a correlation, it is necessary to take the logarithm of Zi in the equation. By logarithm, the protocol is able to prevent participants with long-term benefit doing one-time deceive and provides rational fair from a new point of view. Through the combination of both, the utility function is more practical than others proposed in existing schemes.Additionally, the product of information entropyHi, which is the quantization of QoS, and ∑j=1nwij+ln⁡Zi constitutes the unitary revenue. Furthermore, Ti multiplied by Hi∑j=1nwij+ln⁡Zi is Pi’s revenue. According to the definition, ciTi is the cost in total. Hence, the eventual utility for participant Pi is formalized and quantized by (1).


## 4. The Rational Exchange Protocol

In this section, the proposed concrete rational exchange protocol under asymmetric information is presented at the beginning. Following that, the detailed analysis is thoroughly stated. Additionally, theoretical comparisons between rational exchange protocols are represented to declare the presented rational exchange protocol’s superiority.


### 4.1. Construction

Assume that there is no trusted third party in the proposed rational exchange protocol with multiple participants. That means each participant makes decision by maximizing his utility. Such a participant is rational and enjoys equal status, without considering compromising between participants.In the concrete protocol, any two participants directly exchange information with each other. Assume that a senderPA and a receiver PB exchange infA and infB in the rational exchange protocol. Under asymmetric information, PA is the advantageous participant and PB is the disadvantage one. Additionally, infA is channel-sensitive and takes a long time t to be transmitted, but the time to transmit infB is short and negligible. There is also a bulletin board in the protocol to only manage all participants’ account information and nothing else.Setup. A weakly secret bit commitment function ω(x) is adopted, in which x can only be derived over time t0>t since it is encrypted. An asymmetric encryption algorithm E and a symmetric encryption algorithm E^ are adopted. The corresponding decryption algorithms are D and D^. According to the adopted asymmetric encryption algorithm E, PKA,SKA is generated for participant PA as the public-private key pair, and PKB,SKB is generated for participant PB too. Additionally, the bulletin board PUB is initialized by maintaining QoS evaluation mechanism with an empty list.Rational Exchange. PA and PB rationally exchange information infA and infB by executing the following steps. The interactive processes for two participants are illustrated in Figure 3.(1)
The disadvantageous participantPB calculates the conditional entropy HX∣Y according to the advantageous participant PA’s number of positive feedbacks ZA. He makes decision by checking HX∣Y. If he wishes to exchange information, then he continues to do the following steps. Otherwise, the protocol halts.(2)
PA randomly chooses a session key kA for E^ and sends m1 to PB, in which m1=EPKBESKAB,E^kAinfA,B,E^kAinfA.(3)
After receivingm1=EPKBY1,Y2,Y3, PB decrypt m1 and derive B=Y2 and E^kAinfA=Y3 by checking DPKAY1=Y2,Y3. If DPKAY1=Y2,Y3 does not hold, then PB halts. Otherwise, PB randomly chooses a session key kB for E^ and sends m2 to PUB, in which m2=EPKAESKBA,E^kBinfB,ωkB,A,E^kBinfB,ωkB. Such a process provides an evidence for possible disputation in future.(4)
A downloads m2=EPKAY1,Y2,Y3,Y4 from the bulletin board PUB. PA derives A=Y2, E^kBinfB=Y3, and ω(kB)=Y4 by decrypting m2. If DPKBY1=Y2,Y3,Y4 does not hold, then PA halts. Otherwise, PA sends m3 to PUB and PB simultaneously, in which m3=ωkB,EPKBESKAB,kA,B,kA.(5)
After receivingm3=Y1,EPKBY2,Y3,Y4, if DPKAY2=Y3,Y4 does not holds, PB sends m3 and kA to PUB. Then, PUB checks the validation of received information from PB. If the information is valid, PUB marks infB invalid and rates a negative feedback for PA according to the QoS evaluation mechanism proposed in Section 3.2. Additionally, the feedback information about PA from other participants is also rated in a similar way.Figure 3
The concrete rational exchange protocol.According to the principle of long-term utility maximization for rational participants, rational participants will not deceive others in a game. We analyze possible deceiving behaviors in the following.Step  (2 ). The possible deceiving is that PA sends a fake infA. In such a case, in Step (5), PB can verify the truth of infA and figure out the deceiving. Indeed, PA can not deny such a deceiving. Meanwhile, ω(kB) is still secretive and PA still does not get infB. At the moment, PB reports the deceiving of PA to PUB and posts a negative feedback for PA. PUB invalidates information infA and keeps a record. Other participants will deny the validation of infA. In this way, PA does not get infB and indeed gets a serious negative feedback. In a long-term game, PA will not send a fake infA ever.Step  (3 ). The possible deceiving, in this process, is that PB sends a fake kB. Due to the characteristics of ω(kB), over time t0, PA can not derive infB using kB. Other participants will also observe that PB is deceiving and will not exchange anything else with PB. In a long-term game, PB’s utility decreases dramatically, and hence he will not send a fake infB ever.Step (4 ). PA deceives PB by not sending m3 even over time t or sending a fake kA. PB can post a negative feedback for PA and gain the supports from other participants. In such a case, PA’s utility is UA=-cATA+HA∑j=1nwAj+ln⁡ZATA, in which wAA=0. Obviously, the loss of utility for PA is great. Hence, PA will not deceive in this process.


### 4.2. Theoretical Analysis

The correctness, security, fairness, and robustness of the proposed rational exchange protocol are analyzed, respectively, in this section.Correctness. According to the concrete rational exchange protocol, the sender PA finally receives infB and the corresponding rating wAB. In one hand, the possible deceiving is that PB send a fake session key k^B to PUB in Step(3). In such a case, after a period t0, all participants will observe the deceiving since ωkB will be decrypted due to the inherent property of weakly secret bit commitment function. For long-term utility, PB will also never do deceiving. On the other hand, due to the high relation between wAB and ZB, participant PB will rate wAB to acquire more positive feedbacks.In the whole protocol, all participants are constrained by ratings and utility. In an exchange, specifically,Zi is highly correlated to participant Pi’s reputation and HX∣Y is prerequisite for participant to exchange information. For long-term utility, all participants are of high willingness to positively and honestly participate in an exchange. Hence, both Zi and HX∣Y can prompt all participants to positively participate the protocol.Hence, the protocol is correct.Security. On one hand, security of the presented rational exchange protocol relies on the security of adopted asymmetric and symmetric encryption algorithms, which are assumed to be secure. Specifically, in Step(2), m1 is in the encrypted form, whose security relies on the security of adopted encryption algorithms. It means that infA will not be revealed until the adopted encryption algorithms are breaking. In fact, there is no adversary that can break such algorithms. Hence, information in Step(2) is secure. Similarly, information in Step(3) and (4) is secure too.Also, on the other hand, security relies on the interactive process during the whole protocol. In the following, the presented rational exchange protocol is proved to be secure under BAN logic [16]. For facile analysis, the presented rational exchange is formalized as follows. Note that Step1 and 5 are not interactive and hence can be ignored in the analysis of security. However, it does not put any negative effect on security of the presented rational exchange protocol.( 2 )   A → B: infAkASKAPKB.( 3 )   B → A: infBkB,ωkBSKBPKA.( 4 )   A → B: ωkB,kASKAPKB.The following assumptions are obvious and reasonable in the rational exchange protocol.(2)
A
∣
≡
⟼
S
K
B
B
A
∣
≡
⟼
S
K
A
A
A
∣
≡
⟼
P
K
B
B
A
∣
≡
⟼
P
K
A
A
A
∣
≡
⟼
P
K
B
A
A
∣
≡
⟼
P
K
A
B
A
∣
≡
⟼
k
A
A
A
∣
≡
B
⟾
i
n
f
B
k
B
A
∣
≡
#
i
n
f
B
k
B
B
∣
≡
⟼
S
K
B
B
B
∣
≡
⟼
S
K
A
A
B
∣
≡
⟼
P
K
B
B
B
∣
≡
⟼
P
K
A
A
B
∣
≡
⟼
P
K
B
A
B
∣
≡
⟼
P
K
A
B
B
∣
≡
⟼
k
B
B
B
∣
≡
A
⟾
i
n
f
A
k
A
B
∣
≡
#
ω
k
B
B
∣
≡
#
i
n
f
A
k
A
.Theorem 4 (security).
Under specific assumptions listed above, the presented rational exchange protocol is secure under BAN logic. Specifically, there are four potential objectives: ①A∣≡infBkB; ② B∣≡infAkA; ③ A∣≡ωkB; and ④B⊲kA.
If the protocol is secure under BAN logic, when the protocol is completely finished, all objectives are concluded. Additionally, afterStep(2), objective ② is concluded. Furthermore, after Step(3), objectives ① and ③ are additively concluded.Proof of Theorem4.
ForStep2,(3)
B
⊲
i
n
f
A
k
A
S
K
A
P
K
B
,
B
∣
≡
⟼
S
K
B
B
B
⊲
i
n
f
A
k
A
S
K
A
B
⊲
i
n
f
A
k
A
S
K
A
,
B
∣
≡
⟼
P
K
A
B
B
⊲
i
n
f
A
k
A
B
⊲
i
n
f
A
k
A
,
B
∣
≡
⟼
k
A
A
B
∣
≡
A
∣
~
i
n
f
A
k
A
B
∣
≡
A
∣
~
i
n
f
A
k
A
,
B
∣
≡
#
i
n
f
A
k
A
B
∣
≡
A
∣
≡
i
n
f
A
k
A
B
∣
≡
A
∣
≡
i
n
f
A
k
A
,
B
∣
≡
A
⟾
i
n
f
A
k
A
B
∣
≡
i
n
f
A
k
AFor Step3,(4)
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
P
K
A
,
A
∣
≡
⟼
S
K
A
A
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
,
A
∣
≡
⟼
P
K
B
A
A
⊲
i
n
f
B
k
B
,
ω
k
B
A
⊲
i
n
f
B
k
B
,
ω
k
B
,
A
∣
≡
⟼
k
B
B
A
∣
≡
B
∣
~
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
#
i
n
f
B
k
B
A
∣
≡
#
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
~
i
n
f
B
k
B
,
ω
k
B
,
A
≡
#
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
≡
i
n
f
B
k
B
,
ω
k
B
,
A
∣
≡
B
⟾
i
n
f
B
k
B
A
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
i
n
f
B
k
B
,
A
∣
≡
ω
k
BFor Step4,(5)
B
⊲
ω
k
B
,
k
A
S
K
A
P
K
B
,
B
∣
≡
⟼
S
K
B
B
B
⊲
ω
k
B
,
k
A
S
K
A
B
⊲
ω
k
B
,
k
A
S
K
A
,
B
∣
≡
⟼
P
K
A
B
B
⊲
ω
k
B
,
k
A
B
⊲
ω
k
B
,
k
A
B
⊲
ω
k
B
,
B
⊲
k
AFairness. When the protocol is finished, participant’s utility consists of two parts. The first part comes from the exchanged information. Let U+ and U- be positive and negative utility, respectively. There is an assumption, in the protocol, that both infA and infB are equal-value. It means that both U+infB=U+infA and U-infA=U-infB hold. Hence, after exchanging information, PA’s total utility is U+infB+U-infA=0 and PB’s total utility is U+infA+U-infB=0.The remainder part is the utility derived from the contribution value. Here, participantPi’s utility is Ui=-ciTi+Hi∑j=1nwij+ZiTi. In this protocol, wAB is PB’s credit on PA’s QoS. In a single interaction between PA and PB, for participant PA, the larger wAB is, the larger UA is. Hence, PA will positively promote QoS. Certainly, the larger ZA is, the larger UA is. Here, ZA is the reference level for other participants that interacts with PA in future. Obviously, payments are proportional to utility for all participants. Hence, the presented rational exchange protocol is rationally fair. The quantitative analysis of fairness is elaborated in Section 5.In a word, in the proposed rational exchange protocol, participants positively participate in executing the protocol. In such a way, all participants can obtain maximum expected utility. Hence, the protocol satisfies fairness.Robustness. In the presented rational exchange protocol in Section 4.1, only Steps(2), (3), and (4) may suffer destabilization or interruption.(i)
In Step(2), participant PA can abort the protocol by sending nothing. In such a case, PB receives nothing and will not be executing the following steps. So, the utility for PA and PB is 0. The fairness is satisfied.(ii)
In Step(3), after receiving m1 sent by PA, PB can interrupt the protocol by not sending m2. Now, PB can not derive infA since the unawareness of kA. Hence, PB still knows nothing about infA and the protocol is still fair.(iii)
In Step(4), PA can interrupt the protocol by not sending m3 after receiving m2 sent by PB. In such a case, PB can make an argument on this exchange, and PUB will mark infB invalid and rate a negative feedback for PA according to the QoS evaluation mechanism proposed in Section 3.2. The negative feedback lowers ZA and is a severe punishment for PA. Simultaneously, PB will also rate a low wAB. Hence, PA’s utility UA=-cATA+HA(∑j=1nwAj+ln⁡ZA)TA is inevitable lower than that before the exchange. Obviously, for long-term utility, PA will never destabilize the protocol to maximize his own utility. Hence, the protocol is still fair.In Steps(1) and (5), there is, obviously, no potential destabilization or interruption. Hence, in a word, the presented protocol is fair when destabilization or interruption occurs.


### 4.3. Theoretical Comparisons

Rational exchange protocol is a fresh and crucial branch in cryptographic research field. The greatest difference between our protocol and other related works is that related works have been investigated under complete (symmetric) information, while our protocol is very under asymmetric information. Theoretical comparisons are legibly declared in Table2.Table 2
Theoretical comparisons between rational exchange protocols.
Scheme Information type With entropy Quantification of utility Rational fairness Syverson’s [9] Complete ✘ ✘ ✘ Buttyán’s [10] Complete ✘ ✘ ✘ Alcaide’s [11] Imperfect1 ✘ ✘ ✔ Alcaide’s [12] Complete ✘ ✘ ✔ Ours Asymmetric ✔ ✔ ✔ I m p e r f e c t   1 information is not suitable for realistic application scenarios.In rational exchange protocol, complete information is an ideal assumption which violates the requirements in realistic environment. Rational exchange protocol under imperfect information is first investigated in Alcaide’s protocol [11]. The complete but imperfect information in [11] is, however, not suitable for the scenarios in Section 1. In this paper, rational exchange protocol under asymmetric information is carefully designed with clear definition and much more compatible for practice.It is striking that the utility in existing rational exchange protocol can not be quantized so far, since the absence of entropy. Information theory is introduced in this paper to quantize all participants’ utilities. Such a way is the first attempt to clearly evaluate participant’s utility. Participant can further make accurate decisions by observing participants’ utilities. Obviously, such a characteristic is more compatible and operable for real applications.Rational fairness is an important characteristic for rational exchange protocol and has been attracting vastly attention in cryptographic community. Through analysis under a dynamic model with entropy in Section4.2, rational fairness is guaranteed.


## 4.1. Construction

Assume that there is no trusted third party in the proposed rational exchange protocol with multiple participants. That means each participant makes decision by maximizing his utility. Such a participant is rational and enjoys equal status, without considering compromising between participants.In the concrete protocol, any two participants directly exchange information with each other. Assume that a senderPA and a receiver PB exchange infA and infB in the rational exchange protocol. Under asymmetric information, PA is the advantageous participant and PB is the disadvantage one. Additionally, infA is channel-sensitive and takes a long time t to be transmitted, but the time to transmit infB is short and negligible. There is also a bulletin board in the protocol to only manage all participants’ account information and nothing else.Setup. A weakly secret bit commitment function ω(x) is adopted, in which x can only be derived over time t0>t since it is encrypted. An asymmetric encryption algorithm E and a symmetric encryption algorithm E^ are adopted. The corresponding decryption algorithms are D and D^. According to the adopted asymmetric encryption algorithm E, PKA,SKA is generated for participant PA as the public-private key pair, and PKB,SKB is generated for participant PB too. Additionally, the bulletin board PUB is initialized by maintaining QoS evaluation mechanism with an empty list.Rational Exchange. PA and PB rationally exchange information infA and infB by executing the following steps. The interactive processes for two participants are illustrated in Figure 3.(1)
The disadvantageous participantPB calculates the conditional entropy HX∣Y according to the advantageous participant PA’s number of positive feedbacks ZA. He makes decision by checking HX∣Y. If he wishes to exchange information, then he continues to do the following steps. Otherwise, the protocol halts.(2)
PA randomly chooses a session key kA for E^ and sends m1 to PB, in which m1=EPKBESKAB,E^kAinfA,B,E^kAinfA.(3)
After receivingm1=EPKBY1,Y2,Y3, PB decrypt m1 and derive B=Y2 and E^kAinfA=Y3 by checking DPKAY1=Y2,Y3. If DPKAY1=Y2,Y3 does not hold, then PB halts. Otherwise, PB randomly chooses a session key kB for E^ and sends m2 to PUB, in which m2=EPKAESKBA,E^kBinfB,ωkB,A,E^kBinfB,ωkB. Such a process provides an evidence for possible disputation in future.(4)
A downloads m2=EPKAY1,Y2,Y3,Y4 from the bulletin board PUB. PA derives A=Y2, E^kBinfB=Y3, and ω(kB)=Y4 by decrypting m2. If DPKBY1=Y2,Y3,Y4 does not hold, then PA halts. Otherwise, PA sends m3 to PUB and PB simultaneously, in which m3=ωkB,EPKBESKAB,kA,B,kA.(5)
After receivingm3=Y1,EPKBY2,Y3,Y4, if DPKAY2=Y3,Y4 does not holds, PB sends m3 and kA to PUB. Then, PUB checks the validation of received information from PB. If the information is valid, PUB marks infB invalid and rates a negative feedback for PA according to the QoS evaluation mechanism proposed in Section 3.2. Additionally, the feedback information about PA from other participants is also rated in a similar way.Figure 3
The concrete rational exchange protocol.According to the principle of long-term utility maximization for rational participants, rational participants will not deceive others in a game. We analyze possible deceiving behaviors in the following.Step  (2 ). The possible deceiving is that PA sends a fake infA. In such a case, in Step (5), PB can verify the truth of infA and figure out the deceiving. Indeed, PA can not deny such a deceiving. Meanwhile, ω(kB) is still secretive and PA still does not get infB. At the moment, PB reports the deceiving of PA to PUB and posts a negative feedback for PA. PUB invalidates information infA and keeps a record. Other participants will deny the validation of infA. In this way, PA does not get infB and indeed gets a serious negative feedback. In a long-term game, PA will not send a fake infA ever.Step  (3 ). The possible deceiving, in this process, is that PB sends a fake kB. Due to the characteristics of ω(kB), over time t0, PA can not derive infB using kB. Other participants will also observe that PB is deceiving and will not exchange anything else with PB. In a long-term game, PB’s utility decreases dramatically, and hence he will not send a fake infB ever.Step (4 ). PA deceives PB by not sending m3 even over time t or sending a fake kA. PB can post a negative feedback for PA and gain the supports from other participants. In such a case, PA’s utility is UA=-cATA+HA∑j=1nwAj+ln⁡ZATA, in which wAA=0. Obviously, the loss of utility for PA is great. Hence, PA will not deceive in this process.


## 4.2. Theoretical Analysis

The correctness, security, fairness, and robustness of the proposed rational exchange protocol are analyzed, respectively, in this section.Correctness. According to the concrete rational exchange protocol, the sender PA finally receives infB and the corresponding rating wAB. In one hand, the possible deceiving is that PB send a fake session key k^B to PUB in Step(3). In such a case, after a period t0, all participants will observe the deceiving since ωkB will be decrypted due to the inherent property of weakly secret bit commitment function. For long-term utility, PB will also never do deceiving. On the other hand, due to the high relation between wAB and ZB, participant PB will rate wAB to acquire more positive feedbacks.In the whole protocol, all participants are constrained by ratings and utility. In an exchange, specifically,Zi is highly correlated to participant Pi’s reputation and HX∣Y is prerequisite for participant to exchange information. For long-term utility, all participants are of high willingness to positively and honestly participate in an exchange. Hence, both Zi and HX∣Y can prompt all participants to positively participate the protocol.Hence, the protocol is correct.Security. On one hand, security of the presented rational exchange protocol relies on the security of adopted asymmetric and symmetric encryption algorithms, which are assumed to be secure. Specifically, in Step(2), m1 is in the encrypted form, whose security relies on the security of adopted encryption algorithms. It means that infA will not be revealed until the adopted encryption algorithms are breaking. In fact, there is no adversary that can break such algorithms. Hence, information in Step(2) is secure. Similarly, information in Step(3) and (4) is secure too.Also, on the other hand, security relies on the interactive process during the whole protocol. In the following, the presented rational exchange protocol is proved to be secure under BAN logic [16]. For facile analysis, the presented rational exchange is formalized as follows. Note that Step1 and 5 are not interactive and hence can be ignored in the analysis of security. However, it does not put any negative effect on security of the presented rational exchange protocol.( 2 )   A → B: infAkASKAPKB.( 3 )   B → A: infBkB,ωkBSKBPKA.( 4 )   A → B: ωkB,kASKAPKB.The following assumptions are obvious and reasonable in the rational exchange protocol.(2)
A
∣
≡
⟼
S
K
B
B
A
∣
≡
⟼
S
K
A
A
A
∣
≡
⟼
P
K
B
B
A
∣
≡
⟼
P
K
A
A
A
∣
≡
⟼
P
K
B
A
A
∣
≡
⟼
P
K
A
B
A
∣
≡
⟼
k
A
A
A
∣
≡
B
⟾
i
n
f
B
k
B
A
∣
≡
#
i
n
f
B
k
B
B
∣
≡
⟼
S
K
B
B
B
∣
≡
⟼
S
K
A
A
B
∣
≡
⟼
P
K
B
B
B
∣
≡
⟼
P
K
A
A
B
∣
≡
⟼
P
K
B
A
B
∣
≡
⟼
P
K
A
B
B
∣
≡
⟼
k
B
B
B
∣
≡
A
⟾
i
n
f
A
k
A
B
∣
≡
#
ω
k
B
B
∣
≡
#
i
n
f
A
k
A
.Theorem 4 (security).
Under specific assumptions listed above, the presented rational exchange protocol is secure under BAN logic. Specifically, there are four potential objectives: ①A∣≡infBkB; ② B∣≡infAkA; ③ A∣≡ωkB; and ④B⊲kA.
If the protocol is secure under BAN logic, when the protocol is completely finished, all objectives are concluded. Additionally, afterStep(2), objective ② is concluded. Furthermore, after Step(3), objectives ① and ③ are additively concluded.Proof of Theorem4.
ForStep2,(3)
B
⊲
i
n
f
A
k
A
S
K
A
P
K
B
,
B
∣
≡
⟼
S
K
B
B
B
⊲
i
n
f
A
k
A
S
K
A
B
⊲
i
n
f
A
k
A
S
K
A
,
B
∣
≡
⟼
P
K
A
B
B
⊲
i
n
f
A
k
A
B
⊲
i
n
f
A
k
A
,
B
∣
≡
⟼
k
A
A
B
∣
≡
A
∣
~
i
n
f
A
k
A
B
∣
≡
A
∣
~
i
n
f
A
k
A
,
B
∣
≡
#
i
n
f
A
k
A
B
∣
≡
A
∣
≡
i
n
f
A
k
A
B
∣
≡
A
∣
≡
i
n
f
A
k
A
,
B
∣
≡
A
⟾
i
n
f
A
k
A
B
∣
≡
i
n
f
A
k
AFor Step3,(4)
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
P
K
A
,
A
∣
≡
⟼
S
K
A
A
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
A
⊲
i
n
f
B
k
B
,
ω
k
B
S
K
B
,
A
∣
≡
⟼
P
K
B
A
A
⊲
i
n
f
B
k
B
,
ω
k
B
A
⊲
i
n
f
B
k
B
,
ω
k
B
,
A
∣
≡
⟼
k
B
B
A
∣
≡
B
∣
~
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
#
i
n
f
B
k
B
A
∣
≡
#
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
~
i
n
f
B
k
B
,
ω
k
B
,
A
≡
#
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
B
∣
≡
i
n
f
B
k
B
,
ω
k
B
,
A
∣
≡
B
⟾
i
n
f
B
k
B
A
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
i
n
f
B
k
B
,
ω
k
B
A
∣
≡
i
n
f
B
k
B
,
A
∣
≡
ω
k
BFor Step4,(5)
B
⊲
ω
k
B
,
k
A
S
K
A
P
K
B
,
B
∣
≡
⟼
S
K
B
B
B
⊲
ω
k
B
,
k
A
S
K
A
B
⊲
ω
k
B
,
k
A
S
K
A
,
B
∣
≡
⟼
P
K
A
B
B
⊲
ω
k
B
,
k
A
B
⊲
ω
k
B
,
k
A
B
⊲
ω
k
B
,
B
⊲
k
AFairness. When the protocol is finished, participant’s utility consists of two parts. The first part comes from the exchanged information. Let U+ and U- be positive and negative utility, respectively. There is an assumption, in the protocol, that both infA and infB are equal-value. It means that both U+infB=U+infA and U-infA=U-infB hold. Hence, after exchanging information, PA’s total utility is U+infB+U-infA=0 and PB’s total utility is U+infA+U-infB=0.The remainder part is the utility derived from the contribution value. Here, participantPi’s utility is Ui=-ciTi+Hi∑j=1nwij+ZiTi. In this protocol, wAB is PB’s credit on PA’s QoS. In a single interaction between PA and PB, for participant PA, the larger wAB is, the larger UA is. Hence, PA will positively promote QoS. Certainly, the larger ZA is, the larger UA is. Here, ZA is the reference level for other participants that interacts with PA in future. Obviously, payments are proportional to utility for all participants. Hence, the presented rational exchange protocol is rationally fair. The quantitative analysis of fairness is elaborated in Section 5.In a word, in the proposed rational exchange protocol, participants positively participate in executing the protocol. In such a way, all participants can obtain maximum expected utility. Hence, the protocol satisfies fairness.Robustness. In the presented rational exchange protocol in Section 4.1, only Steps(2), (3), and (4) may suffer destabilization or interruption.(i)
In Step(2), participant PA can abort the protocol by sending nothing. In such a case, PB receives nothing and will not be executing the following steps. So, the utility for PA and PB is 0. The fairness is satisfied.(ii)
In Step(3), after receiving m1 sent by PA, PB can interrupt the protocol by not sending m2. Now, PB can not derive infA since the unawareness of kA. Hence, PB still knows nothing about infA and the protocol is still fair.(iii)
In Step(4), PA can interrupt the protocol by not sending m3 after receiving m2 sent by PB. In such a case, PB can make an argument on this exchange, and PUB will mark infB invalid and rate a negative feedback for PA according to the QoS evaluation mechanism proposed in Section 3.2. The negative feedback lowers ZA and is a severe punishment for PA. Simultaneously, PB will also rate a low wAB. Hence, PA’s utility UA=-cATA+HA(∑j=1nwAj+ln⁡ZA)TA is inevitable lower than that before the exchange. Obviously, for long-term utility, PA will never destabilize the protocol to maximize his own utility. Hence, the protocol is still fair.In Steps(1) and (5), there is, obviously, no potential destabilization or interruption. Hence, in a word, the presented protocol is fair when destabilization or interruption occurs.


## 4.3. Theoretical Comparisons

Rational exchange protocol is a fresh and crucial branch in cryptographic research field. The greatest difference between our protocol and other related works is that related works have been investigated under complete (symmetric) information, while our protocol is very under asymmetric information. Theoretical comparisons are legibly declared in Table2.Table 2
Theoretical comparisons between rational exchange protocols.
Scheme Information type With entropy Quantification of utility Rational fairness Syverson’s [9] Complete ✘ ✘ ✘ Buttyán’s [10] Complete ✘ ✘ ✘ Alcaide’s [11] Imperfect1 ✘ ✘ ✔ Alcaide’s [12] Complete ✘ ✘ ✔ Ours Asymmetric ✔ ✔ ✔ I m p e r f e c t   1 information is not suitable for realistic application scenarios.In rational exchange protocol, complete information is an ideal assumption which violates the requirements in realistic environment. Rational exchange protocol under imperfect information is first investigated in Alcaide’s protocol [11]. The complete but imperfect information in [11] is, however, not suitable for the scenarios in Section 1. In this paper, rational exchange protocol under asymmetric information is carefully designed with clear definition and much more compatible for practice.It is striking that the utility in existing rational exchange protocol can not be quantized so far, since the absence of entropy. Information theory is introduced in this paper to quantize all participants’ utilities. Such a way is the first attempt to clearly evaluate participant’s utility. Participant can further make accurate decisions by observing participants’ utilities. Obviously, such a characteristic is more compatible and operable for real applications.Rational fairness is an important characteristic for rational exchange protocol and has been attracting vastly attention in cryptographic community. Through analysis under a dynamic model with entropy in Section4.2, rational fairness is guaranteed.


## 5. Simulation of Utility Function with Entropy

The utility function with entropy is kernel to guarantee the fairness of rational exchange protocol. In this section, through simulation, the proposed utility function with entropy is investigated in detail.


### 5.1. Simulation Environment

In the following simulation, the number of participants is assumed to be 10. When the system achieves stabilization after several rounds of information exchange, the current transfer matrixP of participants’ types for each participant is assumed same and given as follows.(6)P=0.80.2000.20.60.2000.30.50.2000.30.7By resolving a system of linear equationsD=D•P, the steady-state vector is D=0.32,0.32,0.22,0.14. The vector containing all membership functions is given as g=1.0,0.75,0.5,0, in which great gi (i.e., closer to 1) indicates high-level accuracy of Di. Then, the probability of participant Pj serving Pi is Rij=D•gT=0.67. To evaluate participant’s credits on the process of information exchange, all the vectors wijPj∈P\Pi of credits for participant Pi are generated randomly such that wij∈(0,1) and wii=0. In a similar way, the vector Zi of positive feedbacks is calculated through the above probabilities for all participants in the protocol.The contribution value for participantPi is Ti=α∑j=1nRij, in which α∈(0,1). Here, let α=0.1, and Ti=0.1×(10-1)×0.67=0.603 and Hi=-∑j=1nRijln⁡Rij=2.41 are derived. Given a unitary cost, the utility for each participant can be derived. All the values calculated in the above equations are listed below.The matrixW of credits is generated in the following. (7)0.000.430.850.420.780.230.550.930.640.210.960.000.620.050.390.350.300.780.380.300.000.180.000.900.240.820.740.490.810.470.77_0.26_0.51_0.00_0.40_0.02_0.19_0.44_0.53_0.23_0.790.980.830.760.000.990.830.730.780.820.870.140.080.490.130.000.180.310.940.190.080.870.240.340.940.650.000.510.880.230.400.580.120.900.960.730.630.000.550.170.260.550.180.370.580.650.780.820.000.230.800.140.240.110.060.450.080.790.590.00Assume that participant will respond to a positive feedback when the credit is greater than0.60. Obliviously, the vector Z of positive feedbacks is simulated in the following. (8)Z=4,3,4,1_,9,2,4,4,3,2.The utilityU for all participants is calculated in the following. (9)9.28,7.54,8.71,4.81_,14.05,5.79,8.84,9.28,7.96,5.68.By observing the utilities for all participants, participantP5’s utility is maximal and participant P4’s utility is minimal. It is consistent with the generated credits that P5’s credits are significantly greater than other participant’s and P4’s credits are significantly smaller than other participant’s. Hence, the presented utility function with entropy appropriately reflects the realistic utilities for all participants.


### 5.2. Effect of Parameters

The utility function with entropyUi=-ciTi+Hi∑j=1nwij+ln⁡ZiTi is thoroughly investigated by observing P4 and P5’s utilities by varying c and α, respectively.Effect of c. We vary c∈1,10,20,30,40 to exhibit the effectiveness on the presented utility function. The simulation is illustrated in Figures 4 and 5. Specifically, in Figure 4, Figure 4(b) illustrates the particulars of utility U4’s beginning tendency for participant P4. In a similar way, Figure 5(b) illustrates the details of P5’s utility that is depicted in dotted rectangle in Figure 5(a). It is striking that participant’s utility decreases at the beginning, increases in the middle stage, and decreases again at the end. In general, participant Pi’s utility Ui is acquired in exchange with other participants. The trends of utility function confirm real-world scenarios and are elaborately described in the following content.Figure 4
The effectiveness on utility function while varyingc4 with α=0.1 for participant P4.
(a)
Overall (b)
Beginning partFigure 5
The effectiveness on utility function while varyingc5 with α=0.1 for participant P5.
(a)
Overall (b)
Beginning partAt the very beginning, participantPj is considered to be outside indeed. Participant Pi’s utility coming from Pj is assumed to be 0. During the first increasing of participant Pj’s service probability, Rij is extremely small and less than a threshold. Although the probability increases, the incrementation does not put any positive effect on Ui. Pi still, however, pays out due to the participation in the exchange. The utility coming from such an incrementation does not counteract the payment. Hence, Ui decreases in such a stage.In the next stage, with the incrementation ofPj’s service probability, the utility coming from such an incrementation goes beyond the payment. Hence, Ui increases along with the increasing of probability. Such a situation is compatible for practice and provides a guarantee of fairness for all participants.In the ending stage, ifPj’s service probability is close to 1, other participants will free ride potentially. Due to that, participant Pi’s credits and positive feedbacks will decrease. Following that, the utility Ui inevitably decreases in future. That is still fair for all participants.Effect of α . We vary α∈0.1,0.3,0.5,0.8,1.0 to exhibit the effectiveness on utility function. The simulation is illustrated in Figures 6 and 7. It is striking that the utility’s tendency is consistent with that while varying c. Additionally, with greater α, the utility’s discrimination is more prominent. In practice, α is determined according to consumer’s realistic requirements.Figure 6
The effectiveness on utility function while varyingα with c4=10 and c4=20 for participant P4.
(a)
c 4 = 10 (b)
c 4 = 20Figure 7
The effectiveness on utility function while varyingα with c5=10 and c5=20 for participant P5.
(a)
c 5 = 10 (b)
c 5 = 20


### 5.3. Performance for Participants

In this section, performance for all participants is elaborated in detail by varying contribution weightα and unitary cost c, respectively.Varying α. In the evaluation of performance, contribution weight α is varied in 0.0,1.0 in Figure 8(a). Obviously, with the increment of α, the discrimination between utilities for all participants is increasing significantly. The significant discrimination is important for practice, due to the fact that participant can facilely make decision without any doubt.Figure 8
The performance of utility function with entropy for all participants. In Figure8(a), α is varied with c=10 and in Figure 8(b)c is varied with α=0.1.
(a)
Varyingα (b)
VaryingcWallrabenstein 2014 Varying c. In the evaluation of performance, contribution weight c is varied in 0,40 in Figure 8(b). Obviously, with the increment of α, the discrimination between utilities for all participants remains the same, due to the fact that a theoretical assumption that the probability of participant Pj serving Pi is Rij is the same for all participants. Although the probabilities are completely different in practice, the discrimination remains the same since that the change of c only lowers the coefficient of Ti and does not change the monotonicity of utility in (1).


## 5.1. Simulation Environment

In the following simulation, the number of participants is assumed to be 10. When the system achieves stabilization after several rounds of information exchange, the current transfer matrixP of participants’ types for each participant is assumed same and given as follows.(6)P=0.80.2000.20.60.2000.30.50.2000.30.7By resolving a system of linear equationsD=D•P, the steady-state vector is D=0.32,0.32,0.22,0.14. The vector containing all membership functions is given as g=1.0,0.75,0.5,0, in which great gi (i.e., closer to 1) indicates high-level accuracy of Di. Then, the probability of participant Pj serving Pi is Rij=D•gT=0.67. To evaluate participant’s credits on the process of information exchange, all the vectors wijPj∈P\Pi of credits for participant Pi are generated randomly such that wij∈(0,1) and wii=0. In a similar way, the vector Zi of positive feedbacks is calculated through the above probabilities for all participants in the protocol.The contribution value for participantPi is Ti=α∑j=1nRij, in which α∈(0,1). Here, let α=0.1, and Ti=0.1×(10-1)×0.67=0.603 and Hi=-∑j=1nRijln⁡Rij=2.41 are derived. Given a unitary cost, the utility for each participant can be derived. All the values calculated in the above equations are listed below.The matrixW of credits is generated in the following. (7)0.000.430.850.420.780.230.550.930.640.210.960.000.620.050.390.350.300.780.380.300.000.180.000.900.240.820.740.490.810.470.77_0.26_0.51_0.00_0.40_0.02_0.19_0.44_0.53_0.23_0.790.980.830.760.000.990.830.730.780.820.870.140.080.490.130.000.180.310.940.190.080.870.240.340.940.650.000.510.880.230.400.580.120.900.960.730.630.000.550.170.260.550.180.370.580.650.780.820.000.230.800.140.240.110.060.450.080.790.590.00Assume that participant will respond to a positive feedback when the credit is greater than0.60. Obliviously, the vector Z of positive feedbacks is simulated in the following. (8)Z=4,3,4,1_,9,2,4,4,3,2.The utilityU for all participants is calculated in the following. (9)9.28,7.54,8.71,4.81_,14.05,5.79,8.84,9.28,7.96,5.68.By observing the utilities for all participants, participantP5’s utility is maximal and participant P4’s utility is minimal. It is consistent with the generated credits that P5’s credits are significantly greater than other participant’s and P4’s credits are significantly smaller than other participant’s. Hence, the presented utility function with entropy appropriately reflects the realistic utilities for all participants.


## 5.2. Effect of Parameters

The utility function with entropyUi=-ciTi+Hi∑j=1nwij+ln⁡ZiTi is thoroughly investigated by observing P4 and P5’s utilities by varying c and α, respectively.Effect of c. We vary c∈1,10,20,30,40 to exhibit the effectiveness on the presented utility function. The simulation is illustrated in Figures 4 and 5. Specifically, in Figure 4, Figure 4(b) illustrates the particulars of utility U4’s beginning tendency for participant P4. In a similar way, Figure 5(b) illustrates the details of P5’s utility that is depicted in dotted rectangle in Figure 5(a). It is striking that participant’s utility decreases at the beginning, increases in the middle stage, and decreases again at the end. In general, participant Pi’s utility Ui is acquired in exchange with other participants. The trends of utility function confirm real-world scenarios and are elaborately described in the following content.Figure 4
The effectiveness on utility function while varyingc4 with α=0.1 for participant P4.
(a)
Overall (b)
Beginning partFigure 5
The effectiveness on utility function while varyingc5 with α=0.1 for participant P5.
(a)
Overall (b)
Beginning partAt the very beginning, participantPj is considered to be outside indeed. Participant Pi’s utility coming from Pj is assumed to be 0. During the first increasing of participant Pj’s service probability, Rij is extremely small and less than a threshold. Although the probability increases, the incrementation does not put any positive effect on Ui. Pi still, however, pays out due to the participation in the exchange. The utility coming from such an incrementation does not counteract the payment. Hence, Ui decreases in such a stage.In the next stage, with the incrementation ofPj’s service probability, the utility coming from such an incrementation goes beyond the payment. Hence, Ui increases along with the increasing of probability. Such a situation is compatible for practice and provides a guarantee of fairness for all participants.In the ending stage, ifPj’s service probability is close to 1, other participants will free ride potentially. Due to that, participant Pi’s credits and positive feedbacks will decrease. Following that, the utility Ui inevitably decreases in future. That is still fair for all participants.Effect of α . We vary α∈0.1,0.3,0.5,0.8,1.0 to exhibit the effectiveness on utility function. The simulation is illustrated in Figures 6 and 7. It is striking that the utility’s tendency is consistent with that while varying c. Additionally, with greater α, the utility’s discrimination is more prominent. In practice, α is determined according to consumer’s realistic requirements.Figure 6
The effectiveness on utility function while varyingα with c4=10 and c4=20 for participant P4.
(a)
c 4 = 10 (b)
c 4 = 20Figure 7
The effectiveness on utility function while varyingα with c5=10 and c5=20 for participant P5.
(a)
c 5 = 10 (b)
c 5 = 20


## 5.3. Performance for Participants

In this section, performance for all participants is elaborated in detail by varying contribution weightα and unitary cost c, respectively.Varying α. In the evaluation of performance, contribution weight α is varied in 0.0,1.0 in Figure 8(a). Obviously, with the increment of α, the discrimination between utilities for all participants is increasing significantly. The significant discrimination is important for practice, due to the fact that participant can facilely make decision without any doubt.Figure 8
The performance of utility function with entropy for all participants. In Figure8(a), α is varied with c=10 and in Figure 8(b)c is varied with α=0.1.
(a)
Varyingα (b)
VaryingcWallrabenstein 2014 Varying c. In the evaluation of performance, contribution weight c is varied in 0,40 in Figure 8(b). Obviously, with the increment of α, the discrimination between utilities for all participants remains the same, due to the fact that a theoretical assumption that the probability of participant Pj serving Pi is Rij is the same for all participants. Although the probabilities are completely different in practice, the discrimination remains the same since that the change of c only lowers the coefficient of Ti and does not change the monotonicity of utility in (1).


## 6. Related Work

Cryptography and game theory both concentrate on designing protocol, in which participants are with potential conflicts of benefits [17, 18]. By combining both theories, rational secret sharing and rational secure multiparty computation are proposed by Halpern et al. [5] in 2004. In traditional cryptography, participants are assumed to be honest (strictly follow the protocol) or malicious (violate or destroy the protocol), and participants are however rational instead in practice for WSNs. That means all participants are highly willing to maximize their utilities by selecting their strategies during the whole protocol. That brings enormous challenge in designing protocols. Since the proposal of rational cryptography, there exist a number of studies [19, 20], such as rational secret sharing [21] and rational secure multiparty computation [5]. Indeed, rational exchange protocol, which guarantees security and fairness for peers in WSNs, is practical and necessary for realistic environments.In 1998, Asokan [22] proposed an interactive protocol to exchange digital signature in a fair manner. It is the prototype of rational exchange protocol. The first real rational exchange protocol is proposed based on a weakly secret bit commitment function by Syverson [9] in the same year. In 2001, Buttyán et al. [10] analyzed the fairness of Syverson’s protocol based on game theory, and, in 2004, they modeled rational exchange protocol and further analyzed the fairness of Syverson’s protocol [13]. After that, Alcaide et al. modeled rational exchange protocol based on extended game theory and Bayesian game in [11], improved Syverson’s protocol in [23], and designed rational exchange protocol based on nature-inspired synthesis [12, 14]. However, all the above rational exchange protocols are constructed in environments with complete information, which is not perfectly compatible for scenarios mentioned in Section 1.Rational participants possess asymmetric information about each other in real-world scenarios. Rational exchange protocol in such scenarios is not well investigated so far. By further combining information theory, rational exchange protocol is more practical and compatible for WSN. So far, information theory has been introduced into several cryptographic protocols [24, 25]. However, rational exchange protocol under asymmetric information is not thoroughly studied, which is striking in this paper.


## 7. Conclusion

In this paper, we presented a rational exchange protocol under asymmetric information, which is compatible and practical for WSNs. First of all, a dynamic game model with entropy is presented to quantify utilities of participants. In such a game, utilities for all participants can be quantized. Following that, a utility function with entropy is designed based on integrating a Markov-based entropy function and a novel QoS evaluation model. Furthermore, the concrete rational exchange protocol is presented with thorough analysis. Finally, the utility function with entropy is simulated. The simulation demonstrates effectiveness and availability of the presented rational exchange protocol.



---

*Source: 9437936-2018-05-31.xml*