Secure multi-party collision resolution protocol for air traffic control

Abstract

In this paper, we present a protocol for secure resolution of collision between aircraft, while their corresponding trajectories are kept private. For privacy reasons, we assume that each aircraft’s position, heading and velocity are not available to all aircraft involved in the protocol.

Our new secure protocol is based on an algorithm, which is for collision resolution of aircraft, without considering the privacy requirement. Our approach is Secure Multi-party Computation. To present our Secure Multi-party Collision Resolution Protocol, we propose a new Secure Sorting Protocol and a Modified Distributed Oblivious Transfer Protocol. We also take advantage of employing a Secure Multi-party Collision Detection Protocol, a Homomorphic Encryption, a Secure Comparison Protocol, and a Secure Maximum Finding Protocol.

To prove the security of our proposed protocol and its sub-protocols, we use the Ideal/ Real Simulation Paradigm. The communication complexity of our proposed protocol is in O (n²), and its computation complexity is in O(n). We have also done a simulation for the execution of our proposed protocol for multiple moving aircraft, to show its practicality.

Keywords

Privacy collision detection and resolution line segment intersection algorithm exact and inexact collision

1 Introduction

The idea of decentralizing in Air Traffic Control is part of the Free Flight concept. In Free Flight, each aircraft could optimally choose its own trajectory without interfering of a ground control station, while collision avoidance and safe separation between aircraft are also observed [9]. Thus, collision detection and resolution emerges as a critical issue in Free Flight.

Suppose a Free Flight condition, where there are some personal aircraft, which intend to keep their trajectories private. They also require being out of the tracking of other aircraft, otherwise collision occurs between them.

As another scenario, consider a coalition of some military aircraft, which participate in a joint airborne operation. Although they have a common mission, there are some mutual distrust between them. Hence, they want to avoid collision during the mission, without disclosing their trajectories to each other.

Therefore, collision detection and resolution is required between mutually untrusted aircraft, where each aircraft may also require that its trajectory to be kept private. To conduct such private computations, one solution is that, a trusted entity know the secret trajectories of all the participants. If no commonly trusted party is available, or no entity could be trusted enough to know the secret trajectories, then privacy will become a major concern.

In this paper, our targets are three-folded, i.e., (1) keeping the trajectories private while (2) avoiding the collision of aircraft, where (3) no trusted entity is available. Our approach to achieve such targets is employing a Secure Multi-party Computation protocol.

In a Secure Multi-party Computation scenario, multiple parties with some secret input data wish to perform joint computations on their inputs, where no commonly trusted entity is available. They also wish to preserve the privacy conditions of their secret data. Westin proposed a definition for privacy [3], which has been referred by more than 5000 papers. He defined privacy as:

“The claim of individuals, groups, or institutions

to determine for themselves when, how, and to

what extent information about them is

communicated to others.”

Secure collision detection and resolution of aircraft trajectories can be considered as a privacy-preserving problem, which might be solved through Secure Multi-party Computation where no trusted entity exists. In this problem, some travelling objects wish to prevent collision, while preserving the secrecy of their trajectories.

The notion of secure multi-party computation was first introduced by Yao [2], then, extended by Goldreich, Micali, and Wigderson [24]. In Air Traffic Control, collision detection and resolution is performed using the Traffic Collision Avoidance System (TCAS) [11]. This system is suitable for onboard collision avoidance. Therefore, it cannot be developed to long-range collision detection and resolution.

In a pioneer study, the first protocol for collision detection and resolution was proposed by Hwang and Tomlin [10]. After that, Hwang and Xue-Jun presented another collision detection and resolution protocol [33]. Also, Hafner et al. designed decentralized algorithms for two-party cooperative collision resolution [21]. Russell et al., proposed Automatic Integrated Collision Avoidance System (ICAS), which combines both ground and air collision avoidance capabilities [29]. A. Alonso-Ayuso et al. [1] proposed a Variable Neighborhood Search (VNS) approach for collision resolution of aircraft by turn changes. The basic idea of VNS consists of changing neighborhood structures in search of a better solution for resolving the collision between aircraft.

E. Mueller et al. [7] proposed a collision resolution algorithm using speed adjustment of aircraft. Their algorithm is optimized by using Markov decision process model. M. Abramson et al. [15] proposed an algorithm for alerting and guidance of aircraft to resolve the collision between them. That algorithm combines flexibility, robustness, computational efficiency, and it makes no assumptions regarding temporal or spatial scales, aircraft performance, or its sensor and communication systems. M. Soler et al. [22] proposed a trajectory plan for collision resolution of multiple- aircraft. Their proposed plan is based on optimization of the fuel consumption.

N. Durand [23] proposed an algorithm, which is a modification of Optimal Reciprocal Collision Avoidance Algorithm, which does not solve collisions for small angle converging aircraft. To avoid this behavior, Durand [23] used the directions of the semi-plane to calculate the collision resolution maneuvers. Moreover, Paielli and Erzberger proposed algorithms and software to detect and resolve collision between specified trajectories in the terminal airspace. In that paper, they specified trajectories for aircraft such that the position at any time is constrained to a defined bounding space [26]. Hao et al., proposed a method for collision detection and resolution of aircraft in the context of four-dimensional trajectory- based operation. In that paper, collision detection is performed by verifying whether the Space-Time Prism of aircraft intersect or not, and collision resolution is performed by planning a collision-free spacetime trajectory avoiding intersection [27]. Moreover, Hao et al. proposed a probabilistic collision detection approach for uncertain condition and trajectory-based operation. In that paper, they developed a method for estimating the collision probability of aircraft [28]. Yang et al., proposed a scheme for collision detection and resolution of aircraft in conditions where uncertainty affecting the future positions of aircraft. They used ellipsoidal probabilistic reach sets to detect and resolve collision between aircraft [32]. In addition, Narkawicz and Hagen proposed algorithms for collision detection between a point and a moving polygon, where the point represents an aircraft. The motivation of their proposed algorithm is providing safety for aircraft, and avoiding aircraft to enter the region with bad weather [5].

W. Wang [31] proposed a distributed collision resolution approach which is based on satisficing game theory to reduce flight collisions and improve economic efficiency. That algorithm avoids collisions by adopting the speed and heading of aircraft. Zhao et al. [25] proposed a collision resolution algorithm for multiple ADS-B equipped aircraft. In that paper, they defined a risk map to describe the risk of collision, and plan a cost-minimized trajectory. They used Dijkstra’s algorithm and index method to reduce the computational complexity.

In those researches, the detection and resolution of collisions between aircraft was investigated, while privacy was not preserved. In contrast, privacy was the main security property in the protocol proposed by Boneh et al., for real-time proximity assessment of traveling objects without predefined trajectories [4].

In many applications, the delay due to running of collision detection and resolution protocol is not acceptable and hence, the protocol proposed by Boneh et al., is not suitable to use. In a previous study, the probability of satellite collisions has been appropriately computed based on garbled circuits [6]. However, the size of the garbled circuit that they have employed, is generally too large and does not exhibit an acceptable performance for collision detection.

One of the secure protocols, proposed by Atallah and Du to solve computational geometry problems [19], addresses the secure determination of intersection between polygons. Though that protocol can be utilized to detect the collision of traveling objects at a specific time point, it is not efficient to use this protocol to determine the collision points of all trajectories.

Also, we proposed secure protocols for collision detection of two or more traveling objects such as aircraft [17].

In this paper, we present a protocol for secure resolution of collision between aircraft. The aircraft are supposed to employ the secure protocols for obtaining and resolving collision points before departure.

The proposed secure protocol is designed based on the following assumptions:

The communication between aircraft without the effect of a trusted third-party (here, Ground Stations) is possible.

The trajectories of aircraft are not complicated.

These trajectories are predefined, though they should remain secret. Although, the trajectory of an aircraft is known for itself before departure, but it should be kept secret from the other aircraft. In Free Flight, the delay due to the running of real-time collision detection and resolution protocol is not acceptable. Therefore, the aircraft desire to run the collision detection and resolution protocol before departure. Therefore, we assumed their trajectories are predefined to run the proposed protocol before the start of the flight.

The computational power of aircraft and adversaries are bounded by a polynomial time.

We have also addressed the problem of establishing security in the presence of passive adversaries (or semi-honest parties) that despite following the protocol, can analyze the message transcripts to obtain additional data.

The distance between aircraft at a certain time t should be more than d. This constraint, should be considered for the entire time period and for the entire trajectory. So, if the distance between aircraft at a certain time t are less than or equal to d, the collision occurs.

We also consider the assumptions presented in [10]. Hwang and Tomlin assumed that aircraft travel at constant altitude with varying velocities. Also, they assumed that collisions are resolved by modifying the heading or/and velocity of aircraft in the horizontal plane. They constrained the maneuver to be two straight trajectories of equal length. Moreover, they assumed that all aircraft start collision resolution maneuvers at the same time and the velocities of them along the maneuvers are constant.

Also, for privacy reasons, we assume each aircraft’s position, heading, and velocity are not available to all aircraft involved in the collision.

In summary, the contribution of this paper is proposing a secure protocol for collision resolution of aircraft based on the algorithm proposed in [10]. Our proposed protocol is presented in two steps; first, we consider an unrealistic exact collision, in which the original trajectories of all aircraft collide at a point, and then we consider a realistic inexact collision, in which collision points of multiple aircraft do not coincide.

This paper is organized as follow:

First, we briefly describe the protocol was proposed in [17], which is for secure obtaining the collision points of two or more traveling objects. We use that protocol in our proposed secure collision resolution protocol. Then, we propose a secure protocol for resolving the collision points of aircraft. Afterward, we prove the security of our proposed protocol, and we present the complexity analysis of our proposed protocol.

2 Secure multi-party collision detection protocol

Suppose that some aircraft have predefined trajectories that consist of several line segments. They want to securely know if their trajectories collide. Therefore, they should participate in a secure protocol to determine if a collision occurs.

In [16], an algorithm was proposed, which is for obtaining the intersection of some line segments. However, that algorithm is not secure. So, a secure protocol was proposed in [17], which is based on the algorithm proposed in [16], and composed of four steps. In the following, we briefly describe the protocol proposed in [17].

- The first step is the secure queue generation of line segments endpoints, where the endpoints are the event points of the algorithm. In this step, the parties want to generate a queue from their line segments’ endpoints. They securely sort their line segments’ endpoints on the y-axis from up to down. The moments at which the endpoints are seen are the only moments when the algorithm does something: the status of the queue is updated and intersection tests are done. In particular, if the endpoint is the upper endpoint of a segment, then a new segment must be added to the status. This segment is tested for intersection against the adjacent segments. If the endpoint is a lower endpoint, a segment must be deleted from the status. Therefore, the segments should only be tested when they are adjacent in the horizontal ordering. This means that any new segment is only tested against two segments. Namely, the ones immediately left and right of the upper endpoint. Later, when the next endpoint in the queue is seen, a segment can become adjacent to other segments against which it will be tested.

- In the second step of the protocol, the segments are sorted from left to right to detect the adjacent segments for intersection testing. In this step, by visiting each upper endpoint in the queue, the sorting operation should be done.

- When the adjacent segments are found, intersection testing should be performed on them.

- When an intersection occurs, the intersection point is inserted in the queue. Because the new status not only changes at endpoints of segments; it also changes at intersection points, where the order of the intersected segments changes. When this happens, the two segments that change the position against their new neighbors must be tested. This is a new type of event point of the algorithm.

One important point is that an intersection occurs when the distance between segments is less than or equal to predefined threshold d. However, when the distance is equal to 0, the status of segments changes. So, the intersection points are only inserted in the queue when the distance is equal to 0. For more clarity, some sub-protocols were proposed as building blocks of Secure Multi-party Collision Detection Protocol. These sub-protocols are Secure Queue Generation Protocol and Secure Order Finding Protocol of Line Segments. Also, the intersection of two adjacent line segments is obtained by using the protocol presented in [13]. Then, the intersection points are securely inserted by using the datastructure proposed in [30]. The details of these steps were described in [17].

3 Collision resolution protocol

In this section, we briefly describe the algorithms for resolving the collision of aircraft, which was proposed by Hwang and Tomlin in [10]. Hwang and Tomlin assumed that aircraft travel at constant altitude with varying velocities. Also, they assumed that collisions are resolved by modifying the heading or/and velocity of aircraft in the horizontal plane. They constrained the maneuver to be two straight trajectories of equal length. Moreover, they assumed that all aircraft start collision resolution maneuvers at the same time and the velocity of them along the maneuver are constant and are bounded between v _min and v _max . In [10], a collision is defined as an event, in which at all times, the distance between aircraft is less than a predefined d, which they assumed to be 5 nautical miles (5nm). In the following, we briefly describe the algorithms presented in [10]. Then, we propose our secure collision resolution protocol, which is based on the algorithms presented in [10].

Hwang and Tomlin proposed two algorithms for collision resolution in exact and inexact collisions as Algorithms 1, 2 [10]. They partitioned the space around the collision point into two circular discs of radius r_min = v_min . T and r_max = v_max . T, where T is a fixed look-ahead time. They denoted the heading change of aircraft for collision resolution as u _i . For a safe collision resolution, the minimum distance between aircraft during the resolution maneuver should be greater than or equal to d. Hwang and Tomlin assumed that the heading change of all aircraft to be the same and u = u_i (for i = 1, . . . , N). Thus, the condition for safe resolution is, where it can be used to design a protocol for collision resolution of aircraft: $\sin^{2} u \geq \frac{d^{2}}{r_{i}^{2} + r_{j}^{2} - 2 r_{i} r_{j} \cos (θ_{i} - θ_{j})}$ (1) where i, j = 1, 2, . . . , N, i ≠ j.

Then, they constructed partitions in the angular direction around the collision point and proposed a protocol for collision resolution within each partition using the value of u. In [10], they used six partitions and derived the protocol for an exact collision as below:

${\begin{matrix} 90^{\circ} \leq δ Θ_{\min} \leq 120^{\circ} \Rightarrow u \geq 0.03 = 1 . 56^{\circ} \\ 60^{\circ} \leq δ Θ_{\min} \leq 90^{\circ} \Rightarrow u \geq 0.04 = 2 . 21^{\circ} \\ 45^{\circ} \leq δ Θ_{\min} \leq 60^{\circ} \Rightarrow u \geq 0.051 = 2 . 89^{\circ} \\ 30^{\circ} \leq δ Θ_{\min} \leq 45^{\circ} \Rightarrow u \geq 0.075 = 4 . 27^{\circ} \\ 10^{\circ} \leq δ Θ_{\min} \leq 30^{\circ} \Rightarrow u \geq 0.23 = 12 . 75^{\circ} \\ 0^{\circ} \leq δ Θ_{\min} \leq 10^{\circ} \Rightarrow u \geq 0.34 = 19 . 48^{\circ} \end{matrix}$

where δΘ_min = min {|Θ_i - Θ_j| i, j = 1, 2, . . . , N ; i ≠ j} is the minimum relative angle between aircraft.

Also, they assumed that each aircraft has access to other aircraft position, velocity, and heading, and thus detects a collision. However, we assume that each aircraft’s position, heading, and velocity is not available to all aircraft involved in the collision, for privacy reasons. Therefore, the aircraft should use the Secure Multi-party Collision Detection Protocol proposed in [17], to securely obtain the collision points. Then, they need to securely resolve the collision. Thus, we propose a secure protocol for collision resolution of aircraft based on the algorithms proposed in [10], which are presented in two steps, namely exact and inexact collision. Fig.1 demonstrates an inexact collision. The algorithms of the exact and inexact collision resolution presented in [10], are as follow.

Hwang and Tomlin [10] proved the safety and correctness of the Algorithms 1 and 2 for multiple-aircraft collision resolution. We base our secure multi-party collision resolution protocol on only security enhancing these Algorithms. So, the safety and correctness of our proposed secure protocol can be proved based on the proof presented in [10].

Algorithm 1 - Exact Collision Resolution Procedure

1) Each aircraft chooses a partition based on the collision point and its angular position, computes its own heading change according to this partition, and broadcasts this heading change u_i to all other aircraft;

2) Among all heading changes broadcast including its own each aircraft chooses the smallest (i.e. $u = \min_{i} | u_{i} |, for i = 1, 2, . . ., N$ .), and follows this protocol.

Where u=heading change for collision resolution (rad)

Algorithm 2 - Inexact Collision Resolution Procedure

For i = 1, 2,..., N:

1. Select the last collision point among possible collision points as the center of collision resolution;

2. If aircraft i is not involved in the collision at the origin, adjust its velocity such that v_i = r_i/T

3. Aircraft i computes its own heading change u_exact from Algorithm 1, and computes w_i, w_max, andu;

4. Aircraft i changes its heading by u - w_i.

Where r_i=radial position of aircraft i, nautical miles (nm);

T=finite time horizon; v_i=velocity of aircraft i, (nm/sec);

w_i=heading difference between the true heading of aircraft i and the origin of reference frame; w_max = max(w_i), for i = 1, 2,..., N; and

$u = {\begin{matrix} u_{exact} . sign (w_{\max}) & u_{exact} \geq | w_{\max} | \\ w_{\max} & u_{exact} < | w_{\max} | \end{matrix}$

4 Secure multi-party collision resolution protocol

In this section, we propose a secure protocol for collision resolution of aircraft. We consider the assumptions were presented in [10], and described in section 3. Our proposed protocol for collision resolution of aircraft is based on Algorithms 1, 2.

To propose these algorithms in [10], Hwang and Tomlin have initially partitioned the airspace around the collision point into two concentric circular discs of radii r_min and r_max, where r_min = v_min . T and r_max = v_max . T, and the velocities of aircraft are in [v_min, v_max].

All the aircraft that are in the annulus between the two radii at the initiation of the collision maneuver should participate in the collision resolution algorithm. As our Secure Multi-party Collision Resolution Protocol is based on the algorithms proposed in [10], we use this assumption to determine the specific number of aircraft, which participate in our proposed secure protocol.

Also, Hwang and Tomlin assumed that each aircraft has access to other aircraft’ position, velocity, and heading. So, the privacy issue was not considered in Algorithms 1, 2. However, we want to propose a secure protocol for resolving the collision of aircraft. Thus, we assume that each aircraft has not access to others position, velocity and heading. Our proposed protocol has four steps as below. The following protocol is for secure inexact collision resolution.

1. Secure Selection of Last Collision Point 2. Velocity Adjustment 3. Secure Computation of u_exact, w_i, w_max, and u 4. Heading Change

As steps 1 and 3 require interaction between aircraft, we propose some protocols for them. In these protocols, we need Secure Multi-party Collision Detection and Secure Sorting Protocols. Therefore, we use the proposed protocol in [17] for secure detection of collision points. Also, we propose a secure protocol to sort private inputs of parties as below.

Protocol 1- Secure Sorting Protocol

Party₁ selects a random and secret number a₁. Then he encrypts a₁ with the public key of Party₂. He denotes the result as x₁. x₁ = Enc_{Party
₂} (a₁)

Party₁ sends x₁ - i₁ + 1 to Party₂. Party₂ cannot extract information about the secret value of Party₁ from x₁ - i₁ + 1. Because Party₁ selected a₁ randomly and sent it securely to Party₂

Party₂ computes b_s for s=1,...,10 as b_s = Dec_{Party
₂} (x₁ - i₁ + s). He keeps the obtained values secret.

Party₂ selects randomly a prime number p and computes c_s = b_s (mod p). The condition for selecting p is that the differences between all values of c_s should be at least 2^n-1, where n is the number of parties. If this condition is not satisfied, Party₂ selects a new ’p’ and the above condition is evaluated again.

Party₂ encrypts the values of {c₁, . . . , c_{i
₂}, c_i₂+1 + 1, c_i₂+2 + 1, . . . , c₁₀ + 1} with the public key of Party₃. Then, he sends the obtained array and the value of p to Party₃.

Party₃ decrypts the received array by his private key. Then he adds the values of the received array entries with indices from i₃ + 1 to n by 2¹ = 2.

Party₃ encrypts the obtained array from the previous step with the public key of Party₄. He sends the encrypted array to Party₄.

⋮

Party_n decrypts the received array from Party_n-1 by his private key. Then he adds the values of the received array entries with indices from i_n + 1 to n by 2^n-2.

Party_n encrypts the obtained array from the previous step with the public key of Party₁ and sends it to Party₁.

Party₁ decrypts the received array from Party_n by his private key. Then, he compares the values with index i₁ by a₁ and finds out the position of his secret value rather than other parties secret values.

In this step, all contributors need to know the results of comparison and sorting. So they should query their indices from Party₁ and compare them by array received from the previous party. However, the important point is that, Party₁ should not be aware of their index and they should just know their own indices values. Otherwise, there are information disclosure. Oblivious transfer protocol is a suitable solution for these conditions. However, by using 1-2 oblivious transfer protocol, the operation overhead of Party₁ increases. So, we propose a distributed oblivious transfer protocol, which is a modification of protocol proposed in [20]. The parties use this protocol to securely obtain their indices as below.

Party₁ arbitrarily creates the polynomial G_y (y) of degree n-2 (n ≥ 2) with the following conditions:

${\begin{matrix} G_{y} (y) = e_{n - 2} y^{n - 2} + e_{n - 3} y^{n - 3} + . . . + e_{0} = \sum_{i = 0}^{n - 2} e_{i} y^{i} \\ G_{y} (0) = m_{0} = e_{0} \\ G_{y} (1) = m_{1} = e_{n - 3} + e_{n - 4} + . . . + e_{1} + e_{0} \\ ⋮ \\ G_{y} (n - 2) = m_{n - 2} = e_{n - 2} (n - 2)^{n - 2} + . . . + e_{0} \end{matrix}$

Party₁ selects the arbitrary polynomial G_x (x) of degree k-2, where k is the number of servers. Then he creates the H(x,y), based on G_y (y) and G_x (x) where,

$\begin{matrix} G_{x} (x) & = \sum_{j = 1}^{n - 2} d_{j} x^{j}, H (x, y) = G_{x} (x) + G_{y} (y) \\ = \sum_{j = 1}^{n - 2} d_{j} x^{j} + \sum_{i = 0}^{n - 2} e_{i} y^{i} \end{matrix}$ (2)

Party₁ sets the servers indices for the value of x in H(x,y), and creates the transfer function of each server, i.e., F_i (y). Then he sends the transfer functions to the servers. $F_{i} (y) = H_{(i, y)} = \sum_{j = 1}^{n - 2} d_{j} i^{j} + \sum_{i = 0}^{n - 2} e_{i} y^{i}$ (3)

All the contributors intend to receive their messages from Party₁. So, all of them have the role of receiver in each run of this protocol. Hence, the steps 2n+7 until 2n+10 should be run by each of the contributors, independently.

The k^th receiver (Party_k) creates an arbitrary linear polynomial L_k (x) with the following condition:

$\begin{matrix} L_{k} (x) = l_{i} x, i = 1, 2, . . ., n - 2; \\ l_{i} \in (l_{1}, l_{2}, . . ., l_{n - 2}) \end{matrix}$ (4)

Then, the k^th receiver obtains M(x) by replacing L(x) instead of y in H(x,y).

M_k (x) = H (x, L_k (x)) =

$\begin{matrix} \sum_{j = 1}^{n - 2} d_{j} x^{j} + e_{0} l_{0} + e_{1} l_{1} x + e_{2} l_{2} x^{2} \\ + . . . + e_{n - 2} l_{n - 2} x^{n - 2} \end{matrix}$ (5)

K^th receiver requests for H(i, L(i)) from servers and finds M(x) after receiving the answers of the servers and doing the interpolation operations.

Each contributor declares the ordering of his secret value in the sort.

A secure sorting protocol was proposed in [18], where the first party has operation overhead. In that protocol, Party₁ and other n-1 parties run ${OT}_{1}^{2}$ .

${Party}_{1} \overset{OT}{\leftrightarrow} {Party}_{2} {Party}_{1} \overset{OT}{\leftrightarrow} {Party}_{3} . . . {Party}_{1} \overset{OT}{\leftrightarrow} {Party}_{n}$

In our proposed Secure Sorting Protocol, we propose a modified distributed oblivious transfer protocol to reduce the operation overhead of Party₁.

In the next section, we propose Protocols 2, 3 and 4, that are the building blocks of the Secure Multi-party Collision Resolution Protocol. The first step of our proposed protocol is Secure Selection of Last Collision Point, which is stated as below:

Protocol 2- Secure Selection of Last Collision Point

The aircraft select securely the last collision point based on the Secure Multi-party Collision Detection Protocol [17], which described in section 2. In each time interval [0,T], the position of the last collision point is securely obtained and announced to all aircraft.

It should be noticed thatin Secure Multi-party Collision Detection Protocol, the sweep line is in parallel with the y-axis, and moves from left to right in the direction of the x-axis.

Also, based on the Secure Multi-party Collision Detection Protocol, the last collision point and the location of traveling objects are presented in the cartesian coordinates x and y. Thus, we should convert them to polar coordinates r and Θ with r ≥ 0 and Θ in the interval (- π, π] by:

$r = \sqrt{x^{2} + y^{2}}$ and $θ = \tan^{- 1} (\frac{y}{x})$

When the last collision point is securely obtained, each aircraft i which is not involved in the collision, adjusts its velocity such that v_i = r_i/T. As we assumed that the aircraft are semi-honest and there is not any interaction between aircraft in this step, the Velocity Adjustment is securely done. Then, in the next step (step 3), each aircraft computes its heading change u_exact, w_i, w_max, and u; So, we propose Protocols 3 and 4 for secure computation of u_exact, w_max as below. Protocol 3 is for secure exact collision resolution.

Protocol 3- Secure Computation of u_exact (Exact Collision Resolution Protocol)

Each aircraft obtains its angular position Θ _i based on the last collision point, as obtained in Protocol 1.

The aircraft run Secure Sorting Protocol on their angular position Θ_i.(i.e., Secure Sorting Protocol on $Θ_{1}, Θ_{2}, \dot{.} ., Θ_{n}$ )

The aircraft apply a homomorphic encryption system on their angular position using the public key of the first aircraft. (i.e., $E_{k_{1}}^{H} (Θ_{i_{1}}), E_{k_{1}}^{H} (Θ i_{2}), . . ., E_{k_{1}}^{H} (Θ i_{n})$ )

The aircraft securely compute the difference between their encrypted angular position $E_{k_{1}}^{H} (Θ_{i})$ , and the left and right neighbors of them. Then, they compare the results using the secure protocol proposed in [8], where the result is δΘ_min,i.

In [8], a secure protocol for comparison of encrypted values was proposed, which is a building block for secure sorting of encrypted values. So,

${\begin{matrix} δ Θ_{\min, i_{2}} = \min [(E_{k_{1}}^{H} (Θ i_{2}) - E_{k_{1}}^{H} (Θ i_{1})), \\ (E_{k_{1}}^{H} (Θ i_{3}) - E_{k_{1}}^{H} (Θ i_{2}))] \\ δ Θ_{\min, i_{3}} = \min [(E_{k_{1}}^{H} (Θ i_{3}) - E_{k_{1}}^{H} (Θ i_{2})), \\ (E_{k_{1}}^{H} (Θ i_{4}) - E_{k_{1}}^{H} (Θ i_{3}))] \\ ⋮ \\ δ Θ_{\min, i_{n - 1}} = \min [(E_{k_{1}}^{H} (Θ i_{n - 1}) - E_{k_{1}}^{H} (Θ i_{n - 2})), \\ (E_{k_{1}}^{H} (Θ i_{n}) - E_{k_{1}}^{H} (Θ i_{n - 1}))] \end{matrix}$

The aircraft securely compute max (δΘ_min,i) using secure protocol proposed in [8]. Baldimtsi and Ohrimenko proposed a protocol for secure comparison and secure sorting of encrypted values [8]. Their proposed protocol relies on homomorphic properties of Paillier cryptosystem to allow parties to privately compare and swap pairs of ciphertexts, and a data independent sorting network, i.e., Batcher’s sort.

They proposed a protocol for sorting just two encrypted elements and used it as a black box for general sorting. Their general sorting protocol requires O (n (log ²n))time for sorting, where n is the total number of elements to be sorted.

In this phase of Protocol 3, we use the secure sorting protocol of encrypted values, which proposed in [8] to sort the values of δΘ_min,i, and find the maximum value of them. Where u_exact = max (δΘ_min, i) and is public for all aircraft.

Now, the aircraft should compute w_max. Therefore, they run Protocol 4 on their w_i.

Protocol 4- Secure Computation of w_max

Each aircraft has its own w_i as secret. So, all aircraft apply Protocol 1 to sort $w_{i}^{'} s$ and find the maximum value of them.

Each aircraft has the values of u_exact, w_i, w_max. Therefore, they can compute the value of u without interaction. The next step of secure inexact collision resolution protocol is heading change (step 4), where each aircraft changes its own heading by u - w_i. Thus, they securely resolve the collision. Fig. 2 and 6 demonstrates the steps of our secure proposed protocol.

Fig. 1

Inexact Collision [10]

Fig. 2

The steps of Secure Multi-party Collision Resolution Protocol

In this section, we proposed a protocol for collision resolution of aircraft based on the exact and inexact algorithms, which proposed in [10]. In the appendix, we state an example of our proposed Secure Multi-party Collision Resolution Protocol for combination of three aircraft and only for exact collision.

The following lemma is stated that our proposed protocol guarantees the safety condition.

Lemma. Our proposed Secure Multi-party Collision Resolution Protocol guarantees safety for a multiple-aircraft exact and inexact collision, as Algorithms 1 and 2, guarantees safety [10].

Discussion. Our proposed protocol is based on Algorithms 1 and 2. In our Secure Multi-party Collision Resolution Protocol, we only use Secure Multi-party Computation approach to secure performing Algorithms 1 and 2, and we did not modify these Algorithms. Thus, if Algorithms 1 and 2 guarantee the safety for an exact and inexact collision, the safety of our proposed Secure Multi-party Collision Resolution Protocol is guaranteed as well.

In the next section, we prove that our proposed Secure Multi-party Collision Resolution Protocol is secure too.

5 Security proof

The security of the Secure Multi-party Collision Detection Protocol was proved in [17]. The interested reader is referred to [17], to study the security proof of the Secure Multi-party Collision Detection Protocol and its building blocks.

In this section, we show the proposed Secure Multi-party Collision Resolution protocol is also secure, as long as its building blocks are secure. As the Multi-party Collision Resolution Protocol is composed of some building blocks, we first prove the security of them. So, we first prove the security of Protocols 1, 2, 3 and 4 as below.

Theorem 1. Protocol 1 is fully secure against t < n colluding passive adversaries, in the OT-hybrid model.

Proof. Protocol 1 is composed of two separate sections. The first section is constituted of steps 1 until 2n+3, and the other steps are in the second section. We prove the security of the first section by examining the security of information flow between parties. We should prove that we do not have any information disclosure in this section.

When Party ₁ sends x - i₁ + 1 to Party ₂ , there is not any information disclosure. Because the value of a ₁ is selected randomly and encrypted by the public key of Party ₂ . Thus, Party ₂ cannot extract information about the secret value of Party ₁ .

Also, steps 3 until 2n+3 is done by Party ₂ to Party _n consecutively. Each party receives an encrypted array from the previous party. He decrypts it by his private key. Then, he modifies the decrypted array and encrypts the modified array by the public key of the next party. Since the modified array is transferred between parties, the next party does not learn any thing about the secret value of previous party. Also, the next party cannot obtain any information about secret values of other parties. Because in each step the receiver modifies the received array and encrypts it with the public key of the next party. So, only the next party can decrypt it. Otherwise, they can obtain more information by comparing two arrays.

Now, we prove the security of the second section of Protocol 1. We prove that these steps, preserve the privacy of the sender and receiver in the modified distributed OT protocol.

In the modified distributed OT, the receiver just learns an equation of m _i , for 2 ≤ i ≤ n. Also, he does not obtain any information about m _i by receiving information from less than n-2 servers. The receiver sends queries to servers and receives the answers as $F_{i} (y) = H (i, y) = \sum_{j = 1}^{n - 2} d_{j} i^{j} + \sum_{i = 0}^{n - 2} e_{i} y^{i}$ . Therefore, he obtains n-2 equations, which is composed of the following matrices.

$\underset{A}{\underset{︸}{[\begin{matrix} i_{1}^{n - 2} & i_{1}^{n - 1} & . . . & i_{1} & y_{1}^{n - 2} & y_{1}^{n - 1} & \dot{.} . & y_{1} \\ i_{2}^{n - 2} & i_{2}^{n - 1} & . . . & i_{2} & y_{2}^{n - 2} & y_{2}^{n - 1} & . . . & y_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ i_{n - 2}^{n - 2} & i_{n - 2}^{n - 1} & . . . & i_{n - 2} & y_{n - 2}^{n - 2} & y_{n - 2}^{n - 1} & \dot{.} . & y_{n - 2} \end{matrix}]}} \times \underset{(2 n - 4) \times 1}{\underset{︸}{[\begin{matrix} d_{n - 2} \\ ⋮ \\ d_{1} \\ e_{n - 2} \\ ⋮ \\ e_{1} \end{matrix}]}} = \underset{(n - 2) \times 1}{\underset{︸}{[\begin{matrix} F_{i_{1}} (y_{i_{1}}) \\ F_{i_{2}} (y_{i_{2}}) \\ ⋮ \\ ⋮ \\ ⋮ \\ F_{i_{n - 2}} (y_{i_{n - 2}}) \end{matrix}]}}$

Now, we should show that the receiver just learn a single combination of e _i . In fact, the rows of the matrix A do not span the following vectors:

${\begin{matrix} g_{1} = (\underset{n - 3}{\underset{︸}{0, 0, . . ., 0}}, \underset{n - 3}{\underset{︸}{1, 0, . . ., 0}}) \\ g_{2} = (\underset{n - 3}{\underset{︸}{0, 0, . . ., 0}}, \underset{n - 3}{\underset{︸}{0, 1, . . ., 0}}) \\ ⋮ \\ g_{n - 2} = (\underset{n - 3}{\underset{︸}{0, 0, . . ., 0}}, \underset{n - 3}{\underset{︸}{0, . . ., 0, 1}}) \end{matrix}$

The matrix A has 2n-4 columns and n-2 rows. Consider a matrix A’ with 2n-4 rows which is formed by taking the first n-2 rows of A and appending to them the above vectors g₁ . . . g_n-2. The determinant of A’ is not zero. Therefore, the first n-2 rows of A do not span any of vectors g₁ . . . g_n-2. So, the receiver just learns a single equation of m _i for 2 ≤ i ≤ n. Also, the information from less than n-2 servers does not reveal to the receiver any information about m _i . If we consider the colluding adversaries, the Secure Sorting Protocol is secure against t < n colluding passive adversaries, if Party₁ be honest and other parties collude with each other to earn the secret value of Party₁. Because only Party₁ has the secret value a ₁ . Also, this protocol is secure against every t colluding passive adversaries, as long as, the indices of all colluding passive adversaries k are k > j (or all k < j). However, if parties earlier and after of Party_j collude with each other, they can earn the secret value of Party_j by comparison of their received array. Also, if Party _j (2 ≤ j ≤ n) be honest and other parties collude with each other to earn the secret value of Party_j, the Secure Sorting Protocol is not secure against colluding passive adversaries. It should be mentioned that in our assumptions, we considered semi-honest adversaries who follow the protocol but attempt to learn additional information. So, we assume that semi-honest adversaries do not collude with each other to learn more information.

Now, we prove the security of Protocols 2, 3 and 4 as below.

Theorem 2. Protocol 2 is fully secure against t < n colluding passive adversaries, in the OT-hybrid model.

Proof. In Protocol 2, we use the Secure Multi-party Collision Detection Protocol to securely select the last collision point. As it is proved in [17], the Secure Multi-party Collision Detection Protocol is secure. Although, Protocol 2 differs from Secure Multi-party Collision Detection Protocol in the direction of moving the sweep line, however, this does not affect the security proof of Protocol 2. Thus, if the Secure Multi-party Collision Detection Protocol is secure against semi-honest adversaries, Protocol 2 is also secure against semi-honest adversaries.

Theorem 3. Protocol 3 is fully secure against t < n colluding passive adversaries, in the OT-hybrid model.

Proof. A protocol is fully secure against t semi-honest adversaries, if the view of up to t corrupted parties in a real execution of protocol can be generated by a simulator given only the t corrupted parties’ inputs and outputs. The view of the i^th party P _i during the execution of protocol π on inputs $\vec{x}$ , is denoted ${view}_{i}^{π} (\vec{x})$ and is defined to be {x_i r_i m_{i
₁}, . . . , m_{i
_k}} where x _i is P_i input, r_i is its internal random tapes, and m _{i
_j} is the j^th message that was received by P_i in the protocol execution. Thus, in view of party P _i during execution of Protocol 3, x _i is the angular position of P _i , r _i is the random tape for generation of random values and m _{i
_j} is the result of homomorphic encryption and secure comparison of party P _j . For every I = {i₁, . . . , i_l} , we denote ${view}_{I}^{π} (\vec{x}) = ({view}_{i_{1}}^{π} (\vec{x}), \dot{.} ., {view}_{i_{l}}^{π} (\vec{x}))$ . Also, the output of all parties from an execution of π on inputs $\vec{x}$ is denoted ${output}^{π} (\vec{x})$ .

We should prove that the below expression is true, where the issue of output correctness and privacy is considered:

$\begin{matrix} (S (I, \vec{x}, f_{I} (\vec{x})), f (\vec{x}))} \\ \overset{c}{\equiv} {({view}_{I}^{π} (\vec{x}), {output}^{π} (\vec{x}))} \end{matrix}$ (6)

We are now ready to describe the simulator S, which receives the inputs and outputs of the corrupted parties. Then, it produces the view of the corrupted parties. So, S has the angular positions of the corrupted parties and the value of u_exact. As S does not have the angular positions of the honest parties, it generates some random angular positions using its random tape. Then, in the second step of Protocol 3, the simulator sorts the angular positions of the corrupted parties and random values generated instead of angular positions of the honest parties. In the third step, the simulator encrypts these values using the public key of the first party. In the fourth step, the simulator computes the difference between encrypted consecutive values. Then, it compares the results of differences between encrypted consecutive values. In the last step, the simulator computes the maximum value of them, which is u_exact.

Formally, we construct an algorithm H that receives as input an array of angular positions, where their number is equal to n. Algorithm H generates the view of the corrupted parties. If H receives the values that are generated randomly, then the generated view is the same as the partial view generated by S. In contrast, if H receives the values that are from honest and corrupted parties, then the generated view is the same as the partial view generated in a real execution. However, if H can distinguish the partial view generated by S from the partial view generated in a real execution, this contradicts our assumption that the points of arrays instead of angular positions of honest parties are randomly generated and the results of encryption are random values. Also, this contradicts the security assumption of comparison protocol proposed in [8].

Theorem 4. Protocol 4 is fully secure against t < n colluding passive adversaries, in the OT-hybrid model.

Proof. Protocol 4 is only composed of Secure Sorting Protocol. Hence, Protocol 4 is secure, as long as the employed Secure Sorting Protocol is secure. Moreover, if the Secure Sorting Protocol is secure against semi-honest adversaries, Protocol 4 is also secure against semi-honest adversaries.

Theorem 5. The Secure Multi-Party Collision Resolution Protocol is fully secure against semi-honest adversaries, in the OT-hybrid model.

Proof. The Secure Multi-Party Collision Resolution Protocol is fully secure in the OT-hybrid model, where OT is oblivious transfer protocol, and is done by a trusted third party.

Our proposed protocol is composed of Protocols 2, 3 and 4, where these protocols are based on three sub-functions as f (x₁, x₂, . . . , x_n), g (x₁, x₂, . . . , x_n) and h (x₁, x₂, . . . , x_n), respective to each protocols 2 to 4. We proposed three sub-protocols for f (x₁, x₂, . . . , x_n), g (x₁, x₂, . . . , x_n) and h (x₁, x₂, . . . , x_n), and denote them as π_f, π_g, π_h, where the inputs of π _g are the outputs of π _f , and the inputs of π _h are the outputs of π _g . In Theorem 2, 3 and 4, we showed the security proof of π_f, π_g, π_h. If we construct a GMW garbled circuit which consists of three protocols as π_f, π_g, π_h, we can securely perform the Secure Multi-Party Collision Resolution Protocol.

6 Complexity analysis

In this section, we present the overall complexity of our proposed protocol, where contains the communication and computation complexities. For communication complexity, we consider the number of steps and the length of transferred messages. Also, for computation complexity, we consider the computation of parties in each step of protocol. Hence, we break the operation of parties to modular exponentiation.

Accordingly, the communication and computation complexity of Secure Multi-party Collision Detection Protocol is in order of n, as mentioned in [17], where n is the number of parties. So, the overall complexity of Protocol 2, which is only composed of Secure Multi-party Collision Detection Protocol, is in order of n.

Also, Protocol 3 is composed of Protocol 1 (Secure Sorting Protocol), homomorphic encryption, secure difference and secure comparison. The communication complexity of Protocol 1 is in order of n ² . Moreover, Protocol 1 is composed of some encryption, decryption and OT operations. We can break these operations to some modular exponentiations. Therefore, the computation complexity of this protocol is in order of n.

Also, the overall complexity of homomorphic encryption of angular positions is in O(1). Because the homomorphic encryption is composed of some modular exponentiations. The homomorphic encryption should be done n times.

The overall complexity of secure difference is in O(1), where it should be done (n-1) times in the fourth step of Protocol 3. Moreover, the computation complexity of the secure comparison and sorting of encrypted values, which is constituted of Batcher’s Sort, is in O(1). The communication complexity of this operation is in order of (nlog²n) as stated in [8]. Thus, the overall complexity of Protocol 3 is in order of n², where n is the number of parties.

Protocol 4 is only composed of Protocol 1, where its overall complexity is in order of n ² . Eventually, the communication complexity of Secure Multi-party Collision Resolution Protocol is in order of n², and its computation complexity is in order of n. Table 1 demonstrates the complexity of building blocks of our Secure Multi-party Collision Resolution Protocol.

Table 1
The overall complexity of our proposed protocols

Protocol Building Blocks Communication Complexity Computation Complexity

Protocol 1 (2n+1) encryption and decryption, (n) addition, (2n) exponentiation, (n) multiplication 2n+10 transferred array with the size of n ≈ O(n²) O(n)

Protocol 2 Secure Multi-party Collision Detection Protocol [17] O(n) [17] O(n)

Protocol 3 Secure Multi-party Collision Detection Protocol [17], Secure Sorting Protocol, (n) homomorphic encryption, (n) Batcher’s Sort O(n) [17] + O(n²) + 2 × O(n) + 2 × O(nlog²n) ≈ O(n²) O(n)

Protocol 4 Secure Sorting Protocol O(n²) O(n)

Secure Multi-party Collision Resolution Protocol Protocol 2 Protocol 3 Protocol 4 O(n²) O(n)

Protocol	Building Blocks	Communication Complexity	Computation Complexity
Protocol 1	(2n+1) encryption and decryption, (n) addition, (2n) exponentiation, (n) multiplication	2n+10 transferred array with the size of n ≈ O(n²)	O(n)
Protocol 2	Secure Multi-party Collision Detection Protocol [17]	O(n) [17]	O(n)
Protocol 3	Secure Multi-party Collision Detection Protocol [17], Secure Sorting Protocol, (n) homomorphic encryption, (n) Batcher’s Sort	O(n) [17] + O(n²) + 2 × O(n) + 2 × O(nlog²n) ≈ O(n²)	O(n)
Protocol 4	Secure Sorting Protocol	O(n²)	O(n)
Secure Multi-party Collision Resolution Protocol	Protocol 2 Protocol 3 Protocol 4	O(n²)	O(n)

7 Simulation results

In this section, we present the results for the simulated execution of our collision resolution protocol. The results demonstrate that the collision between multi aircraft are resolved by employing our protocol. As mentioned earlier, r_min and r_max are the radii of two concentric circular discs around the collision point. We considered r_min = 130 nm and r_max = 250 nm. We also set the amount of the look-ahead time as T = 20 min. Then, we simulated the execution of our protocol for the resolution of collision between n aircraft. The simulation results of inexact collision resolution for 3, 4 and 5 aircraft are illustrated as follows. In the following Fig. 3, 4 and 5, the straight lines represent the initial route of the aircraft, and the dashed broken lines represent the modified routes, which resolve the collision. Moreover, the small and colored squares represent the origin of aircraft.

Fig. 3

Collision Resolution for three-aircraft

Fig. 4

Collision Resolution for four-aircraft

Fig. 5

Collision Resolution for five-aircraft

8 Conclusion

In this paper, we presented a new secure protocol to resolve a possible collision between aircraft, while keeping their trajectories private. In this paper, our targets are three-folded, i.e., (1) keeping the trajectories private while (2) avoiding the collision of aircraft, where (3) no trusted entity is available. Our approach to achieve such targets is employing a Secure Multi-party Computation protocol. To present our Secure Multi-party Collision Resolution Protocol, we proposed some new sub-protocols. We proposed a new Secure Sorting Protocol and a Modified Distributed Oblivious Transfer Protocol. We also take advantage of employing a Secure Multi-party Collision Detection Protocol, a Homomorphic Encryption, a Secure Comparison Protocol, and a Secure Maximum Finding Protocol.

We presented the security proof of our proposed protocol and the simulation results for collision resolution between three, four and five aircraft.

Validation of the collision resolution protocol with a dynamic aircraft model shows applicability of the protocol to real air traffic control problems, where a controller keeps the aircraft on the collision resolution trajectory. To control the aircraft on the resolved trajectories, applying the fuzzy controller systems, as described in [12, 14], might be useful.

As pointed out earlier, no research has been previously conducted on the secure resolution of the collision between aircraft with predefined trajectories.

In many applications, the delay due to the running of collision detection and resolution protocol is not acceptable. Therefore, we assumed the aircraft desire to run the proposed protocol before departure. Moreover, we assumed that the trajectories of aircraft are not complicated, and we can break them to some line segments. Hence, our proposed protocol is suitable and efficient for such applications. Otherwise, our proposed protocol may not be efficient, and designing a secure and efficient protocol for collision detection and resolution of moving objects with complicated and arbitrary trajectories is of interest.

Furthermore, we assumed that the computational power of adversaries is bounded by a polynomial time. Otherwise, the security of our proposed protocol could be violated. Because, the adversaries can obtain the security parameters of our proposed protocols, such as the private keys of encryption systems.

We also addressed the problem of establishing security in the presence of passive adversaries (or semi-honest parties). Utilization of GMW Compiler for such protocols can result in secure protocols against active adversaries (or malicious adversaries) [24]. However, these protocols would not be efficient for practical cases, and designing efficient collision detection and resolution protocols that are secure in the presence of malicious adversaries is still an attractive task.

Moreover, designing a secure protocol for collision detection and resolution of other moving objects, with different assumptions and requirements is of interest.

Footnotes

Appendix

The steps of our proposed Secure Multi-party Collision Resolution Protocol for inexact collision resolution of three aircraft were demonstrated in the Fig. 6. In this example, we just run the steps 1 to 4 for exact collision resolution of three aircraft.

We first set the public and private keys of Aircraft 1, Aircraft 2 and Aircraft 3. Then, we run the steps 1 to 4 (for exact collision resolution) of our proposed protocol based on the Fig. 6.

Public key of Aircraft 1: (43, 143) Private key of Aircraft 1: (7, 143)

Public key of Aircraft 2: (79, 3337) Private key of Aircraft 2: (1019, 3337)

Public key of Aircraft 3: (7, 143) Private key of Aircraft 3: (103, 143)

In our proposed Secure Sorting Protocol (Protocol 1), we use an array with the size of L, where impress on the security and performance of protocol. For simplicity, we set L=10. Thus, we set the radial position of aircraft in [1,10, 1,10].

Step 1 - Secure Multiparty Collision Detection Protocol based on the protocol proposed in [17].

Aircraft 1, Aircraft 2 and Aircraft 3 obtain θ₁, θ₂ and θ₃ based on the collision point, which were detected in Secure Multi-party Collision Detection Protocol [17]. (θ₁ = 6, θ₂ = 5, θ₃ = 7)

Step 2 - Secure Sorting Protocol on θ₁, θ₂, θ₃.

Aircraft 1: selects random x as 1234 and encrypts it with the public key of Aircraft 2.

k = Enc_{Aircraft
₂} (x) = (1234) ⁷⁹ mod 3337 = 901

Aircraft 1 → Aircraft 2: 901 - 6 + 1 = 896

Aircraft 2: y_s = Dec_{Aircraft
₂} (896 + 2) s = 1, 2, . . , 10[-6pt]

$(896)^{1019} \mod 3337 = 1059 \dot{.} ., (906)^{1019} \mod 3337 = 1311$

y_s = (1059, 1156, 2502, 2918, 385, 1234, 269, 1596, 2804, 1311)

Aircraft 2: selects p=107 and computes z_s ≡ y_s mod p

z_s = (96, 86, 41, 29, 64, 57, 82, 98, 22, 27)

Aircraft 2 → Aircraft 3: Enc_{Aircraft
₃} (z₁, z₂, z₃, z₄, z₅, z₆ + 1, z₇ + 1, z₈ + 1, z₉ + 1, z₁₀ + 1) =

$(96)^{7} \mod 143 = 112, \dot{.} . (27 + 1)^{7} \mod 143 = 63$

=(112, 70, 24, 94, 127, 20, 8, 44, 23, 63), p=107

Aircraft 3: Dec_{Aircraft
₃} (112, 70, 24, 94, 127, 20, 8, 44, 23, 63)

$(112)^{103} \mod 143 = 96, \dot{.} . (63)^{103} \mod 143 = 28$

=(96, 86, 41, 29, 64, 58, 83, 99, 23, 28)

Aircraft 3 → Aircraft 1: Enc_{Aircraft
₁} (96, 86, 41, 29, 64, 58, 83,

99 + 2, 23 + 2, 28 + 2)

$(96)^{7} \mod 143 = 112, \dot{.} ., (30)^{7} \mod 143 = 6$

(112, 70, 24, 94, 103, 20, 8, 62, 64, 134)

Aircraft 1: Dec_{Aircraft
₁} (112, 70, 24, 94, 103, 20, 8, 62, 64, 134)

$(112)^{43} \mod 143 = 96, \dot{.} . (134)^{43} \mod 143 = 30$

(96, 86, 41, 29, 64, 58, 83, 101, 25, 30)

Aircraft 1 compares the value with index θ₁ by x.

The value with index θ₁ = x + β (mod p)

58 = 57 + 1 (mod 107) while 1 =(01) and β is 2 bit

Thus, Aircraft 1 finds that his radial position is greater than the radial position of Aircraft 2 and less than the radial position of Aircraft 3. (θ₂ < θ₁ < θ₃)

Step 3 - Homomorphic Encryption of θ₁, θ₂, θ₃ using the key of Aircraft 1.

Paillier Cryptosystem:

p = 11 q = 17 n = 187 n² = 34696 g = n + 1 =188 λ = lcm (17 - 1, 11 - 1) =80

$μ = L (g . λ \mod n^{2})^{- 1} \mod n L (u) = \frac{u - 1}{n}$

$public \underline{} key = (n, g) = (187, 188)$

$private \underline{} key = (p, q, λ) = (11, 17, 80)$

Encryption: Select a random number r and compute c = g^m . rⁿ mod n²

Decryption: $m = \frac{L (c λ \mod n^{2})}{L (g λ \mod n^{2})} \mod n$ or in same expression m = L (cλ mod n²) . μ mod n

r=97

$E_{{Aircraft}_{1}}^{H} (θ_{1}) = 188^{6} . 97^{187} = 31915$

$E_{{Aircraft}_{1}}^{H} (θ_{2}) = 188^{5} . 97^{187} = 8540$

$E_{{Aircraft}_{1}}^{H} (θ_{3}) = 188^{7} . 97^{187} = 20321$

Step 4 - Calculation of $(E_{{Aircraft}_{1}}^{H} (θ_{2}) - E_{{Aircraft}_{1}}^{H}$ $(θ_{1})), (E_{{Aircraft}_{1}}^{H} (θ_{3}) - E_{{Aircraft}_{1}}^{H} (θ_{2}))$

$E_{{Aircraft}_{1}}^{H} (θ_{2}) - E_{{Aircraft}_{1}}^{H} (θ_{1}) = E_{{Aircraft}_{1}}^{H} (θ_{2} - θ_{1}) = E_{{Aircraft}_{1}}^{H} (5 - 6) = E_{{Aircraft}_{1}}^{H} (- 1) =$

$- E_{{Aircraft}_{1}}^{H} (1) = - (188^{1} . 97^{187}) \mod 34969$

= -19947

$E_{{Aircraft}_{1}}^{H} (θ_{3}) - E_{{Aircraft}_{1}}^{H} (θ_{2}) = E_{{Aircraft}_{1}}^{H} (θ_{3} - θ_{2}) = E_{{Aircraft}_{1}}^{H} (7 - 5) = E_{{Aircraft}_{1}}^{H} (2) =$

(188² . 97¹⁸⁷) mod 34969 = 8353

Step 5 - Secure Computation of max (δθ_min, i) using secure protocol proposed in [8].

$u_{exact} = \max (δ θ_{\min}, i) = {Dec}_{{Aircraft}_{1}} (\min [E_{{Aircraft}_{1}}^{H}$

$(θ_{3} - θ_{2}), E_{{Aircraft}_{1}}^{H} (θ_{2} - θ_{1})])$ =

L (-19947⁸⁰ mod 34969) =1

→ u_exact = 1

References

Alonso-Ayuso

, Escudero

L.F.

, et al., A VNS metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes, Journal of Global Optimization 63(3) (2015), 583–596, doi: 10.1007/s10898-014-0144-8

Yao

A.C.

, Protocols for secure computations, in: Proc. Foundations of Computer Science (FOCS) 1 (1982), 160–164, doi: 10.1109/SFCS.1982.88

Westin

A.F.

, Privacy and Freedom, Washington and Lee Law Review, Atheneum, New York 25(1) (1967), xvi–487.

Narayanan

, Boneh

, et al., Location Privacy via Private Proximity Testing, in: Proc. the Network and Distributed System Security Symposium (NDSS), 2011.

Narkawicz

and Hagen

, Algorithms for collision detection between a point and a moving polygon with applications to aircraft weather avoidance, 16th AIAA Aviation Technology Integration and Operations Conference (2016), 35–98, doi: 10.2514/6.2016-3598

Hemenway

, Ostrovsky

, et al., High-precision secure computation of satellite collision probabilities, in: Proc. The 10th International Conference on Security and Cryptography for Networks 9841 (2016), 169–187, doi: 10.1007/978-3-319-44618-9_9

Mueller

and Kochenderfer

, Multi-rotor aircraft collision avoidance using partially observable Markov decision processes, in: Proc. AIAA Modeling and Simulation Technologies Conference, 2016, doi: 10.2514/6.2016-3673

Baldimtsi

and Ohrimenko

, Sorting and Searching Behind the Curtain, in: Proc. the International Conference on Financial Cryptography and Data Security, Lecture Notes in Computer Science, Springer, Heidelberg 8975 (2015), 127–146, doi: 10.1007/978-3-662-47854-7_8

Hwang

, Kim

and Tomlin

, Protocol-Based Conflict Resolution for Air Traffic Control, Air Traffic Control Quarterly 15(1) (2007), 1–34, doi: 10.2514/atcq.15.1.1

10.

Hwang

, Tomlin

, Protocol Based conflict Resolution for Finite Information Horizon, in: Proc. the American Control Conference 1 (2002), 748–753, doi: 10.1109/ACC.2002.1024903

11.

Kuchar

and Drumm

, The traffic alert and collision avoidance system, Lincoln Laboratory Journal 16(2) (2007), 277–296.

12.

Qiu

, Sun

, et al., Observer-Based Fuzzy Adaptive Event-Triggered Control for Pure-Feedback Nonlinear Systems with Prescribed Performance, IEEE Transactions on Fuzzy Systems, 2019, doi: 10.1109/TFUZZ.2018.2883374

13.

Frikken

K.B.

and Atallah

M.J.

, Privacy preserving route planning, in: Proc. the 3rd ACM Workshop on Privacy in the Electronic Society (2004), 8–15, doi: 10.1109/JIOT.2014.2361016

14.

Sun

, Mou

, et al., Adaptive Fuzzy Control for Non-Triangular Structural Stochastic Switched Nonlinear Systems, IEEE Transactions on Fuzzy Systems 27(8) (2019), 1587–1601, doi: 10.1109/TFUZZ.2018.2883374

15.

Abramson

, Refai

, et al., The Generic Resolution Advisor and Conflict Evaluator (GRACE) for Detect-And-Avoid (DAA) Systems, in: Proc. 17th AIAA Aviation Technology, Integration, and Operations Conference, 2017, doi: 10.2514/6.2017-4485

16.

de Berg

, van Kreveld

, et al., Computational Geometry: Algorithms and Applications, Springer-Verlag, New York, 1997.

17.

Dehghan

and Sadeghiyan

, Privacy Preserving Collision Detection of Moving Objects, Wiley Transactions on Emerging Telelcommunications Technologies 30(3) (2018), doi: 10.1002/ett.3484

18.

Dehghan

and Sadeghyian

, An Efficient Secure Generalized Comparison Protocol, in: Proc. the 26th Iranian Conference on Electrical Engineering (ICEE), Mashhad, Iran, 2018, doi: 10.1109/ICEE.2018.8472437

19.

Atallah

M.J.

and Du

, Secure Multi-party Computational Geometry, in: Proc. the 7th International Workshop on Algorithms and Data Structures 2125 (2001), 165–179, doi: 10.1007/3-540-44634-6_16

20.

Naor

and Pinkas

, Distributed oblivious transfer, in: Proc. International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000: Advances in Cryptology, LNCS 1976 (2000), 205–219.

21.

Hafner

M.R.

, Cunningham

, et al., Cooperative collision avoidance at intersections: Algorithms and experiments, IEEE Transactions on Intelligent Transportation Systems 14(3) (2013), 1162–1175, doi: 10.1109/TITS.2013.2252901

22.

Soler

, Kamgarpour

, et al., A hybrid optimal control approach to fuel-efficient aircraft conflict avoidance, IEEE Transactions on Intelligent Transportation Systems 17(7) (2016), 1826–1838, doi: 10.1109/TITS.2015.2510824

23.

Durand

, Constant speed optimal reciprocal collision avoidance, Transportation research part C: emerging technologies 96 (2018), 366–379, doi: 10.1016/j.trc.2018.10.004

24.

Goldreich

, Micali

and Wigderson

, How to play ANY mental game, in: Proc. ACM Symposium on Theory of Computing (ACM STOC) (1987), 218–229, doi: 10.1145/28395.28420

25.

Zhao

, Wang

, et al., Multiple Aircraft Collision Avoidance Method Based on ADS-B System, in: Proc. AIAA Aviation 2019 Forum, 2019, 10.2514/6.2019-3417

26.

Paielli

R.A.

and Erzberger

, Trajectory Specification for Terminal Airspace: Conflict Detection and Resolution, Journal of Air Transportation 27(2) (2019), doi: 10.2514/1.D0132

27.

Hao

, Cheng

Sh.

, et al., multi-aircraft conflict detection and resolution method for 4-dimensional trajectory-based operation, Chinese Journal of Aeronautics 31(7) (2018), 1579–1593, doi: 10.1016/j.cja.2018.04.017

28.

Hao

, Zhang

, et al., Probabilistic Multi-Aircraft Conflict Detection Approach for Trajectory-Based Operation, Transportation Research Part C: Emerging Technologies 95 (2018), 698–712, doi: 10.1016/j.trc.2018.08.010

29.

Russell

, Andrew

, et al., Automatic collision avoidance technology, 18th Australian International Aerospace Congress, 2019, 495–503.

30.

Toft

, A Secure Priority Queue; or: On Secure Datastructures from Multi-party Computation, in: Proc. the International Conference on Information Security and Cryptology, 2013, 20–33, doi: 10.1007/978-3-319-12160-4_2

31.

Wang

, A Satisficing Game Theoretic Approach to Multi-Aircraft Collision Avoidance, in: Proc. IOP Conference Series: Materials Science and Engineering 533(1) (2019), doi: 10.1088/1757-899X/533/1/012028

32.

Yang

, Zhang

, et al., Multi-aircraft conflict detection and resolution based on probabilistic reach sets, IEEE Transactions on Control Systems Technology 25(1) (2017), 309–316, doi: 10.1109/TCST.2016.2542046

33.

XueJun

, Hwang

, et al., A hybrid distributed-centralized conflict resolution approach for multi-aircraft based on cooperative co-evolutionary, Science China Information Sciences 56(12) (2013), 1–16, doi: 10.1007/s11432-013-4836-3