JP5543821B2 - ENCRYPTION DEVICE, DECRYPTION DEVICE, AND ROUTE SEARCH SYSTEM - Google Patents

Description

  The present invention relates to an encryption device, a decryption device, and a route search system that use encrypted route search data.

  The geographic information system provides various functions such as map display and route search. Among these, in the route search, the route search of the starting point and the destination is performed using the route search algorithm such as the Dijkstra method using the route search data composed of nodes and links.

  By the way, the map information includes a lot of information that should not be disclosed in general, such as military bases, privately owned sites, or factories of companies. Conventionally, in geographic information distribution systems, there are many services that provide outdoor map information, but with the development of the information service industry in recent years, services that provide indoor map information such as underground shopping malls and stations are also increasing. . Such indoor map information includes, for example, information that should not be disclosed to the public, such as work areas of employees in stores and floor plans in offices. For example, in a floor plan in an office, it is necessary to restrict information to be disclosed appropriately according to a user of map information, such as a storage location of a confidential document. Accordingly, it is desired that the route search be performed within an appropriate range according to the disclosure range of the user.

  In the conventional technology, when map information is distributed to a vehicle by a network or broadcast, the map information is managed for each vehicle so that only appropriate information is disclosed according to the distribution destination vehicle. A technique for restricting disclosure of map information according to the type of vehicle by encrypting with a key is known (for example, Patent Document 1).

  For route search data, a method is known in which a user edits route search data and protects the alteration of the route search data using encryption (for example, Patent Document 2).

JP 2005-121719 A JP 2000-193472 A

  In patent document 1, in disclosure of map information according to type, encrypted map information is prepared for each vehicle type of a transmission destination, and a private key is stored in advance for each type in a car. Accordingly, encrypted map information can be distributed, a map in which only a specific vehicle type is encrypted can be decrypted, and disclosure restriction can be made according to the type of vehicle.

  However, the method disclosed in Patent Document 1 targets attribute information such as the shape of a feature constituting a map and the name associated therewith, and does not disclose encryption of route search data. In the route search, it is necessary to search for a route from an arbitrary starting point to the destination, and it is necessary to execute a route search according to a request for each user. In the method of preparing encrypted data in advance and distributing it simultaneously as in Patent Document 1, it is necessary to individually encrypt and manage the route search results for each type of user, or for each departure point / destination It becomes. For this reason, there is a problem that an increase in data size to be managed and only a route search result between points prepared in advance can be provided, and an appropriate route search cannot be performed for each user.

  In addition, in the method disclosed in Patent Document 2, a method for preventing falsification of route search data is described, but a method of restricting the disclosure destination of route search data for each user or user type Is not disclosed, and similarly to Patent Document 1, there is a problem that an appropriate route search cannot be performed for each user.

  The present invention has been made in view of the above, and an object thereof is to provide an encryption device, a decryption device, and a route search system capable of performing an appropriate route search for each user.

  In order to achieve the above-described object, an encryption apparatus according to the present invention includes a route search data including a node indicating a position on a map and link information indicating a relationship between the node and a node adjacent to the node. Encryption in which map data associated with display data for displaying a map corresponding to the search data is associated with a disclosure destination user who is a user who discloses the node and the display data Based on the encryption definition information, a storage unit for storing an encryption key for encrypting the route search data, the route search data, the encryption key, and the encryption definition information, For each user, the node to be encrypted is identified, the route search data of the identified node and the node adjacent to the identified node is encrypted, and the encrypted route Characterized in that it comprises an encryption processing unit for generating the encrypted map data that associates search for data and the display data.

  In addition, the decryption device according to the present invention, when receiving a route search request for searching a route from a point on the map to another point from the user, the position on the encrypted map And the route search data based on a decryption key for decrypting the route search data including link information indicating the relevance between the node and the node adjacent to the node. A decryption processing unit for decrypting encrypted map data associated with display data for displaying an object, and a route from the certain point to the other point corresponding to the encrypted map data Based on the node and the link information included in the route search data, the decryption processing unit is used to decrypt the encrypted map data, and based on the node and the link information using the decryption result. There are, characterized in that it comprises a route searching unit for repeatedly searching, a.

  The present invention also provides a route search system including the encryption device and the decryption device.

  According to the present invention, it is possible to provide an encryption device, a decryption device, and a route search system that can perform an appropriate route search for each user.

It is a block diagram which shows the outline of the map data delivery system in 1st Embodiment. It is a block diagram of each apparatus which comprises the map data delivery system shown in FIG. It is a sequence diagram of the process performed in a map data delivery system (registration process). It is a sequence diagram of the process performed in a map data delivery system. It is a figure showing the outline of the processing flow of a route search (route processing). It is a figure which shows a part of data structure of plaintext map data, and its display image. It is a figure which shows an example of encryption definition information. It is a flowchart which shows the process sequence of the encryption process in 1st Embodiment. It is a flowchart which shows the process sequence of the decoding process in 1st Embodiment. It is a processing flowchart which shows the outline of the decoding process of the data for a route search in a 1st Example. It is a figure which shows the example of the data storage part for a route search. It is a figure which shows an example of the application screen for producing | generating encryption definition information. It is a flowchart which shows the process sequence of the encryption process in 2nd Embodiment. It is a flowchart which shows the process sequence of the decoding process in 2nd Embodiment. It is a figure which shows an example of the change of the data structure before and behind the encryption process in 2nd Embodiment.

Exemplary embodiments of an encryption device, a decryption device, and a route search system according to the present invention will be explained below in detail with reference to the accompanying drawings.
(First embodiment)
FIG. 1 is a configuration diagram showing an outline of a map data distribution system 1 according to the first embodiment. In FIG. 1, the dotted line represents the outline of the data flow. The map data distribution system 1 includes a map encryption device 101, a map storage device 102, a key management device 103, a map distribution device 104, a map browsing device 105, and a map decryption device 106. Each device is connected via the network 100.

  The map encryption apparatus 101 includes an encryption definition information generation unit 110 and an encryption processing unit 111. The encryption definition information generation unit 110 generates encryption definition information 121 from plaintext map data 120 that is map data before being encrypted, and the encryption processing unit 111 includes encryption definition information 121, plaintext map data 120. The encryption map data 124 is generated from the encryption key 122. The specific contents of the encryption definition information 121 will be described later.

  The map storage device 102 has a database processing unit 112 and stores encrypted map data 124. Here, the database processing unit 112 uses, for example, a search or registration in response to a request from the map distribution apparatus 104 using an API (Application Program Interface) of an SQL (Structured Query Language) or a GIS product (Geographic Information System). Various processes relating to the encrypted map data 124 such as deletion, change, etc. are performed.

  The key management apparatus 103 includes a key generation unit 113. The key generation unit 113 generates a decryption key 123 corresponding to the encryption key 122 used for encryption. Here, the encryption key 122 and the decryption key 123 generated by the key generation unit 1113 may be a public key or a secret key in a public key encryption technology such as RSA, or a common key such as AES (Advanced Encryption Standard). It may be a shared key in cryptographic technology.

  The map distribution device 104 includes a query processing unit 117. When the query processing unit 117 receives a request from the query request unit 115 in the map browsing device 105, analyzes the query, and receives the display map data generated by the display image generation unit 1142 of the map decoding device 106, Map data to be returned to the map browsing device 105 and displayed is created.

  The map browsing device 105 includes a query request unit 115 and a display processing unit 118. Here, the query request unit 115 transmits a query such as a search for map data to the map distribution device 104, receives the map data returned from the map distribution device 104, and the display processing unit 118 displays the map data. To do. The map data received by the map browsing device 105 is obtained by performing decryption processing using the decryption key 123 by the decryption processing unit 116 of the map decryption device 106, as will be described later.

  The map decoding apparatus 106 includes a route search processing unit 1141, a display map image generation unit 1142, and a decoding processing unit 116. The display map image generation unit 1142 receives the request for decoding the display map data from the query processing unit 117 of the map distribution device 104 by the decoding processing unit 116 and sends the decoded display map data. The route search processing unit 1142 performs route search when receiving route search data from the map distribution device 104. Specific processing for route search will be described later. The decryption processing unit 116 decrypts the encrypted map data 124 using the decryption key 123. In the following description, the map decoding device 106 is described as a single device. However, the map decoding device 106 may be a part of the map distribution device 104, and the map decoding device 106 may be the map browsing device 105. It may be configured as a part of.

  FIG. 2 is a configuration diagram of each device constituting the map data distribution system 1 shown in FIG. As shown in FIG. 2, each device constituting the map data distribution system 1 shown in FIG. 1 includes a CPU (Central Processor Unit) 201, a RAM (Random Access Memory) 202, an input device 203, a display device 204, a communication device. 205, a reading device 206, and an external storage device 207 are connected via an interface 205 and configured as a computer (electronic computer) 200 having a general configuration.

  The input device 203 is, for example, a keyboard or a mouse, the display device 204 is a display for display, and the external storage device 207 is an HDD (Hard Disk Drive) or the like. The communication device 205 is a communication interface for communicating with other devices via a network. Furthermore, the reading device 206 is a device for reading or writing data from an external storage medium 208 such as an FD (Floppy (registered trademark) Disk), a USB memory, or a CD-R.

  The CPU 201 implements each processing unit (such as the encryption processing unit 111) of each device illustrated in FIG. 1 as a process by executing a program loaded on the RAM 202. The interface 209 is an internal path for transmitting and receiving data between the components in the apparatus.

  3 and 4 are sequence diagrams of processes performed in the map data distribution system 1. FIG. First, FIG. 3 will be described. FIG. 3 shows an encryption for performing a route search according to the type of the user and displaying map data corresponding to the type on the map browsing device 105 when a route search request is received from the map browsing device 105. It is a flowchart which shows the process sequence of the process (henceforth a registration process) which registers the map data.

  This registration process is performed by the map data distribution system 1 before the map data is distributed to the map browsing device 105, for example, at a timing when a user who uses the map data distribution system 1 is registered. Is done by. In the registration process, key generation in the key management device 103, transmission to the map encryption device 101 and the map browsing device 105, encryption of plain text map data, and map storage device 102 of the encrypted map data Perform processing up to storage.

  As shown in FIG. 3, when the registration process is started (step S300), the key management apparatus 103 generates an encryption key 122 and a decryption key 123 according to the user (step S301), and the generated decryption key 123 is transmitted to the map decoding apparatus 106 (step S302).

  Upon receiving the decryption key 123, the map decryption device 106 stores the received decryption key 123 in a storage device such as the external storage device 207 (step S303), and then the key management device 103 stores the encryption key 122. It transmits to the map encryption apparatus 101 (step S304).

  Upon receiving the encryption key 122, the map encryption device 101 stores the received encryption key 122 in a storage device such as the external storage device 207 (step S305), and the encryption definition information generation unit 110 receives the plaintext map data. Using 120, the encryption definition information 121 is generated (step S306).

  Here, the encryption definition information 121 is a route search data composed of a node and a link representing a relationship between nodes described later, a user (or a type of user) to be disclosed, and a node. This is stored in association with each other.

  The encryption definition information 121 is created for the plain text map data 120 handled by the map data distribution system 1, and the specific contents will be described later with reference to FIG. The content of data described as the encryption definition information 121 (for example, which node is disclosed to which user) is determined in advance by an administrator or the like, and the encryption definition information 121 is set according to the setting. Is generated.

  Then, the encryption processing unit 111 of the map encryption apparatus 101 generates encrypted map data 124 from the encryption definition information 121, the plaintext map data 120, and the encryption key 122, and stores the generated encrypted map data 124 in a map. It transmits to the apparatus 102 (step S307). Specific processing (encryption processing) in step S307 will be described later with reference to FIG.

  The map storage device 102 receives the encrypted map data 124 from the map encryption device 101, stores the encrypted map data 124 (step S308), and ends the registration process shown in FIG. 3 (step S309). When this registration process is completed, an encryption key 122 and a decryption key 123 for each user, encrypted map data 124, and encryption definition information 121 are generated.

  Here, in step S302, when the key management apparatus 103 transmits the decryption key 123 to the map decryption apparatus 106, and generates these keys using the shared key in the common key encryption technique as the encryption key 122 and the decryption key 123. In step S304, when the key management apparatus 103 transmits the encryption key 122 to the map encryption apparatus 101, it is preferable that the key management apparatus 103 directly delivers it using an external storage medium or transmits it using encrypted communication. . Moreover, it is desirable to store the secret key in the public key cryptography and the shared key in the common key cryptography in a tamper-resistant device such as an IC card or HSM (Hardware Security Module).

  On the other hand, since the public key in the public key encryption technology can be disclosed to the public, a general communication path such as HTTP (Hyper Text Transfer Protocol) may be used. However, for example, the key management device 103 issues a public key certificate to the public key, and uses the public key certificate to confirm that the encryption key 122 used in the encryption device 101 has no errors or tampering. It is desirable to do.

  FIG. 4 is a flowchart showing a processing procedure of processing (hereinafter referred to as route processing) for the map data distribution system 1 to accept a map route search request from the user and display the result to the user. is there. FIG. 4 shows a processing flow from map data distribution from the map distribution device 104 to the map browsing device 105 until display on the map browsing device 105. In this processing flow, mainly, a route search request is transmitted from the map browsing device 105, a query is analyzed by the map distribution device 104, a search is performed using the map storage device 102, and is transmitted to the map browsing device 105. And the decoding and the display process in the map browsing apparatus 105 are performed.

  As shown in FIG. 4, when the map data distribution system 1 receives a route search request for map data from a user and starts route processing (step S400), the query request unit 115 of the map browsing device 105 The received route search request is transmitted to the distribution device 104 (step S401).

  Then, the query processing unit 117 of the map distribution device 104 analyzes the query that constitutes the route search request transmitted from the map browsing device 105, and according to the analysis result, the map storage device 102 sends route search data. A search request is transmitted (step S402).

  The database processing unit 112 of the map storage device 102 receives the search request from the map distribution device 104, and in accordance with the search request, the encrypted map data 124 or the map encryption device 101 registered by the registration process shown in FIG. The plaintext map data 120 is accessed, search processing is executed, and the search result (for example, information including coordinate data and node IDs of the departure point, destination, and intermediate nodes) is sent to the map distribution device 104 as route search data. A reply is made (step S403).

Subsequently, the query processing unit 117 of the map distribution device 104 receives the route search data from the map storage device 102, transmits the received route search data to the map decoding device 106 (step S404), and the map decoding device. 106, the route search processing unit 1141 and the decoding processing unit 116 execute the route search with reference to the received route search data, and transmit the route search result to the map distribution device 104 (step S405). Note that the specific processing (decoding processing) in step S405 will be described later with reference to FIG. 8. Then, the query processing unit 117 of the map distribution device 104 receives the route search result, and receives the received route search result. The display map data search request is referred to and transmitted to the map storage device 102 (step S406), and the database processing unit 112 of the map storage device 102 searches the display map data according to the display map data search request. The search result is transmitted to the map distribution device 104 (step S407).

  The query processing unit 117 of the map distribution device 104 transmits a display map data generation request to the map decoding device 106 (step S408), and the display map image generation unit 1142 and the decoding processing unit 116 of the map decoding device 106 are encrypted. A display map image obtained by decoding the converted map data 124 is generated and transmitted to the map distribution device 104 (step S409).

Thereafter, the query processing unit 117 of the map distribution device 104 transmits the display map image to the map browsing device 105 (step S410), and the query request unit 115 of the map browsing device 105 receives the display map image and displays it. The processing unit 118 displays the display map image on the display device 204 of the map browsing device 105 (step S411), and the search process shown in FIG. 4 ends (step S412).
The

  In step S401, prior to the transmission of the route search request from the map browsing device 105 to the map distribution device 104, the encryption key 122 and the decryption key 123 are determined for each user, as will be described later. In order to make these keys correspond to each other, it is desirable that the map distribution device 104 performs user authentication of the map browsing device 105. Therefore, the query processing unit 117 of the map distribution device 104 uses a device ID (for example, a MAC address (Media Access Control Address), etc.) unique to the map browsing device 105 for authentication from the map browsing device 105. User authentication may be performed by receiving information. Alternatively, the user of the map browsing device 105 may be requested to input ID / PW (Password), and user authentication may be performed using the input, or authentication using an encryption technology such as SSL (Secure Sockets Layer). Or user authentication using biometric information may be used.

  Further, when information that should not be disclosed to the map browsing device 105 is clear as a result of the user authentication (when a range that is not disclosed to a certain user is clear), the map storage device 102 in step S402. In the search request for the route search data, a search request excluding a range including information that should not be disclosed may be performed, and a search request for only a disclosing range may be performed. For example, as a result of the above user authentication, if the user does not have the browsing authority for all the non-disclosure areas, the search result transmission from the map storage device 102 in step S403 is for the route search of only the disclosure range. Data should be included.

  In the transmission of the route search request in step S401, for example, the current position (departure point) and the coordinate information of the destination (hereinafter also simply referred to as position information) are transmitted to the map distribution device 104. In steps S402 and S403, the query processing unit 117 of the map distribution device 104 performs a search process on the map storage device 102 based on the position information, and selects the node closest to the current position and the destination as the departure node and the destination. As the ground node, the encrypted data corresponding to the route search data necessary for the route search is acquired from the map storage device 102. At this time, the data necessary for the route search is, for example, a route search that uses only a specific range for the search when it is clear that the search range is a limited range such as only the first floor of a building or a town. What is necessary is just to acquire as business data.

  Further, the processing in steps S402 and S403 may be performed interactively. For example, if the starting point or destination of the route search request transmitted from step S401 is a place name or a room name, the map distribution device 104 makes an inquiry to the map storage device 102 and identifies the feature from the name. Then, the node may be specified from the node associated with the feature or the position of the feature.

  Alternatively, when the departure node or the destination node is encrypted, the map distribution device 104 identifies the feature from the position information included in the route search request and relates to the identified feature. If the encrypted data is obtained from the map storage device 102, the map distribution device 104 transmits the encrypted data to the map decryption device 106, and the map decryption device 106 decrypts the encrypted data to obtain the feature node. Good. Details of the route search data will be described later.

  Or, even when the departure place or destination is specified from the above place name or room name, the feature is directly specified because the feature itself or the attribute information of the feature is encrypted. There are cases where it is not possible. In this case, for example, in addition to the encrypted map data 124, the map storage device 102 stores a keyword list including the place name, room name, etc. in association with the encrypted feature or attribute information. These may be managed. By creating such a keyword list, it is possible to cope with keyword searches such as the place names and room names described above.

  Further, in the keyword list, instead of storing the keyword itself, for example, a hash value may be generated and stored by using a cryptographic hash function such as SHA-1. Due to the one-way nature of the cryptographic hash function, it becomes difficult to know the original keyword from the hash value stored in the keyword list. Furthermore, it is desirable for each keyword to limit the keywords that can be used by user authentication as described above. The method for creating the keyword list is not limited to the above, and other methods may be used.

  In addition, in the decryption process of the map decryption device 106, when the starting node and the destination node are not obtained by any of the methods described above, for example, because the encrypted data could not be decrypted, An error such as “Destination not found” is transmitted to the map browsing device 105, and the process is terminated.

  The route search is completed by the processing up to step S405. The result of the route search is the set of nodes and links described above. In step S406, a search request is transmitted again to the map storage device 102 based on the coordinate information of the node obtained from the route search result or the associated feature, and a surrounding map image describing the route search result is created. If encrypted data is included in the search result from step S407 (the map data itself other than the route search data is encrypted), decryption processing is performed in step S409 to restore the map data. May be performed.

  The processing from step S402 to step S405 may be repeated. For example, when the route search range is large, or when the route search request transmission from the map transmission device 105 (step S401) designates a route point, the route point is set as the destination node or the departure point node. The processing from step S402 to step S405 may be repeated a plurality of times.

  In the transmission of the display map image to the map browsing device 105 in step S410, not only the surrounding map image displaying the route search result generated in step S409, but also, for example, the title and cost (for example, travel time and fee) ) Etc. may be formed by HTML (Hypertext Markup Language) and transmitted. This process may be performed in step S409.

  Next, the data structure of the plaintext map data 120 stored in the map encryption apparatus 101 will be described. FIG. 5 is a diagram showing a part of the data structure of the plaintext map data 120 and its display image 510.

  As shown in FIG. 5, the plaintext map data 120 includes a map data storage unit 500 and a route search data storage unit 501. The route search data storage unit 501 includes a node storage unit 502 and a link. A storage unit 503 is stored. Here, the node storage unit 502 and the link storage unit 503 store data used for the route search, and the node storage unit 502 stores the node of the route search data and the corresponding position coordinates on the map of each node. Alternatively, information on corresponding features is stored. The link storage unit 503 stores link information for connecting the nodes stored in the node storage unit 502 and information on the movement cost thereof. Here, the movement cost is a time required for movement, a linear distance, an expense, or the like. The data structures of the node storage unit 502 and the link storage unit 503 will be described later with reference to FIG.

  As shown in FIG. 5, in the map data storage unit 500, attribute information such as the type and name of each feature on the map is associated with the geometry representing the position (coordinates) and shape of the feature on the map. Composed. Of the attribute information, the FID (Feature ID) of the map data storage unit 500 is an identifier for uniquely identifying each feature.

  In the lower part of FIG. 5, a display image 510 displayed on the map browsing device 105 as a result of the route search is shown. The display image 510 is created according to the feature metric and attribute information stored in the map data storage unit 500, and the position information stored in the node storage unit 502 and link storage unit 503 and the connection information between nodes. Is done.

  In the map data storage unit 500 of the plaintext map data 120 shown in FIG. 5, the various data described above are expressed in a table format, but the present invention is not limited to this. For example, GIS (Geographic Information System) is not a simple table format, but features, for example, features as minimum units (called objects, features, etc.), and collects multiple features that exist in the same property or location. Some are expressed in a tree structure by collecting and managing them in units called containers and arranging the containers in accordance with the map structure (for example, the structure of a building). Even in such a case, it can be similarly applied by treating each row in the table of FIG. 5 as the above feature.

  Next, the encryption definition information 121 will be described. FIG. 6 is a diagram illustrating an example of the encryption definition information 121. As shown in FIG. 6, in the encryption definition information 121, a node to be encrypted and a user who makes a route search request are described in association with each other. In the following description, it is assumed that these pieces of information are described using XML (extensible Markup Language).

  The encryption definition information 121 includes an encryption target node element as an element for searching for a route. The encryption target node element includes a node list element for designating a node to be encrypted and a disclosure destination list element for setting a disclosure destination. In the node element, the node ID to be encrypted is described, and in the disclosed element, the disclosed user or the identifier for uniquely identifying the type of user is described. Is identified. In the example shown in FIG. 6, nodes with node IDs (N01) “N01” and “N02” are described as nodes to be encrypted, and “user A” and “user B” are described as disclosure destination lists. These nodes are shown to be disclosed only to user A and user B.

  Here, as an identifier for uniquely identifying the user, for example, an employee number, a member number, an e-mail address, or the like may be used. The reason why a plurality of node elements and disclosure destination elements are specified in the same encryption target node element is that nodes having the same disclosure destination are grouped and a plurality of disclosure destinations can be specified. In this way, by specifying a plurality of nodes to be encrypted, it is possible to set a plurality of node lists with different disclosure destinations.

  In this embodiment, since the disclosure destination is restricted depending on the encryption technology, that is, the presence or absence of the decryption key 123, the disclosure destination element is not a user or an identifier that identifies the type of user, but a decryption key. The identifier of the corresponding encryption key 122 or the reference destination may be described. When the identifier of the user or the user is described in the above disclosure destination element, the encryption key 122 or the reference destination thereof is specified from the described identifier, and the encryption key 122 is set during the encryption process. Use.

  Note that the encryption definition information 121 illustrated in FIG. 6 may have different element names such as a disclosure destination list and a disclosure destination. In addition, ASN. Data representations other than XML, such as 1, may be used. For example, when restricting the disclosure destination of data other than the route search data such as the feature itself or the attribute information and geometry of the feature, a child different from the encryption target node in the encryption definition information element. Add an element and set the disclosure destination.

  Next, step S307 (encryption process) shown in FIG. 3, step S405 (decryption process) shown in FIG. 4, and changes in the data structure before and after the encryption process will be described. First, changes in the data structure before and after the encryption process will be described with reference to FIG. FIG. 9 is a diagram illustrating a part of the route search data storage unit 501 of the display image 510 illustrated in FIG. As described above, the route search data storage unit 501 includes the node storage unit 502 that stores information about nodes among the nodes and links that constitute the data for route search, and the link storage unit 503 that stores information about links. Is done.

  FIG. 9 is a diagram illustrating an example of the route search data storage unit 501. As shown in FIG. 9, in the node storage unit 502a of the route search data storage unit 501a, in order to store each node information, the NID that is an identifier for uniquely identifying the node and the position information on the map of the node are stored. And a decryption flag indicating whether or not the adjacent node is encrypted after the encryption process. The link storage unit 503a includes an identifier for uniquely identifying a link, a start point NID for specifying a start point side node in a connection relationship, an end point NID for specifying a node on the end point side, And a cost representing the movement cost of

  Note that the start point NID and the end point NID are for representing movement in one direction between the nodes. When the connection relation between the nodes is all in both directions, it is not necessary to distinguish the start point NID and the end point NID. . In addition, when there is a distinction between the start point NID and the end point NID, to express the movement cost in both directions, the data in which the start point NID and the end point NID are exchanged are separately input, or the link storage unit 503a is bidirectional. What is necessary is just to add the data for showing that it is. Further, the link storage unit 503a illustrated in FIG. 9 stores only the travel time as an example of the cost, but may store a plurality of costs in addition to this. For example, a plurality of costs such as a moving distance and time may be stored according to a user's moving method such as a car, a bicycle, and walking. In the following, a case where the cost is one will be described. However, even when a plurality of costs are stored, it is possible to perform encryption in the same procedure.

  The node storage unit 502a and the link storage unit 503a illustrated in FIG. 9 may include information such as names, supplementary explanations, or FIDs of related features, for example. Note that the decryption flag in the node storage unit 502a is data necessary after encryption, and therefore may not be present in the route search data storage unit 501a.

  The encrypted route search data 504a represents an encryption result when the node with NID N5 is encrypted in the route search data 501a. The encrypted path search data 504a includes a node storage unit 502a, a link storage unit 503a, and an encrypted data unit 505a.

  The encrypted data unit 505a specifies the encrypted data for storing the result of encrypting the node and the link, the CID that is an identifier for uniquely identifying the encrypted data, and the encrypted data to be decrypted at the time of decryption And related data including the FID and NID.

  As described in the present embodiment, in the encryption of the route search data performed by the encryption processing unit 111 of the map encryption apparatus 101, the node to be encrypted and all the links connected to the node (for example, 9 is deleted from the encrypted node storage unit 502a and link storage unit 503a, and the decryption flags of all adjacent nodes of the encryption target node are set to T (TRUE). . Note that F (FALSE) is set for a node whose decoding flag is not T.

  The node to be encrypted and all links connected thereto (hereinafter, the data to be encrypted are referred to as encryption target data) are encrypted according to the setting of the disclosure destination element of the encryption definition information 121, The result of BASE64 encoding of the encryption result is stored in the encrypted data. The encrypted data needs to store the encryption results of all the data related to the nodes and links. For this, for example, the result of structuring each data such as NID and coordinates using XML or the like May be stored as a result of BASE64 encoding.

  In the encryption of the encryption target data, the encryption target data is individually encrypted using the encryption key 122 for each disclosure destination, the result is shaped using XML or the like, and the encrypted data unit 505a is encrypted. Or may be written as follows, for example.

  First, the key generation unit 113 of the key management apparatus 103 generates a random shared key (hereinafter referred to as a session key) in the common key encryption technique separately for each encryption target node, and transmits it to the map encryption apparatus 101. . Next, the encryption processing unit 111 of the map encryption apparatus 101 encrypts the session key generated for each encryption target node for each disclosure destination in the encryption definition information 121 as follows.

  First, if there is a disclosure destination that matches the disclosure destination that is currently performing processing at the disclosure destination that is set for each encryption target node, the session key encryption of the session key of the encryption target node that is currently processing is performed. Add to the conversion list. By repeating this for all the encryption target nodes, a session key encryption list of session keys of the encryption target nodes that can be decrypted by the disclosure destination currently being processed is created. Next, the generated session key encryption list is aggregated and encrypted using the disclosed encryption key 122. Thereafter, the same processing is repeated for all disclosure destinations, and the result is shaped using XML or the like and written into the encrypted data portion 505a. In the above description, encryption is performed for each node to be encrypted, but as described above, when the node storage unit 503a includes a plurality of costs, a session key may be assigned for each cost.

  In the encryption using the encryption key 122 of the above session key encryption list, the hash value of the encryption target node for guaranteeing the integrity of the encryption target node at the time of decryption, the MAC (Message Authentication Code), etc. May be included. The above encryption processing is called selective disclosure type encryption, and is disclosed in Japanese Unexamined Patent Application Publication No. 2009-499731.

  In the route search, the Dijkstra method or a route search algorithm improved from the Dijkstra method is used. In these route search algorithms, a certain node is used as a starting point (referred to as a starting node), its neighboring nodes are searched, and the total cost from the departure node to the neighboring nodes is repeatedly evaluated, whereby the total cost to the destination node is determined. The route search from the final starting point to the destination is performed. The Dijkstra method is a route search algorithm of a breadth-first search in which a route from a departure node to a destination node is searched by using the above procedure as a core process. Algorithms that perform efficient route searches by improving cost evaluation, search termination conditions, etc. in the Dijkstra method are known (for example, the A * method).

  When the decoding processing unit 116 of the map decoding apparatus 106 performs the decoding process, the search for the adjacent node first determines whether there is data to be decoded based on the decoding flag of the starting node. When the decryption flag is T, the related data in the encrypted data unit 505a is referred to obtain the encrypted data to be decrypted. Next, decryption processing is executed, and when encrypted data is decrypted, nodes and links are restored from the decrypted data, and the route search is continued.

  Hereinafter, specific processing procedures of the above-described encryption processing and decryption processing will be described with reference to FIGS. In this embodiment, a method of performing decoding processing in the core processing of the Dijkstra method will be described. However, the route search algorithm is not limited to the Dijkstra method, and other route search algorithms that extend the Dijkstra method may be used. Is also applicable.

  After encryption in this embodiment, T is set in the decryption flags of all adjacent nodes of the encryption target node. In the route search algorithm, when the decryption flag of the origin node is set to T, the encrypted data to be decrypted is retrieved from the encrypted data unit 505a and the decryption key 123 given to the decryption processing unit 116 is retrieved. Is used to decrypt the encrypted data. If the encrypted data can be decrypted by this decryption, the decrypted data is restored to the node storage unit 502a and the link storage unit 503a. It should be noted that the related data of the encrypted data portion 505a is used for searching the encrypted data to be decrypted from the encrypted data portion 505a.

  Hereinafter, specific encryption processing and decryption processing in the present embodiment will be described. FIG. 7 is a flowchart showing the processing procedure of the encryption processing in the present embodiment.

  As shown in FIG. 7, when the encryption process is started (step S700), the encryption processing unit 111 of the map encryption apparatus 101 stores the route search data storage unit 501a constituting the plaintext map data 120. The data is copied to the encrypted path search data storage unit 504a and the decryption flag is set to F once (step S701).

  Then, the encryption processing unit 111 refers to the encryption definition information 121 and determines whether there is an encryption target node to be encrypted (step S702). If the encryption processing unit 111 determines that there is an encryption target node to be encrypted (step S702; Yes), the process proceeds to step S703 and determines that there is no encryption target node to be encrypted (step S702). No), the encryption process shown in FIG. 7 is terminated (step S710).

  If it is determined that there is an encryption target node to be encrypted (step S702; Yes), the encryption processing unit 111 acquires the encryption target node described in the encryption definition information 121 (step S703), and stores the link. With reference to the unit 503a, it is determined whether or not there is an unoperated link in the connection link connected to the acquired encryption target node (step S704).

  When the encryption processing unit 111 determines that there is an unoperated link in the connection link connected to the acquired encryption target node (step S704; Yes), the encryption processing unit 111 acquires the connection link as a related link ( In step S705), an adjacent node of the encryption target node is identified from the connection link connected to the acquired encryption target node, and the decryption flag is changed to T (step S706). Then, the encryption processing unit 111 repeatedly performs the processing from steps S704 to S706.

  On the other hand, if it is determined that there is no unoperated link in the connection link connected to the encryption target node (step S704; No), the encryption processing unit 111 determines the encryption target node and the relationship acquired in step S705. The link is encrypted (step S707), and the encryption target node and the related link acquired in step S705 are deleted from the node storage unit 502a and link storage unit 503a in the encrypted route search data 504a (step S708).

  Thereafter, the encryption processing unit 111 stores the encryption result of step S707 in the encrypted data storage unit 504a (step S709), and returns to step S702. Then, the encryption processing unit 111 repeatedly performs the processing from steps S702 to S709 for all the encryption target nodes described in the encryption definition information 121.

  In step 702 in the above encryption processing, for example, the encryption target node elements of the encryption definition information 121 illustrated in FIG. 6 may be sequentially processed and repeated until there are no encryption target nodes. Such sequential processing may be realized using, for example, XML SAX (Simple API for XML).

  In the example of FIG. 9, only one node (N6, link L14) is connected to the encryption target node (N5) (see FIG. 5 for a display image), which is shown in steps S704 to S706. As described above, when there are a plurality of adjacent nodes in the encryption target node, the same processing is performed on all these adjacent nodes.

  Note that the encryption processing in step S708 is not performed for each node, but a plurality of nodes may be processed together. In this case, the writing of the encrypted data to the encrypted data portion 505a in step S709 is performed as a single encrypted data obtained by collectively encrypting these, and the feature related to the related data and the NID of the adjacent node are set. All may be written.

  Further, when a plurality of nodes are processed together, if the nodes to be encrypted are in the same region, only steps S705 and S706 are performed on the adjacent nodes of the nodes on the boundary line in the region. Should be executed. The reason is that when nodes and links are restored by decrypting encrypted data, the nodes and links in the area are decrypted together, so the nodes and links outside the boundary in the area should be decrypted. This is because it is not necessary to examine whether or not

  Through the above encryption process, all nodes to be encrypted and link information connected thereto are deleted from the node storage unit 502a and link storage unit 503a of the encryption path search data 504a, and the encryption results are related. It is stored in the encrypted data part 505a together with the data.

  In the route search, the cost is calculated by searching from the start node to the adjacent node, and the cost evaluation from the departure node is performed from the calculated cost. In the above encryption process, the encrypted node The decoding flags of all adjacent nodes are set to T. Therefore, by checking whether or not the decryption flag is T when searching for an adjacent node for route search, it is possible to know the presence or absence of encrypted data to be decrypted, and it is possible to decrypt at a required location in the route search algorithm. It becomes. Subsequently, the decoding process will be described.

  FIG. 8 is a flowchart showing the processing procedure of the decoding processing in the present embodiment. FIG. 8 shows a processing flow for performing the decoding process in the route search algorithm, and only the outline of the procedure is shown for the processing of the route search algorithm itself. The dotted line in FIG. 8 is the core processing of the route search algorithm. Hereinafter, the decoding process shown in FIG. 8 will be described.

  As shown in FIG. 8, when the decoding process is started (step S800), the decoding processing unit 116 of the map decoding apparatus 106 first sets the departure point node as the starting point node (step S801).

  Then, the decoding processing unit 116 determines whether or not the route search has ended (step S802). If it is determined that the route search has ended (step S802; Yes), the decoding processing illustrated in FIG. Is terminated (step S810).

  On the other hand, if the decoding processing unit 116 determines that the route search has not ended (step S802; No), the decoding processing unit 116 determines whether the decoding flag of the starting node is T (step S803) and decodes the starting node. If it is determined that the flag is T (step S803; Yes), the encrypted data is acquired from the encrypted data unit 505a, and the acquired encrypted data is decrypted (step S804). On the other hand, when the decoding processing unit 116 determines that the decoding flag of the starting point node is not T (F) (step S803; No), the decoding processing unit 116 proceeds to step S807.

  The decryption processing unit 116 determines whether or not the decryption of the encrypted data acquired in step S804 is successful (step S805). When it is determined that the decryption is successful (step S805; Yes), the decryption result in step S804 is determined. Then, the node and the link are restored, and the restored node and link are added to the node storage unit 502a and the link storage unit 503a (step S806). On the other hand, when the decoding processing unit 116 determines that the decoding is not successful (failed) (step S805; No), the process proceeds to step S807.

  Then, the decoding processing unit 116 refers to the node storage unit 502a and the link storage unit 503a, searches for the connection link (adjacent node) of the start node (step S807), and determines whether there is an unsearched adjacent node. Determination is made (step S808).

  When it is determined that there is an unsearched adjacent node (step S808; Yes), the decoding processing unit 116 refers to the cost column in the link storage unit 503a, calculates the cost from the start point node to the adjacent node, Cost evaluation from the node to the adjacent node is performed (step S809).

  On the other hand, when it is determined that there is no unsearched adjacent node (step S808; No), the decoding processing unit 116 returns to step S802. Then, the decoding processing unit 116 repeatedly performs the processing from steps S802 to S810 until the route search is completed.

  In step S804 described above, it is desirable to stop the processing when decoding stops abnormally, for example, when the decoding result is not a correct node or link. Also, when the route search does not reach the destination node during the route search process, such as when the route search does not finish for a certain period of time or when it is unrealistic cost (for example, it takes more than 100 years to walk) In step S802, the process may be stopped.

  The decoding in step S804 and the restoration of the node and link in step S806 may be performed not on a single node but on a plurality of nodes and links. For example, when a plurality of nodes are encrypted together at the time of the encryption process described above, the result of decryption in step S804 includes a plurality of nodes and links, so step S806 includes the decrypted nodes and links. All will be restored.

  In the above decryption process, sequential decryption is performed within the route search algorithm. However, when there is a small amount of data to be decrypted in advance (for example, one encrypted data is included in the response from the map storage device 102 in step 403). In such a case, the decoding process may be performed collectively before the process of FIG.

  In route search, in order to efficiently perform data management or route search, data management may be performed for each hierarchy or area such as a building floor. In this case, also for the route search, the route search algorithm is executed for each region or layer, the route search is executed by connecting these results, and the processing of FIG. 8 is performed for each layer or region. Also good.

  As described above, the storage unit (or map storage device 102) stores the route search data storage unit 501 including the node indicating the position on the map and the link information indicating the relationship between the node and the node adjacent to the node. The plaintext map data 120 in which the data (data for route search) and the data (display data) stored in the map data storage unit 500 for displaying the feature in the node are associated, and the node and the display data are The encryption definition information 121 associated with the disclosure target user who is the user to be disclosed and the encryption key 122 for encrypting the route search data are stored, and the encryption processing unit 111 is used for route search. Based on the data, the encryption key 122, and the encryption definition information 121, a node to be encrypted is identified for each user, and the identified node and the identified node It encrypts the route search data of the adjacent node to generate encrypted map data 124 that associates display data and encrypted route search data.

  In addition, when the decryption processing unit 116 executes a search for a route from a point on the map to another point from the user, the decryption processing unit 116 determines the node indicating the position on the encrypted map and the node and the node. Based on the decryption key 123 for decrypting the data (route search data) stored in the route search data storage unit 501 including the link information indicating the relevance with the adjacent node, the route search data and the node The encrypted map data 124 associated with the data (display data) stored in the map data storage unit 500 for displaying a certain feature is decrypted, and the route search unit processing unit 1141 receives the data from a certain point to another The route to the point is repeated based on the node and link information included in the route search data using the decryption result of the encrypted map data 124 by the decryption processing unit 116. To search.

  Therefore, an appropriate route search can be performed for each user. That is, a route search using only the route search data that can be disclosed according to the type of user can be performed, and an appropriate route search result can be provided for each type of user.

  In route search, in order to efficiently perform data management or route search, data management may be performed for each hierarchy or area such as a building floor. In this case, the route search may be executed by executing a route search algorithm for each region or layer, and connecting these results. In that case, the route search from the final departure node to the destination node may be performed by performing route search for each hierarchy or region in the processing of FIG. 8 and combining these search results.

  Next, a case will be described in which an operation from an administrator or the like of the map data distribution system 1 is received and the map encryption apparatus 101 registers or changes the encryption definition information 121.

  FIG. 10 is a diagram illustrating an example of an implementation image of an application screen (GUI: Graphic User Interface) for generating the encryption definition information 121. In the following, the GUI for encrypting route search data will be described with reference to FIG. 10, but this GUI is extended when encrypting the features themselves or their attributes and geometry. However, these may be encrypted together.

  As shown in FIG. 10, the GUI includes a map display area 1 and a setting area 1001. Note that a file menu 1002, a database menu 1003, and a key reading menu 1004 at the top of the GUI represent menu tags for switching operations on the application screen. When each menu tag is selected, the following operation is performed (“Menu” is omitted in FIG. 10).

  When the file menu 1002 is active, the map encryption apparatus 101 reads the created encryption definition information 121 or saves the encryption definition information 121 being created. In addition, when the database menu 1003 is active, the map encryption apparatus 101 connects to the database storing the plaintext map data 120, reads the plaintext map data 120, and encrypts the storage destination. The map data 124 is designated. Also, the disclosure setting is ended and the encryption definition information 121 is generated. Further, the map encryption apparatus 101 reads the encryption key 122 necessary for setting the encryption definition information 121 when the key reading menu 1004 is active.

  In the above description, it is assumed that the database menu 1003 is arranged as the menu, and the plaintext map data 120 and the encrypted map data 124 are on the database system. However, the map data 120 and the encrypted map data are not necessarily used. 124 does not need to exist on the database system, and may exist as a file in a format such as CSV (Comma Separated Values).

  In the GUI shown in FIG. 10, the map display area 1000 displays the result of rendering the plaintext map data 120 and designates a node to be encrypted in accordance with an input from the input device 203 such as a mouse. In the specification, as illustrated in FIG. 10, all nodes included in the rectangular area may be set as encryption target nodes according to mouse input, or polygons, circles, or the like may be used. Alternatively, a node may be directly selected using a mouse, and the selected node may be selected as an encryption target node, or a feature is selected using a mouse, and a previous node included in the feature is set as an encryption target node. Also good.

  Hereinafter, the operation of the GUI illustrated in FIG. 10 will be described by taking as an example the case where the disclosure destination of the area selected by the mouse cursor 1005 illustrated in FIG. 10 is limited and the nodes included in the area are set.

  The setting area 1001 is a non-disclosure area for designating an area in which the plaintext map data 120 is not disclosed, a related feature indicating a feature included in the non-disclosure area, and a target indicating a node included in the non-disclosure area A node and a disclosure destination indicating a disclosure destination user.

  When the administrator selects an area with the mouse cursor 1005, a new item (referred to as area 2 in FIG. 10) is registered in the non-disclosure area item of the setting area 1001. In addition, a list of features related to the list of features included in area 2 is displayed, and a list of nodes included in area 2 is displayed in the target node column (N5 ( machine room)).

  Next, when a feature or area to be set is selected from the target feature list using the input device 203 such as a mouse by the administrator or the like (the area is selected in FIG. 10), the selected feature is selected. All attributes in the object are displayed on a sub-screen (not shown). At this time, the display color of the corresponding feature in the map display area 906 is changed or the boundary line is thickened to clearly indicate which feature on the map the selected feature is. May be.

  Next, a node for setting a disclosure destination is designated by selecting a feature from the target node or a feature in the related feature column. Then, the map encryption apparatus 101 receives the selection of the user designated as the disclosure destination from the disclosure destination column, and completes the setting for one area when the depression of the disclosure destination setting button is accepted. Information set in this way (for example, part A shown in FIG. 6) is output as the encryption definition information 121. In addition, in order to select all the nodes included in the feature, the feature in the related feature column may be selected. As described above, a plurality of nodes having the same disclosure destination are set. Furthermore, when a node having a different disclosure destination is set, the above process may be repeated.

Thus, since the map encryption apparatus 101 receives the setting and change of the encryption definition information 121 by GUI, the figure manager of the map data delivery system 1 can perform the setting and change easily.
(Second Embodiment)
In the first embodiment, the method of deleting the encryption target node and the connection link connected to the encryption target node from the node storage unit 502 and the link storage unit 503 after encryption has been described. In the second embodiment, a method for performing encryption and decryption by changing data in an encryption target node and a connection node will be described. Compared to the first embodiment, the second embodiment is characterized in that it is not necessary to destroy the structure of the route search data.

  Since the difference between the first embodiment and the second embodiment is only the encryption process and the decryption process, the difference between the encryption process and the decryption process in the first embodiment will be described below. explain.

  FIG. 11 and FIG. 12 are flowcharts showing the processing procedures of the encryption process and the decryption process in the second embodiment. FIG. 13 is a diagram illustrating an example of a change in the data structure before and after the encryption process. The encryption process and the decryption process will be described below with reference to these drawings.

  First, changes in the data structure before and after the encryption process will be described with reference to FIG. 13 is a diagram illustrating a part of the route search data storage unit 501 of the display image 510 illustrated in FIG. 5, as in FIG. 9.

  As in the case of the first embodiment, the encrypted path search data storage unit 504b includes a node storage unit 502b, a link storage unit 503b, and an encrypted data unit 505b. The node storage unit 502b includes an NID that is an identifier for uniquely identifying a node and coordinates representing the position of the node on the map, and the link storage unit 503b is an LID that is an identifier for uniquely identifying a link; It includes the start point NID representing the start point and end point node of the node, the end point NID, and the cost required to move the link.

  The reason why the link storage unit 503b is composed of the start point NID and the end point NID is to indicate that the movement route is unidirectional, and as in the case of the first embodiment, bidirectional data A structure may be used. Similarly to the first embodiment, the node storage unit 502b and the link storage unit 503b may include items other than those described above.

  In the first embodiment, the node to be encrypted and the connection link connected to the node are deleted from the node storage unit 502a and the link storage unit 503a, and the encryption flag of the adjacent node is set to T (TRUE). Data to be decoded at the time of search was specified. In the second embodiment, as shown in FIG. 13, data is not deleted from the node storage unit 502b and the link storage unit 503b. Instead, information stored in each storage unit is exchanged with other nodes and links. Rewrites information that can be distinguished attributes and values.

  In the example illustrated in FIG. 13, as in the first embodiment, the case where the node N5 is encrypted as the encryption target node is illustrated. As shown in FIG. 13, the coordinate information of the node (N5) to be encrypted is rewritten with the symbol “ENC” indicating that it is encrypted, and the cost of the connection link of the node (N5) to be encrypted is further reduced. The maximum value is set (“99” in the example shown in FIG. 13). The original coordinate information of the encryption target node and the cost of the connection link are encrypted by the same method as in the first embodiment and stored in the encrypted data unit 505b.

  If information other than coordinates cannot be stored in the coordinate information due to problems with the database or GIS product, the above rewriting to “ENC” is an alternative value meaning “ENC”. Alternatively, the coordinate information may be rewritten to another coordinate. In order to make the node position itself undisclosed, a random coordinate position may be used, but in order not to affect the use of the encrypted map data (encrypted map data 124). It is desirable to store unmanaged coordinate information in the plaintext map data 120.

  For example, when a plurality of nodes exist in the same feature, the coordinate information may be replaced with the center coordinates of the feature. As a result, the original coordinate position of the node can be made undisclosed to some extent. Further, when encrypting a plurality of nodes, as shown in the first embodiment, only the representative points may be left and the subsequent nodes and links may be deleted from the node storage unit 502b and the link storage unit 503b. . Note that the coordinate information need not be rewritten, but in this case, since only the cost is encrypted and the position where the node is arranged on the map is known, care is required.

  At the time of decryption, when the coordinate information of the node storage unit 502b is “ENC” or when the cost of the link storage unit 503b is the maximum value, the decryption processing unit 116 is based on the related data of the encrypted data unit 505b. Acquire and decrypt encrypted data to be decrypted. When a node and a link are decoded by this decoding process, a route search using the original map data (plain text map data 120) is performed by restoring the node coordinates and the link cost from the decoding result. Can be executed. On the other hand, if the decryption fails, the cost remains at the maximum value. Therefore, the cost can be deleted when compared with another optimum route when evaluating the cost of route search, or an unrealistic route. As can be deleted.

  Hereinafter, specific processing procedures of encryption and decryption processing in the second embodiment will be described with reference to FIGS. 11 and 12. First, the encryption process in the second embodiment will be described. FIG. 11 is a flowchart illustrating a processing procedure of encryption processing according to the second embodiment.

  As shown in FIG. 11, when the encryption processing in the second embodiment is started (step S1100), the encryption processing unit 111 converts the route search data storage unit 501a into the encrypted route search data storage unit. Copy to 504a (step S1101).

  Then, the encryption processing unit 111 refers to the encryption definition information 121 and determines whether there is an encryption target node to be encrypted (step S1102). If it is determined that there is an encryption target node to be encrypted (step S1102; Yes), the encryption processing unit 111 acquires the encryption target node described in the encryption definition information 121 (step S1103). Then, the encryption target node is changed (step S1104). On the other hand, if the encryption processing unit 111 determines that there is no encryption target node to be encrypted (step S1102; No), the encryption processing unit 111 ends the encryption process illustrated in FIG. 11 (step S1110).

  Then, the encryption processing unit 111 determines whether there is an unoperated link in the connection link connected to the changed encryption target node (step S1105), and is connected to the changed encryption target node. When it is determined that there is an unoperated link in the connection link (step S1105; Yes), the cost of the connection link is acquired (step S1106), and the acquired cost is set to the maximum value (step S107). Then, the encryption processing unit 111 repeatedly performs the processing from steps S1105 to S1107.

  On the other hand, if the encryption processing unit 111 determines that there is no unoperated link among the connection links connected to the encryption target node (step S1105; No), the encryption processing unit 111 and the coordinate information acquired in step S1103 The acquired cost is encrypted (step S1108), the encryption result is stored in the encrypted data storage unit 504a (step S1109), and the process returns to step S1102. Then, the encryption processing unit 111 repeatedly performs the processing from steps S1102 to S1109 for all the encryption target nodes described in the encryption definition information 121.

  In step S1102, for example, the encryption target node elements of the encryption definition information 121 illustrated in FIG. 6 may be sequentially processed and repeated until there are no encryption target node elements. In the example shown in FIG. 9, only one node (N6, link L14) is connected to the encryption target node (N5). However, as shown in steps S1105 to S1107, the connection link is not connected. When there are a plurality of links, the same processing is performed for all the connection links.

  As in the first embodiment, the encryption processing in step S1108 may be performed by encrypting a plurality of nodes instead of performing the nodes one by one. Further, when encrypting a plurality of nodes, the following may be performed. For example, if the node to be encrypted is in the same area instead of “ENC” when rewriting the coordinate information, the processing in step 1104 may store the center coordinates of the area. Further, in this case, as in the first embodiment, only the node that is a representative point may be left and other node links may be deleted from the node storage unit 502b and the link storage unit 503b. Note that in this case, it is necessary to rewrite the start point NID and the end point NID of the link storage unit 503b in accordance with the deleted node.

  Next, the decoding process in the second embodiment will be described. FIG. 12 is a flowchart illustrating a processing procedure of the decoding processing according to the second embodiment. As in the first embodiment, FIG. 12 shows a processing flow for performing the decoding process in the route search algorithm, and the route search algorithm itself shows only the outline of the procedure. Yes. The core processing of the route search algorithm is a portion indicated by a dotted line in FIG. Hereinafter, the decoding process shown in FIG. 12 will be described.

  As shown in FIG. 12, when the decoding process is started (step S1200), the decoding processing unit 116 of the map decoding apparatus 106 first sets the departure node as the start point node (step S1201).

  Then, the decoding processing unit 116 determines whether or not the route search has ended (step S1202). When the decoding processing unit 116 determines that the route search has ended (step S1202; Yes), the decoding processing illustrated in FIG. Is terminated (step S1210).

  On the other hand, when it is determined that the route search has not ended (step S1202; No), the decoding processing unit 116 refers to the node storage unit 502a and the link storage unit 503a, and determines the connection link (adjacent node) of the start point node. Search is performed (step S1203), and it is determined whether there is an unsearched adjacent node (step S1204).

  If the decryption processing unit 116 determines that there is an unsearched adjacent node (step S1204; Yes), whether there is encrypted data having the unsearched adjacent node as related data in the encrypted data unit 505b. If it is determined whether the encrypted data is in the encrypted data portion 505b (step S1205; Yes), the encrypted data is obtained from the encrypted data portion 505a, and the obtained encrypted data is obtained. Is decoded (step S1206). On the other hand, when the decryption processing unit 116 determines that the encrypted data is not in the encrypted data unit 505b (step S1205; No), the process proceeds to step S1209.

  The decryption processing unit 116 determines whether or not the decryption of the encrypted data acquired in step S1206 has succeeded (step S1207). When it is determined that the decryption has succeeded (step S1207; Yes), the decryption result in step S1206. Then, the node and the link are restored, and the restored node and link are added to the node storage unit 502b and the link storage unit 503b (step S1208). On the other hand, when the decoding processing unit 116 determines that the decoding has not been successful (failed) (step S1207; No), the process proceeds to step S1209.

  When the processing of either step S1205, step S1207, or step S1208 ends, the decoding processing unit 116 refers to the cost column in the link storage unit 503a, calculates the cost from the start point node to the adjacent node, and starts. Cost evaluation from the ground node to the adjacent node is performed (step S1209), and the process returns to step S1202. Then, the decoding processing unit 116 repeatedly performs the processing from steps S1202 to S1209 until the route search is completed.

  In the second embodiment, the cost of the connection link of the encryption target node is maximized at the time of encryption. As a result, if the encrypted data cannot be decrypted, in step S1209, the cost is evaluated from the starting node to the corresponding node as the maximum cost. When there is a path having the path, the path including the encryption node can be excluded. Accordingly, as shown in FIG. 5, the display image 510 that does not include such a route is finally displayed to the user.

  In step S1206 described above, it is desirable to stop the processing when the decoding stops abnormally, for example, when the decoding result is not a node or a link. Also, when the route search does not reach the destination node in the route search home, such as when the route search does not finish for a certain period of time or when it is an unrealistic cost (for example, it takes more than 100 years to move on foot) In step S1202, the process may be stopped.

  The decoding in step S1206 and the restoration of nodes and links in step S1208 may be performed not on a single node but on a plurality of nodes and links. For example, when a plurality of nodes are encrypted together at the time of the above-described encryption process, the decryption result in step S1206 includes a plurality of nodes and links, so step S1208 includes the decrypted nodes and links. All will be restored.

  In the above-described decryption processing, sequential decryption is performed within the route search algorithm. However, when there is little data to be decrypted in advance (for example, one encrypted data is included in the response from the map storage device 102 in step S403). In the case where only the data is included, the decoding processing unit 116 may perform the decoding processing collectively before the processing of FIG.

  Similarly to the first embodiment, in route search, data management may be performed for each hierarchy or area such as a building floor in order to efficiently perform data management or route search. In this case, the route search may be executed by executing a route search algorithm for each region or layer, and connecting these results. In that case, the route search from the final departure node to the destination node may be performed by performing route search for each layer or region in the processing of FIG. 12 and combining these search results.

  It should be noted that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. In addition, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the above embodiments. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined.

1: map data distribution system, 100: network, 101: map encryption device, 102: map storage device, 103: key management device, 104: map distribution device, 105: map browsing device, 106: map decryption device, 110: Encryption information generation unit 111: Encryption processing unit 112: Database processing unit 113: Key generation unit 114: Path search processing unit 115: Query request unit 116: Decryption processing unit 117: Query processing unit 118: Display processing unit, 120: Plain text map data, 121: Encryption definition information, 122: Encryption key, 123: Decryption key, 124: Encryption map data, 200: Computer, 201: CPU, 202: RAM, 203 : Input device, 204: display device, 205: communication device, 206: reading device, 207: external storage device, 208: external storage medium, 209: i 500: Map data storage unit, 501: Route search data storage unit, 502: Node storage unit, 503: Link storage unit, 510: Display image 510, 501a: Route search data storage unit, 502a: Node storage 503a: Link storage unit, 504a: Encrypted path search data storage unit, 505a: Encrypted data unit, 1000: Map display area, 1001: Setting area, 1002: File, 1003: Database, 1004: Key reading, 1005: Mouse cursor, 501b: Route search data storage unit, 502b: Node storage unit, 503b: Link storage unit, 504b: Encrypted route search data storage unit, 505b: Encrypted data unit.

Claims (6)

Route search data including a node indicating a position on a map and link information indicating a relationship between the node and a node adjacent to the node, and display data for displaying a map corresponding to the route search data; Is associated with map data, encryption definition information in which the node and a disclosure destination user, who is a user for disclosing the display data, and encryption for encrypting the route search data A storage unit for storing the activation key;
Based on the route search data, the encryption key, and the encryption definition information, the user specifies the node to be encrypted for each user, and is adjacent to the specified node and the specified node. An encryption processor that encrypts the route search data of link information with a node and generates encrypted map data in which the encrypted route search data and the display data are associated with each other;
An encryption device comprising: The encryption processing unit encrypts link information between the identified node and a node adjacent to the node as the route search data, and then deletes and further encrypts the node specified as the adjacent node. A decryption flag indicating that, and generating encrypted map data in which the encrypted route search data and the display data are associated with each other,
The encryption apparatus according to claim 1, wherein: The node includes coordinate information, and the link information includes cost information required from the node to a node adjacent to the node,
The encryption processing unit encrypts the coordinate information included in the specified node and the cost information included in the link information, and then sets information different from the coordinate information to the specified node, and specifies Updating the cost information by setting a value that maximizes the cost, and generating encrypted map data in which the encrypted route search data and the display data are associated with each other.
The encryption apparatus according to claim 1, wherein: When a route search request for searching a route from a point on the map to another point is received from the user, the node indicating the position on the map and the node and the node adjacent to the node Encryption in which a disclosure destination user who is a user for disclosing display data for displaying a map corresponding to route search data including the node and the link information is associated with link information indicating relevance Based on the definition information, the route search data, and the encryption key for encrypting the route search data, the node to be encrypted is identified for each user, and the identified node and if the route search data include link information and adjacent node identified the nodes is encrypted, encrypting the node identified in the adjacent node By determining whether it is set the decoded flag indicating the judges said route search data, whether or not to decrypt the encrypted map data to which the display data is associated , If it is determined that the encrypted map data should be decrypted, a decryption processing unit that replaces the encrypted data with a decryption result;
Encrypted map data using the decryption processing unit based on the node and the link information included in the route search data corresponding to the encrypted map data for a route from the certain point to the other point A route search unit that repeatedly performs a search based on the node and the link information using a decoding result;
A decoding device comprising: A route search system that searches a route from a point on a map to another point in response to a request from a user,
The map browsing device
A request unit for transmitting a request for searching for the route requested by the user via a network;
A display processing unit for displaying a result of searching for the route requested by the request unit,
The map storage device
A route search data including a node indicating a position on a map encrypted by an encryption key, and link information indicating a relationship between the node and a node adjacent to the node, and a map corresponding to the route search data A storage unit for storing encrypted map data associated with display data for display;
A search processing unit for searching the route search data from the encrypted map data encrypted by the encryption key, and transmitting the searched search result via the network,
The decryption device
A decryption processing unit that decrypts the encrypted map data based on a decryption key corresponding to the encryption key when the map storage device performs the search;
The route is decrypted using the decryption processing unit based on the node and the link information included in the route search data corresponding to the encrypted map data, and the decryption result is used. A route search unit that repeatedly searches based on the node and the link information and transmits the searched search results via the network,
Map distribution device
When the request is received from the map browsing device, the map storage device is requested to perform the search via the network, the search result is received, and the received search result is transmitted to the decoding device. A query processing unit that requests to perform the search and transmits the search result to the map browsing device via the network when the search result is received from the decoding device;
A route search system comprising: The map distribution device includes:
The query processing unit receives the search data and the display data as the search results from the map storage device, and displays them on the map browsing device based on the display data received from the decoding device. Map data to be generated, and the generated map data is transmitted to the map browsing device,
The decoding device
An image generation unit that generates the display data corresponding to the encrypted data decrypted based on the search data received from the map distribution device, and transmits the generated display data to the map distribution device Further comprising
The route search system according to claim 5.

Images