CN115200603A - Navigation service privacy protection method and device based on homomorphic encryption and anonymous masquerading - Google Patents
Navigation service privacy protection method and device based on homomorphic encryption and anonymous masqueradingDownload PDFInfo
- Publication number
- CN115200603A CN115200603ACN202211106644.XACN202211106644ACN115200603ACN 115200603 ACN115200603 ACN 115200603ACN 202211106644 ACN202211106644 ACN 202211106644ACN 115200603 ACN115200603 ACN 115200603A
- Authority
- CN
- China
- Prior art keywords
- anonymous
- route
- service provider
- camouflage
- lbs
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
- G01C21/3492—Special cost functions, i.e. other than distance or default speed limit of road segments employing speed data or traffic data, e.g. real-time or historical
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L63/00—Network architectures or network communication protocols for network security
- H04L63/04—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
- H04L63/0407—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the identity of one or more communicating identities is hidden
- H04L63/0421—Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L63/00—Network architectures or network communication protocols for network security
- H04L63/04—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
- H04L63/0428—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the data content is protected, e.g. by encrypting or encapsulating the payload
- H04L63/0442—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the data content is protected, e.g. by encrypting or encapsulating the payload wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/12—Protocols specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
Landscapes
- Engineering & Computer Science (AREA)
- Remote Sensing (AREA)
- Radar, Positioning & Navigation (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Automation & Control Theory (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Health & Medical Sciences (AREA)
- General Health & Medical Sciences (AREA)
- Medical Informatics (AREA)
- Navigation (AREA)
Abstract
Translated fromChinese
Description
Translated fromChinese技术领域technical field
本发明属于导航服务的技术领域，具体涉及一种基于同态加密和匿名伪装的导航服务隐私保护方法及装置。The invention belongs to the technical field of navigation services, and in particular relates to a method and device for privacy protection of navigation services based on homomorphic encryption and anonymous masquerading.
背景技术Background technique
为了实现导航服务的隐私保护，前人提出了许多方案，这些方案对出发地、目的地、导航路线的隐私推断具有鲁棒性。这些方案通过采用现有技术（如数据加密）或利用路线规划问题的特定结构来实现所需的鲁棒性。现有技术中导航服务常见的隐私保护方案有以下几种：In order to realize the privacy protection of navigation services, many schemes have been proposed, which are robust to the privacy inference of departure, destination and navigation routes. These schemes achieve the required robustness by employing existing techniques such as data encryption or exploiting the specific structure of the route planning problem. Common privacy protection solutions for navigation services in the prior art are as follows:
（1）隐私信息检索（PIR）：PIR保证查询用户在向服务器上的数据库提交查询请求，在用户查询隐私信息不被泄漏的条件下完成查询，即在过程中服务器不知道用户具体查询信息及检索出的数据项。利用这项技术，用户本身客户端上需要有路网的结构图，通过PIR访问路径的权重，在本地客户端上生成导航路线。然而，这种方法需要服务提供商的充分合作，以支持该协议。基于隐私信息检索的导航服务隐私方案，主要有以下两点缺点：1、隐私信息检索技术在耗时上开销巨大，并且随着路况的更新，LBS（Location-Based Service）服务商需要耗费大量精力维护数据库；2、该方案需要LBS服务商的高度配合来搭建一个通用的隐私保护查询框架，对于LBS服务商的配合程度较高；3、该方案需要用户在本地客户端做路径规划计算，需要承载较大的地图框架数据。(1) Private Information Retrieval (PIR): PIR ensures that the query user submits a query request to the database on the server, and completes the query under the condition that the user's 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 structure diagram of the road network on his client, access the weight of the route through PIR, and generate a navigation route on the local client. However, this approach requires the full cooperation of service providers to support the protocol. The navigation service privacy scheme based on private information retrieval mainly has the following two shortcomings: 1. The private 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）分布式方案：该方案是基于将完整的路线进行分段请求的思想，通过将一整条路线进行分段，将不同段的出发地、目的地的分别交由不同LBS服务商进行请求，最后将请求的结果分别返回给用户，用户再将所有路线进行聚合，生成最后的导航路线。基于分布式的导航服务隐私保护，主要有以下两点缺点：1、需要多个独立的、互不串谋的LBS 服务商进行对多段路线请求进行分布式计算，条件严苛；2、各LBS服务商只处理自己获得请求，对于每一段来说只是局部最优路线，在用户本地聚合后所获得的路线并非全局最优路线，会牺牲掉一部分的服务质量。(2) Distributed scheme: This scheme is based on the idea of segmenting the complete route. By segmenting the entire route, the departure and destination of different segments are handed over 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. The privacy protection of distributed navigation services mainly has the following two shortcomings: 1. Multiple independent and non-colluding LBS service providers are required to perform distributed computing on multi-segment route requests, and the conditions are strict; 2. Each LBS The service provider only processes the requests obtained by itself. For each segment, it is only the local optimal route. The route obtained after the local aggregation of users is not the global optimal route, which will sacrifice part of the service quality.
发明内容SUMMARY OF THE INVENTION
本发明的主要目的在于克服现有技术的缺点与不足，提供一种基于同态加密和匿名伪装的导航服务隐私保护方法及装置，在实现导航服务的隐私保护同时，也能够利用LBS服务商的实时路况数据，提高服务质量，为用户生成安全优质的导航路线。The main purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and to provide a method and device for privacy protection of navigation services based on homomorphic encryption and anonymous masquerading. 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 a first aspect, the present invention provides a navigation service privacy protection method based on homomorphic encryption and anonymous disguise, comprising the following steps:
由LBS服务商进行同态加密方案的初始化、生成公钥pk、私钥sk和评估密钥evk，然后将初始化参数params、公钥pk和评估密钥evk发送给云服务商进行初始化；The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, the private key sk and the evaluation key evk, and then sends the initialization parameters params, public key pk and evaluation key evk to the cloud service provider for initialization;
用户利用匿名伪装算法分别生成出匿名伪装区域，并向云服务商请求该匿名伪装区域，云服务商收到匿名伪装区域请求后，将该匿名伪装区域的路网信息传输给用户；所述匿名伪装区域包括出发地匿名伪装区域和目的地匿名伪装区域；所述匿名伪装算法是基于K-匿名算法进行改造，将K-匿名算法前置条件满足的K个在线用户改变成随机生成的K个坐标；The user generates an anonymous disguised area by using an anonymous disguising algorithm, and requests the anonymous disguised area from the cloud service provider. After receiving the request for the anonymous disguised area, the cloud service provider transmits the road network information of the anonymous disguised area to the user; the anonymous disguised area The disguised area includes an anonymous disguised area of origin and an anonymous disguised area of the destination; the anonymous disguising algorithm is based on the K-anonymous algorithm to transform, and the K online users that satisfy the preconditions of the K-anonymous algorithm are changed into K randomly generated coordinate;
用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离L的出发地伪装点和目的地伪装点，并将该出发地伪装点和目的地伪装点发送给云服务商；同时根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线；According to the road network information of the anonymous camouflage area, the user randomly selects the departure camouflage point and the destination camouflage point that satisfy the camouflage distance L near the departure point, and sends the departure camouflage point and the destination camouflage point to the cloud service provider; The road network information of the camouflaged area can simultaneously plan the route from the real departure point to the camouflaged departure point;
云服务商收到出发地伪装点和目的地伪装点后，规划出一组候选路线{w1,…，wn}，其中w1,…，wn分别代表一条候选路线，同时向LBS服务商请求候选路线涉及路网区域R的实时路况信息，LBS服务商将路网区域R的实时路况信息利用全同态公钥加密后传输给云服务商；After receiving the masquerading point of departure and destination, the cloud service provider plans a set of candidate routes{w1 ,...,wn }, wherew1 ,...,wn represent a candidate route respectively, andserve the LBS at the same time. The candidate route requested by the merchant involves the real-time road condition information of the road network area R, and the LBS service provider encrypts the real-time road condition information of the road network area R with the fully homomorphic public key and transmits it to the cloud service provider;
云服务商收到路网区域R加密后的实时路况信息，并根据实时路况信息，对之前的候选路线组的开销进行进一步计算，得到密文后的路线开销，利用全同态加密的比较运算，将每条路线相互比较，将密文比较结果传输给LBS服务商；The cloud service provider receives the encrypted real-time road condition information of 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 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;
LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，将该序号传输给用户；用户收到序号，将从候选路线组{w1,…，wn}中选取的最佳路线在本地和伪装区域内的路线连接，生成最终的出行路线。The LBS service provider receives the ciphertext comparison result, decrypts it with the private keysk , sorts the comparison results, obtains the sequence number of the best path, and transmits the sequence number to the user;1 ,...,wn } The best route selected in the local and camouflaged areas is connected to the route to generate the final travel route.
作为优选的技术方案，所述匿名伪装算法具体为：As a preferred technical solution, the anonymous camouflage algorithm is specifically:
用户拥有出发地经纬度坐标S，目的地经纬度坐标D，设定伪装距离L、伪装等级K；The user has the longitude and latitude coordinates S of the departure place, the longitude and latitude coordinates D of the destination, and sets the camouflage distance L and the camouflage level K;
用户基于伪装距离L和伪装等级K，在半径L处生成K-1个随机坐标。The user generates K-1 random coordinates at the radius L based on the camouflage distance L and the camouflage level K.
作为优选的技术方案，所述根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线，具体为：As a preferred technical solution, according to the road network information of the anonymous disguised area, the route from the real departure place to the disguised departure place is synchronously planned, 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 routes are planned by the following methods:
根据路径规划的策略要求，生成一条距离最短的路线，再根据道路的限速生成一条用时最短的路线，这是两条基础路线；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 two basic routes;
增加定制化的策略，策略包括避免收费、费用最少、不走高速路或不走快速路，进而生成多条定制路线；Add customized strategies, including avoiding tolls, minimizing costs, 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 service ends. The specific process is as follows:
当用户允许时，收集并存储所有请求的路径规划{伪装出发地S，伪装目的地D，发起时间T}三元组集合；When the user allows, collect and store all requested path planning {disguised origin S, disguised destination D, origination time T} triplet set;
在第二天的同一时间T，由云服务商请求LBS服务商进行{伪装出发地S，伪装目的地D}的路径规划，生成导航路线；At the same time T on the next day, the cloud service provider requests the LBS service provider to plan the path of {disguised origin S, disguised destination D} to generate a navigation route;
在收到LBS服务商的路线后，对比自己根据策略选出的路线，找出不同之处，找出首次出现分叉后的地图节点，标记为中继点；After receiving the route of the LBS service provider, compare the route selected by yourself according to the strategy, find out the differences, find the map node after the first fork, and mark it as a relay point;
在下一次涉及到该范围内的路线时，将该中继点加入路径规划，生成多组经过中继点的导航路线{伪装出发地，中继点1，伪装目的地}，…，{伪装出发点，中继点n，伪装目的地}。When the route within the range is involved next time, the relay point is added to the route planning, and multiple sets of navigation routes passing through the relay point are generated {disguised departure point, relay point 1, disguised destination}, ..., {disguised departure point , relay point n, masquerading destination}.
作为优选的技术方案，所述LBS服务商将路网区域R的实时路况信息利用全同态公钥加密传输给云服务商，具体为：As a preferred technical solution, the LBS service provider encrypts and transmits the real-time road condition information of the road network area R to the cloud service provider by using a fully homomorphic public key, specifically:
所述LBS服务商收到来自云服务商的路网区域R的实况地图信息请求，LBS服务商将对应地图数据结构中每条边edge的路况权重加密，整个地图的其他数据结构不会进行加密，再将路网区域R的实时路况地图数据结构传送给云服务商，由云服务商解析使用。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 corresponding to eachedge in the map data structure, and other data structures of the entire map will not be encrypted , and then transmit the real-time road condition 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:
云服务商收到来自LBS服务商的权重信息后，将自己生成的候选路线组{w1,…，wn}中的每一条路线都进行开销计算，所述开销计算具体为：每一条候选路线由多条边edge连接起来，将第i条边edgei的距离长度利用公钥加密为密文长度信息enc(edgei.len)，再获取来自LBS服务商的地图数据中这条边edgei的密文权重信息enc(edgei.weight)，将enc(edgei.len)和enc(edgei.weight)做密文乘法运算，得到该条边edgei的开销，再将每条边的密文乘法结果累加起来，得到该条候选路线；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 {w1 ,...,wn } generated by itself. The cost calculation is specifically: each candidate route The route is connected by multipleedges , and the distance length of thei -th edgeedgei is encrypted with the public key into the ciphertext length informationenc (edgei .len ), and then the edgeedge in the map data from the LBS service provider is obtained. For the ciphertext weight informationenc (edgei .weight ) ofi , perform ciphertext multiplication operation onenc (edgei .len ) andenc (edgei .weight ) to obtain the cost of the edgeedgei , and then add each edge The ciphertext multiplication results of are accumulated to obtain the candidate route;
计算完所有路线后，得到最终每条路线的开销结果。After calculating all the routes, get the final cost result of each route.
作为优选的技术方案，所述LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，具体为：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 sequence number of the best path, specifically:
根据隐私要求不同，当隐私等级为K时，对于当前候选路线数目N>2K时，采取“淘汰制”:According to different privacy requirements, when the privacy level is K, for the current number of candidate routes N>2K, the "elimination system" is adopted:
（1）候选路线组中的候选路线两两采用密文比较算法进行密文比较运算，得到N/2个比较结果密文，将比较结果密文传输给LBS服务商进行解密；(1) The ciphertext comparison algorithm is used for each candidate route in the candidate route group to perform ciphertext comparison operation, and N/2 ciphertexts of comparison results are obtained, and the ciphertexts of the comparison results are transmitted to the LBS service provider for decryption;
（2）LBS服务商解密后得到N/2个比较结果明文，再将比较结果明文传输云服务商，云服务商将开销过大的路线进行剔除；(2) The LBS service provider decrypts and obtains N/2 plaintexts of comparison results, and then transmits the plaintexts of the comparison results to the cloud service provider, and the cloud service provider eliminates routes with excessive overhead;
（3）令N=N/2，如果N>2K，重复（1）-（2）步骤的过程，如果N<=2K,执行第（4）步；(3) Let N=N/2, if N>2K, repeat the process of steps (1)-(2), if N<=2K, execute step (4);
（4）将候选路线组中候选路线的开销，每条候选路线依次与其他候选路线比较一次，得到
（5）LBS服务商在解密
第二方面，本发明还提供了一种基于同态加密和匿名伪装的导航服务隐私保护系统，包括预处理模块、伪装区域生成模块、伪装点选取模块、路径规划模块、路线开销计算模块以及路径生成模块；In the second aspect, the present invention also provides a navigation service privacy protection system based on homomorphic encryption and anonymous disguise, including a preprocessing module, a disguised area generation module, a disguised point selection module, a path planning module, a route cost calculation module and a path generate module;
所述预处理模块，用于由LBS服务商进行同态加密方案的初始化、生成公钥pk、私钥sk和评估密钥evk，然后将初始化参数params、公钥pk和评估密钥evk发送给云服务商进行初始化；The preprocessing module is used by the LBS service provider to initialize the homomorphic encryption scheme, 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 to the The cloud service provider initializes;
所述伪装区域生成模块，用于用户利用匿名伪装算法分别生成出匿名伪装区域，并向云服务商请求该匿名伪装区域，云服务商收到匿名伪装区域请求后，将该匿名伪装区域的路网信息传输给用户；所述匿名伪装区域包括出发地匿名伪装区域和目的地匿名伪装区域；所述匿名伪装算法是基于K-匿名算法进行改造，将K-匿名算法前置条件满足的K个在线用户改变成随机生成的K个坐标；The disguised area generating module is used for the user to generate an anonymous disguised area by using an anonymous disguised algorithm, and request the anonymous disguised area from the cloud service provider. After the cloud service provider receives the anonymous disguised area request, the route of the anonymous disguised area is The network information is transmitted to the user; the anonymous disguise area includes the departure anonymous disguise area and the destination anonymous disguise area; the anonymous disguise algorithm is modified based on the K-anonymity algorithm, and K-anonymity algorithm preconditions are satisfied. Online users are changed to randomly generated K coordinates;
所述伪装点选取模块，用于用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离L的出发地伪装点和目的地伪装点，并将该出发地伪装点和目的地伪装点发送给云服务商；同时根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线；The camouflage point selection module is used for the user to randomly select a departure point camouflage point and a destination camouflage point that satisfy the camouflage distance L near the departure point according to the road network information of the anonymous camouflage area, and use the departure point camouflage point and the destination camouflage point. Send it to the cloud service provider; at the same time, according to the road network information of the anonymous disguised area, synchronously plan the route from the real departure point to the disguised departure point;
所述路径规划模块，用于云服务商收到出发地伪装点和目的地伪装点后，规划出一组候选路线{w1,…，wn}，其中w1,…，wn分别代表一条候选路线，同时向LBS服务商请求候选路线涉及路网区域R的实时路况信息，LBS服务商将路网区域R的实时路况信息利用全同态公钥加密后传输给云服务商；The route planning module is used for the cloud service provider to plan a set of candidate routes {w1 ,...,wn } after receiving the origin camouflage point and the destination camouflage point,wherew1 ,...,wnrepresent respectively A candidate route, and at the same time request the LBS service provider for the real-time road condition information of the candidate route involving the road network area R, 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;
所述路线开销计算模块，用于云服务商收到路网区域R加密后的实时路况信息，并根据实时路况信息，对之前的候选路线组的开销进行进一步计算，得到密文后的路线开销，利用全同态加密的比较运算，将每条路线相互比较，将密文比较结果传输给LBS服务商；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 groups according to the real-time road condition information, and obtain the route cost after the ciphertext. , using the comparison operation of fully homomorphic encryption, compare each route with each other, and transmit the ciphertext comparison result to the LBS service provider;
所述路径生成模块，用于LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，将该序号传输给用户；用户收到序号，将从候选路线组{w1,…，wn}中选取的最佳路线在本地和伪装区域内的路线连接，生成最终的出行路线。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 sequence number of the best path, and transmit the sequence number to the user; the user receives the sequence number , the best route selected from the candidate route group {w1 ,...,wn } connects the routes in the local and camouflaged areas 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 being executed by the at least one processor to enable the at least one processor to perform the homomorphic-based encryption and anonymous disguised navigation service privacy protection method.
第四方面，本发明还提供了一种计算机可读存储介质，存储有程序，所述程序被处理器执行时，实现所述的基于同态加密和匿名伪装的导航服务隐私保护方法。In a fourth aspect, the present invention also provides a computer-readable storage medium storing a program, which, when executed by a processor, implements the method for privacy protection of navigation services based on homomorphic encryption and anonymous disguise.
本发明与现有技术相比，具有如下优点和有益效果：Compared with the prior art, the present invention has the following advantages and beneficial effects:
1．LBS服务商在之前的方案中需要较高的配合度，现在只需要利用全同态加密，加密自己的商业数据，解密云服务商发送过来的密文比较结果即可，更利于LBS服务商进行改造。1. LBS service providers need a high degree of cooperation in the previous solution. Now they only need to use fully homomorphic encryption to encrypt their own business data and decrypt the ciphertext comparison results sent by the cloud service provider, which is more conducive to LBS service providers. Retrofit.
2. 之前的分布式技术方案，返回给用户的路线非全局最优路线（非实时路况），本发明中基于云服务商中的路网图即可一组候选路线，其中包含非实时路况下的全局最优路线，并利用实时路况数据进一步优化，得到实时路况下的一条开销较小的路线方案。2. In the previous distributed technical solution, the route returned to the user is not a globally optimal route (non-real-time road conditions). In the present invention, based on the road network map in the cloud service provider, a group of candidate routes can be used, including non-real-time road conditions. The global optimal route is obtained, and the real-time road condition data is used for further optimization to obtain a route plan with less overhead under real-time road conditions.
3．安全性高。之前的方案需要抵御LBS服务商之间的串谋，本发明即使有LBS服务商和云计算平台有串谋，经过伪装后的出发地点也会给LBS服务商的推导带来极大的难度，同时因为导航服务时效性极强，即使被穷举也会因为过长时间推算，而失去意义。3. High security. The previous scheme needs to resist the conspiracy between the LBS service providers. Even if there is a conspiracy between the LBS service provider and the cloud computing platform in the present invention, the disguised departure location 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 exhausted, it will lose its meaning because it is calculated for too long.
附图说明Description of drawings
为了更清楚地说明本申请实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。In order to illustrate the technical solutions in the embodiments of the present application more clearly, the following briefly introduces the drawings that are used in the description of the embodiments. Obviously, the drawings in the following description are only some embodiments of the present application. For those of ordinary skill in the art, other drawings can also be obtained from these drawings without creative effort.
图1为本发明实施例基于同态加密和匿名伪装的导航服务隐私保护方法的流程图；1 is a flowchart of a method for protecting navigation service privacy based on homomorphic encryption and anonymous disguise according to an embodiment of the present invention;
图2为本发明实施例基于同态加密和匿名伪装的导航服务隐私保护系统的方框图。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.
图3为本发明实施例电子设备的结构图。FIG. 3 is a structural diagram of an electronic device according to an embodiment of the present invention.
具体实施方式Detailed ways
为了使本技术领域的人员更好地理解本申请方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述。显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。In order to make those skilled in the art better understand the solutions of the present application, the following will clearly and completely describe the technical solutions in the embodiments of the present application with reference to the accompanying drawings in the embodiments of the present application. Obviously, the described embodiments are only a part of the embodiments of the present application, but not all of the embodiments. Based on the embodiments in this application, all other embodiments obtained by those skilled in the art without creative efforts shall fall within the protection scope 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 application. The appearances of the phrase in various places in the specification are not necessarily all referring to the same embodiment, nor a separate or alternative embodiment that is mutually exclusive of other embodiments. It is explicitly and implicitly understood by those skilled in the art that the embodiments described in this application may be combined with other embodiments.
同态加密：同态加密是一种加密算法，允许对密文进行特定形式的代数运算后，对结果密文进行解密，可以得到对明文进行相同运算的结果，借助同态加密，能够在保护隐私不泄露的同时实现对数据的运算。Homomorphic encryption: Homomorphic encryption is an encryption algorithm that allows a specific form of algebraic operation to be performed on the ciphertext, and then the resulting ciphertext is decrypted, and the result of performing the same operation on the plaintext can be obtained. The operation of data is realized without leakage of privacy.
匿名伪装：匿名伪装是指对身份的匿名和对位置的伪装，以达到对于请求者和位置进行混淆的目的。Anonymous masquerading: Anonymous masquerading refers to the anonymity of identity and the masquerading of location in order to obfuscate the requester and location.
导航服务：用于查找将对象从出发地转移到目的地的一系列有效路径，此专利特指城市道路网规划导航问题。Navigation service: used to find a series of efficient paths for moving objects from origin to destination, this patent specifically refers to the planning and navigation problem of urban road network.
导航服务隐私保护方案的实现是将隐私保护技术应用到导航服务中去，因此路径规划的效率、效果、安全性等与所采用的隐私保护方案密切相关。隐私信息检索、分布式计算等常见的导航服务隐私保护方案在在计算时间开销和生成的导航路线质量上都有其缺陷所在，同时针对导航服务中最重要的实时路况数据的参与并没有说明。LBS服务商的实时路况数据作为重要商业数据，交给在第三方的平台计算时需要进行加密处理，防止商业数据泄露，丧失其因数据服务带来的独有商业地位。本发明希望在实现导航服务的隐私保护同时，也能够利用LBS服务商的实时路况数据，提高服务质量，为用户生成安全优质的导航路线。The realization of the privacy protection scheme of navigation service is to apply the privacy protection technology to the navigation service, so the efficiency, effect and security of route planning are closely related to the privacy protection scheme adopted. Common privacy protection schemes for navigation services, such as private information retrieval and distributed computing, have their shortcomings in terms of computational time overhead and the quality of the 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 road condition data of LBS service providers, as important commercial data, needs to be encrypted when it is handed over to a third-party platform for calculation to prevent commercial data leakage and loss of its unique commercial status due to 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 a safe and high-quality navigation route for the user.
本发明引入第三方半诚实云服务，第三方半诚实云服务拥有城市的路网数据包括路网节点之间的距离信息。通过对LBS服务商的路况数据进行全同态加密和对用户的位置请求进行匿名伪装后，再利用第三方半诚实云服务计算出最佳的路线，为用户提供出行隐私保护。同态加密技术能够在极高的安全性下对密文进行特定的算术运算，非常适合用于加密LBS服务商的商业路况数据。The present invention introduces a third-party semi-honest cloud service, and the third-party semi-honest cloud service owns the road network data of the city, including the distance information between road network nodes. After fully homomorphic encryption of the road condition data of the LBS service provider and anonymous disguise of 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.
本发明所使用的全同态加密方案为CKKS方案。CKKS方案是由Cheon等人于2017年提出，支持对浮点数和复数的加密，非常适合用于路况数据的运算场景。CKKS同态加密方案包含8个主要的函数，以下是其详细的定义：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 operation scenarios of road condition data. The CKKS homomorphic encryption scheme contains 8 main functions, the following is its detailed definition:
1、KeyGen(λ)：输入安全参数λ，生成密文模数qL，然后由λ和qL生成整数h、P和实数σ。然后以h为汉明重量，从{-1,0,1}N选取一个向量作为s，从RqL中选取a，从RP·qL中选取a＇，以σ2为高斯分布的方差生成两个随机数e和e＇；根据上述参数，生成私钥sk、公钥pk和评估密钥evk：1. KeyGen(λ): Input the security parameter λ, generate the ciphertext modulusqL , and then generate integers h, P and real numbersσ from λ andqL . Then take h as the Hamming weight, choose a vector from {-1,0,1 }N as s, choose a fromR qL, choose a' fromRP qL , and useσ2 as the variance of the Gaussian distribution to generate Two random numbers e and e'; according to the above parameters, generate the private key sk, the public key pk and the evaluation key evk:
2、Ecd(z,Δ)：输入一个消息向量
3、Dcd(m,Δ)：输入一个明文多项式m∈R和比例因子Δ，输出对应的
4、Enc(m, pk)：输入明文多项式m和公钥pk，首先从{-1,0,1}N中选取向量v，然后以σ2为高斯分布的方差生成两个随机数e1和e2，输出密文：4. Enc(m, pk): Input the plaintext polynomial m and the public key pk, first select the vectorv from {-1,0,1}N , and then generate two random numbers e1 withσ2 as the variance of the Gaussian distribution and e2 , output the ciphertext:
5、Dec(c,sk)：输入密文c=(b，a)和私钥sk，输出明文m＇：5. Dec(c, sk): Input the ciphertextc = (b, a ) and the private key sk, and output the plaintext m':
6、Add(c1,c2)：输入两个密文c1和c2，输出密文之和 cadd：6. Add(c1 , c2 ): Input two ciphertexts c1 and c2 , and output the sum of ciphertexts cadd :
7、Mult(c1,c2,evk)：输入两个密文c1=(b1，a1)和c2=(b2，a2)，设d=(d0,d1,d2)=(b1b2,a1b2+a2b1,a1a2)modql，d表示两个密文的乘积，输出d的重线性化形式：7. Mult(c1 , c2 , evk): Input two ciphertextsc1 =(b1, a1 ) andc2 =(b2, a2 ), set d=(d0 ,d1 ,d2 )=(b1b2 ,a1b2 +a2b1 ,a1a2 )modql , d represents the product of two ciphertexts, and outputs the relinearized form of d:
其中
8、
在本发明中，第三方半诚实云服务会在计算一组路线后，与全同态加密后的商业路况数据进行聚合运算，生成该组路线的密文下的路线开销。接着对不同的密文路线开销进行全同态比较运算，选出最优路线。假如密文直接做减法，再让LBS服务商解密后，根据差值来确定比较结果，那么LBS服务商有可能利用差值推算路线。所以必须实现全同态的比较运算，最终密文下的比较结果只是1或0或-1，即大于、相等、小于，从而让LBS服务商无法推断路线。In the present invention, after calculating a set of routes, the third-party semi-honest cloud service will perform an aggregation operation with the fully homomorphically encrypted commercial road condition data to generate the route cost under the ciphertext of the set of routes. Then, a fully homomorphic comparison operation is performed on different ciphertext route costs to select the optimal route. If the ciphertext is directly subtracted, and then decrypted by the LBS service provider, the comparison result is determined according to the difference, then the LBS service provider may use the difference to calculate the route. Therefore, a fully homomorphic comparison operation must be implemented, and the comparison result under the final ciphertext is only 1 or 0 or -1, that is, greater than, equal, and less than, so that the LBS service provider cannot infer the route.
CKKS全同态支持的密文下的加法、乘法运算，因此它更擅长多项式计算，而不擅长逻辑运算包括比较。但是可以通过多项式逼近实现比较运算，来补足这方面的弱点。由于符号函数和比较函数实际在计算上是等价的，即
匿名伪装算法：在实际导航过程中，用户所发送的出发地目的地，往往并不是路网图中的节点，而是根据出发地、目的地的经纬度定位。LBS服务商根据收到经纬度在路网图中找到最近的节点，从而在两节点之间进行路径规划。本发明根据此特性，提出匿名伪装算法：本算法基于K-匿名算法进行改造，本质上将算法前置条件满足的K个在线用户改变成随机生成的K个坐标：Anonymous camouflage algorithm: In the actual navigation process, the departure and destination sent by the user are often not nodes in the road network diagram, but are located according to the latitude and longitude of the departure and destination. The LBS service provider finds the nearest node in the road network diagram according to the received latitude and longitude, so as to plan the path between the two nodes. According to this feature, the present invention proposes an anonymous camouflage algorithm: this algorithm is transformed based on the K-anonymous algorithm, essentially changing the K online users that satisfy the preconditions of the algorithm into randomly generated K coordinates:
1.用户拥有出发地经纬度坐标S，目的地经纬度坐标D，设定伪装距离L，伪装等级K。1. The user has the longitude and latitude coordinates S of the departure place, the longitude and latitude coordinates of the destination D, the set camouflage distance L, and the camouflage level K.
2.用户基于伪装距离L和伪装等级K，在半径L处生成K个随机地点。2. The user generates K random locations at the radius L based on the camouflage distance L and the camouflage level K.
3.例如对于出发地，用户利用K-匿名算法f(S,K,L)得到匿名伪装矩形区域的四个经纬度坐标。3. For example, for the starting place, the user uses the K-anonymity algorithm f(S, K, L) to obtain the four latitude and longitude coordinates of the anonymous disguised rectangular area.
可以理解的是，用户利用这四个经纬度坐标向第三方云服务发出请求，获取四个坐标构成矩形区域内的路网信息。用户获取匿名伪装区域并随机构建伪装节点。该算法生成的伪装区域，即使算法公开，服务商反推导用户原来经纬度定位信息的难度极高，且导航服务时效性较强It is understandable that the user sends a request to the third-party cloud service by using the four latitude and longitude coordinates to obtain the road network information in the rectangular area formed by the four coordinates. The user obtains an anonymous masquerading area and randomly builds masquerading nodes. For the camouflaged area generated by the algorithm, even if the algorithm is public, it is extremely difficult for the service provider to deduce the user's original latitude and longitude positioning information, and the navigation service has a strong timeliness.
基于上述全同态加密方案和逻辑运算补充，再加上匿名伪装技术，本发明LBS服务商、云服务商和用户的具体内容为：Based on the above-mentioned fully homomorphic encryption scheme and the addition of logical operations, coupled with the anonymous camouflage technology, the specific contents of the LBS service provider, cloud service provider and user of the present invention are:
LBS服务商：本系统中LBS服务商拥有庞大的实时路况数据，负责生成全同态加密的密钥，加密LBS服务商的实时路况数据交付给云服务商进行运算。另外还负责将密文比较结果解密后，将最优路径选取的次序传输给用户。LBS service provider: In this system, the LBS service provider has huge real-time road condition data, and is responsible for generating the key of fully homomorphic encryption, and encrypting the real-time road condition data of the LBS service provider and delivering it to the cloud service provider for calculation. In addition, it is also responsible for transmitting the order of optimal path selection to the user after decrypting the ciphertext comparison result.
云服务商：第三方的半诚实云计算服务平台，拥有地图路网的基本信息，负责初步生成一组候选路线，通过LBS服务商传输过来的加密路况信息，进一步计算每条路线的精准开销。之后将密文下的路线开销利用全同态加密的比较运算，分别进行比较，将每组比较结果交由LBS服务商进行解密。同时也将生成的候选路线传输给用户。Cloud Service Provider: A third-party semi-honest cloud computing service platform that 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 by the comparison operation of fully homomorphic encryption, and each group of comparison results is sent to the LBS service provider for decryption. At the same time, the generated candidate routes are also transmitted to the user.
用户：用户负责对地点进行伪装，将伪装后的地点，向云服务商发起请求，收到云服务商生成的候选路线组，随即收到LBS服务商提供的最佳路线序号，自行选取最佳路线。User: The user is responsible for disguising the location, initiates a request to the cloud service provider for the disguised location, receives the candidate route group generated by the cloud service provider, and immediately receives the best route sequence number provided by the LBS service provider, and selects the best route by himself. route.
如图1所示，本实施例基于同态加密和匿名伪装的导航服务隐私保护方法，包括下述具体步骤：As shown in Figure 1, the present embodiment based on homomorphic encryption and anonymous disguise navigation service privacy protection method, including the following specific steps:
S1、由LBS服务商进行同态加密方案的初始化、生成公钥pk、私钥sk和评估密钥evk，然后将初始化参数params、公钥pk和评估密钥evk发送给云服务商进行初始化。S1. The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, the private key sk and the evaluation key evk, and then sends the initialization parameters params, the public key pk and the evaluation key evk to the cloud service provider for initialization.
进一步的，云服务商采用CKKS全同态加密方案进行相关加密参数的初始化，流程如下：Further, the cloud service provider adopts the CKKS fully homomorphic encryption scheme to initialize the relevant encryption parameters. The process is as follows:
KeyGen(λ)：输入安全参数λ，生成密文模数qL，然后由λ和qL生成整数h、P和实数σ。然后以h为汉明重量，从{-1,0,1}N选取一个向量作为s，从RqL中选取a，从RP·qL中选取a＇，以σ2为高斯分布的方差生成两个随机数e和e＇；根据上述参数，生成私钥sk、公钥pk和评估密钥evk：KeyGen(λ): Input security parameter λ, generate ciphertext modulusqL , and then generate integer h, P and real numberσ from λ andqL . Then take h as the Hamming weight, choose a vector from {-1,0,1 }N as s, choose a fromR qL, choose a' fromRP qL , and useσ2 as the variance of the Gaussian distribution to generate Two random numbers e and e'; according to the above parameters, generate the private key sk, the public key pk and the evaluation key evk:
S2、用户利用匿名伪装算法分别生成出发地匿名伪装区域和目的地匿名伪装区域，并向云服务商请求这片区域。S2. The user generates an anonymous disguised area of origin and an anonymous disguised area of destination respectively by using an anonymous disguising algorithm, and requests the area from the cloud service provider.
进一步的，所述匿名伪装算法具体为：Further, the anonymous disguise algorithm is specifically:
用户拥有出发地经纬度坐标S，目的地经纬度坐标D，设定伪装距离L、伪装等级K；The user has the longitude and latitude coordinates S of the departure place, the longitude and latitude coordinates D of the destination, and sets the camouflage distance L and the camouflage level K;
用户基于伪装距离L和伪装等级K，在半径L处生成K-1个随机坐标。The user generates K-1 random coordinates at the radius L based on the camouflage distance L and the camouflage level K.
更进一步的，本实施例利用Kalnis在07年发表的文章中基于K-匿名概念发布了生成匿名空间区域的算法，该算法即使公布生成方法，对于匿名空间的获取方也难以计算出生成者的坐标位置。Furthermore, in this embodiment, an algorithm for generating anonymous space regions is published based on the concept of K-anonymity in an article published by Kalnis in 2007. Even if the algorithm publishes the generation method, it is difficult for the acquirer of the anonymous space to calculate the generator's value. Coordinate location.
S3、云服务收到匿名伪装区域请求，将该片区域的路网信息传输给用户。S3. The cloud service receives the anonymous disguised area request, and transmits the road network information of the area to the user.
S4、用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离l的出发地目的地伪装点，发送给云服务商。同时根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线。S4. The user randomly selects a departure destination camouflage point near the departure point that satisfies the camouflage distance l according to the road network information of the anonymous camouflage area, and sends it to the cloud service provider. At the same time, according to the road network information of the anonymous disguised area, the route from the real departure point to the disguised departure point is simultaneously planned.
进一步的，所述根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线，具体为：Further, according to the road network information of the anonymous disguised area, the route from the real departure place to the disguised departure place is synchronously planned, specifically:
因为所生成的匿名伪装区域存储在用户端且地图范围较小，在本地加载地图后，采取调用用户系统内部的常规路径规划算法，分别生成从真实出发地到伪装出发地以及从伪装目的地到真实目的地的两条导航路线。Because the generated anonymous camouflage area is stored on the user side and the map range is small, after loading the map locally, the conventional path planning algorithm inside the user system is called to generate the route from the real departure point to the camouflaged departure point and from the camouflaged destination to the Two navigation routes to the real destination.
S5、云服务商收到伪装后的出发地，目的地并为该请求，规划处一组候选路线{w1,…，wn}；同时向LBS服务商请求候选路线涉及路网区域R的实时路况信息。S5. The cloud service provider receives the disguised departure and destination and plans a set of candidate routes{w1 , . . . ,wn } for the request; at the same time, requests the LBS service provider for candidate routes involving the road network area R Real-time traffic information.
进一步的，候选路线通过下述方式规划：Further, candidate routes are planned in the following ways:
首先，根据路径规划的策略要求，生成一条距离最短的路线，再根据道路的限速生成一条用时最短的路线，这是两条基础路线；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 two basic routes;
其次，增加定制化的策略，策略包括避免收费、费用最少、不走高速路或不走快速路，进而生成多条路线；Second, add customized strategies, including avoiding tolls, minimizing costs, not taking expressways or expressways, and generating multiple routes;
此外，在用户允许的前提下，云服务商在服务结束后进行路线的优化，具体流程如下：In addition, under the premise of the user's permission, the cloud service provider will optimize the route after the service ends. The specific process is as follows:
当用户允许时，收集并存储所有请求的路径规划{伪装出发地S，伪装目的地D，发起时间T}三元组集合；When the user allows, collect and store all requested path planning {disguised origin S, disguised destination D, origination time T} triplet set;
在第二天的同一时间T，由云服务商请求LBS服务商进行{伪装出发地S，伪装目的地D}的路径规划，生成导航路线；At the same time T on the next day, the cloud service provider requests the LBS service provider to plan the path of {disguised origin S, disguised destination D} to generate a navigation route;
在收到LBS服务商的路线后，对比自己根据策略选出的路线，找出不同之处，找出首次出现分叉后的地图节点，标记为中继点；After receiving the route of the LBS service provider, compare the route selected by yourself according to the strategy, find out the differences, find the map node after the first fork, and mark it as a relay point;
在下一次涉及到该范围内的路线时，将该中继点加入路径规划，如{伪装出发地，中继点1，伪装目的地}，…，{伪装出发点，中继点n，伪装目的地}，生成的多组经过中继点的导航路线。The next time a route within this range is involved, add the relay point to the path planning, such as {disguised departure point, relay point 1, fake destination}, ..., {disguised departure point, relay point n, fake destination }, multiple groups of generated navigation routes passing through the relay point.
S6、LBS服务商将区域R的实时路况信息进行利用全同态公钥加密传输给云服务商。S6. The LBS service provider encrypts and transmits the real-time road condition information of the area R to the cloud service provider using a fully homomorphic public key.
进一步的，所述LBS服务商将路网区域R的实时路况信息利用全同态公钥加密传输给云服务商，具体为：Further, the LBS service provider encrypts and transmits the real-time road condition information of the road network area R to the cloud service provider by using a fully homomorphic public key, specifically:
所述LBS服务商收到来自云服务商的路网区域R的实况地图信息请求，LBS服务商将对应地图数据结构中每条边edge的路况权重加密，整个地图的其他数据结构不会进行加密，再将路网区域R的实时路况地图数据结构传送给云服务商，由云服务商解析使用。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 corresponding to each edge in the map data structure, and other data structures of the entire map will not be encrypted , and then transmit the real-time road condition map data structure of the road network area R to the cloud service provider for analysis and use by the cloud service provider.
S7、云服务商收到路网区域R加密后的实时路况信息，并根据实时路况信息，对之前的候选路线组的开销进行进一步计算，得到密文后的路线开销，利用全同态加密的比较运算，将每条路线相互比较，将密文比较结果传输给LBS服务商。S7. The cloud service provider receives the encrypted real-time road condition information of 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 ciphertext, and uses the fully homomorphic encryption The comparison operation compares each route with each other, and transmits the ciphertext comparison result to the LBS service provider.
进一步的，云服务商收到来自LBS服务商的权重信息后，将自己生成的候选路线组{w1,…，wn}中的每一条候选路线都进行开销计算，所述开销的计算方法为：依次取出路线wi（一条路线由多条边edge连接起来），依次将第i条边edgei的距离长度进行利用公钥加密为密文长度信息enc(edgei.len)，再获取来自LBS服务商的地图数据结构中这条边edgei的密文权重信息enc(edgei.weight)，两者做密文乘法运算enc(edgei.len)*enc(edgei.weight)，得到该段edgei的开销；再将每条边edge的密文乘法结果累加起来，即可得到路线wi的开销
计算完所有路线后，随后可以得到最终每条路线的开销结果（密文状态）。After all routes are calculated, the final per-route cost result (ciphertext state) can then be obtained.
S8、LBS服务商收到密文比较结果，利用私钥进行解密，并对比较结果进行排序，获得最佳路径的序号，将该序号传输给用户。S8. The LBS service provider receives the ciphertext comparison result, uses the private key to decrypt it, sorts the comparison result, obtains the sequence number of the best path, and transmits the sequence number to the user.
密文比较算法：
进一步的，所述LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，具体为：Further, the LBS service provider receives the ciphertext comparison result, uses the private key sk to decrypt, and sorts the comparison result to obtain the sequence number of the best path, specifically:
根据隐私要求不同，当隐私等级为K时，对于当前候选路线组数目N>2K时，采取“淘汰制”:According to different privacy requirements, when the privacy level is K, for the current number of candidate route groups N>2K, the "elimination system" is adopted:
（1）候选路线组中的候选路线两两采用密文比较算法进行密文比较运算，得到N/2个比较结果密文，将比较结果序列
（2）LBS服务商解密后得到N/2个比较结果明文，再将比较结果明文传输云服务商，云服务商将开销过大的路线进行剔除；(2) The LBS service provider decrypts and obtains N/2 plaintexts of comparison results, and then transmits the plaintexts of the comparison results to the cloud service provider, and the cloud service provider eliminates routes with excessive overhead;
（3）令N=N/2，如果N>2K，重复（1）-（2）步骤的过程；如果N<=2K,执行第（4）步；(3) Let N=N/2, if N>2K, repeat the process of steps (1)-(2); if N<=2K, execute step (4);
（4）将路线组中路线开销，每条路线比较一次，可以得到
（5）LBS服务商在解密
S9、用户收到序号，将从候选路线组{w1,…，wn}中选取的最佳路线在本地和伪装区域内的路线连接，生成最终的出行路线。S9. The user receives the sequence number, andconnects the best route selected from the candidate route group{w1 , .
本发明借助于全同态加密技术支持密文加法和密文乘法的特性，实现了对LBS服务商的加密数据整合后进一步提高路线规划的服务质量，也能保证LBS服务商的商业数据的机密性。另外利用匿名伪装算法保证用户的出行地点得到伪装，对第三方半诚实的云服务商的实现伪装效果，增加第三方半诚实云服务反向追踪的难度。同时云服务商只作为计算的中间平台，负责完成整个系统中的计算任务。The invention supports the characteristics of ciphertext addition and ciphertext multiplication by means of the fully homomorphic encryption technology, realizes the integration of the encrypted data of the LBS service provider and further improves the service quality of the 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 achieved 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 convenience of description, the foregoing method embodiments are all 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 masquerading in the above embodiment, the present invention also provides a navigation service privacy protection system based on homomorphic encryption and anonymous masquerading, which can be used to implement the above-mentioned Homomorphic encryption and anonymous masquerading for privacy protection of 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 disguise, only the part related to the embodiment of the present invention is shown. Those skilled in the art can understand that the illustrated structure does not constitute a The definition of the device may include more or fewer components than shown, or a combination of certain components, or a different arrangement of components.
请参阅图2，在本申请的另一个实施例中，提供了一种基于同态加密和匿名伪装的导航服务隐私保护系统100，该系统包括预处理模块101、伪装区域生成模块102、伪装点选取模块103、路径规划模块104、路线开销计算模块105以及路径生成模块106；Referring to FIG. 2 , in another embodiment of the present application, a navigation service
所述预处理模块101，用于由LBS服务商进行同态加密方案的初始化、生成公钥pk、私钥sk和评估密钥evk，然后将初始化参数params、公钥pk和评估密钥evk发送给云服务商进行初始化；The
所述伪装区域生成模块102，用于用户利用匿名伪装算法分别生成出匿名伪装区域，并向云服务商请求该匿名伪装区域，云服务商收到匿名伪装区域请求后，将该匿名伪装区域的路网信息传输给用户；所述匿名伪装区域包括出发地匿名伪装区域和目的地匿名伪装区域；所述匿名伪装算法是基于K-匿名算法进行改造，将K-匿名算法前置条件满足的K个在线用户改变成随机生成的K个坐标；The disguised
所述伪装点选取模块103，用于用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离L的出发地伪装点和目的地伪装点，并将该出发地伪装点和目的地伪装点发送给云服务商；同时根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线；The camouflage
所述路径规划模块104，用于云服务商收到出发地伪装点和目的地伪装点后，规划出一组候选路线{w1,…，wn}，同时向LBS服务商请求候选路线涉及路网区域R的实时路况信息，LBS服务商将路网区域R的实时路况信息利用全同态公钥加密后传输给云服务商；The
所述路线开销计算模块105，用于云服务商收到路网区域R加密后的实时路况信息，并根据实时路况信息，对之前的候选路线组的开销进行进一步计算，得到密文后的路线开销，利用全同态加密的比较运算，将每条路线相互比较，将密文比较结果传输给LBS服务商；The route
所述路径生成模块106，用于LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，将该序号传输给用户；用户收到序号，将从候选路线组{w1,…，wn}中选取的最佳路线在本地和伪装区域内的路线连接，生成最终的出行路线。The
需要说明的是，本发明的基于同态加密和匿名伪装的导航服务隐私保护系统与本发明的基于同态加密和匿名伪装的导航服务隐私保护方法一一对应，在上述基于同态加密和匿名伪装的导航服务隐私保护方法的实施例阐述的技术特征及其有益效果均适用于基于同态加密和匿名伪装的导航服务隐私保护的实施例中，具体内容可参见本发明方法实施例中的叙述，此处不再赘述，特此声明。It should be noted that the navigation service privacy protection system based on homomorphic encryption and anonymous disguise of the present invention corresponds to the navigation service privacy protection method based on homomorphic encryption and anonymous disguise of the present invention. The technical features and beneficial effects described in the embodiments of the method for protecting the privacy of navigation services in disguise are applicable to the embodiments of the method for protecting the privacy of navigation services based on homomorphic encryption and anonymous disguise. For details, please refer to the descriptions in the method embodiments of the present invention. , which will not be repeated here, it 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 embodiment, the logical division of each program module is only an example, and in practical applications, it can be used as needed, for example, due to the configuration requirements of the corresponding hardware Or for 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 disguise is divided into different program modules, so as to complete the above description. All or part of the functionality.
请参阅图3，在一个实施例中，提供了一种实现基于同态加密和匿名伪装的导航服务隐私保护方法的电子设备，所述电子设备200可以包括第一处理器201、第一存储器202和总线，还可以包括存储在所述第一存储器202中并可在所述第一处理器201上运行的计算机程序，如导航服务隐私保护程序203。Referring to FIG. 3 , in one embodiment, an electronic device for implementing a method for privacy protection of navigation services based on homomorphic encryption and anonymous masquerading is provided. The
其中，所述第一存储器202至少包括一种类型的可读存储介质，所述可读存储介质包括闪存、移动硬盘、多媒体卡、卡型存储器(例如：SD或DX存储器等)、磁性存储器、磁盘、光盘等。所述第一存储器202在一些实施例中可以是电子设备200的内部存储单元，例如该电子设备200的移动硬盘。所述第一存储器202在另一些实施例中也可以是电子设备200的外部存储设备，例如电子设备200上配备的插接式移动硬盘、智能存储卡(Smart Media Card，SMC)、安全数字(SecureDigital，SD)卡、闪存卡(Flash Card)等。进一步地，所述第一存储器202还可以既包括电子设备200的内部存储单元也包括外部存储设备。所述第一存储器202不仅可以用于存储安装于电子设备200的应用软件及各类数据，例如导航服务隐私保护程序203的代码等，还可以用于暂时地存储已经输出或者将要输出的数据。Wherein, the
所述第一处理器201在一些实施例中可以由集成电路组成，例如可以由单个封装的集成电路所组成，也可以是由多个相同功能或不同功能封装的集成电路所组成，包括一个或者多个中央处理器(Central Processing unit，CPU)、微处理器、数字处理芯片、图形处理器及各种控制芯片的组合等。所述第一处理器201是所述电子设备的控制核心(Control Unit)，利用各种接口和线路连接整个电子设备的各个部件，通过运行或执行存储在所述第一存储器202内的程序或者模块，以及调用存储在所述第一存储器202内的数据，以执行电子设备200的各种功能和处理数据。The
图3仅示出了具有部件的电子设备，本领域技术人员可以理解的是，图3示出的结构并不构成对所述电子设备200的限定，可以包括比图示更少或者更多的部件，或者组合某些部件，或者不同的部件布置。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 on the
所述电子设备200中的所述第一存储器202存储的导航服务隐私保护程序203是多个指令的组合，在所述第一处理器201中运行时，可以实现：The navigation service
由LBS服务商进行同态加密方案的初始化、生成公钥pk、私钥sk和评估密钥evk，然后将初始化参数params、公钥pk和评估密钥evk发送给云服务商进行初始化；The LBS service provider initializes the homomorphic encryption scheme, generates the public key pk, the private key sk and the evaluation key evk, and then sends the initialization parameters params, public key pk and evaluation key evk to the cloud service provider for initialization;
用户利用匿名伪装算法分别生成出匿名伪装区域，并向云服务商请求该匿名伪装区域，云服务商收到匿名伪装区域请求后，将该匿名伪装区域的路网信息传输给用户；所述匿名伪装区域包括出发地匿名伪装区域和目的地匿名伪装区域；所述匿名伪装算法是基于K-匿名算法进行改造，将K-匿名算法前置条件满足的K个在线用户改变成随机生成的K个坐标；The user generates an anonymous disguised area by using an anonymous disguising algorithm, and requests the anonymous disguised area from the cloud service provider. After receiving the request for the anonymous disguised area, the cloud service provider transmits the road network information of the anonymous disguised area to the user; the anonymous disguised area The disguised area includes an anonymous disguised area of origin and an anonymous disguised area of the destination; the anonymous disguising algorithm is based on the K-anonymous algorithm to transform, and the K online users that satisfy the preconditions of the K-anonymous algorithm are changed into K randomly generated coordinate;
用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离L的出发地伪装点和目的地伪装点，并将该出发地伪装点和目的地伪装点发送给云服务商；同时根据匿名伪装区域的路网信息，同步规划出真实出发地到伪装出发地的路线；According to the road network information of the anonymous camouflage area, the user randomly selects the departure camouflage point and the destination camouflage point that satisfy the camouflage distance L near the departure point, and sends the departure camouflage point and the destination camouflage point to the cloud service provider; The road network information of the camouflaged area can simultaneously plan the route from the real departure point to the camouflaged departure point;
云服务商收到出发地伪装点和目的地伪装点后，规划出一组候选路线{w1,…，wn}，同时向LBS服务商请求候选路线涉及路网区域R的实时路况信息，LBS服务商将路网区域R的实时路况信息利用全同态公钥加密后传输给云服务商；After receiving the masquerading point of departure and the masquerading point of destination, the cloud service provider plans a set of candidate routes{w1 ,...,wn }, and at the same time requests the LBS service provider for the real-time road condition information of the candidate route involving the road network area R, 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;
云服务商收到路网区域R加密后的实时路况信息，并根据实时路况信息，对之前的候选路线组的开销进行进一步计算，得到密文后的路线开销，利用全同态加密的比较运算，将每条路线相互比较，将密文比较结果传输给LBS服务商；The cloud service provider receives the encrypted real-time road condition information of 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 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;
LBS服务商收到密文比较结果，利用私钥sk进行解密，并对比较结果进行排序，获得最佳路径的序号，将该序号传输给用户；用户收到序号，将从候选路线组{w1,…，wn}中选取的最佳路线在本地和伪装区域内的路线连接，生成最终的出行路线。The LBS service provider receives the ciphertext comparison result, decrypts it with the private keysk , sorts the comparison results, obtains the sequence number of the best path, and transmits the sequence number to the user;1 ,...,wn } The best route selected in the local and camouflaged areas is connected to the route to generate the final travel route.
进一步地，所述电子设备200集成的模块/单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个非易失性计算机可读取存储介质中。所述计算机可读介质可以包括：能够携带所述计算机程序代码的任何实体或装置、记录介质、U盘、移动硬盘、磁碟、光盘、计算机存储器、只读存储器(ROM，Read-Only Memory)。Further, if the modules/units integrated in the
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一非易失性计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM (DRAM)、同步DRAM (SDRAM)、双数据率SDRAM (DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。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 implemented by instructing relevant hardware through a computer program, and the program can be stored in a non-volatile computer-readable storage medium , when the program is executed, it may include the flow of the embodiments of the above-mentioned methods. Wherein, any reference to memory, storage, database or other medium used in the various embodiments provided in this application may include non-volatile and/or volatile memory. Nonvolatile memory may include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory. Volatile memory may include random access memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in various forms such as static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous chain Road (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. In order to make the description simple, 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 It is considered to be the range described in this specification.
上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。The above-mentioned embodiments are preferred embodiments of the present invention, but the embodiments of the present invention are not limited by the above-mentioned embodiments, and any other changes, modifications, substitutions, combinations, The simplification should be equivalent replacement manners, which are all included in the protection scope of the present invention.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211106644.XACN115200603B (en) | 2022-09-13 | 2022-09-13 | Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211106644.XACN115200603B (en) | 2022-09-13 | 2022-09-13 | Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115200603Atrue CN115200603A (en) | 2022-10-18 |
| CN115200603B CN115200603B (en) | 2023-01-31 |
Family
ID=83573570
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211106644.XAActiveCN115200603B (en) | 2022-09-13 | 2022-09-13 | Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115200603B (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116170191A (en)* | 2023-01-16 | 2023-05-26 | 西安电子科技大学 | A Location Service Task Assignment Method Based on Homomorphic Encryption |
| CN116405545A (en)* | 2022-12-18 | 2023-07-07 | 合肥工业大学 | Secure navigation method and system supporting k unordered passing points |
| EP4358057A1 (en)* | 2022-10-20 | 2024-04-24 | Industry-Academic Cooperation Foundation Dankook University | System for providing autonomous driving safety map service |
Citations (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6738808B1 (en)* | 2000-06-30 | 2004-05-18 | Bell South Intellectual Property Corporation | Anonymous location service for wireless networks |
| CN105530609A (en)* | 2015-12-16 | 2016-04-27 | 上海交通大学 | Indoor positioning method with efficient privacy protection based on Wi-Fi fingerprint |
| WO2016201775A1 (en)* | 2015-06-17 | 2016-12-22 | 中兴通讯股份有限公司 | Method and device for protecting position information of mobile terminal |
| US20170053282A1 (en)* | 2015-08-21 | 2017-02-23 | Pitney Bowes Inc. | Fraud risk score using location information while preserving privacy of the location information |
| WO2017037151A1 (en)* | 2015-09-03 | 2017-03-09 | Commissariat A L'energie Atomique Et Aux Energies Alternatives | Method for confidentially querying a location-based service by homomorphic cryptography |
| WO2017193783A1 (en)* | 2016-05-10 | 2017-11-16 | 北京京东尚科信息技术有限公司 | Method and device for protecting user location information |
| CN107831512A (en)* | 2017-10-30 | 2018-03-23 | 南京大学 | A kind of location privacy protection method of MSB AGPS positioning |
| US20190028279A1 (en)* | 2015-08-31 | 2019-01-24 | Mitsubishi Electric Corporation | Map information management system, map information management device, map company exclusive application data management device, and automotive data management device |
| CN109740376A (en)* | 2018-12-21 | 2019-05-10 | 哈尔滨工业大学（深圳） | Location privacy protection method, system, device and medium based on neighbor query |
| CN110557375A (en)* | 2019-08-01 | 2019-12-10 | 上海电力大学 | k anonymous location privacy protection incentive method based on block chain intelligent contract |
| EP3671281A1 (en)* | 2018-12-21 | 2020-06-24 | European Space Agency | Method and system for processing a gnss signal using homomorphic encryption |
| WO2022007889A1 (en)* | 2020-07-08 | 2022-01-13 | 浙江工商大学 | Searchable encrypted data sharing method and system based on blockchain and homomorphic encryption |
| WO2022082893A1 (en)* | 2020-10-22 | 2022-04-28 | 香港中文大学（深圳） | Privacy blockchain-based internet of vehicles protection method, and mobile terminal |
| US20220136857A1 (en)* | 2020-11-03 | 2022-05-05 | Rutgers, The State University Of New Jersey | Safety-aware route recommendation system and method |
| CN115035720A (en)* | 2022-06-10 | 2022-09-09 | 翁敏 | Traffic road condition data acquisition and processing method and management system based on satellite positioning |
- 2022
- 2022-09-13CNCN202211106644.XApatent/CN115200603B/enactiveActive
Patent Citations (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6738808B1 (en)* | 2000-06-30 | 2004-05-18 | Bell South Intellectual Property Corporation | Anonymous location service for wireless networks |
| WO2016201775A1 (en)* | 2015-06-17 | 2016-12-22 | 中兴通讯股份有限公司 | Method and device for protecting position information of mobile terminal |
| US20170053282A1 (en)* | 2015-08-21 | 2017-02-23 | Pitney Bowes Inc. | Fraud risk score using location information while preserving privacy of the location information |
| US20190028279A1 (en)* | 2015-08-31 | 2019-01-24 | Mitsubishi Electric Corporation | Map information management system, map information management device, map company exclusive application data management device, and automotive data management device |
| WO2017037151A1 (en)* | 2015-09-03 | 2017-03-09 | Commissariat A L'energie Atomique Et Aux Energies Alternatives | Method for confidentially querying a location-based service by homomorphic cryptography |
| CN105530609A (en)* | 2015-12-16 | 2016-04-27 | 上海交通大学 | Indoor positioning method with efficient privacy protection based on Wi-Fi fingerprint |
| WO2017193783A1 (en)* | 2016-05-10 | 2017-11-16 | 北京京东尚科信息技术有限公司 | Method and device for protecting user location information |
| CN107831512A (en)* | 2017-10-30 | 2018-03-23 | 南京大学 | A kind of location privacy protection method of MSB AGPS positioning |
| CN109740376A (en)* | 2018-12-21 | 2019-05-10 | 哈尔滨工业大学（深圳） | Location privacy protection method, system, device and medium based on neighbor query |
| EP3671281A1 (en)* | 2018-12-21 | 2020-06-24 | European Space Agency | Method and system for processing a gnss signal using homomorphic encryption |
| CN110557375A (en)* | 2019-08-01 | 2019-12-10 | 上海电力大学 | k anonymous location privacy protection incentive method based on block chain intelligent contract |
| WO2022007889A1 (en)* | 2020-07-08 | 2022-01-13 | 浙江工商大学 | Searchable encrypted data sharing method and system based on blockchain and homomorphic encryption |
| WO2022082893A1 (en)* | 2020-10-22 | 2022-04-28 | 香港中文大学（深圳） | Privacy blockchain-based internet of vehicles protection method, and mobile terminal |
| US20220136857A1 (en)* | 2020-11-03 | 2022-05-05 | Rutgers, The State University Of New Jersey | Safety-aware route recommendation system and method |
| CN115035720A (en)* | 2022-06-10 | 2022-09-09 | 翁敏 | Traffic road condition data acquisition and processing method and management system based on satellite positioning |
Non-Patent Citations (2)
| Title |
|---|
| CHENGJIN LIU等: "Efficient and Privacy-Preserving Logistic Regression Scheme based on Leveled Fully Homomorphic Encryption", 《IEEE INFOCOM WKSHPS: BIGSECURITY 2022: INTERNATIONAL WORKSHOP ON SECURITY AND PRIVACY IN BIG DATA》* |
| FIFI FAROUK等: "Efficient Privacy-Preserving Scheme for Location Based Services in VANET System", 《IEEE ACCESS》* |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP4358057A1 (en)* | 2022-10-20 | 2024-04-24 | Industry-Academic Cooperation Foundation Dankook University | System for providing autonomous driving safety map service |
| CN116405545A (en)* | 2022-12-18 | 2023-07-07 | 合肥工业大学 | Secure navigation method and system supporting k unordered passing points |
| CN116170191A (en)* | 2023-01-16 | 2023-05-26 | 西安电子科技大学 | A Location Service Task Assignment Method Based on Homomorphic Encryption |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115200603B (en) | 2023-01-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Luo et al. | pRide: Privacy-preserving ride matching over road networks for online ride-hailing service | |
| CN115200603B (en) | Navigation service privacy protection method and device based on homomorphic encryption and anonymous camouflage | |
| Baza et al. | A light blockchain-powered privacy-preserving organization scheme for ride sharing services | |
| Schlegel et al. | User-defined privacy grid system for continuous location-based services | |
| CN107347096B (en) | Location privacy protection method based on cloud server | |
| Šeděnka et al. | Privacy-preserving distance computation and proximity testing on earth, done right | |
| Yu et al. | lpRide: Lightweight and privacy-preserving ride matching over road networks in online ride hailing systems | |
| Mouratidis et al. | Shortest path computation with no information leakage | |
| Yu et al. | PGRide: Privacy-preserving group ridesharing matching in online ride hailing services | |
| Xie et al. | A privacy-preserving online ride-hailing system without involving a third trusted server | |
| CN115905633B (en) | Privacy-protected graph similarity retrieval method and system | |
| CN115767722B (en) | Indoor positioning privacy protection method based on inner product function encryption in cloud environment | |
| Zhang et al. | Privacy preserving in cloud environment for obstructed shortest path query | |
| Shen et al. | Location privacy-preserving in online taxi-hailing services | |
| CN109951279A (en) | An anonymous data storage method based on blockchain and edge devices | |
| CN109728904A (en) | A kind of spatial network querying method for protecting privacy | |
| Meng et al. | Verifiable spatial range query over encrypted cloud data in VANET | |
| Luo et al. | P 2 ride: Practical and privacy-preserving ride-matching scheme for ridesharing | |
| CN118138381A (en) | A lightweight, privacy-preserving reputation-based approach for pilot vehicle selection | |
| Xu et al. | An efficient and privacy-preserving route matching scheme for carpooling services | |
| Badsha et al. | Privacy preserving location recommendations | |
| Zhao et al. | Privacy-preserving any-hop cover shortest distance queries on encrypted graphs | |
| CN112671543B (en) | A publicly verifiable outsourced attribute-based encryption method based on blockchain | |
| CN109257167A (en) | A kind of resource allocation methods for protecting privacy in mist calculating | |
| Li et al. | A Dynamic Location Privacy Protection Scheme Based on Cloud Storage. |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |