CN115200603B - Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage - Google Patents

Abstract

The invention discloses a navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage. The method includes: an LBS service provider initializes a homomorphic encryption scheme; users use anonymous camouflage algorithms to generate anonymous camouflage areas; The road network information of the anonymous camouflaged area randomly selects the camouflaged point of departure and the camouflaged point of the destination that meet the camouflage distance L near the departure point, and simultaneously plans the route from the real departure point to the camouflaged departure point; the cloud service provider plans a set of candidate routes, At the same time, request real-time road condition information from the LBS service provider; the cloud service provider further calculates the cost of the candidate route group, uses the comparison operation of fully homomorphic encryption, and transmits the ciphertext comparison result to the LBS service provider; selects the most The optimal route is connected locally with the route in the camouflage area to generate the final travel route. The invention adopts fully homomorphic encryption and anonymous camouflage technology to realize high-quality navigation service privacy protection.

Description

Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage

technical field

The invention belongs to the technical field of navigation services, and in particular relates to a navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage.

Background technique

In order to achieve the privacy protection of navigation services, many schemes have been proposed by predecessors, and these schemes are robust to the privacy inference of origin, destination, and navigation routes. These schemes achieve the required robustness by adopting existing techniques such as data encryption or exploiting the specific structure of the route planning problem. Common privacy protection schemes for navigation services in the prior art are as follows:

(1) Privacy Information Retrieval (PIR): PIR ensures that query users submit query requests to the database on the server, and complete the query under the condition that the user query privacy information is not leaked, that is, the server does not know the user's specific query information and information during the process. The retrieved data item. Using this technology, the user needs to have a structural diagram of the road network on his own client, access the weight of the path through PIR, and generate a navigation route on the local client. However, this approach requires the full cooperation of the service provider to support the protocol. The navigation service privacy scheme based on privacy information retrieval has the following two main disadvantages: 1. The privacy information retrieval technology is time-consuming and expensive, and with the update of road conditions, LBS (Location-Based Service) service providers need to spend a lot of energy Maintain the database; 2. This solution requires a high degree of cooperation from LBS service providers to build a general privacy protection query framework, which has a high degree of cooperation with LBS service providers; 3. This solution requires users to do path planning calculations on the local client. Hosts larger map frame data.

(2) Distributed solution: This solution is based on the idea of segmenting the complete route into segments. By segmenting the entire route, the origin and destination of different segments are assigned to different LBS service providers. request, and finally return the results of the request to the user, and the user aggregates all the routes to generate the final navigation route. Privacy protection based on distributed navigation services has the following two main disadvantages: 1. Multiple independent and non-colluding LBS service providers are required to perform distributed calculations on multi-segment route requests, and the conditions are strict; 2. Each LBS The service provider only processes its own request, which is only a local optimal route for each segment. The route obtained after the user's local aggregation is not the global optimal route, which will sacrifice part of the service quality.

Contents of the invention

The main purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and provide a navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage. While realizing the privacy protection of navigation services, it is also possible to use the LBS service provider's Real-time traffic data, improve service quality, and generate safe and high-quality navigation routes for users.

In order to achieve the above object, the present invention adopts the following technical solutions:

In the first aspect, the present invention provides a navigation service privacy protection method based on homomorphic encryption and anonymous masquerading, comprising the following steps:

The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, private key sk, and evaluation key evk, and then sends the initialization parameters params, public key pk, and evaluation key evk to the cloud service provider for initialization;

The user uses an anonymous camouflage algorithm to generate an anonymous camouflage area respectively, and requests the anonymous camouflage area from the cloud service provider, and the cloud service provider transmits the road network information of the anonymous camouflage area to the user after receiving the anonymous camouflage area request; The masquerading area includes the anonymous masquerading area of the departure place and the anonymous masquerading area of the destination; the anonymous masquerading algorithm is transformed based on the K-anonymous algorithm, and the K online users whose preconditions of the K-anonymous algorithm are satisfied are changed into randomly generated K coordinate;

According to the road network information of the anonymous masquerading area, the user randomly selects the departure masquerading point and the destination masquerading point that meet the masquerading distance L near the departure point, and sends the departure masquerading point and destination masquerading point to the cloud service provider; at the same time, according to the anonymous The road network information of the camouflaged area, synchronously planning the route from the real departure point to the disguised departure point;

After receiving the masquerading point at the departure point and the masquerading point at the destination, the cloud service provider plans a set of candidate routes { w ₁ ,..., w _n }, where w ₁ ,..., w _n represent a candidate route and serve LBS at the same time The provider requests that the candidate route involves the real-time traffic information of the road network area R, and the LBS service provider encrypts the real-time traffic information of the road network area R with a fully homomorphic public key and transmits it to the cloud service provider;

The cloud service provider receives the encrypted real-time road condition information in the road network area R, and further calculates the cost of the previous candidate route group according to the real-time road condition information, obtains the route cost after the ciphertext, and uses the comparison operation of fully homomorphic encryption , compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider;

The LBS service provider receives the ciphertext comparison result, decrypts it with the private key sk, sorts the comparison results, obtains the serial number of the best path, and transmits the serial number to the user ; ₁ ,…, w _n } the best route selected in the local and camouflaged area to generate the final travel route.

As a preferred technical solution, the anonymous camouflage algorithm is specifically:

The user has the latitude and longitude coordinates S of the departure point, the latitude and longitude coordinates D of the destination, and sets the camouflage distance L and camouflage level K;

Based on the camouflage distance L and camouflage level K, the user generates K-1 random coordinates at a radius L.

As a preferred technical solution, according to the road network information of the anonymous camouflage area, the route from the real departure point to the disguised departure point is planned synchronously, specifically:

After the map is loaded locally, the conventional path planning algorithm inside the user system is called to generate two navigation routes from the real departure point to the fake departure point and from the fake destination to the real destination.

As a preferred technical solution, the candidate route is planned by the following method:

According to the strategic requirements of path planning, generate a route with the shortest distance, and then generate a route with the shortest time according to the speed limit of the road, these are the two basic routes;

Add customized strategies, including avoiding tolls, minimizing fees, not taking expressways or expressways, and then generating multiple customized routes;

Under the premise of the user's permission, the cloud service provider will optimize the route after the end of the service. The specific process is as follows:

When the user allows it, collect and store all requested path planning {disguised origin S, disguised destination D, initiation time T} triplet set;

At the same time T on the second day, the cloud service provider requests the LBS service provider to plan the route of {disguised origin S, disguised destination D} to generate a navigation route;

After receiving the route from the LBS service provider, compare the route selected by yourself according to the strategy, find out the difference, find out the map node after the first bifurcation, and mark it as a relay point;

When the route within this range is involved next time, the relay point will be added to the route planning to generate multiple sets of navigation routes passing through the relay point {pretend origin, relay point 1, camouflage destination}, ..., {pretend departure point , relay point n, masquerade destination}.

As a preferred technical solution, the LBS service provider transmits the real-time road condition information of the road network area R to the cloud service provider using fully homomorphic public key encryption, specifically:

The LBS service provider receives the live map information request from the road network area R of the cloud service provider, and the LBS service provider encrypts the road condition weight of each edge in the corresponding map data structure, and other data structures of the entire map will not be encrypted , and then transmit the real-time traffic map data structure of the road network area R to the cloud service provider for analysis and use by the cloud service provider.

As a preferred technical solution, according to the real-time road condition information, the cost of the previous candidate route group is further calculated to obtain the route cost after the ciphertext, specifically:

After the cloud service provider receives the weight information from the LBS service provider, it calculates the cost of each route in the candidate route group { w ₁ ,..., w _n } generated by itself. The cost calculation is specifically: each candidate The route is connected by multiple edges , and the distance length of the i -th edge edge _i is encrypted with a public key into the ciphertext length information enc ( edge _i . len ), and then this edge in the map data from the LBS service provider is obtained The ciphertext weight information enc ( edge _i . weight ) of _i , the ciphertext multiplication of enc ( edge _i . len ) and enc ( edge _i . weight ) is performed to obtain the cost of the edge edge _i , and then each edge The ciphertext multiplication results are accumulated to obtain the candidate route;

After all routes are calculated, the final cost result of each route is obtained.

As a preferred technical solution, the LBS service provider receives the ciphertext comparison result, uses the private key sk to decrypt, and sorts the comparison results to obtain the serial number of the best path, specifically:

According to different privacy requirements, when the privacy level is K, when the number of current candidate routes N>2K, the "elimination system" is adopted:

(1) Two pairs of candidate routes in the candidate route group use the ciphertext comparison algorithm to perform ciphertext comparison operations to obtain N/2 comparison result ciphertexts, and transmit the comparison result ciphertexts to the LBS service provider for decryption;

(2) The LBS service provider decrypts and obtains N/2 comparison result plaintexts, and then transmits the comparison results in plaintext to the cloud service provider, and the cloud service provider eliminates routes with excessive costs;

(3) Let N=N/2, if N>2K, repeat the process of steps (1)-(2), if N<=2K, execute step (4);

个比较结果密文,构造开销的比较结果序列；(4) Comparing the cost of candidate routes in the candidate route group, each candidate route is compared with other candidate routes in turn to obtain

A comparison result ciphertext, constructing an overhead comparison result sequence;

个开销的比较结果序列后，根据明文比较结果，对N条候选路线进行排序，获得开销最小候选路线的序号。(5) The LBS service provider is decrypting

After the comparison result sequences of the costs, the N candidate routes are sorted according to the plaintext comparison results, and the serial number of the candidate route with the minimum cost is obtained.

In the second aspect, the present invention also provides a navigation service privacy protection system based on homomorphic encryption and anonymous masquerading, including a preprocessing module, a masquerading area generation module, a masquerading point selection module, a path planning module, a route cost calculation module and a path Generate modules;

The preprocessing module is used to initialize the homomorphic encryption scheme by the LBS service provider, generate the public key pk, the private key sk and the evaluation key evk, and then send the initialization parameter params, the public key pk and the evaluation key evk to The cloud service provider initializes;

The camouflage area generating module is used for the user to generate an anonymous camouflage area using an anonymous camouflage algorithm, and request the anonymous camouflage area to the cloud service provider. After the cloud service provider receives the anonymous camouflage area request, the path of the anonymous camouflage area The network information is transmitted to the user; the anonymous camouflage area includes the anonymous camouflage area of departure and the destination anonymous camouflage area; the anonymous camouflage algorithm is transformed based on the K-anonymity algorithm, and K Online users change to randomly generated K coordinates;

The masquerading point selection module is used for the user to randomly select a departure masquerading point and a destination masquerading point satisfying the masquerading distance L near the departure point according to the road network information of the anonymous masquerading area, and set the departure masquerading point and destination masquerading point Send it to the cloud service provider; at the same time, according to the road network information of the anonymous camouflage area, the route from the real departure point to the fake departure point is planned synchronously;

The path planning module is used for the cloud service provider to plan a set of candidate routes { w ₁ ,..., w _n } after receiving the departure masquerading point and the destination masquerading point, where w ₁ ,..., w _n represent A candidate route, and at the same time request the LBS service provider for the real-time road condition information of the road network area R involved in the candidate route, and the LBS service provider encrypts the real-time road condition information of the road network area R with a fully homomorphic public key and transmits it to the cloud service provider;

The route cost calculation module is used for the cloud service provider to receive the encrypted real-time road condition information of the road network area R, and further calculate the cost of the previous candidate route group according to the real-time road condition information, and obtain the route cost after the ciphertext , use the comparison operation of fully homomorphic encryption to compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider;

The path generation module is used for the LBS service provider to receive the ciphertext comparison result, use the private key sk to decrypt, and sort the comparison results to obtain the serial number of the best path, and transmit the serial number to the user; the user receives the serial number , connect the best route selected from the candidate route group { w ₁ ,…, w _n } in the local area and the route in the camouflage area to generate the final travel route.

In a third aspect, the present invention also provides an electronic device, the electronic device comprising:

at least one processor; and,

a memory communicatively coupled to the at least one processor; wherein,

The memory stores computer program instructions executable by the at least one processor, the computer program instructions are executed by the at least one processor, so that the at least one processor can perform the homomorphic encryption based and anonymous masquerading navigation service privacy protection method.

In a fourth aspect, the present invention also provides a computer-readable storage medium storing a program, and when the program is executed by a processor, the method for protecting navigation service privacy based on homomorphic encryption and anonymous masquerade is implemented.

Compared with the prior art, the present invention has the following advantages and beneficial effects:

1. The LBS service provider needs a high degree of cooperation in the previous scheme. Now it only needs to use fully homomorphic encryption to encrypt its own business data and decrypt the ciphertext comparison results sent by the cloud service provider, which is more conducive to the LBS service provider. remodel.

2. In the previous distributed technical solution, the route returned to the user is not the global optimal route (non-real-time road conditions). In this invention, a group of candidate routes can be obtained based on the road network diagram in the cloud service provider, including the route under non-real-time road conditions. The global optimal route is further optimized by using real-time traffic data to obtain a less expensive route scheme under real-time traffic conditions.

3. High security. The previous scheme needs to resist the collusion between LBS service providers. In the present invention, even if there is a conspiracy between the LBS service provider and the cloud computing platform, the disguised starting point will bring great difficulty to the derivation of the LBS service provider. At the same time, because the navigation service is extremely time-sensitive, even if it is exhaustive, it will lose its meaning due to too long calculation.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present application, the drawings that need to be used in the description of the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the present application. For those skilled in the art, other drawings can also be obtained based on these drawings without creative effort.

Fig. 1 is the flowchart of the navigation service privacy protection method based on homomorphic encryption and anonymous masquerading according to an embodiment of the present invention;

Fig. 2 is a block diagram of a navigation service privacy protection system based on homomorphic encryption and anonymous masquerading according to an embodiment of the present invention.

FIG. 3 is a structural diagram of an electronic device according to an embodiment of the present invention.

Detailed ways

In order to enable those skilled in the art to better understand the solutions of the present application, the technical solutions in the embodiments of the present application will be clearly and completely described below in conjunction with the drawings in the embodiments of the present application. Apparently, the described embodiments are only some of the embodiments of this application, not all of them. Based on the embodiments in this application, all other embodiments obtained by those skilled in the art without making creative efforts belong to the scope of protection of this application.

Reference in this application to an "embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the present application. The occurrences of this phrase in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. It is understood explicitly and implicitly by those skilled in the art that the embodiments described in this application can be combined with other embodiments.

Homomorphic encryption: Homomorphic encryption is an encryption algorithm that allows specific forms of algebraic operations on the ciphertext, and then decrypts the resulting ciphertext to obtain the result of the same operation on the plaintext. With the help of homomorphic encryption, it is possible to protect Realize the operation of the data while keeping the privacy confidential.

Anonymous masquerading: Anonymous masquerading refers to the anonymity of the identity and the disguise of the location, so as to confuse the requester and the location.

Navigation service: It is used to find a series of effective paths to transfer objects from the origin to the destination. This patent specifically refers to the problem of urban road network planning and navigation.

The realization of navigation service privacy protection scheme is to apply privacy protection technology to navigation service, so the efficiency, effect and security of path planning are closely related to the adopted privacy protection scheme. Common navigation service privacy protection schemes such as privacy information retrieval and distributed computing have their shortcomings in terms of computing time overhead and the quality of generated navigation routes. At the same time, there is no explanation for the participation of the most important real-time traffic data in navigation services. The real-time traffic data of the LBS service provider, as important commercial data, needs to be encrypted when it is calculated on a third-party platform to prevent commercial data leakage and lose its unique commercial status brought about by data services. The present invention hopes that while realizing the privacy protection of the navigation service, the real-time road condition data of the LBS service provider can also be used to improve the service quality and generate safe and high-quality navigation routes for users.

The present invention introduces a third-party semi-honest cloud service, and the third-party semi-honest cloud service owns road network data of cities including distance information between road network nodes. After fully homomorphically encrypting the LBS service provider's traffic data and anonymously disguising the user's location request, the third-party semi-honest cloud service is used to calculate the best route to provide users with travel privacy protection. Homomorphic encryption technology can perform specific arithmetic operations on ciphertext with extremely high security, which is very suitable for encrypting commercial traffic data of LBS service providers.

The fully homomorphic encryption scheme used in the present invention is the CKKS scheme. The CKKS scheme was proposed by Cheon et al. in 2017. It supports the encryption of floating-point numbers and complex numbers, and is very suitable for computing scenarios of traffic data. The CKKS homomorphic encryption scheme contains 8 main functions, the following are their detailed definitions:

1. KeyGen(λ): Input security parameter λ, generate ciphertext modulus q _L , and then generate integer h, P and real number σ by λ and q _L . Then take h as the Hamming weight, select a vector from {-1,0,1} ^N as s, select a from R _qL , select a' from R _{P qL} , and use σ ² as the variance of Gaussian distribution to generate Two random numbers e and e'; according to the above parameters, generate private key sk, public key pk and evaluation key evk:

和比例因子Δ，输出一个对应的明文多项式m∈R。2. Ecd(z,Δ): Input a message vector

and scaling factor Δ, output a corresponding plaintext polynomial m ∈ R .

。3. Dcd(m,Δ): Input a plaintext polynomial m ∈ R and scale factor Δ, and output the corresponding

.

4. Enc(m, pk): Input plaintext polynomial m and public key pk, first select vector v from {-1,0,1} ^N , and then generate two random numbers e ₁ with σ ² as the variance of Gaussian distribution and e ₂ , output ciphertext:

5. Dec(c, sk): Input ciphertext c = ( b, a ) and private key sk, output plaintext m':

6. Add(c ₁ ,c ₂ ): Input two ciphertexts c ₁ and c ₂ , and output the sum of ciphertexts c _add :

7. Mult(c ₁ ,c ₂ ,evk): Input two ciphertexts c ₁ =( b ₁ , a ₁ ) and c ₂ =( b ₂ , a ₂ ), set d=( d ₀ , d ₁ , d ₂ )=( b ₁ b ₂ , a ₁ b ₂ + a ₂ b ₁ , a ₁ a ₂ ) modq _l , d represents the product of two ciphertexts, and outputs the relinearized form of d:

运算符表示舍入到最近的整数。in

operator indicates rounding to the nearest integer.

：输入一个密文c，将其密文模数由q _l 变为

，一般用在密文乘法之后的线性化步骤中：8,

: Input a ciphertext c, change its ciphertext modulus from q _l to

, generally used in the linearization step after ciphertext multiplication:

In the present invention, after calculating a group of routes, the third-party semi-honest cloud service will perform an aggregation operation with the fully homomorphically encrypted commercial traffic data to generate the route cost under the ciphertext of the group of routes. Then, a fully homomorphic comparison operation is performed on different ciphertext route costs to select the optimal route. If the ciphertext is subtracted directly, and the LBS service provider decrypts it, and then determines the comparison result based on the difference, then the LBS service provider may use the difference to calculate the route. Therefore, a fully homomorphic comparison operation must be implemented. In the end, the comparison result under the ciphertext is only 1 or 0 or -1, that is, greater than, equal to, or less than, so that the LBS service provider cannot infer the route.

。本发明利用符号函数的复合多项式逼近来实现比较运算，通过寻找合适的有理函数f，对f的多次复合，即

来接近符号函数，从而实现高效CKKS的全同态比较运算。对f的分析可以得到以下核心性质：1、f(-x)=- f(x)；2、 f(1)=1；3、

；求解得到以下ｆ的函数：

，通过合适的复合计算即可逼近符号函数。CKKS fully homomorphic supports addition and multiplication operations under ciphertext, so it is better at polynomial calculations than logical operations including comparisons. However, the comparison operation can be realized by polynomial approximation to make up for this weakness. Since the sign function and the comparison function are actually computationally equivalent, that is

. The present invention utilizes the compound polynomial approximation of sign function to realize comparison operation, by searching for suitable rational function f , to the multiple compound of f , namely

To approach the sign function, so as to realize the fully homomorphic comparison operation of efficient CKKS. The analysis of f can get the following core properties: 1. f (- x )=- f ( x ); 2. f (1)=1; 3.

; Solve to get the following function of f:

, the symbolic function can be approximated by a suitable compound calculation.

Anonymous camouflage algorithm: In the actual navigation process, the departure destination sent by the user is often not a node in the road network graph, but is positioned according to the latitude and longitude of the departure place and destination. The LBS service provider finds the nearest node in the road network graph according to the received latitude and longitude, so as to plan the path between the two nodes. According to this characteristic, the present invention proposes an anonymous camouflage algorithm: this algorithm is transformed based on the K-anonymity algorithm, and essentially changes the K online users whose preconditions of the algorithm are met into randomly generated K coordinates:

1. The user has the longitude and latitude coordinates S of the departure point, the longitude and latitude coordinates D of the destination, sets the camouflage distance L, and the camouflage level K.

2. Based on the camouflage distance L and camouflage level K, the user generates K random locations at a radius L.

3. For example, for the departure place, the user uses the K-anonymity algorithm f(S, K, L) to obtain the four latitude and longitude coordinates of the anonymous masquerading rectangular area.

It can be understood that the user uses these four latitude and longitude coordinates to send a request to the third-party cloud service to obtain the road network information within the rectangular area formed by the four coordinates. Users obtain anonymous masquerading areas and randomly build masquerading nodes. For the camouflaged area generated by this algorithm, even if the algorithm is made public, it is extremely difficult for the service provider to deduce the user’s original latitude and longitude positioning information, and the navigation service is time-sensitive

Based on the above-mentioned fully homomorphic encryption scheme and logical operation supplements, coupled with anonymous camouflage technology, the specific content of the LBS service provider, cloud service provider and users of the present invention is:

LBS service provider: In this system, the LBS service provider has huge real-time traffic data and is responsible for generating a fully homomorphic encryption key, encrypting the real-time traffic data of the LBS service provider and delivering it to the cloud service provider for calculation. In addition, it is also responsible for decrypting the comparison result of the ciphertext, and then transmitting the order of optimal path selection to the user.

Cloud service provider: The third-party semi-honest cloud computing service platform, which has the basic information of the map road network, is responsible for initially generating a set of candidate routes, and further calculates the precise cost of each route through the encrypted road condition information transmitted by the LBS service provider. Afterwards, the route overhead under the ciphertext is compared separately using the comparison operation of fully homomorphic encryption, and each group of comparison results is handed over to the LBS service provider for decryption. At the same time, the generated candidate routes are also transmitted to the user.

User: The user is responsible for disguising the location, sending a request to the cloud service provider for the disguised location, receiving the candidate route group generated by the cloud service provider, and then receiving the best route number provided by the LBS service provider, and selecting the best route by himself. route.

As shown in Figure 1, the navigation service privacy protection method based on homomorphic encryption and anonymous masquerading in this embodiment includes the following specific steps:

S1. The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, private key sk, and evaluation key evk, and then sends the initialization parameters params, public key pk, and evaluation key evk to the cloud service provider for initialization.

Furthermore, the cloud service provider uses the CKKS fully homomorphic encryption scheme to initialize relevant encryption parameters, and the process is as follows:

KeyGen(λ): Input security parameter λ, generate ciphertext modulus q _L , and then generate integer h, P and real number σ by λ and q _L . Then take h as the Hamming weight, select a vector from {-1,0,1} ^N as s, select a from R _qL , select a' from R _{P qL} , and use σ ² as the variance of Gaussian distribution to generate Two random numbers e and e'; according to the above parameters, generate private key sk, public key pk and evaluation key evk:

S2. The user uses the anonymous masquerading algorithm to generate the departure anonymous masquerading area and the destination anonymous masquerading area respectively, and requests this area from the cloud service provider.

Further, the anonymous masquerading algorithm is specifically:

The user has the latitude and longitude coordinates S of the departure point, the latitude and longitude coordinates D of the destination, and sets the camouflage distance L and camouflage level K;

Based on the camouflage distance L and camouflage level K, the user generates K-1 random coordinates at a radius L.

Furthermore, this embodiment utilizes Kalnis’s article published in 2007 to publish an algorithm for generating anonymous space regions based on the concept of K-anonymity. Even if the algorithm publishes the generation method, it is difficult for the acquirer of the anonymous space to calculate the generator’s coordinate location.

S3. The cloud service receives the anonymous masquerading area request, and transmits the road network information of the area to the user.

S4. According to the road network information of the anonymous masquerading area, the user randomly selects a masquerading point near the departure point that satisfies the masquerading distance l, and sends it to the cloud service provider. At the same time, according to the road network information of the anonymous camouflage area, the route from the real departure point to the disguised departure point is planned synchronously.

Further, according to the road network information of the anonymous camouflage area, the route from the real departure point to the disguised departure point is planned synchronously, specifically:

Because the generated anonymous masquerading area is stored on the user end and the map range is small, after the map is loaded locally, the routine path planning algorithm inside the user system is called to generate the route from the real departure point to the masquerading departure point and from the masquerading destination to the Two navigation routes to real destinations.

S5. The cloud service provider receives the disguised origin and destination and plans a group of candidate routes { w ₁ ,..., w _n } for the request; at the same time, it requests the LBS service provider for the candidate routes involving the road network area R Real-time traffic information.

Further, candidate routes are planned in the following way:

First, according to the strategic requirements of path planning, a route with the shortest distance is generated, and then a route with the shortest time is generated according to the speed limit of the road. These are the two basic routes;

Secondly, add customized strategies, including avoiding tolls, minimizing fees, not taking expressways or expressways, and then generating multiple routes;

In addition, under the premise of the user's permission, the cloud service provider will optimize the route after the end of the service. The specific process is as follows:

When the user allows it, collect and store all requested path planning {disguised origin S, disguised destination D, initiation time T} triplet set;

At the same time T on the second day, the cloud service provider requests the LBS service provider to plan the route of {disguised origin S, disguised destination D} to generate a navigation route;

After receiving the route from the LBS service provider, compare the route selected by yourself according to the strategy, find out the difference, find out the map node after the first bifurcation, and mark it as a relay point;

When it comes to the route within this range next time, add this relay point to the route planning, such as {pretend origin, relay point 1, camouflage destination}, ..., {pretend departure point, relay point n, camouflage destination }, the generated sets of navigation routes passing through relay points.

S6. The LBS service provider encrypts and transmits the real-time road condition information of the region R to the cloud service provider using a fully homomorphic public key.

Further, the LBS service provider transmits the real-time road condition information of the road network area R to the cloud service provider using fully homomorphic public key encryption, specifically:

The LBS service provider receives the live map information request from the road network area R of the cloud service provider, and the LBS service provider encrypts the road condition weight of each edge in the corresponding map data structure, and other data structures of the entire map will not be encrypted , and then transmit the real-time traffic map data structure of the road network area R to the cloud service provider for analysis and use by the cloud service provider.

S7. The cloud service provider receives the encrypted real-time road condition information in the road network area R, and according to the real-time road condition information, further calculates the cost of the previous candidate route group, obtains the route cost after the ciphertext, and uses the fully homomorphic encryption Comparison operation, compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider.

。Further, after the cloud service provider receives the weight information from the LBS service provider, it calculates the cost of each candidate route in the candidate route group { w ₁ ,..., w _n } generated by itself. The cost calculation method It is: sequentially take out the route w _i (a route is connected by multiple edges ), sequentially encrypt the distance length of the i- th edge edge _i with a public key into the ciphertext length information enc ( edge _i . len ), and then obtain The ciphertext weight information enc ( edge _i . weight ) of this edge edge _i in the map data structure from the LBS service provider, the two do the ciphertext multiplication enc ( edge _i . len )* enc ( edge _i . weight ), Get the cost of edge _i in this segment; then add up the ciphertext multiplication results of each edge to get the cost of route w _i

.

After all the routes are calculated, the final cost result (ciphertext state) of each route can then be obtained.

S8. The LBS service provider receives the ciphertext comparison result, decrypts it with the private key, sorts the comparison results, obtains the serial number of the best path, and transmits the serial number to the user.

,分别代表小于，等于，大于。比较结果必须在在解密后次才能得出。Ciphertext comparison algorithm:

, representing less than, equal to, and greater than, respectively. The comparison result must be obtained after decryption.

Further, the LBS service provider receives the ciphertext comparison result, uses the private key sk to decrypt, and sorts the comparison results to obtain the serial number of the best path, specifically:

According to different privacy requirements, when the privacy level is K, when the number of current candidate route groups N>2K, the "elimination system" is adopted:

传输给LBS服务商进行解密；(1) The candidate routes in the candidate route group use the ciphertext comparison algorithm to perform ciphertext comparison operation in pairs, and obtain N/2 comparison result ciphertexts, and compare the result sequence

Transmission to the LBS service provider for decryption;

(2) The LBS service provider decrypts and obtains N/2 comparison result plaintexts, and then transmits the comparison results in plaintext to the cloud service provider, and the cloud service provider eliminates routes with excessive costs;

(3) Let N=N/2, if N>2K, repeat the process of steps (1)-(2); if N<=2K, execute step (4);

个比较结果密文,构造结果序列

；(4) Comparing the cost of the routes in the route group with each route once, we can get

A comparison result ciphertext, construct the result sequence

;

个比较结果序列后，根据明文比较结果，对N条路线进行排序，获得开销最小路线的序号。(5) The LBS service provider is decrypting

After comparison result sequences, sort the N routes according to the plaintext comparison results, and obtain the serial number of the route with the least cost.

S9. After receiving the serial number, the user connects the best route selected from the candidate route group { w ₁ ,..., w _n } in the local area and the route in the camouflaged area to generate a final travel route.

The present invention supports the characteristics of ciphertext addition and ciphertext multiplication by means of fully homomorphic encryption technology, realizes the integration of the encrypted data of the LBS service provider, and further improves the service quality of route planning, and can also ensure the confidentiality of the commercial data of the LBS service provider sex. In addition, the anonymous camouflage algorithm is used to ensure that the user's travel location is camouflaged, and the camouflage effect is realized for the third-party semi-honest cloud service provider, which increases the difficulty of reverse tracking of the third-party semi-honest cloud service. At the same time, the cloud service provider only acts as an intermediate platform for computing and is responsible for completing the computing tasks in the entire system.

It should be noted that for the foregoing method embodiments, for the sake of simplicity of description, they are expressed as a series of action combinations, but those skilled in the art should know that the present invention is not limited by the described action sequence, because Certain steps may be performed in other orders or simultaneously in accordance with the present invention.

Based on the same idea as the navigation service privacy protection method based on homomorphic encryption and anonymous masquerade in the above embodiments, the present invention also provides a navigation service privacy protection system based on homomorphic encryption and anonymous masquerade, which can be used to implement the above-mentioned method based on Homomorphic encryption and anonymous masquerade privacy protection method for navigation services. For the convenience of description, in the schematic structural diagram of the embodiment of the navigation service privacy protection system based on homomorphic encryption and anonymous masquerade, only the parts related to the embodiment of the present invention are shown. Those skilled in the art can understand that the illustrated structure does not constitute Definitions of devices may include more or fewer components than shown, or combinations of certain components, or different arrangements of components.

Please refer to Fig. 2, in another embodiment of the present application, a navigation service privacy protection system 100 based on homomorphic encryption and anonymous masquerade is provided, the system includes a preprocessing module 101, a masquerading area generating module 102, a masquerading point Selection module 103, path planning module 104, route cost calculation module 105 and path generation module 106;

The preprocessing module 101 is used to initialize the homomorphic encryption scheme by the LBS service provider, generate the public key pk, the private key sk and the evaluation key evk, and then send the initialization parameters params, the public key pk and the evaluation key evk Initialize the cloud service provider;

The masquerading area generation module 102 is used for the user to generate an anonymous masquerading area using an anonymous masquerading algorithm, and request the anonymous masquerading area to the cloud service provider. After the cloud service provider receives the anonymous masquerading area request, the anonymous masquerading area The road network information is transmitted to the user; the anonymous camouflage area includes the anonymous camouflage area of departure and the anonymous camouflage area of the destination; the anonymous camouflage algorithm is transformed based on the K-anonymity algorithm, and the K-anonymity algorithm precondition is satisfied K Online users change to randomly generated K coordinates;

The masquerading point selection module 103 is used for the user to randomly select a departure masquerading point and a destination masquerading point satisfying the masquerading distance L near the departure point according to the road network information of the anonymous masquerading area, and masquerading the departure masquerading point and destination Points are sent to the cloud service provider; at the same time, according to the road network information of the anonymous camouflage area, the route from the real departure point to the disguised departure point is planned synchronously;

The path planning module 104 is used for the cloud service provider to plan a set of candidate routes { w ₁ ,..., w _n } after receiving the departure masquerade point and the destination masquerade point, and at the same time request the LBS service provider for the candidate routes For the real-time traffic information of the road network area R, the LBS service provider encrypts the real-time traffic information of the road network area R with a fully homomorphic public key and transmits it to the cloud service provider;

The route cost calculation module 105 is used for the cloud service provider to receive the encrypted real-time road condition information of the road network area R, and further calculate the cost of the previous candidate route group according to the real-time road condition information, and obtain the route after the ciphertext Overhead, use the comparison operation of fully homomorphic encryption to compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider;

The path generation module 106 is used for the LBS service provider to receive the ciphertext comparison result, use the private key sk to decrypt, and sort the comparison results to obtain the sequence number of the best path, and transmit the sequence number to the user; The sequence number connects the best route selected from the candidate route group { w ₁ ,..., w _n } in the local area and the route in the camouflage area to generate the final travel route.

It should be noted that the navigation service privacy protection system based on homomorphic encryption and anonymous masquerading of the present invention corresponds to the navigation service privacy protection method based on homomorphic encryption and anonymous masquerading of the present invention. The technical features and beneficial effects described in the embodiment of the disguised navigation service privacy protection method are applicable to the embodiment of the navigation service privacy protection based on homomorphic encryption and anonymous masquerading. For details, please refer to the description in the method embodiment of the present invention , which will not be repeated here, and is hereby declared.

In addition, in the implementation of the navigation service privacy protection system based on homomorphic encryption and anonymous masquerading in the above-mentioned embodiments, the logical division of each program module is only an example. Or considering the convenience of software implementation, the above-mentioned function distribution is completed by different program modules, that is, the internal structure of the navigation service privacy protection system based on homomorphic encryption and anonymous masquerading is divided into different program modules to complete the above-described full or partial functionality.

Please refer to FIG. 3 , in one embodiment, an electronic device for implementing a navigation service privacy protection method based on homomorphic encryption and anonymous masquerade is provided, and the electronic device 200 may include a first processor 201 and a first memory 202 and bus, may also include a computer program stored in the first memory 202 and operable on the first processor 201, such as a navigation service privacy protection program 203.

Wherein, the first memory 202 includes at least one type of readable storage medium, and the readable storage medium includes a flash memory, a mobile hard disk, a multimedia card, a card-type memory (for example: SD or DX memory, etc.), a magnetic memory, Disk, CD, etc. The first storage 202 may be an internal storage unit of the electronic device 200 in some embodiments, such as a mobile hard disk of the electronic device 200 . The first memory 202 may also be an external storage device of the electronic device 200 in other embodiments, such as a plug-in mobile hard disk equipped on the electronic device 200, a smart memory card (Smart Media Card, SMC), a secure digital ( SecureDigital, SD) card, flash memory card (Flash Card), etc. Further, the first memory 202 may also include both an internal storage unit of the electronic device 200 and an external storage device. The first memory 202 can not only be used to store application software and various data installed in the electronic device 200, such as the code of the navigation service privacy protection program 203, etc., but also can be used to temporarily store data that has been output or will be output.

In some embodiments, the first processor 201 may be composed of an integrated circuit, for example, may be composed of a single packaged integrated circuit, or may be composed of multiple integrated circuits with the same function or different functions packaged, including one or A combination of multiple central processing units (Central Processing unit, CPU), microprocessors, digital processing chips, graphics processors and various control chips, etc. The first processor 201 is the control core (Control Unit) of the electronic device, which uses various interfaces and lines to connect various components of the entire electronic device, and runs or executes programs stored in the first memory 202 or modules, and call data stored in the first memory 202 to execute various functions of the electronic device 200 and process data.

FIG. 3 only shows an electronic device with components. Those skilled in the art can understand that the structure shown in FIG. 3 does not constitute a limitation to the electronic device 200, and may include fewer or more components, or combinations of certain components, or different arrangements of components.

The navigation service privacy protection program 203 stored in the first memory 202 in the electronic device 200 is a combination of multiple instructions. When running in the first processor 201, it can realize:

The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, private key sk, and evaluation key evk, and then sends the initialization parameters params, public key pk, and evaluation key evk to the cloud service provider for initialization;

The user uses an anonymous camouflage algorithm to generate an anonymous camouflage area respectively, and requests the anonymous camouflage area from the cloud service provider, and the cloud service provider transmits the road network information of the anonymous camouflage area to the user after receiving the anonymous camouflage area request; The masquerading area includes the anonymous masquerading area of the departure place and the anonymous masquerading area of the destination; the anonymous masquerading algorithm is transformed based on the K-anonymous algorithm, and the K online users whose preconditions of the K-anonymous algorithm are satisfied are changed into randomly generated K coordinate;

According to the road network information of the anonymous masquerading area, the user randomly selects the departure masquerading point and the destination masquerading point that meet the masquerading distance L near the departure point, and sends the departure masquerading point and destination masquerading point to the cloud service provider; at the same time, according to the anonymous The road network information of the camouflaged area, synchronously planning the route from the real departure point to the disguised departure point;

After the cloud service provider receives the departure masquerading point and the destination masquerading point, it plans a group of candidate routes { w ₁ ,..., w _n }, and at the same time requests the LBS service provider for the real-time traffic information of the road network area R involved in the candidate route, The LBS service provider encrypts the real-time road condition information of the road network area R with a fully homomorphic public key and transmits it to the cloud service provider;

The cloud service provider receives the encrypted real-time road condition information in the road network area R, and further calculates the cost of the previous candidate route group according to the real-time road condition information, obtains the route cost after the ciphertext, and uses the comparison operation of fully homomorphic encryption , compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider;

The LBS service provider receives the ciphertext comparison result, decrypts it with the private key sk, sorts the comparison results, obtains the serial number of the best path, and transmits the serial number to the user ; ₁ ,…, w _n } the best route selected in the local and camouflaged area to generate the final travel route.

Further, if the integrated modules/units of the electronic device 200 are realized in the form of software function units and sold or used as independent products, they may be stored in a non-volatile computer-readable storage medium. The computer-readable medium may include: any entity or device capable of carrying the computer program code, a recording medium, a U disk, a removable hard disk, a magnetic disk, an optical disk, a computer memory, and a read-only memory (ROM, Read-Only Memory) .

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be realized through computer programs to instruct related hardware, and the programs can be stored in a non-volatile computer-readable storage medium When the program is executed, it may include the processes of the embodiments of the above-mentioned methods. Wherein, any references to memory, storage, database or other media used in the various embodiments provided in the present application may include non-volatile and/or volatile memory. Nonvolatile memory can include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory. Volatile memory can include random access memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in many forms such as Static RAM (SRAM), Dynamic RAM (DRAM), Synchronous DRAM (SDRAM), Double Data Rate SDRAM (DDRSDRAM), Enhanced SDRAM (ESDRAM), Synchronous Chain Synchlink DRAM (SLDRAM), memory bus (Rambus) direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM), etc.

The technical features of the above embodiments can be combined arbitrarily. To make the description concise, all possible combinations of the technical features in the above embodiments are not described. However, as long as there is no contradiction in the combination of these technical features, they should be It is considered to be within the range described in this specification.

The above-mentioned embodiment is a preferred embodiment of the present invention, but the embodiment of the present invention is not limited by the above-mentioned embodiment, and any other changes, modifications, substitutions, combinations, Simplifications should be equivalent replacement methods, and all are included in the protection scope of the present invention.

Claims (10)

1. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage is characterized by comprising the following steps:

initializing a homomorphic encryption scheme by an LBS server, generating a public key pk, a private key sk and an evaluation key evk, and then sending an initialization parameter params, the public key pk and the evaluation key evk to the cloud server for initialization;

the method comprises the steps that users respectively generate anonymous disguised regions by using an anonymous disguising algorithm, the anonymous disguised regions are requested from a cloud service provider, and the cloud service provider transmits road network information of the anonymous disguised regions to the users after receiving the anonymous disguising region requests; the anonymous disguised area comprises a departure place anonymous disguised area and a destination anonymous disguised area; the anonymous camouflage algorithm is reconstructed based on a K-anonymous algorithm, and K online users meeting the precondition of the K-anonymous algorithm are changed into K coordinates generated randomly;

the user randomly selects a departure place pseudo-assembly point and a destination pseudo-assembly point which are close to a departure point and meet the pseudo-assembly distance L according to the road network information of the anonymous pseudo-assembly area, and sends the departure place pseudo-assembly point and the destination pseudo-assembly point to a cloud service provider; synchronously planning a route from a real departure place to a camouflage departure place according to the road network information of the anonymous camouflage area;

after receiving the pseudo-erection point of the departure place and the pseudo-erection point of the destination, the cloud service provider plans a group of candidate routesw ₁ ,…，w _n Therein ofw ₁ ,…，w _n Respectively represent a candidate route and simultaneously go to LBS clothesThe service provider requests the candidate route to relate to the real-time road condition information of the road network region R, and the LBS service provider encrypts the real-time road condition information of the road network region R by using the fully homomorphic public key and transmits the encrypted information to the cloud service provider;

the cloud service provider receives the encrypted real-time road condition information of the road network region R, further calculates the cost of the previous candidate route group according to the real-time road condition information to obtain the cost of the route after the ciphertext, compares each route by using comparison operation of homomorphic encryption, and transmits a ciphertext comparison result to the LBS service provider;

the LBS facilitator receives the ciphertext comparison result, decrypts by using the private key sk, sequences the comparison result, obtains the sequence number of the optimal path, and transmits the sequence number to the user; the user receiving the serial number will check from the candidate route groupw ₁ ,…，w _n And connecting the selected optimal route in the local area with the route in the camouflage area to generate a final travel route.

2. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein the anonymous camouflage algorithm is specifically:

the user has a starting place longitude and latitude coordinate S and a destination longitude and latitude coordinate D, and sets a camouflage distance L and a camouflage level K;

the user generates K-1 random coordinates at radius L based on the camouflage distance L and the camouflage level K.

3. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein a route from a real departure place to a camouflage departure place is synchronously planned according to road network information of an anonymous camouflage area, and specifically comprises the following steps:

after the map is loaded locally, a conventional path planning algorithm in a user system is called to respectively generate two navigation routes from a real departure place to a camouflage departure place and from a camouflage destination to a real destination.

4. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein the candidate route is planned by the following method:

generating a route with the shortest distance according to the policy requirement of path planning, and generating a route with the shortest time according to the speed limit of a road, wherein the route is two basic routes;

adding a customized strategy, wherein the strategy comprises avoiding charging, minimizing cost, and not walking an expressway or an expressway, and further generating a plurality of customized routes;

on the premise that the user allows, the cloud service provider optimizes the route after the service is finished, and the specific flow is as follows:

when the user allows, collecting and storing all requested path planning { disguised starting place S, disguised destination D and initiation time T } triple sets;

at the same time T on the next day, the cloud service provider requests the LBS service provider to plan a path of the (disguised starting place S and disguised destination D) and generate a navigation route;

after receiving the route of the LBS service provider, comparing the route selected by the LBS service provider according to the strategy, finding out the difference, finding out the map node with the first bifurcation, and marking the map node as a relay point;

and when the next route in the anonymous disguised area is related, adding the relay point into the path planning to generate a plurality of groups of navigation routes passing through the relay point, wherein the navigation routes comprise a disguised starting place, a relay point 1 and a disguised destination, … and a disguised starting point, a relay point n and a disguised destination.

5. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein the LBS facilitator transmits the real-time road condition information of the road network region R to the cloud facilitator by using fully homomorphic public key encryption, and the method specifically comprises the following steps:

the LBS facilitator receives a live map information request of a road network region R from the cloud facilitator, and the LBS facilitator corresponds to each edge in the map data structureedgeThe road condition weight of the map is encrypted, and other data structures of the whole map are not addedAnd transmitting the real-time road condition map data structure of the road network region R to a cloud service provider, and analyzing and using by the cloud service provider.

6. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein the method further calculates the cost of the previous candidate route group according to the real-time road condition information to obtain the route cost after the ciphertext, and specifically comprises the following steps:

after receiving the weight information from the LBS facilitator, the cloud facilitator makes the candidate route group generated by the cloud facilitatorw ₁ ,…，w _n Performing overhead calculation on each route, wherein the overhead calculation specifically comprises the following steps: each candidate route is formed by a plurality of edgesedgeAre connected together toiEdgeedge _i The distance length is encrypted into ciphertext length information by using a public keyenc(edge _i .len) Then, the edge in the map data from the LBS facilitator is acquirededge _i Ciphertext weight information ofenc(edge _i .weight) Will beenc(edge _i .len) Andenc(edge _i .weight) Performing ciphertext multiplication to obtain the edgeedge _i The ciphertext multiplication results of each edge are accumulated to obtain the candidate route;

and after all the routes are calculated, the final overhead result of each route is obtained.

7. The navigation service privacy protection method based on homomorphic encryption and anonymous camouflage according to claim 1, wherein the LBS facilitator receives the ciphertext comparison result, decrypts by using a private key sk, and sorts the comparison result to obtain the sequence number of the optimal path, specifically:

according to different privacy requirements, when the privacy level is K, and the number N of the current candidate routes is greater than 2K, adopting 'elimination':

(1) Every two candidate routes in the candidate route group adopt a ciphertext comparison algorithm to perform ciphertext comparison operation to obtain N/2 comparison result ciphertexts, and the comparison result ciphertexts are transmitted to an LBS service provider for decryption;

(2) The LBS service provider decrypts the data to obtain N/2 comparison result plaintexts, transmits the comparison result plaintexts to the cloud service provider, and eliminates the route with excessive cost;

(3) Making N = N/2, if N >2K, repeating the process of the steps (1) - (2), if N < =2K, executing the step (4);

(4) Comparing the cost of the candidate routes in the candidate route group with other candidate routes once in turn to obtain the cost of the candidate routes in the candidate route group

Constructing a comparison result sequence of the overhead by using the comparison result ciphertext;

(5) LBS facilitator is decrypting

After the comparison result sequence of the cost, the N candidate routes are sequenced according to the comparison result of the plaintext, and the serial number of the candidate route with the minimum cost is obtained.

8. The navigation service privacy protection system based on homomorphic encryption and anonymous camouflage is characterized by comprising a preprocessing module, a camouflage area generating module, a fake node selecting module, a path planning module, a route overhead calculating module and a path generating module;

the preprocessing module is used for initializing a homomorphic encryption scheme by an LBS (location based service) provider, generating a public key pk, a private key sk and an evaluation key evk, and then sending an initialization parameter params, the public key pk and the evaluation key evk to the cloud provider for initialization;

the disguise region generating module is used for generating anonymous disguise regions by a user respectively by using an anonymous disguise algorithm, requesting the anonymous disguise regions from a cloud service provider, and transmitting road network information of the anonymous disguise regions to the user after the cloud service provider receives the request of the anonymous disguise regions; the anonymous disguised area comprises a departure place anonymous disguised area and a destination anonymous disguised area; the anonymous camouflage algorithm is modified based on a K-anonymous algorithm, and K online users meeting the precondition of the K-anonymous algorithm are changed into K coordinates generated randomly;

the pseudo-mounting point selecting module is used for the user to randomly select a starting place pseudo-mounting point and a destination pseudo-mounting point which are close to the starting point and meet the pseudo-mounting distance L according to the road network information of the anonymous pseudo-mounting area, and the starting place pseudo-mounting point and the destination pseudo-mounting point are sent to a cloud service provider; synchronously planning a route from a real departure place to a camouflage departure place according to the road network information of the anonymous camouflage area;

the path planning module is used for planning a group of candidate routes, namely a hard start route, after the cloud facilitator receives the origin pseudo-assembly point and the destination pseudo-assembly pointw ₁ ,…，w _n Therein ofw ₁ ,…，w _n Respectively representing a candidate route, simultaneously requesting real-time road condition information of the candidate route related to a road network region R from an LBS service provider, encrypting the real-time road condition information of the road network region R by the LBS service provider by using a fully homomorphic public key, and transmitting the encrypted information to a cloud service provider;

the route overhead calculation module is used for the cloud service provider to receive the encrypted real-time road condition information of the road network region R, further calculate the overhead of the previous candidate route group according to the real-time road condition information to obtain the route overhead after the ciphertext, compare each route with each other by using comparison operation of the homomorphic encryption, and transmit the ciphertext comparison result to the LBS service provider;

the path generation module is used for the LBS service provider to receive the ciphertext comparison result, decrypt the ciphertext comparison result by using a private key sk, sort the comparison result to obtain the sequence number of the optimal path, and transmit the sequence number to the user; the user receiving the serial number will check from the candidate route groupw ₁ ,…，w _n And connecting the selected optimal route in the local area with the route in the camouflage area to generate a final travel route.

9. An electronic device, characterized in that the electronic device comprises:

at least one processor; and the number of the first and second groups,

a memory communicatively coupled to the at least one processor; wherein,

the memory stores computer program instructions executable by the at least one processor to cause the at least one processor to perform a navigation service privacy protection method based on homomorphic encryption and anonymous masquerading as recited in any one of claims 1-7.

10. A computer-readable storage medium storing a program, wherein the program, when executed by a processor, implements the navigation service privacy protection method based on homomorphic encryption and anonymous masquerading of any of claims 1-7.

Images