Secure Two-Party Distance Computation Protocols with a Semihonest Third Party and Randomization for Privacy Protection in Wireless Sensor Networks

Abstract

Scenarios in which two nodes who distrust each other in wireless sensor networks (WSNs) would like to know the distance between them are considered. The scenario is designed to protect the private information of WSNs, in this case each node's location, from the other nodes and from a passive attacker. The goal of the present work is to provide two novel and secure two-party distance computation protocols based on a semihonest model, the first with aid of a third party and the second based on randomization technique. Both of these protocols can extend the calculated value into a real number field. The output of the distance computation and the intermediate values in the proposed protocols are also private and not accessible to a third party or any other attackers. When executing these two protocols, security is guaranteed, and the performances of communication and computation of them are found to be satisfactory when compared to those of other similar protocols.

1. Motivation

With the development of the computer and communication technologies, wireless sensor networks have gradually extended into the fabric of human society. Communications between people and things have become a reality so that many researchers have begun to pay attention to wireless sensor networks, where many techniques [1, 2] require secure authentication and secure privacy computation. This is because privacy protection is a significant research point which cannot be ignored in today's wireless sense applications. The privacy of wireless sensor networks’ entity may appear to be either a natural property or a social characteristic depending on the requirements of specific scenarios. The matter of defining privacy in terms of different applications and realizing privacy protection can be explained in detail through the following scenarios regarding secure communications.

Wireless sensor networks can usually be deployed in the enemies’ battle field to monitor military information. Once found, each node has the risk of being captured by enemies so that all nodes do not trust each other. However, these nodes have to cooperate with each other in this unreliable environment in order to complete tasks of data collection. For example, Node A decides to expand its coverage area through enhancing transmitting power in one region to obtain more sensing data. Node A also notices that Node B, possibly the adjacent node of Node A, is also expanding the coverage area of his located region. But the two nodes do not want to collect data in the same area, so they want to know whether there are overlapping areas between their respective regions without disclosing the corresponding location information, in order to avoid the danger of being captured caused by the leakage of location information. If Node A and Node B are able to calculate the distance between their respective regions in the case of keeping geographical location information confidentiality and meanwhile telling each other their respective coverage radiuses, then this problem can be effectively solved: if the distance is too close, it indicates that there is overlap; otherwise there is no overlap.

Location information becomes important and confidential in the above scenarios, though the utilization of the respective positions of two participants is the most common method for calculating Euclidean distance. In this case, secure two-party distance computation without revealing location information becomes a vital problem.

Secure two-party computation, introduced by Yao, allows two parties to jointly compute any function using their inputs in such a way that (1) the output of the computation is correct and public and (2) the inputs are not revealed to both users [3]. Secure calculation of the distance between two parties (or two nodes in WSNs) is a specific case of secure two-party computation, and it provides a solution to the scenario described above. Currently, there exist two ways of computing the distance, and both of them allow the location of each party to be kept secret. The first requires the help of a third party, and the other does not. The primary contribution of this paper is that it puts forward two novel, secure, and efficient protocols that can be used in accordance with the above two methods.

The rest of the paper is organized as follows. The next section reviews related works in the field of secure two-party distance computation. Section 3 presents the preliminaries and assumptions. Section 4 provides two novel and secure two-party distance computation protocols used in WSN, the first involving a semihonest third party and the other involving randomization technique, and their respective correctness proofs. Security analysis and performance comparisons between the proposals and previous work are presented in Sections 5 and 6, respectively. Further discussions about sensitive issues are given in Section 7. Section 8 concludes this paper.

2. Related Work

Secure two-party computation is widely used in network security protocol design to protect important information related to location, identity, and healthcare. Recently, location information during the use of location-based services (LBSs) has raised considerable concerns [12], especially in distance calculation application. Currently, secure two-party distance protocols are generally divided into three categories. The first [4–7] is established using a homomorphic encryption mechanism that serves as the secure basis of privacy protection. The second [8, 13] is established with the assistance of a third party, usually a semihonest third party. The third [14] is established with the randomization technique.

As the first type of protocol, [4] describes and analyzes a scheme for biometric authentication and it uses homomorphic encryption for secure calculation of Hamming Distance without revealing the participants’ secret information. The work [5] puts forward a secure two-party computation protocol of Euclidean distance using Paillier homomorphic encryption [11] and this protocol is implemented for private querying of face images and maintains low communication overhead. The work [6] also proposes a secure multiparty distance computation protocol, which is also designed based on Paillier homomorphic encryption without a third party. The work [7] suggests a secure, privacy-preserving opportunistic computing (SPOC) framework for healthcare emergency based on a secure scalar product protocol that can be used to design a secure two-party distance computation protocol. Pronounced computational complexity is the common weakness of secure two-party computation protocols based on homomorphic encryption mechanisms. This is difficult to use with resource-constrained outdoor wireless link networks.

In the second category protocol, two participants are unable to calculate the distance between them if there is no third party involved. The protocol in [13] involves a quantum private comparison based on the presence of a semihonest third party and it enables two parties to determine whether their information matches without revealing the specifics. The work [8] allows the participant to calculate the distance based on an honest third party for comparison of local data and simultaneously causes private values to be fully grasped by the third party, which is followed by obvious information leakage and security issues that cannot be ignored. Although intervention by a third party may improve the efficiency of computation and communication, this increases network costs. This issue of decreasing the number of secrets learned by a third party is significant here. The distinction between honest and semihonest third parties is illustrated in Section 3.2.

Broad application of homomorphic encryption mechanisms results in less use of other digital disguise techniques, such as randomization methods, which can be used to design secure two-party computation protocols. Randomized disguises obscure the real data by adding random elements to them to facilitate privacy protection. For example, [14] provides a randomization method by performing a linear transformation on the real data or a random permutation replacement of the real data to achieve a secure two-party distance computation protocol. The protocol in [9] also involves randomization method and 1 out of m oblivious transfer protocol [11]. Designing a secure and efficient two-party distance computation protocol based on randomized masquerade is mathematically difficult. Many current protocols, such as one described in a previous study [8], can only be used in integer domains and cannot be expanded into real number domains. This limits their use.

In wireless sensor networks, literatures related to privacy protection of location and distance [15] can be traced back to 2007. Actually only few literatures apply the distance computation protocols based on privacy protection to data security of wireless sensor networks. To the best of our knowledge, [16] is the first paper that uses the secure distance calculation protocol to solve location privacy in WSNs. The work [17] presents an overview of the solutions that provide source location privacy such as anonymity and unobservability, within a WSN, in relation to the assumptions about the adversary's capabilities. A location privacy routing protocol (LPR) is proposed in [18] to achieve path diversity, and, combining with fake packet injection, LPR is able to minimize the traffic direction information that an adversary can retrieve from eavesdropping. However, LPR does not provide the data-level privacy protection. The work [19] found out that Lu et al.'s protocol in [7] still has some secure flaws such as user anonymity and mutual authentication, and it presents an improved mobile-healthcare emergency system based on extended chaotic maps for applications of wireless body sensor networks (BSNs).

3. Preliminaries and Premises

3.1. Definition of Secure Two-Party Computation

There are two participants in WSNs, Node A and Node B. Node A selects a secret input x and Node B selects another one y. They hope to calculate the function $f(x,y)$ and produce final results but they must keep their respective inputs secret. We call this computation process “secure two-party computation.” Here, x (or y) may be the location information of Node A (or Node B), and $f(x,y)$ may be the distance between the two nodes.

3.2. Semihonest Model

Secure two-party computation should guarantee the safety of the information even if one participant behaves deceitfully in the execution of the protocol. The attacker may perform one of two types of attacks: one is active that is called “malicious (or adversarial) model [20]” and another is passive, here called the “semihonest model.” In the malicious model, the attacker manipulates one of the participants into executing the protocol improperly. For example, the attacker may cause a participant to substitute mendacious data for real input in order to interrupt implementation of the protocol. In the semihonest model, the attacker only grasps the entirety of the information of the captive participant, including those intermediate data acquired from the other participant, and the purpose of the attacker is solely to reveal some private information, but the protocol is carried out correctly and all inputs are true. Some researchers refer to the semihonest participant as “honest but curious” [21].

Based on the above, the reliability of a third party can be defined (hereinafter abbreviated “TP”). There exist three cases. In the first case, the TP is honest, and both the participants send their secrets to the TP without worrying that the TP will leak any private information. This case is perfect but impractical. In the second case, the TP is dishonest or malicious, and neither participant believes the TP. This case is dangerous. In the third case, the TP is semihonest. The TP executes the protocol faithfully, and all kinds of intermediary data and computational results are recorded. The TP tries to make this information publicly available. In WSNs, base station or the cluster-header usually acts as the role of TP.

In the present paper, it is supposed that both participants and TP all follow the semihonest model. Generally, the semihonest secure two-party computation model can be illustrated in detail as follows. This can be used in security proofs of protocols.

There exists a mapping function $f:{\left\{\mathrm{0,1}\right\}}^{\ast }\times {\left\{\mathrm{0,1}\right\}}^{\ast }\mapsto {\left\{\mathrm{0,1}\right\}}^{\ast }\times {\left\{\mathrm{0,1}\right\}}^{\ast }$ , where $f_1(x,y)$ is the first element and π denotes the secure two-party computation protocol. During the implementation of π, the view of the first party ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{\pi }(x,y)$ is represented by $(x,r^{\mathrm{1}},m_{\mathrm{1}}^{\mathrm{1}},m_{\mathrm{2}}^{\mathrm{1}},\dots ,m_t^{\mathrm{1}})$ (analogously $(y,r^{\mathrm{2}},m_{\mathrm{1}}^{\mathrm{2}},m_{\mathrm{2}}^{\mathrm{2}},\dots ,m_t^{\mathrm{2}})$ denotes the view of the second party ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_2^{\pi }(x,y)$ ). Here, x is the input, $r^1$ denotes the result of random coin toss, and $m_i^{\mathrm{1}}$ stands for the ith intermediate message received by the first party. When π is complete, the output of the first party is marked with ${\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{1}}^{\pi }(x,y)$ (the output of the second party is ${\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{2}}^{\pi }(x,y)$ ) and the output of π is ${\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}^{\pi }(x,y)=({\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{1}}^{\pi }(x,y),{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{2}}^{\pi }(x,y))$ .

Generally, if there exists a probabilistic polynomial-time algorithm (denoted by $S_1$ or $S_2$ ) to execute the privacy computation of f, it can be concluded that the following is true:

$$\begin{array}{l}{\left\{\left(S_{\mathrm{1}}\left(x,f_{\mathrm{1}}\left(x,y\right)\right),f_{\mathrm{2}}\left(x,y\right)\right)\right\}}_{x,y}\\ \hspace{1em}\hspace{1em}\equiv {\left\{\left({\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{\pi }\left(x,y\right),{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{2}}^{\pi }\left(x,y\right)\right)\right\}}_{x,y},\\ {\left\{\left(f_{\mathrm{1}}\left(x,y\right),S_{\mathrm{2}}\left(y,f_{\mathrm{2}}\left(x,y\right)\right)\right)\right\}}_{x,y}\\ \hspace{1em}\hspace{1em}\equiv {\left\{\left({\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{1}}^{\pi }\left(x,y\right),{\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{2}}^{\pi }\left(x,y\right)\right)\right\}}_{x,y}.\end{array}$$

(1)

Here, the meaning of “≡” is “calculation of indiscernibility,” ${\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_i^{\pi }(x,y)$ is entirely determined by ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_i^{\pi }(x,y)$ , and both of them are stochastic variables. $S_1$ and $S_2$ are called the time simulators.

3.3. Definition of Distance

There are many definitions of distance between two participants, including the Minkowski distance, Hamming distance, and Levenshtein distance [22]. The Minkowski distance is the most common one. It can be expressed using

$$\begin{array}{cc}& d\left(p\right)={\left({\displaystyle \sum }_{i=\mathrm{1}}^n{\left|x_i-y_i\right|}^p\right)}^{\mathrm{1}/p}.\end{array}$$

(2)

Here $x_i$ and $y_i$ are from $\mathit{P}=(x_1,x_2,\dots ,x_n)\in {\mathit{R}}^n$ and $\mathit{Q}=\left(y_1,y_2,\dots ,y_n\right)\in {\mathit{R}}^n$ , respectively. When $p=1$ , it becomes the Manhattan distance; when $p=\infty$ , it becomes the Chebyshev distance; when $p=2$ , it becomes the Euclidean distance, which can be described by

$$\begin{array}{cc}& d\left(\mathrm{2}\right)=\sqrt{\left({\displaystyle \sum }_{i=\mathrm{1}}^n{\left|x_i-y_i\right|}^{\mathrm{2}}\right)}.\end{array}$$

(3)

In this paper, the Euclidean distance between two participants is calculated exactly in the two proposed secure protocols.

3.4. Privacy Measure

Most researchers use the “calculation of indiscernibility” method to realize security proofs, but this method cannot quantify privacy. If it is necessary to prove that one protocol is absolutely secret (perfect zero leakage), privacy measures become essential because it can validate safety of protocols against attackers more efficiently. However, currently there is no common method of measuring privacy. Although the utilization of information theory can quantify privacy, it has limitations [23, 24]. Specifically, it is only available for the protocols whose input has a linear relationship with output. It cannot be applied to nonlinear protocols.

Several symbols and concepts regarding the measurement of privacy are given below. These were used to confirm the validity of the proposed protocol.

•  

$X_i^{\pi }$ denotes the input of the ith participant in π, and ${\mathrm{m}\mathrm{s}\mathrm{g}}_i^{\pi }$ is described as the message received by the ith participant. After the beginning of π, one participant receives some information from his partner. In this way, the following can be defined:

 

$H_i^{\pi }=H(X_i^{\pi })$ : the entropy of stochastic variable $X_i^{\pi }$ ;

 

$H_{ij}^{\pi }=H(X_i^{\pi }\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_j^{\pi })$ : the conditional entropy of $X_i^{\pi }$ when ${\mathrm{m}\mathrm{s}\mathrm{g}}_j^{\pi }$ is given and when it implies the uncertainty on $X_i^{\pi }$ of the jth participant while receiving ${\mathrm{m}\mathrm{s}\mathrm{g}}_j^{\pi }$ ;

 

$\mathrm{m}\mathrm{i}{\mathrm{n}}_{i,j}(H_{ij}^{\pi }\hspace{0.17em}|\hspace{0.17em}{H}_i^{\pi })$ : the relative privacy of π;

 

$\mathrm{m}\mathrm{i}{\mathrm{n}}_{i,j}(H_{ij}^{\pi })$ : the absolute privacy of π.

Relative privacy is believed to be more likely to reflect the degree of privacy divulgence than the absolute privacy, and it can be standardized to a value between 0 and 1 where 0 represents full leakage and 1 indicates perfect safety (perfect zero leakage).

Theorem 1 (see [23]).

Consider that $\mathbf{V},\mathbf{C}\in GF(p{)}^n$ (both V and C are one-dimensional vectors); A is a matrix with m rows and n columns whose element belongs to $GF(p{)}^n$ and $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathit{A})=k$ . If there exists a functional dependency relationship among A , V , and C , which can be expressed by $\mathit{A}\ast \mathit{V}=\mathit{C}$ , and meanwhile if V has n unknown quantities, then $H(\mathit{V}\hspace{0.17em}|\hspace{0.17em}\mathit{C})=(n-k)\mathrm{l}\mathrm{o}\mathrm{g}p$ .

The proof for Theorem 1 is shown in a previous study [23].

4. Two Novel Secure Two-Party Distance Computation Protocols

4.1. Description of the TPEDP Protocol

In this section, a novel third party-based Euclidean distance protocol (abbreviated TPEDP) is used to securely calculate the distance between two participants of Node A and Node B. Based on semihonest model, the TPEDP is divided into three phases: the input phase, computation phase, and output phase.

Input Phase. Node A selects a secret vector $\mathit{P}=(x_1,x_2,\dots ,x_n)$ , and Node B chooses another one $\mathit{Q}=(y_1,y_2,\dots ,y_n)$ , where $n\ge 1$ and their location information are represented by P and Q , respectively.

Output Phase. Through two-party calculation, $f(\mathit{P},\mathit{Q})$ is the final result that denotes Euclidean distance ${\left|\mathit{P}\mathit{Q}\right|}^2$ . Node A grasps $f_a$ and Node B keeps $f_b$ . Equation (4) shows the relationship among those symbols:

$$\begin{array}{cc}& f_a=f\left(\mathit{P},\mathit{Q}\right)+f_b.\end{array}$$

(4)

At last, Node A declares $f_a$ and Node B reveals $f_b$ , and they share the resulting $f(\mathit{P},\mathit{Q})$ according to (4).

Computation Phase

Step  0. The TP (a third party, i.e., a base station or a cluster-header) randomly generates two vectors, $\mathit{R}\mathit{a}=(r{a}_1,r{a}_2,\dots ,r{a}_n)$ , $\mathit{R}\mathit{b}=(r{b}_1,r{b}_2,\dots ,r{b}_n)$ , and two numbers, p and q. It causes them to satisfy (5). Then the TP sends $\mathit{R}\mathit{a}$ and p to Node A and $\mathit{R}\mathit{b}$ and q to Node B. Consider

$$\begin{array}{cc}& \left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)\ast {\left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)}^T=p+q.\end{array}$$

(5)

Step  1. Node A receives $\mathit{R}\mathit{a}$ , calculates ${\mathit{P}}_1=\mathit{P}+\mathit{R}\mathit{a}=(x_1+r{a}_1,x_2+r{a}_2,\dots ,x_n+r{a}_n)$ , and sends ${\mathit{P}}_1$ to Node B.

Step  2. Node B computes ${\mathit{Q}}_1=\mathit{R}\mathit{b}-\mathit{Q}=(r{b}_1-y_1,r{b}_2-y_2,\dots ,r{b}_n-y_n)$ using the received vector $\mathit{R}\mathit{b}$ and its secret Q . Then Node B generates a random number v, together with ${\mathit{P}}_1$ , and establishes (6). Finally, Node B sends ${\mathit{Q}}_1$ and s to Node A. Consider

$$\begin{array}{l}s=\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)\ast {\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)}^T+\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{Q}}^T\\ -\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{P}}_{\mathrm{1}}^T-q+v.\end{array}$$

(6)

Step  3. After receiving ${\mathit{Q}}_1$ and s, Node A calculates u in terms of

$$\begin{array}{cc}& u=s-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{Q}}_{\mathrm{1}}^T-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{P}}^T-p.\end{array}$$

(7)

Finally, Node A and Node B determine the distance ${\left|\mathit{P}\mathit{Q}\right|}^2$ (i.e., $d^2$ ) with respect to

$$\begin{array}{cc}& u=d^{\mathrm{2}}+v.\end{array}$$

(8)

Here, $f_a=-u$ , $f_b=-v$ , and $f(\mathit{P},\mathit{Q})=d^2$ satisfy the form of (4).

Proof (correctness proof).

The TPEDP can achieve the correct result of Euclidean distance between two participants.

Proof.

The arithmetic expression of (6) can be expanded as follows:

$$\begin{array}{l}s=\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)\ast {\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)}^T+\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{Q}}^T\\ \hspace{1em}-\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{P}}_{\mathrm{1}}^T-q+v\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i+r{a}_i+r{b}_i-y_i\right)}^{\mathrm{2}}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i{y}_i\\ \hspace{1em}-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i\left(x_i+r{a}_i\right)-q+v\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(\left(x_i-y_i\right)+\left(r{a}_i+r{b}_i\right)\right)}^{\mathrm{2}}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i{y}_i\\ \hspace{1em}-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i\left(x_i+r{a}_i\right)-q+v\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}+{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(r{a}_i-r{b}_i\right)}^{\mathrm{2}}+\mathrm{4}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{a}_{i}r{b}_i\\ \hspace{1em}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^n\left(x_i-y_i\right)\left(r{a}_i+r{b}_i\right)\\ \hspace{1em}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i{y}_i-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{b}_i\left(x_i+r{a}_i\right)-q+v\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}+{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(r{a}_i-r{b}_i\right)}^{\mathrm{2}}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_{i}r{a}_i\\ \hspace{1em}+\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{n}r{a}_i\left(r{b}_i-y_i\right)-q+v\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}+{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(r{a}_i-r{b}_i\right)}^{\mathrm{2}}+\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{P}}^T\\ \hspace{1em}+\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{Q}}_{\mathrm{1}}^T-q+v.\end{array}$$

(9)

If ${\mathit{Q}}_1$ and s of (7) are displaced, then (10) can be produced:

$$\begin{array}{l}u=s-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{Q}}_{\mathrm{1}}^T-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{P}}^T-p\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}+{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(r{a}_i-r{b}_i\right)}^{\mathrm{2}}+\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{P}}^T\\ \hspace{1em}+\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{Q}}_{\mathrm{1}}^T-q+v\\ \hspace{1em}-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{Q}}_{\mathrm{1}}^T-\mathrm{2}\mathit{R}\mathit{a}\ast {\mathit{P}}^T-p\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}+{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(r{a}_i-r{b}_i\right)}^{\mathrm{2}}-p-q+v.\end{array}$$

(10)

From (5), the equality of $p+q={\sum }_{i=\mathrm{1}}^n(r{a}_i-r{b}_i{)}^{\mathrm{2}}$ can be deduced. It can be substituted into (10). Finally, the expression of $u={\sum }_{i=\mathrm{1}}^n(x_i-y_i{)}^{\mathrm{2}}+v={\left|\mathbf{P}\mathbf{Q}\right|}^{\mathrm{2}}+v$ can be concluded and the validity of the TPEDP is proven.

4.2. Description of the REDP Protocol

Some outdoor wireless sensor network environments do not allow the existence of a reliable third party, so the two nodes must complete security distance calculation relying only on each other. A randomization technique is used to avoid the high computational complexity produced by homomorphic encryption, and the design of an efficient two-party protocol is described in this section. It is here called the randomization-based Euclidean distance protocol (abbreviated REDP). The difficulty of designing REDP is that it requires randomly camouflaging vectors in the domain of real numbers and it involves exchanging some elements within those modified vectors.

It can be supposed that Node A and Node B are semihonest participants and operations in input and output phases of the REDP are identical to those of the TPEDP. Then only the steps of computation phase are displayed as follows.

Computation Phase

Step  1. Node A generates a random sequence $\{r{a}_0,r{a}_1,\dots ,r{a}_n\}$ where $r{a}_i\ne 0$ , $i\in [\mathrm{0},n]$ , and, for each $x_i$ in P ( $\mathit{P}=(x_1,x_2,\dots ,x_n)$ ), Node A calculates $x_i^{\prime }=r{a}_0{x}_i+ir{a}_i$ ( $i=\mathrm{1,2},\dots ,n$ ) which creates a new vector ${\mathit{P}}_1=(x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime })$ . Node A continues to calculate the values of λ and $x_i^{\prime \prime }$ according to (11) and (12), respectively, where u, e, and w ( $u,e,w\ne 0$ ) are random numbers chosen by Node A:

$$\begin{array}{cc}& \lambda =-\frac{\mathrm{1}}{\mathrm{2}}r{a}_{\mathrm{0}}\left(u+{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^2\right),\end{array}$$

(11)

$$\begin{array}{cc}& x_i^{\prime \prime }=\frac{w-r{a}_i}{e},\hspace{1em}\left(i=\mathrm{1,2},\dots ,n\right).\end{array}$$

(12)

All $x_i^{\prime \prime }$ form a new vector ${\mathit{P}}_2=(x_1^{\prime \prime },x_2^{\prime \prime },\dots ,x_n^{\prime \prime })$ , and Node A sends ${\mathit{P}}_1$ , ${\mathit{P}}_2$ , and λ to Node B but keeps $\{r{a}_0,r{a}_1,\dots ,r{a}_n\}$ , e, w, and u secret.

Step  2. Node B constructs two fresh vectors ${\mathit{Q}}_1=(y_1^{\prime },y_2^{\prime },\dots ,y_n^{\prime })=(r_b{y}_1,r_b{y}_2,\dots ,r_b{y}_n)$ and ${\mathit{Q}}_2=(y_1^{\prime \prime },y_2^{\prime \prime },\dots ,y_n^{\prime \prime })=(r_b{y}_1,2r_b{y}_2,\dots ,n{r}_b{y}_n)$ with a random number $r_b$ ( $r_b\ne 0$ ) and Q ( $\mathit{Q}=(y_1,y_2,\dots ,y_n)$ ). Then Node B computes $h_1$ , $h_2$ , and $h_3$ in terms of (13), (14), and (15), separately, and ${\mathit{P}}_1$ , ${\mathit{P}}_2$ , and λ are obtained from Node A. Consider

$$\begin{array}{l}{h}_{\mathrm{1}}=\lambda r_b+{\mathbf{P}}_{\mathrm{1}}\ast {\mathbf{Q}}_{\mathrm{1}}=r{a}_{\mathrm{0}}{r}_b\left(u+{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}\right)+{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\prime }{y}_i^{\prime }\\ =-\frac{\mathrm{1}}{\mathrm{2}}r{a}_{\mathrm{0}}{r}_b\left(u+{\displaystyle \sum }_{i=\mathrm{1}}^n{x_i}^{\mathrm{2}}\right)+{\displaystyle \sum }_{i=\mathrm{1}}^n\left(r{a}_{\mathrm{0}}{x}_i+ir{a}_i\right)r_b{y}_i,\end{array}$$

(13)

$$\begin{array}{ll}& h_{\mathrm{2}}={\mathbf{P}}_{\mathrm{2}}\ast {\mathbf{Q}}_{\mathrm{2}}={\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\prime \prime }{y}_i^{\prime \prime }={\displaystyle \sum }_{i=\mathrm{1}}^n\left(w-\frac{r{a}_i}{e}\right)i{r}_b{y}_i,\end{array}$$

(14)

$$\begin{array}{ll}& h_{\mathrm{3}}={\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\prime \prime }.\end{array}$$

(15)

At last, Node B sends $h_1$ , $h_2$ , and $h_3$ to Node A but keeps $r_b$ secret.

Step  3. Node A determines the value of m on the basis of (16) and sends it to Node B:

$$\begin{array}{cc}& m=-\frac{\left(h_{\mathrm{1}}+e{h}_{\mathrm{2}}-we{h}_{\mathrm{3}}\right)}{r{a}_{\mathrm{0}}}.\end{array}$$

(16)

Step  4. Node B obtains the value of v according to

$$\begin{array}{cc}& v=\frac{\mathrm{2}m}{r_b}+{\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\mathrm{2}}.\end{array}$$

(17)

Finally, Node A and Node B share the value of ${\left|\mathit{P}\mathit{Q}\right|}^2$ (i.e., $d^2$ ) in the light of

$$\begin{array}{cc}& v=d^{\mathrm{2}}+u.\end{array}$$

(18)

Here $f_a=u$ , $f_b=v$ , and $f(\mathit{P},\mathit{Q})=d^2$ all satisfy the form of (4).

Proof (correctness proof).

According to (16), (17), and (18), (19) can be deduced:

$$\begin{array}{l}{d}^2=v-u=\frac{\mathrm{2}m}{r_b}+{\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\mathrm{2}}-u\\ =-\frac{\mathrm{2}\left(h_{\mathrm{1}}+e{h}_{\mathrm{2}}-we{h}_{\mathrm{3}}\right)}{r{a}_{\mathrm{0}}{r}_b}+{\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\mathrm{2}}-u.\end{array}$$

(19)

It makes use of the expressions of (13), (14), and (15) to displace $h_1$ , $h_2$ , and $h_3$ in (19), respectively. Then the following can be concluded:

$$\begin{array}{l}{d}^{\mathrm{2}}=-\frac{\mathrm{2}\left[-\left(\mathrm{1}/\mathrm{2}\right)r{a}_{\mathrm{0}}{r}_b\left(u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}\right)+{\sum }_{i=\mathrm{1}}^{n}r{a}_{\mathrm{0}}{r}_b{x}_i{y}_i\right]}{r{a}_{\mathrm{0}}{r}_b}\\ \hspace{1em}\hspace{1em}+{\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\mathrm{2}}-u\\ =u+{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i{y}_i+{\displaystyle \sum }_{i=\mathrm{1}}^n{y}_i^{\mathrm{2}}-u\\ ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(x_i-y_i\right)}^{\mathrm{2}}.\end{array}$$

(20)

Equation (20) shows the exact computation of the expression of Euclidean distance between Node A and Node B. In this way, the proof is complete.

5. Security Analysis

5.1. Security of the TPEDP Protocol

In this section, the security of the TPEDP protocol is proven. Node A and Node B cannot learn any private vectors from each other except for the distance between them. This provides a detailed analysis of each step of the TPEDP.

• (1)

In Step 0, the TP receives no reply from either Node A or Node B, so it cannot gain any information from either of the two participants.

(2)

In Step 1, Node B learns ${\mathit{P}}_1=\mathit{P}+\mathit{R}\mathit{a}$ from Node A but cannot analyze P because Node B knows nothing about $\mathit{R}\mathit{a}$ . After receiving ${\mathit{P}}_1$ , Node B encounters a group of nonhomogeneous linear equations with $2n$ unknown quantities but only n equations. These equations cannot be solved in an algebraic field.

(3)

In Step 2, Node A receives s, which is the result of scalar products for ${\mathit{P}}_1$ , ${\mathit{Q}}_{\mathit{1}}$ . For Node A, s and ${\mathit{Q}}_1$ are equivalent to a group of nonhomogeneous linear equations, including $2n+2(\mathit{Q},\mathit{R}\mathit{b},q,v)$ unknown quantities, but the $n+1$ equations are not enough to solve for those elements of Q .

(4)

In Step 3, owing to adding stochastic number v into (6) by Node B, Node A cannot hold the final result by itself. It means that u is only available to Node A and v is only available to Node B. For any one participant, (8) has two unknown quantities and an infinity of solutions. In this way, neither Node A nor Node B can deduce the value of $d^2$ from their respective data alone. So the scenario protects the secrecy of the information regarding the location of the two participants.

In summary, none of the information is compromised during communications among Node A, Node B, and TP. In order to render the procedure of security analysis more convincing, the calculation of indiscernibility method was adopted for further validation.

Theorem 2.

The TPEDP (marked with ${\pi }_1$ ) ensures that Node A and Node B cannot acquire private input of each other.

Proof.

Because both Node A and Node B are semihonest participants, it is necessary to prove, in the TPEDP, that the intermediate information obtained by the passive attacker cannot be differentiated from those produced in no-attack and real situations, that is, calculation of indiscernibility.

A simulator must be constructed to imitate all of information acquired by a passive attacker in the executing process of the TPEDP. It can be discretionarily determined whether Node A or Node B is captured by the attacker. For this reason, the simulator $S_1$ can simulate data from the view of Node A ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathit{P}=(x_1,x_2,\dots ,x_n)$ , $\mathit{Q}=(y_1,y_2,\dots ,y_n))$ . In this way, this proof process can be used to verify whether $\{S_1(\mathit{P},f_1(\mathit{P},\mathit{Q}),f_2(\mathit{P},\mathit{Q}))\}$ and $\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q}),\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{\mathrm{2}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})\}$ are equivalent, where ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})=(\mathbf{P},r^{\mathrm{1}},m_{\mathrm{1}}^{\mathrm{1}},m_{\mathrm{2}}^{\mathrm{1}},\dots ,m_t^{\mathrm{1}})$ . The location information $\mathit{P}=(x_1,x_2,\dots ,x_n)$ of Node A and the final distance d serve as the inputs of $S_1$ .

Input Phase of ${\pi }_1$ . The attacker informs $S_1$ that it will collect all of information held by Node A, including its private location P and the final result d. Because of the absence of $\mathit{Q}=(y_1,y_2,\dots ,y_n)$ which is held by Node B, $S_1$ can only generate one simulated vector ${\mathbf{Q}}^{\prime }=(y_{\mathrm{1}}^s,y_{\mathrm{2}}^s,\dots ,y_n^s)$ that satisfies (3). Here, $y_i$ in (3) is replaced by $y_i^s$ .

Computation Phase of ${\pi }_1$ . In Step 0, Node A receives the true data $\mathit{R}\mathit{a}$ and p distributed by the TP. But $S_1$ still generates simulant data involved in ${\mathit{R}\mathit{a}}^{\prime }=(r{a}_1^{\prime },r{a}_2^{\prime },\dots ,r{a}_n^{\prime })$ , ${\mathit{R}\mathit{b}}^{\prime }=(r{b}_1^{\prime },r{b}_2^{\prime },\dots ,r{b}_n^{\prime })$ , $p^{\prime }$ , $q^{\prime }$ in terms of the result of coin toss $r^1$ , and all those values satisfy the form of (5); that is, $({\mathit{R}\mathit{a}}^{\prime }-{\mathit{R}\mathit{b}}^{\prime })\ast {\left({\mathit{R}\mathit{a}}^{\prime }-{\mathit{R}\mathit{b}}^{\prime }\right)}^T=p^{\prime }+q^{\prime }$ .

In Step $\mathrm{1}$ , $S_{\mathrm{1}}$ can calculate ${\mathit{P}}_{\mathrm{1}}^{\prime }=\mathit{P}+{\mathit{R}\mathit{a}}^{\prime }=(x_{\mathrm{1}}+r{a}_{\mathrm{1}}^{\prime },x_{\mathrm{2}}+r{a}_{\mathrm{2}}^{\prime },\dots ,x_n+r{a}_n^{\prime }$ ) and send ${\mathit{P}}_{\mathrm{1}}^{\prime }$ to Node B.

In Step 2, Node A receives s and ${\mathit{Q}}_1$ , which are produced by Node B. But $S_1$ can select a random number $v^{\prime }$ with ${\mathit{R}\mathit{b}}^{\prime }$ & $q^{\prime }$ . These values can be used to simulate the following equalities of ${\mathit{Q}}_{\mathrm{1}}^{\prime }$ and $s^{\prime }$ in accordance with (6):

$$\begin{array}{l}{\mathit{Q}}_{\mathrm{1}}^{\prime }={\mathit{R}\mathit{b}}^{\prime }-{\mathbf{Q}}^{\prime }=\left(r{b}_{\mathrm{1}}^{\prime }-y_{\mathrm{1}}^s,r{b}_{\mathrm{2}}^{\prime }-y_{\mathrm{2}}^s,\dots ,r{b}_n^{\prime }-y_n^s\right)\\ s^{\prime }=\left({\mathit{P}}_{\mathrm{1}}^{\prime }+{\mathit{Q}}_{\mathrm{1}}^{\prime }\right)\ast {\left({\mathit{P}}_{\mathrm{1}}^{\prime }+{\mathit{Q}}_{\mathrm{1}}^{\prime }\right)}^T+{\mathit{R}\mathit{b}}^{\prime }\ast {\mathit{Q}}^{\prime T}-{\mathit{R}\mathit{b}}^{\prime }\\ \hspace{1em}\ast {\mathit{P}}_{\mathrm{1}}^{\prime T}-q^{\prime }+v^{\prime }.\end{array}$$

(21)

In Step 3, $S_1$ incites Node A to calculate the simulant parameter $u^{\prime }=s^{\prime }-2\mathit{R}{\mathit{a}}^{\prime }\ast {\mathit{Q}}_1^{\prime T}-2\mathit{R}{\mathit{a}}^{\prime }\ast {\mathit{P}}^T-p^{\prime }$ .

Output Phase of ${\pi }_1$ . Finally, $f_a^{\prime }=-u^{\prime }$ , $f_b^{\prime }=-v^{\prime }$ , and all satisfy the form of (4); that is, $f_b^{\prime }=f(\mathit{P},\mathit{Q})+f_a^{\prime }$ . After the exchange of data between Node A and Node B, through simulation, $S_1$ obtains all information of Node A: $\{f_a^{\prime },f_b^{\prime },f(\mathit{P},\mathit{Q})\}$ .

However, in each of the steps outlined above, all of the data (denoted by $S_1(\mathit{P},d)=\{\mathit{P},r^1,s^{\prime },{\mathit{Q}}_1^{\prime },d\})$ handled by $S_1$ cannot be distinguished from those produced in the normal execution of ${\pi }_1$ . Because the view of Node A is ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})=\{\mathbf{P},r^{\mathrm{1}},s,{\mathbf{Q}}_{\mathrm{1}}\}$ and the output of ${\pi }_1$ is ${\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})={\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{2}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})=d$ , $\{S_{\mathrm{1}}(\mathbf{P},d),d\}\equiv \{{\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q}),{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}}_{\mathrm{2}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})\}$ can be concluded. This indicates “calculation of indiscernibility.”

Likewise, if the attacker suborns Node B, then the attacker will gather all information in Node B's possession using another simulator, $S_2$ . The view of Node B is ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{2}}^{{\pi }_{\mathrm{1}}}(\mathit{P}=(x_1,x_2,\dots ,x_n)$ , $\mathit{Q}=(y_1,y_2,\dots ,y_n))$ , and the same conclusion of “calculation of indiscernibility” can be drawn: $\{f_1(\mathit{P},\mathit{Q})$ , $S_2(\mathit{Q},f_2(\mathit{P},\mathit{Q}))\}$ and $\{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{\mathrm{1}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q}),\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{\mathrm{2}}^{{\pi }_{\mathrm{1}}}(\mathbf{P},\mathbf{Q})\}$ are equivalent.

If the attacker captures the TP, then the attacker cannot realize the simulation because the TP has not obtained any information from Node A or Node B at any point in the protocol.

This proves Theorem 2.

5.2. Security of the REDP Protocol

Node A and Node B cannot obtain any private vectors from each other except for the distance value between them. The following is a detailed analysis of each step in the REDP process.

(1) In Step 1, Node B receives some data from Node A, including ${\mathit{P}}_1=(x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime })$ , ${\mathit{P}}_2=(x_1^{\prime \prime },x_2^{\prime \prime },\dots ,x_n^{\prime \prime })$ , where $x_i^{\prime }=r{a}_0{x}_i+ir{a}_i$ , $x_i^{\prime \prime }=(w-r{a}_i)/e$ ( $i=\mathrm{1,2},\dots ,n$ ). However, because Node B cannot learn the specific values of $r{a}_i$ , w, or e, it is faced with the difficulty of solving $x_i$ with $2n$ nonlinear polynomial equations but $2n+3$ unknown quantities. These can be expressed by (22), where $b_j$ ( $j=\mathrm{1,2},\dots ,n,n+1,\dots ,2n$ ) is a specific constant. Consider

$$\begin{array}{l}{x}_{\mathrm{2}n+\mathrm{1}}{x}_{\mathrm{1}}+x_{\mathrm{1}}=b_{\mathrm{1}},\\ ⋮\\ x_{\mathrm{2}n+\mathrm{1}}{x}_i+i{x}_i=b_i,\\ ⋮\\ x_{\mathrm{2}n+\mathrm{1}}{x}_n+n{x}_n=b_n,\\ x_{\mathrm{2}n+\mathrm{2}}-\frac{x_{n+\mathrm{1}}}{x_{\mathrm{2}n+\mathrm{3}}}=b_{n+\mathrm{1}},\\ ⋮\\ x_{\mathrm{2}n+\mathrm{2}}-\frac{x_{n+i}}{x_{\mathrm{2}n+\mathrm{3}}}=b_{n+i},\\ ⋮\\ x_{\mathrm{2}n+\mathrm{2}}-\frac{x_{\mathrm{2}n}}{x_{\mathrm{2}n+\mathrm{3}}}=b_{\mathrm{2}n},\\ \left(i=\mathrm{1,2},\dots ,n\right).\end{array}$$

(22)

Equation (22) has infinity of solutions. In some cases, such as $r{a}_0=1$ , $e=1$ , (22) can be degraded to a group of nonhomogeneous linear equations group represented by (23). Here, $b_j$ ( $j=\mathrm{1,2},\dots ,n,n+1,\dots ,2n$ ) is a specific constant. Consider

$$\begin{array}{l}{x}_{\mathrm{1}}+x_{n+\mathrm{1}}=b_{\mathrm{1}},\\ ⋮\\ x_i+i{x}_{n+i}=b_i,\\ ⋮\\ x_n+n{x}_{\mathrm{2}n}=b_n,\\ x_{\mathrm{2}n+\mathrm{1}}-x_{n+\mathrm{1}}=b_{n+\mathrm{1}},\\ ⋮\\ x_{\mathrm{2}n+\mathrm{1}}-x_{n+i}=b_{n+i},\\ ⋮\\ x_{\mathrm{2}n+\mathrm{1}}-x_{\mathrm{2}n}=b_{\mathrm{2}n},\\ \left(i=\mathrm{1,2},\dots ,n\right).\end{array}$$

(23)

Because (23) can be solved using features of the nonhomogeneous linear equations, it shows that the coefficient matrix and the augmented matrix of the equations outlined above have the same rank. For this reason, only the rank of the coefficient matrix is considered. This is displayed as follows:

$$\begin{array}{l}\mathbf{A}=\left(\begin{array}{lllll}\begin{array}{l}\mathrm{1}\\ \mathrm{0}\end{array}& \stackrel{\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}”\mathrm{0}”:n-\mathrm{1}}{\overbrace{\begin{array}{l}\begin{array}{llll}\mathrm{0}& \mathrm{0}& \cdots & \mathrm{0}\end{array}\\ \begin{array}{llll}\mathrm{1}& \mathrm{0}& \cdots & \mathrm{0}\end{array}\end{array}}}& \begin{array}{l}\mathrm{1}\\ \mathrm{0}\end{array}& \stackrel{\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}”\mathrm{0}”:n-\mathrm{1}}{\overbrace{\begin{array}{l}\begin{array}{llll}\mathrm{0}& \mathrm{0}& \cdots & \mathrm{0}\end{array}\\ \begin{array}{llll}\mathrm{2}& \mathrm{0}& \cdots & \mathrm{0}\end{array}\end{array}}}& \begin{array}{l}\mathrm{0}\\ \mathrm{0}\end{array}\\ & \cdots & & \cdots & \\ \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& \mathrm{1}\end{array}& \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& n\end{array}& \mathrm{0}\\ \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& \mathrm{0}\end{array}& -\mathrm{1}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& \mathrm{0}\end{array}& \mathrm{1}\\ \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& \mathrm{0}\end{array}& \mathrm{0}& \begin{array}{llll}-\mathrm{1}& \cdots & \mathrm{0}& \mathrm{0}\end{array}& \mathrm{1}\\ & \cdots & & \cdots & \\ \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& \mathrm{0}\end{array}& \mathrm{0}& \begin{array}{llll}\mathrm{0}& \cdots & \mathrm{0}& -\mathrm{1}\end{array}& \mathrm{1}\end{array}\right)\\ r\left(\mathbf{A}\right)=\mathrm{2}n.\end{array}$$

(24)

However, there are $2n+1$ unknown quantities in (23) for which the rank of the coefficient matrix is $2n$ . Equation (23) has an infinite number of solutions because the rank of the augmented matrix (i.e., the number of linearly independent equations) is less than the number of unknown quantities. Even in some extreme situations, (22) still has an infinity of solutions. Node B cannot discriminate u or $r{a}_0$ from the value of λ. In this way, the data obtained by Node B are not sufficient for detection of any private information regarding location vector $\mathit{P}=(x_1,x_2,\dots ,x_n)$ , which is owned by Node A.

(2) In Step 2, Node A encounters the same problem with respect to solving a group of nonlinear equations. In extreme situations (e.g., if Node B selects $r_b=1$ ), Node A may choose a zero vector $\mathit{P}=0$ in input phase. This can be used repeatedly in (13) and (14) after Node A receives $h_1$ , $h_2$ , and $h_3$ . Finally, Node A can deduce the value of $r_b$ with considerable probability of success. Even so, Node A still needs to solve a group of nonhomogeneous linear equations with $n+1$ unknown quantities and only three equations. This problem has an infinite number of solutions. Just by virtue of $r_b$ , Node A is unable to infer Node B's confidential location information Q .

(3) In Step 3, if Node B utilizes the expressions of (13), (14), and (15) to successively substitute for the values of $h_1$ , $h_2$ , and $h_3$ in (16), Node B can produce

$$\begin{array}{l}m=-\frac{\left(h_{\mathrm{1}}+e{h}_{\mathrm{2}}-we{h}_{\mathrm{3}}\right)}{r{a}_{\mathrm{0}}}\\ =-\frac{\left[-\left(\mathrm{1}/\mathrm{2}\right)r{a}_{\mathrm{0}}{r}_b\left(u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}\right)+{\sum }_{i=\mathrm{1}}^{n}r{a}_{\mathrm{0}}{r}_b{x}_i{y}_i\right]}{r{a}_{\mathrm{0}}}\\ =\frac{\mathrm{1}}{\mathrm{2}}{r}_b\left(u+{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}\right)-r_b{\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i{y}_i.\end{array}$$

(25)

There is a variety of ways in which Node B might separate individual components such as $u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}$ from (25). During the input phase, Node B may select a special vector Q that only includes one nonzero element to participate in all calculations from Steps 1 to 4. However, this method does not allow Node B to discriminate $u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}$ or ${\sum }_{i=\mathrm{1}}^n{x}_i{y}_i$ from (25). Unless Node B uses a zero vector, that is, $\mathit{Q}=0$ , it can determine the value of $u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}$ in Step 3 with considerable probability of success. Using the received value of λ, Node B may determine the value of $r{a}_0$ after successfully cracking $u+{\sum }_{i=\mathrm{1}}^n{x}_i^{\mathrm{2}}$ . Even so, Node B cannot find solutions to a group of nonlinear polynomial equations with only $n+2$ equations though the number of unknown quantities is reduced from the original $2n+3$ to the current $2n+2$ .

(4) The security analysis in Step 4 of this process is the same as the analysis in Step 4 of the TPEDP.

In order to make the above security analysis more persuadable, it must be proven that the intermediate information obtained by a passive attacker and that produced in no-attack and real situations involve the “calculation of indiscernibility.”

Theorem 3.

The REDP (marked with ${\pi }_2$ ) ensures that Node A and Node B cannot acquire private input regarding each other.

Proof.

Because of the premises and assumptions of the simulator and because the process of the input phase of the REDP protocol is similar to that of the TPEDP protocol, the validation procedures of computation and output phases may be paid more attention. It can still be supposed that the passive attacker captures Node A and constructs the simulator $S_1$ to implement the REDP protocol.

Computation Phase of ${\pi }_2$ . In Step 1, $S_1$ produces $\{{ra}_0^{\prime },{ra}_1^{\prime },\dots ,{ra}_n^{\prime }\}$ , $u^{\prime }$ , $w^{\prime }$ , and $e^{\prime }$ successively according to the results of $r^1$ and then calculates $\{{\mathit{P}}_1^{\prime },{\mathit{P}}_2^{\prime },{\lambda }^{\prime }\}$ , which serves as the simulated information that would be sent to Node B.

In Step 2, because Node A does not know the real $r_b$ generated by Node B, $S_1$ will forge $r_b^{\prime }$ , together with ${\mathbf{Q}}^{\prime }=(y_{\mathrm{1}}^s,y_{\mathrm{2}}^s,\dots ,y_n^s)$ and simulate the intermediate data ${\mathit{Q}}_1^{\prime }$ , ${\mathit{Q}}_2^{\prime }$ , $h_1^{\prime }$ , $h_2^{\prime }$ , and $h_3^{\prime }$ , which must be selected by Node B in (13)–(15):

$$\begin{array}{l}{\mathbf{Q}}_{\mathrm{1}}^{\prime }=\left(r_b{y}_{\mathrm{1}}^s,r_b{y}_{\mathrm{2}}^s,\dots ,r_b{y}_n^s\right),\\ {\mathbf{Q}}_{\mathrm{2}}^{\prime }=\left(r_b{y}_{\mathrm{1}}^s,\mathrm{2}{r}_b{y}_{\mathrm{2}}^s,\dots ,n{r}_b{y}_n^s\right),\\ h_{\mathrm{1}}^{\prime }={\lambda }^{\prime }{r}_b^{\prime }+{\mathbf{P}}_{\mathrm{1}}^{\prime }\ast {\mathbf{Q}}_{\mathrm{1}}^{\prime }=-\frac{\mathrm{1}}{\mathrm{2}}r{a}_{\mathrm{0}}^{\prime }{r}_b^{\prime }\left(u^{\prime }+{\displaystyle \sum }_{i=\mathrm{1}}^n{x_i}^{\mathrm{2}}\right)\\ \hspace{1em}+{\displaystyle \sum }_{i=\mathrm{1}}^n\left(r{a}_{\mathrm{0}}^{\prime }{x}_i+ir{a}_i^{\prime }\right)r_b^{\prime }{y}_i^s,\\ h_2^{\prime }={\mathbf{P}}_{\mathbf{2}}^{\prime }\ast {\mathbf{Q}}_{\mathbf{2}}^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^n\left(w^{\prime }-\frac{r{a}_i^{\prime }}{e^{\prime }}\right)i{r}_b^{\prime }{y}_i^s,\\ h_{\mathrm{3}}^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^{n}i{r}_b^{\prime }{y}_i^s.\end{array}$$

(26)

In Step 3, $S_1$ continues to create $f_a^{\prime }=u^{\prime }$ and $m^{\prime }=-(h_{\mathrm{1}}^{\prime }+e^{\prime }{h}_2^{\prime }-w^{\prime }{e}^{\prime }{h}_{\mathrm{3}}^{\prime })/r{a}_{\mathrm{0}}^{\prime }$ .

In Step 4, $S_1$ obtains $f_b^{\prime }=v^{\prime }=\mathrm{2}{m}^{\prime }/r_b^{\prime }+{\sum }_{i=\mathrm{1}}^n{y}_i^{s\mathrm{2}}$ in terms of (17) to complete the simulation for Node B.

Output Phase of ${\pi }_2$ . $S_1$ collects all information of Node A: $\{f_a^{\prime },f_b^{\prime },f(\mathit{P},\mathit{Q})\}$ , which satisfy the form of (4); that is, $f_b^{\prime }=f(\mathit{P},\mathit{Q})+f_a^{\prime }$ , where $f_a^{\prime }=-u^{\prime }$ , $f_b^{\prime }=-v^{\prime }$ .

$S_1(\mathit{P},d)=\{\mathit{P},r^1,h_{\mathrm{1}}^{\prime },h_2^{\prime },h_{\mathrm{3}}^{\prime },d\}$ cannot be distinguished from all information produced in the normal execution of ${\pi }_2$ . The view of Node A is ${\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{2}}}(\mathbf{P},\mathbf{Q})=\{\mathit{P},r^{\mathrm{1}},h_{\mathrm{1}},h_{\mathrm{2}},h_{\mathrm{3}}\}$ and the output of ${\pi }_2$ is $\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{\mathrm{1}}^{{\pi }_{\mathrm{2}}}(\mathbf{P},\mathbf{Q})=\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{\mathrm{2}}^{{\pi }_{\mathrm{2}}}(\mathit{P},\mathbf{Q})=d$ , so $\{S_{\mathrm{1}}(\mathit{P},d),d\}\equiv \{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{\mathrm{1}}^{{\pi }_{\mathrm{2}}}(\mathbf{P},\mathbf{Q}),\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{\mathrm{2}}^{{\pi }_{\mathrm{2}}}(\mathbf{P},\mathbf{Q})\}$ implies “calculation of indiscernibility.”

The same conclusion can be drawn if the participant captured by the attacker is Node B.

This proves Theorem 3.

6. Efficiency Analysis and Comparisons

In this section, the complexity of communication round is analyzed, and the complexity of computation and the type of data involved in various protocols are also evaluated. These protocols obey semihonest execution rules and their objectives are to determine the result of secure distance computation. One of these protocols in previous study [4] is based on homomorphic encryption, called “Rane's Scheme.” A similar scheme [5], in which Rane's Scheme was improved upon, is called “Rane's Improved Scheme.” Another previous study [8] proposed two kinds of secure two-party closest-pair of points protocols. The first one comprised the computation of distance aided by a third party, and the distance computation procedure can be separated from the protocol itself and called “Huang's 1st Scheme.” The second one was designed according to discrete logarithm principles without any third party and could be used to realize secure two-party distance computation, called “Huang's 2nd Scheme.” Luo's Scheme, Lu's Scheme, and Li's Scheme are introduced, respectively, in [6], [7], and [9] in the Related Work section. Lu's Scheme only realized a scalar product protocol, but, through it, a distance calculation protocol can be simulated at no extra cost. Table 1 lists the results of a comparison of the protocols given above from several perspectives.

Table 1

Secure two-party distance computation protocols.

	Communication round complexity	Computation complexity	Data type	Need for a third party	Degree of privacy protection
TPEDP	2	$$O(n)$$	Real	Yes	1 (perfect zero leakage)
REDP	3	$$O(n)$$	Real	No	Zero leakage
Rane's Scheme [4]	n	$$O(n^{\mathit{3}})$$	Integer	No	Zero leakage
Rane's Improved Scheme [5]	n	$$O(n^{\mathit{3}})$$	Real	No	Zero leakage
Luo's Scheme [6]	2	$$O(n^{\mathit{3}})$$	Real	No	Zero leakage
Lu's Scheme [7]	n	$$O(n^{\mathit{3}})$$	Real	No	Zero leakage
Huang's 1st Scheme [8]	3	$$O(n)$$	Real	Yes	The TP obtains all messages from two participants
Huang's 2nd Scheme [8]	2	$$O(n)$$	Integer	No	Zero leakage
Li's Scheme [9]	10	$$O(n^{\mathit{2}})$$	Real	No	One participant obtains all messages from another

Note: for a fair comparison, a specific effective algorithm in [10], whose communications round complexity is 2 and computational cost is $$\mathit{2}n+\mathit{2}$$ exponential modulo operation, is selected as the complement of oblivious transfer protocol $$\text{O}{\text{T}}_n^{\text{1}}$$ [11] of Li's Scheme [9].

(a) Communication Round Complexity. As shown in Table 1, communication round complexities of those protocols are almost roughly the same level except for Li's Scheme, which includes many communication steps. Rounds of communication in Lu's Scheme, Rane's Scheme, and the Rane's Improved Scheme are determined by the dimensions of the input vector. However, the dimensions of location information must be less than or equal to 3. Even if there is a third party, the TPEDP can be completed within two rounds, but the REDP has a total of four steps and three rounds of interaction, so the complexity of communication round is 3.

(b) Computation Complexity. As shown in Table 1, the overhead of these protocols to generate random numbers can be ignored because that can be addressed in the input phase. The complexity of computation is primarily produced during the computation phase of those protocols, including the TPEDP and REDP. Both of these protocols rely on the dimensions of input vectors, so the computation complexity of them are both $O(n)$ .

Some protocols based on Paillier additive homomorphic encryption can be used to perform $2\mathrm{l}\mathrm{o}\mathrm{g}N$ rounds of modular multiplication (modular operator $N^2$ ) for each encryption and decryption, at most $2d$ rounds of modular multiplication (modular operator $N^2$ ) per modular exponential calculation $(E{\left(x\right)}^y)$ , where d denotes the number of bits of processed data. For example, the complexity of computation of Rane's Scheme and its improved one is ( $(2n+2)\mathrm{l}\mathrm{o}\mathrm{g}N+2nd+n+1$ ) rounds of modular multiplication (modular operator $N^2$ ) and that of Lu's is ( $(6n+2)\mathrm{l}\mathrm{o}\mathrm{g}N+(2n+2)d+n$ ) rounds; it means that the computational cost of Rane's Scheme and its improved one totally includes ( $n+1$ ) times encryptions, n times modular exponentiations, n times modular multiplications, and once decryption; Luo's Scheme is not based on Paillier additive homomorphic encryption but rather on another form of encryption. The complexity of the computation can still be evaluated; it is ( $6n\mathrm{l}\mathrm{o}\mathrm{g}N+2nd+2$ ) rounds of modular multiplication (modular operator $N^2$ ). Generally, the value of N is larger than the dimension n, so the complexity of the computation processes involved in the protocols outlined above is no less than $O(n^3)$ .

(c) Type of Data. Rane's Scheme shows satisfactory performance with respect to the complexity of rounds of communication, but the types of data that it can process are limited to integer field. Huang's 2nd Scheme shows the same defect. The two proposed protocols have a broader range of computation because they can be implemented in real number domains.

(d) Degree of Privacy Protection. The TP of Huang's 1st Scheme holds all the information from both participants, so there is no privacy protection at all. Li's Scheme, which is based on oblivious transfer protocol and involves no TP, has a primary disadvantage that one participant may acquire all results of distance computation and deduce some private information of the other participant. In this case, if one participant can obtain all three distances from three different starting points to the same terminal point, the exact location of the other participant can be calculated. For example, as shown in Figure 1, if Node A holds $d_{11}$ , $d_{12}$ , and $d_{13}$ , which represent distances from points $T_1$ , $T_2$ , and $T_3$ to point $H_1$ , it can deduce the location of Node B, $H_1$ , correctly.

Figure 1

Deduction of location.

Both the TPEDP and REDP use a result-sharing mechanism in which two participants can determine the distance calculation results until publishing their respective random numbers (u and v). This prevents the privacy leakage that can be caused when one participant monopolizes the results. In Section 7.1, especially, it can be proven that the TPEDP protocol's degree of privacy is 1, that is, the perfect zero leakage.

7. Further Discussion

7.1. Privacy Measurement Problem of the TPEDP Protocol

Not all protocols can be carried out and used to measure privacy; only those that always satisfy linear dependence between their inputs and intermediate messages can be evaluated for the degree of privacy by using the methods recommended in Section 3.4. In this way, only the TPEDP protocol meets the requirements outlined in this paper. In the TPDEP protocol, the impact of TP can be completely ignored, because it only distributed some initial values but did not receive any valid information from either of the two participants.

During the running of the TPDEP protocol, all messages received by Node A can be denoted by ${\mathrm{m}\mathrm{s}\mathrm{g}}_T=\{s,p,{\mathit{Q}}_1\}$ , which includes the following:

$$\begin{array}{l}{\mathit{Q}}_{\mathrm{1}}={\mathit{Q}}^T+\mathit{R}\mathit{b},\\ p=\left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)\ast {\left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)}^T-q\\ =\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{a}}^T-\mathrm{2}\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{b}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T-q,\\ s=\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)\ast {\left({\mathit{P}}_{\mathrm{1}}+{\mathit{Q}}_{\mathrm{1}}\right)}^T+\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{Q}}^T-\mathrm{2}\mathit{R}\mathit{b}\\ \hspace{1em}\ast {\mathit{P}}_{\mathrm{1}}^T-q+v\\ ={\mathit{P}}_{\mathrm{1}}\ast {\mathit{P}}_{\mathrm{1}}^T+{\mathit{P}}_{\mathrm{1}}\ast {\mathit{Q}}_{\mathrm{1}}^T+{\mathit{Q}}_{\mathrm{1}}\ast {\mathit{P}}_{\mathrm{1}}^T+{\mathit{Q}}_{\mathrm{1}}\ast {\mathit{Q}}_{\mathrm{1}}^T\\ \hspace{1em}+\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{Q}}^T-\mathrm{2}\mathit{R}\mathit{b}\ast {\mathit{P}}_{\mathrm{1}}^T-q+v\\ ={\mathit{P}}_{\mathrm{1}}\ast {\mathit{P}}_{\mathrm{1}}^T-\mathrm{2}{\mathit{P}}_{\mathrm{1}}\ast {\mathit{Q}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T+\mathit{Q}\ast {\mathit{Q}}^T-q+v.\end{array}$$

(27)

The expressions of p and s can be altered as follows:

$$\begin{array}{cc}& p=-\mathrm{2}\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{b}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T-q,\\ s=-\mathrm{2}{\mathit{P}}_{\mathrm{1}}\ast {\mathit{Q}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T+\mathit{Q}\ast {\mathit{Q}}^T-q+v.\end{array}$$

(28)

These values are related to Node B's inputs, Q and $\mathit{R}\mathit{b}$ . For the convenience of measurement of privacy, the expressions of all three elements can be changed as follows:

$$\begin{array}{l}{\mathit{Q}}_{\mathrm{1}}={\mathit{I}}_n\ast {\mathit{Q}}^T+{\mathit{I}}_n\ast \mathit{R}{\mathit{b}}^T+\mathrm{0}\ast \left(\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T\right)\\ +\mathrm{0}\ast \left(\mathit{Q}\ast {\mathit{Q}}^T\right)+\mathrm{0}\ast q+\mathrm{0}\ast v,\\ p={\mathrm{0}}_{\mathrm{1}\ast n}\ast {\mathit{Q}}^T-\mathrm{2}\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{b}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T\\ +\mathrm{0}\ast \left(\mathit{Q}\ast {\mathit{Q}}^T\right)+\mathrm{0}\ast q+\mathrm{0}\ast v,\\ s_{\mathrm{1}}=-\mathrm{2}{\mathit{P}}_{\mathrm{1}}\ast {\mathit{Q}}^T+{\mathrm{0}}_{\mathrm{1}\ast n}\ast \mathit{R}{\mathit{b}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T\\ +\mathit{Q}\ast {\mathit{Q}}^T-q+v.\end{array}$$

(29)

Here, it is supposed that

$$\begin{array}{cc}& {\mathbf{A}}_{\mathrm{1}}=\left(\begin{array}{cccccc}{\mathbf{I}}_n& {\mathbf{I}}_n& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ {\mathbf{0}}_{\mathrm{1}\ast n}& -\mathrm{2}\mathbf{R}\mathbf{a}& \mathrm{1}& \mathrm{0}& -\mathrm{1}& \mathrm{0}\\ -\mathrm{2}{\mathbf{P}}_{\mathrm{1}}& {\mathbf{0}}_{\mathrm{1}\ast n}& \mathrm{1}& \mathrm{1}& -\mathrm{1}& \mathrm{1}\end{array}\right),\\ {\mathbf{Z}}_{\mathrm{1}}=\left(\begin{array}{c}{\mathbf{Q}}^T\\ \mathbf{R}\mathbf{b}\\ \mathbf{R}\mathbf{b}\ast \mathbf{R}{\mathbf{b}}^T\\ \mathbf{Q}\ast {\mathbf{Q}}^T\\ q\\ v\end{array}\right),\hspace{1em}\hspace{1em}{\mathbf{C}}_{\mathrm{1}}=\left(\begin{array}{c}{\mathbf{Q}}_{\mathrm{1}}^T\\ p\\ s\end{array}\right).\end{array}$$

(30)

This satisfies ${\mathit{A}}_1\ast {\mathit{Z}}_1={\mathit{C}}_1$ ( ${\mathit{I}}_n$ represents identity matrix). ${\mathit{C}}_1$ is equivalent to ${\mathrm{m}\mathrm{s}\mathrm{g}}_T=\left\{s,p,{\mathit{Q}}_1\right\}$ and $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}({\mathbf{A}}_{\mathrm{1}})$ is $n+2$ . If any participant obtains Q and ${\mathrm{m}\mathrm{s}\mathrm{g}}_T$ , he would easily calculate $\mathit{R}\mathit{b}$ , $\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T$ , q, $\mathit{Q}\ast {\mathit{Q}}^T$ , and v. According to the definitions given in Section 3.4, it can be concluded that $H(\mathit{R}\mathit{b}\hspace{0.17em}|\hspace{0.17em}\mathit{Q},{\mathrm{m}\mathrm{s}\mathrm{g}}_T)=H(\mathit{R}\mathit{b}\mathit{\ast }\mathit{R}{\mathit{b}}^T\hspace{0.17em}|\hspace{0.17em}\mathit{Q},{\mathrm{m}\mathrm{s}\mathrm{g}}_T)=H(q\hspace{0.17em}|\hspace{0.17em}\mathit{Q},{\mathrm{m}\mathrm{s}\mathrm{g}}_T)=H\left(\mathit{Q}\mathit{\ast }{\mathit{Q}}^T∣\mathit{Q},{\mathrm{m}\mathrm{s}\mathrm{g}}_T\right)$ = $H(v\hspace{0.17em}|\hspace{0.17em}\mathit{Q},{\mathrm{m}\mathrm{s}\mathrm{g}}_T)$ =  0 and $H(\mathit{Q}\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_T)$ = $H(\mathit{Q},\mathit{R}\mathit{b},\mathit{R}\mathit{b}\mathit{\ast }\mathit{R}{\mathit{b}}^T,\mathit{Q}\mathit{\ast }{\mathit{Q}}^T,q,v\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_T)$ . According to Theorem 1, it can finally be deduced that $H(\mathit{Q}\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_T)=n\mathrm{l}\mathrm{o}\mathrm{g}p$ .

Next, the degree of privacy is examined from Node B's perspective. All messages received by Node B can be denoted with ${\mathrm{m}\mathrm{s}\mathrm{g}}_H=\{q,{\mathit{P}}_1\}$ , where the following are true:

$$\begin{array}{l}{\mathit{P}}_{\mathrm{1}}={\mathit{I}}_n\ast \mathit{P}+{\mathit{I}}_n\ast \mathit{R}\mathit{a},\\ q=\left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)\ast {\left(\mathit{R}\mathit{a}-\mathit{R}\mathit{b}\right)}^T-p\\ =\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{a}}^T-\mathrm{2}\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{a}}^T+\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{b}}^T-p.\end{array}$$

(31)

The expressions of q and ${\mathit{P}}_1$ can be altered into

$$\begin{array}{cc}& {\mathit{P}}_{\mathrm{1}}={\mathit{I}}_n\ast \mathit{P}+{\mathit{I}}_n\ast \mathit{R}\mathit{a}+\mathbf{0}\ast \mathit{R}\mathit{a}\ast \mathit{R}{\mathit{a}}^T-\mathrm{0}\ast p,\\ q={\mathbf{0}}_{\mathrm{1}\ast n}\ast \mathit{P}-\mathrm{2}\mathit{R}\mathit{b}\ast \mathit{R}{\mathit{a}}^T+\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{a}}^T-p.\end{array}$$

(32)

Here it is assumed that

$$\begin{array}{cc}& {\mathbf{A}}_{\mathrm{2}}=\left(\begin{array}{cccc}{\mathbf{I}}_n& {\mathbf{I}}_n& \mathrm{0}& \mathrm{0}\\ {\mathbf{0}}_{\mathrm{1}\ast n}& -\mathrm{2}\mathbf{R}\mathbf{b}& \mathrm{1}& -\mathrm{1}\end{array}\right),\\ {\mathbf{Z}}_{\mathrm{2}}=\left(\begin{array}{c}P\\ \mathbf{R}{\mathbf{a}}^T\\ \mathbf{R}\mathbf{a}\ast \mathbf{R}{\mathbf{a}}^T\\ p\end{array}\right),\hspace{1em}\hspace{1em}{\mathbf{C}}_{\mathrm{2}}=\left(\begin{array}{c}{\mathbf{P}}_{\mathrm{1}}\\ q\end{array}\right).\end{array}$$

(33)

This satisfies ${\mathit{A}}_2\ast {\mathit{Z}}_2={\mathit{C}}_2$ ( ${\mathit{I}}_n$ represents identity matrix). $\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}({\mathbf{A}}_{\mathrm{2}})$ can be shown to be $n+1$ and ${\mathit{C}}_2$ can be shown to be ${\mathrm{m}\mathrm{s}\mathrm{g}}_H$ . P and ${\mathrm{m}\mathrm{s}\mathrm{g}}_H$ allow $\mathit{R}\mathit{a}$ , $\mathit{R}\mathit{a}\ast \mathit{R}{\mathit{a}}^T$ , and p to be determined. In this way, it is obvious that $H(\mathit{R}\mathit{a}\hspace{0.17em}|\hspace{0.17em}\mathit{P},{\mathrm{m}\mathrm{s}\mathrm{g}}_H)=H(\mathit{R}\mathit{a}\mathit{\ast }\mathit{R}{\mathit{a}}^T\hspace{0.17em}|\hspace{0.17em}\mathit{P},{\mathrm{m}\mathrm{s}\mathrm{g}}_H)=H(p\hspace{0.17em}|\hspace{0.17em}\mathit{P},{\mathrm{m}\mathrm{s}\mathrm{g}}_H)=0$ , $H(\mathit{P}\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_H)$ = $H(\mathit{P},\mathit{R}\mathit{a},\mathit{R}\mathit{a}\mathit{\ast }\mathit{R}{\mathit{a}}^T$ , $p\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_H)$ , and $H(\mathit{P}\hspace{0.17em}|\hspace{0.17em}{\mathrm{m}\mathrm{s}\mathrm{g}}_H)=((2n+1)-(n+1))\mathrm{l}\mathrm{o}\mathrm{g}p=n\mathrm{l}\mathrm{o}\mathrm{g}p$ in terms of Theorem 1.

Based on the information given above, the following conclusions can be drawn.

Theorem 4.

The result of privacy measure for the TPEDP is $\mathrm{m}\mathrm{i}\mathrm{n}(H(\mathit{P}\hspace{0.17em}|\hspace{0.17em}{msg}_H)/H(\mathit{P})$ , $H(\mathit{Q}\hspace{0.17em}|\hspace{0.17em}{msg}_T)/H(\mathit{Q}\hspace{0.17em}|\hspace{0.17em}{msg}_T))=1$ , which implies perfect zero leakage.

7.2. The Repeated Calculation Problem of the REDP Protocol

Repeated calculation problem is worth emphasizing. It merits attention from both of the participants in the REDP protocol. An erroneous choice of participants may lead to a serious reduction in privacy. If Node A and Node B meet again after they have executed the REDP protocol at least once, then, during the new execution, the REDP protocol requires fresh initial vectors and random numbers distinguished from those used in the last calculation. A specific example can be cited and used to illustrate this issue, but discussions are not limited to this example.

Node A and Node B, who held initial vectors P and Q , respectively, have completed the REDP protocol once. To run the REDP again, Node B here reselects the initial vector R substituted for Q , but Node A insists on keeping the original vector P and updates the random sequence $r{a}_i$ ( $i=\mathrm{0,1},2,\dots ,n$ ) and random numbers w and e to construct new ${\mathit{P}}_1$ , ${\mathit{P}}_2$ , and λ values. This indicates that Node B may encounter a group of $2n$ nonlinear polynomial equations when it receives those renewed data from Node A. If the new equations in the group are linearly independent from those obtained by Node B in the last execution (Node A held P and Node B held Q ), then Node B can obtain a group of $4n$ nonlinear polynomial equations and $2n+3+n+3=3n+6$ unknown quantities. If Node A selects $r{a}_0=1$ , $e=1$ in the new interaction (though this case is almost impossible), the $4n$ nonlinear polynomial equations will degenerate into a group of nonhomogeneous linear equations with $3n+6$ unknown quantities. In this case, if $n<6$ (i.e., $4n<3n+6$ ), then Node B cannot learn the value of P because of prohibitively high number of solutions. If $n\ge 6$ (i.e., $4n\ge 3n+6$ ) and the number of unknown quantities is less than the number of equations, then Node B will break P and the location information of Node A is revealed. In this way, if Node A persists in using its original vector, it will be unable to update random sequences and random numbers (such as $r{a}_i$ , w, and e) in another running of this protocol. Otherwise, Node B will collect more equations regarding this original vector of Node A, which will increase the risk of loss of privacy. However, in this case, Node A can change the random value of u to produce the corresponding alteration of the results $f_a$ and $f_b$ .

For this reason, extra limitations must be added to the REDP protocol when it is encoded into the wireless communication devices. This can prevent some extreme situations such as selecting $r{a}_0=1$ , $e=1$ in Node A's computation round. Certainly, a better provision for the REDP protocol is that each participant should try to choose inputs different from those in previous executions to prevent hidden danger unless the location information of the participant has not changed. (This case has a negligible probability for moving entities.) In this way, Node A must only renew the values of u or v.

7.3. Availability in Wireless Sensor Networks

It is necessary to verify the availability of TPEDP and REDP in wireless sensor networks. We design such simulation experiments related to distance to observe the changes of network lifetime and energy consumption in the following three scenarios: the first is calculating the distance between Nodes A and B which use the REDP protocol; the second aids TPEDP to achieve the distance calculation (the current cluster-header is “TP”); and the third is based on ECC (elliptic curves cryptography), which is considered as the most lightweight public key method in WSNs, to realize the computation through encryptions, decryptions, and the reliable third party (the base station). To achieve the data-level privacy protection, in the third scenario, Nodes A and B must encrypt their locations separately using the public key of the base station, and the base station decrypts them and calculates the distance between Nodes A and B, and then the base station must encrypt the distance value by their respective public keys and send it to A and B. Finally, Nodes A and B decrypt it and obtain the result. If A and B cannot communicate with the base station within one hop, this method will cause heavy network loads.

In order to ensure the validity of comparisons, we make some assumptions aimed at the three scenarios. Shown in Figure 2, any two nodes who want to calculate the distance between them in the network can form a group; once a node joins one group it will not be able to join other groups, except the death of the other node in the same group, it will find a new single node with the same situation again to form a new group. In our simulation experiments, nodes would prefer to search the closest neighbor to form a group. All groups repeatedly calculate the distance between two members, until the network life cycle is ended. The base station, especially, does not participate in any group and all packets are in the same size which can be divided exactly by 16. Leach protocol will be used as the clustering and routing protocol in order to ensure path accessibility. If one current cluster-header is dead, it will reselect the new header in terms of Leach protocol. In TPEDP protocol, the same cluster-header can act as the TP for several groups of nodes. Detailed simulation parameters can be shown in Table 2.

Table 2

Simulation parameters setting.

Parameters	The setting value
Network range	400 * 400 m2
Distribution of sensor nodes	Uniform distribution with the number from 100 to 400 nodes, and the base station is in the center
Clustering and routing protocol	Leach
The number of dimensions of location information	$$n=\mathit{3}$$ , $$n=\mathit{8}$$
Original energy of node	20 J (infinite energy for the base station)
Energy consumption when sending a packet (at most d = 128 bits)	0.35 J
Energy consumption when receiving a packet (at most d = 128 bits)	0.15 J
Energy consumption when processing one bit (at most d = 128 bits)	0.0005 J
Energy consumption when encrypting or decrypting one bit with ECC (at most d = 128 bits)	0.0005 J
Energy consumption when processing a modular multiplication (modular operator $$N^{\mathit{2}}$$ ) (at most d = 128 bits)	0.001 J
Communication radius of node	50 m
Modular operator $$N^{\mathit{2}}$$	$$N=\mathit{79}$$ , $$N^{\mathit{2}}=\mathit{6241}$$

Figure 2

Three simulation scenarios.

We set two cases “ $n=3$ , $d=64$  bits” and “ $n=8$ , $d=96$  bits” to reflect the trend of network lifetime, based on the comparisons of REDP, TPEDP, and ECC, seen in Figures 3(a) and 3(b), respectively. We can watch that, with the increase of sensor nodes, the network lifetimes of three scenarios (or protocols?) appear to decline (or downtrend?) after a little growth in the initial stage. There exit different reasons of these phenomena for REDP, TPEDP, and ECC. There still exit some active sensor nodes in REDP (or TPEDP) because they cannot find another neighbor (or a suitable TP) in their communication ranges when the number of nodes is 100; however the lifecycle is terminated. With the increase of sensor nodes, the above symptoms will be relieved; for instance, the number of nodes is 150 or 200. With the further raise of the number of nodes (350 or 400), more and more new groups emerge while some previous groups are still running, which causes more communication costs, so the lifetime is shortened. Owing to direct or multihop communication to the base station for each node in the network, the secure distance calculation based on ECC would lead to more energy consumption, compared with REDP and TPEDP. Similarly, 100 nodes are uniformly distributed in 400 ∗ 400 field, however some active nodes have never been able to establish the paths to the base station before their lifecycles end. The suitable enhancement of sensor nodes would create more paths to the base station, which can prolong the network lifetime. However, when the number of nodes is 250 or more, many nodes will play the role of relay to achieve more paths, which causes the decline of lifecycle because of more energy consumption. It is worthy to notice that parameters n and d make have influence on the lifetime of REDP and TPEDP, which in Figure 3(b) is less than Figure 3(a), and the larger the n and d, the more the computation cost of the two protocols. However, the increase of the values of n and d cannot affect the decline of ECC too much, even if it also brings more computational overhead. Compared with TPEDP, REDP causes more energy consumption because of the requirements for more communication rounds and the cost of reselection of new cluster-headers for TP.

Figure 3

Comparisons of network lifetime among REDP, TPEDP, and ECC.

7.4. Extended Multiparty Computation

The flexibility characteristics of the TPEDP and REDP protocols make them conveniently transform from two-party distance computation to multi-party distance computation. We suppose that there are totally m nodes in WSNs, and they can be denoted by $U_1,U_2,\dots ,U_m$ and hold their secret inputs $P_1,P_2,\dots ,P_m$ , respectively, where $P_1=\left\{p_{11},p_{12},\dots ,p_{1n}\right\},\dots ,P_m=\{p_{m1},p_{m2},\dots ,p_{mn}\}$ are all n-dimensional vectors. In a security multiparty distance protocol, any one of the nodes $U_i$ ( $i=\mathrm{1,2},\dots ,m$ ) expects that it can achieve the correct distance value with any other node $U_j$ ( $j=\mathrm{1,2},\dots ,m$ & $i\ne j$ ) without release of its secret; however $U_i$ cannot obtain any privacy from $U_j$ . So the output phase can be described as follows: $f(U_i,U_j)$ is the final result that denotes Euclidean distance ${\left|U_i{U}_j\right|}^2$ , $U_i$ grasps $f_{U_i}$ , and $U_j$ keeps $f_{U_j}$ . Equation (4) shows the relationship among those symbols:

$$\begin{array}{cc}& f_{U_i}=f\left(U_i,U_j\right)+f_{U_j}.\end{array}$$

(34)

At last, $U_i$ declares $f_{U_i}$ and $U_j$ reveals $f_{U_j}$ , and they share the resulting $f(U_i,U_j)$ according to (34).

The details of calculation are determined by the specific protocol. If $U_1,U_2,\dots ,U_m$ select their respective random number denoted by ${\theta }_1,{\theta }_2,\dots ,{\theta }_m$ in the calculation procedure, ${\theta }_i={\left|U_i{U}_j\right|}^2+{\theta }_j$ can be used to represent the final result that keeps the same form of (34). For example, another participant (holds vector R and random number r) other than Node A and Node B can easily enjoy the implement of the two proposed protocols, which need to be upgraded simply, and the results would be shared by the form of $u={\left|\mathit{P}\mathit{Q}\right|}^2+v$ , $u={\left|\mathit{P}\mathit{R}\right|}^2+r$ and $v={\left|\mathit{Q}\mathit{R}\right|}^2+r$ .

8. Conclusions

Wireless sensor networks make communication and computation between humans and other things become a research hotspot. Two novel secure two-party protocols for distance computation are presented in this paper, designed to address the scenarios of privacy-preservation of location information in an encounter between Node A and Node B. The first proposed protocol, the TPEDP, involves a semihonest TP that protects the location of all participants from a passive attacker inside or outside the network. The problem of nonexistence of a suitable TP in wireless sensor networks was considered. The second protocol lacks a third party. The REDP, which benefits from randomization method, can be used to acquire the correct results of distance between two nodes securely. Compared to the similar protocols, the two proposals, TPEDP and REDP, performed more satisfactorily on the efficiency including rounds of communication, computation, and data type.

However, the assumption of the semihonest model is only suitable for certain scenarios, those that can resist only passive attacks. Some protocols secure against the malicious adversary model have been proposed especially for privacy-preserving data applications [20, 25]. However, these techniques are expensive in both communication and computation costs. In the future, the design of efficient protocols that can resist active or malicious attacks may remain challenging.