JP2012164031A - Data processor, data storage device, data processing method, data storage method and program - Google Patents

Abstract

Secure search using probabilistic encryption is speeded up safely.
A user terminal device 201 entropy-encodes a random value obtained uniquely from a storage keyword specified for document information to be stored, and a tag associated with the document information to be stored is a data center. A storage index value attached to the tag when stored in the apparatus 301 is generated, and the document information to be stored, the tag, and the storage index value are transmitted to the data center apparatus 301. In the data center device 301, tags can be classified and indexed using the storage index value, and the confidential search using probabilistic encryption can be safely accelerated.
[Selection] Figure 1

Description

  The present invention relates to a secret search technique.

The secret search is a technique for searching encrypted data while encrypting it.
In recent years, when managing data on the Internet such as a cloud service, it is attracting attention as a security technology for protecting against threats such as eavesdropping.

There are two methods for retrieving encrypted data: a method using deterministic encryption and a method using probabilistic encryption.
In the method using deterministic encryption, the same ciphertext can be obtained when the same keyword is encrypted. Therefore, the same speed-up method as the database search system without encryption can be used (for example, the same keyword) Keyword tag grouping).
On the other hand, a method using probabilistic encryption results in different ciphertexts even when the same keyword is encrypted.
Therefore, a method of simply grouping the same ciphertext (as binary data) cannot be used.
In particular, in a method using probabilistic encryption, a security proof is often added, and it is mathematically proved that no information can be obtained from the ciphertext.
For this reason, indexing using (partial) information of keywords is difficult.

  Next, a keyword search system using probabilistic encryption will be described.

In secret search using probabilistic encryption, data search is generally performed between a user (searcher, registrant) and a data center (data manager) as follows.
A data registrant registers document data and tag data (hereinafter referred to as a tag) obtained by encrypting meaningless plaintext using a keyword for searching for the document information as a key.
The data center stores tags and document information in pairs.
At the time of search, the searcher sends a search query created with a keyword to be searched to the data center.
The data center uses the search query to perform a matching check with the stored tag.
If they match, the document information stored in the group is returned to the searcher.
In the above description, the document information includes a document itself encrypted with a different encryption from the search system, a document name, location information of a database storing the document, and the like.
In the above, the search query is a decryption key for decrypting a tag encrypted with a keyword corresponding to the search term. Further, the search keyword cannot be read from the search query.

As a simple confidential search method, for example, there is a method described in Non-Patent Document 1.
This realizes a secret search for a single keyword.

In the secret search, the data center cannot obtain any information in any of the tag, the search query, and the matching check, so that high security is provided.
However, there is a problem that the search speed is low because all the stored tags must be inspected at the time of a matching check performed in the data center.
As a solution to this problem, Patent Document 1 proposes a method of speeding up using a search history. Patent Document 2 proposes a method of constructing an index tree using a Bloom filter.
The Bloom filter is a filter for determining whether a certain element is included in the set with respect to the set registered in the filter.

JP 2005-134990 A JP 2007-52698 A

D Boneh, G.D. D. Crescenzo, R.A. Ostrovsky, Persiano G, “Public Key Encryption with Keyword Search”, Proceedings of EUROCRYPT '04, vol. 3027 LNCS, pp. 506-522 (2004)

Non-patent document 1 is the most basic method of confidential search.
This method is a secret search method using ID-based encryption (hereinafter referred to as IBE: Identity-Based Encryption).
IBE encrypts data using an ID as a key.
An ID such as an e-mail address, an address, or a name can uniquely identify a user.
Since ID is used as a key, anyone can encrypt data.
Only the person who has the decryption key corresponding to the ID (generally the owner of the ID used for encryption) can decrypt the encrypted data.
First, the data registrant uses the IBE encryption function to encrypt the meaningless plaintext using the keyword as a key (ID) and sets the keyword to be set in the document information as a document information tag to the data center along with the document information. save.
Since the tag is encrypted, no information about keywords is leaked.
Next, the searcher generates a search query from the keyword to be searched and its own secret key (user key), and transmits it to the data center.
A third party cannot obtain keyword information from a search query.
The data center that has received the search query executes IBE decryption processing on the stored tag using the search query.
When a meaningless plaintext can be correctly decrypted, it means that the keyword (keyword set in the document information) used for encryption corresponds to the ID (search keyword) used when generating the search query. The data center can know only the search result “match”.

Patent Document 1 is a mechanism for storing a search result with a certain search keyword in an index and responding the search result at a high speed when the same keyword is searched after the next time.
The method of Patent Document 1 can return a search result to a searcher at high speed for a keyword once searched, but a keyword that has never been searched is stored in a data center. It is necessary to search all tags.
Therefore, there is a problem that it takes a lot of time to obtain a search result for a keyword searched for the first time in a database storing a huge number of tags.

The method of Patent Document 2 is a method for creating a Bloom filter from a keyword encrypted with deterministic encryption and constructing an index tree.
In this method, it is necessary to calculate the Hamming distance between Bloom filters stored in the data center. Therefore, when the number of stored Bloom filters increases, the calculation amount for generating the index tree increases rapidly. is there.
Further, there is a limit to identification of keywords included in the Bloom filter due to the size of the Bloom filter.
In particular, because of the false positive problem, it is necessary to prepare a sufficiently large filter in consideration of the number of keyword types that may be registered in the Bloom filter.
In addition, when one keyword corresponds to one Bloom filter (when only a single keyword is input to the Bloom filter), the data center corresponding to the Bloom filter is analyzed to analyze the data center. There is a problem that information on keyword distribution leaks.

Most other similar index methods manage data groups corresponding to a single keyword.
Therefore, the data center can know the keyword distribution, and there is a problem that “frequency analysis” for estimating the keyword can be performed by collating with the distribution known from experience.

  The main object of the present invention is to solve the above-described problems, and it is an object of the present invention to speed up a secure search using probabilistic encryption safely.

The data processing apparatus according to the present invention
Connected to a data storage device that stores a plurality of encrypted data and tag data that is associated with each encrypted data and that is collated when searching for the encrypted data;
A keyword designating unit for designating a keyword of data to be stored to be stored in the data storage device as a storage keyword;
An index value assigned to the tag data when the tag data associated with the encrypted data of the storage target data is stored in the data storage device by entropy encoding a random value uniquely obtained from the storage keyword An index generation unit for generating
A communication unit that transmits a storage request including encrypted data of the storage target data, the tag data, and the index value to the data storage device.

  According to the present invention, in a data processing apparatus, a random number value uniquely obtained from a storage keyword is entropy-encoded, and tag data associated with encrypted data of storage target data is stored in the data storage apparatus. In order to generate an index value to be assigned to data, tag data can be classified and indexed by using the index value in the data storage device, and secure search using probabilistic encryption can be safely accelerated. it can.

FIG. 3 is a diagram illustrating a configuration example of a confidential search system according to the first embodiment. FIG. 3 shows a configuration example of a user terminal device according to the first embodiment. FIG. 3 shows a configuration example of a data center apparatus according to the first embodiment. FIG. 4 is a diagram showing a data configuration example of a search request according to the first embodiment. FIG. 3 is a diagram illustrating a data configuration example of registration data according to the first embodiment. FIG. 3 is a diagram showing a data configuration example of index information according to Embodiment 1. FIG. 4 is a diagram showing an example of data storage in the data storage unit according to the first embodiment. The flowchart figure which shows the index value production | generation process in the user terminal device which concerns on Embodiment 1. FIG. FIG. 3 is a flowchart showing data registration processing in the data center apparatus according to the first embodiment. FIG. 3 is a flowchart showing search processing in the data center device according to the first embodiment. The figure which shows the example of the hash calculation which concerns on Embodiment 1, and the example of Huffman encoding. The figure which shows the hardware structural example of the user terminal device and data center apparatus which concern on Embodiment 1. FIG.

Embodiment 1 FIG.
In the present embodiment, a configuration for speeding up a secure search using probabilistic encryption by classifying and indexing keyword tags using entropy codes will be described.
In the present embodiment, a description will be given using a Huffman code as an example of the entropy code.
Further, in this embodiment, an example will be described in which a code value obtained by Huffman coding a keyed hash value of a keyword between a user (searcher, registrant) and a data center (data manager) is used as an index value. .

The general flow in the present embodiment is as follows.
First, the data registrant encodes the “document information” related to the document to be stored and the “tag data (hereinafter referred to as a tag)” generated from the keyword related to the document and the keyed hash value of the keyword with a Huffman code Store the value (index value) in the data center.
Here, the document information includes a document itself encrypted with a different encryption from the search system, a document name, location information of a database storing the document, and the like.
The document itself cannot be viewed from the document information.
The tag is a value obtained by encrypting meaningless plaintext (random number) using a keyword as an encryption key and used when searching for document information.
The data center stores tags and document information in pairs, and builds an index using index values.
At the time of search, the searcher transmits a search query created with the keyword to be searched and an index value generated from the search keyword in the same procedure as at the time of registration to the data center.
The data center limits the tags to be searched from the received index values, and performs a matching check with these tags using a search query.
If they match, the document information stored in the group is returned to the searcher.
In the following, when document information is stored in a data center, a keyword specified for the document information to be stored is also expressed as a storage keyword, and a keyword specified at the time of search is also expressed as a search keyword.
An index value stored in the data center together with the document information and the tag is also referred to as a storage index value, and an index value transmitted to the data center together with the search query at the time of search is also referred to as a search index value.

Next, the configuration of the secret search system according to the present embodiment will be described.
FIG. 1 is a diagram illustrating a configuration example of a secret search system according to the present embodiment.

In FIG. 1, the confidential search system 100 includes a user terminal device 201 and a data center device 301.
A user terminal device 201 is connected to an in-house LAN (Local Area Network) 102.
The in-house LAN 102 is connected to the data center device 301 via the network 101.

The user terminal device 201 is a PC (Personal Computer) used by corporate users.
The user terminal device 201 stores the document information and a tag for searching for the document information in the data center device 301, searches for the tag stored in the data center device 301, and extracts the document information from the data center device 301.
The user terminal device 201 is an example of a data processing device.

The data center device 301 is a server device having a large-capacity storage device that stores document information and tags created in a company.
In addition, it has an index value using an entropy-encoded value of a keyword ciphertext (or hash value) transmitted from the user terminal device 201, and has a function of efficiently searching for a stored tag.
Since the tag is stored in an encrypted state, the data center device 301 cannot know the keyword from the tag.
The data center device 301 is an example of a data storage device.

The network 101 is a communication path that connects the in-house LAN 102 and the data center device 301.
An example of a typical network 101 is the Internet.

The in-house LAN 102 is a communication path established in the company, and is connected to various server devices and PCs used in the company.
The communication path is a complicated communication path composed of a dedicated line, a radio, a router, and the like.

FIG. 2 is a block diagram illustrating a configuration example of the user terminal device 201.
A user terminal device 201 includes a document / key storage area 202, a document information management unit 203, a user I / F (Interface) unit 204, a search query generation unit 205, a tag generation unit 206, a communication unit 207, and an index generation unit 208. Is provided.

The document / key storage area 202 stores an original document for generating document information to be stored in the data center device 301, a user secret key for generating a search query, and a public key for generating a tag.
When using data obtained by encrypting a document as document information, a key for encrypting the document information is also stored.
The index generation unit 208 stores a key for encrypting (or hashing) the keyword obtained from the user I / F 204.

The document information management unit 203 generates document information based on the document stored in the document / key storage area 202.
Documents cannot be viewed from document information.
Examples of document information include a document itself encrypted with a different encryption from the search system, a document name, and location information of a database storing the document.
That is, the document information management unit 203 encrypts a document to be stored (storage target data) in the data center device 301 to generate document information (encrypted data of storage target data).

The user I / F unit 204 is an interface for operating the confidential search system 100.
A function for inputting keywords for the search query generation unit 205 and the tag generation unit 206 from the user is provided.
That is, the user I / F unit 204 specifies a storage keyword and a search keyword in accordance with an instruction from the user.
The user I / F unit 204 is an example of a keyword specifying unit.

The search query generation unit 205 generates a search query from the keyword that the user wants to search via the user I / F unit 204 and the user key stored in the document / key storage area 202.
That is, the search query generation unit 205 generates a decryption key for decrypting a tag corresponding to the search keyword as a search query.
The search query generation unit 205 is an example of a search keyword concealment unit.

  The tag generation unit 206 generates tag data from the keyword that the user wants to set in the document input via the user I / F unit 204 and the public key stored in the document / key storage area 202.

The communication unit 207 performs a search request (search query and search index value) for executing a search with respect to the data center device 301, and registration data for newly storing document information and a tag with respect to the data center device 301. In order to transmit (document information, tag, storage index value) to the data center apparatus 301, it is connected to the in-house LAN 102.
The registration data is also called a storage request.

The index generation unit 208 hashes the keyword received from the user I / F unit 204 using a common key (common key between the data registrant and the searcher) stored in the document / key storage area 202. Calculate the value (hereinafter referred to as keyed hash value).
Further, a value obtained by performing Huffman coding on the keyed hash value is output as an index value.
That is, the index generation unit 208 Huffman-codes a random value uniquely obtained from the storage keyword, and generates an index value (storage index value) attached to the tag when the tag is stored in the data center device 301. .
Further, the index generation unit 208 performs Huffman coding on a random value uniquely obtained from the search keyword, and selects a tag to be collated with the search query (the concealed search keyword) in the data center device 301. Therefore, an index value (search index value) to be compared with the storage index value stored in the data center device 301 is generated.

FIG. 3 is a block diagram illustrating a configuration example of the data center device 301.
The data center device 301 includes a search request receiving unit 302, a search processing unit 303, an index storage unit 304, a data storage unit 305, an index classification unit 306, a search request answering unit 307, and a registered data receiving unit 308.

When the registration data receiving unit 308 receives the registration data (storage request) from the user terminal device 201, the registration data receiving unit 308 gives a tag ID (Identification) to the tag included in the received registration data, and stores the storage index value and the index classification unit 306. The tag ID and document information are transferred to the data storage unit 305, respectively.
The tag ID is an identifier that can uniquely identify the tag.
The registration data receiving unit 308 is an example of a storage request receiving unit.

The index classification unit 306 has a function of receiving a storage index value and a tag ID as registration data from the registration data receiving unit 308 and adding index information to the index storage unit 304.
That is, the index classification unit 306 generates index information that associates a tag ID with a storage index value.
The index classification unit 306 is an example of an index information generation unit.
The index classification unit 306 has a function of extracting a corresponding tag ID group from the index storage unit 304 from a search index value received from the search processing unit 303 described later.

The index storage unit 304 has a function of storing index information indicating a correspondence between stored index values and tag IDs.
In the index information stored in the index storage unit 304, one or more tag IDs correspond to one storage index value.

  The data storage unit 305 stores the document information received from the registered data reception unit 308 in association with the tag.

  The search request receiving unit 302 receives the search request transmitted from the user terminal device 201 and transfers it to the search processing unit 303.

The search processing unit 303 receives the search request from the search request receiving unit 302, transmits the search index value included in the search request to the index classification unit 306, and the storage index value that matches the search index value is stored in the index storage unit 304. If it exists, the search target tag obtained from the storage index value is taken out from the data storage unit 305 and checked for a match with the search query.
Then, the search processing unit 303 transmits the document information obtained from the result of the matching check to the user terminal device 201 via the search request answering unit 307.
That is, the search processing unit 303 refers to the index information stored in the index storage unit 304, and sets one or more tag IDs associated with the storage index value that matches the search index value included in the search request. elect.
Further, the search processing unit 303 extracts a tag corresponding to the selected tag ID from the data storage unit 305, and checks each extracted tag with a search query (a concealed search keyword) included in the search request. The tag generated from the storage keyword that matches the search keyword is specified, and the document information associated with the specified tag is extracted from the data storage unit 305.
The search processing unit 303 corresponds to an example of a tag ID selection unit and a data extraction unit.

  The search request answering unit 307 transmits the document information searched by the search processing unit 303 to the user terminal device 201 that is the search request source.

  FIG. 4 shows an example of the data structure of the search request 2001 according to this embodiment.

Here, this configuration example is referred to as a search request A.
The search request A includes a search query 2002 and an index value 2004.
The search query 2002 is generated using the user secret key stored in the document / key storage area 202 and the search keyword 2003.
The search keyword 2003 cannot be known from the generated search query 2002.
The data center device 301 uses the search query 2002 to perform a matching check with the tag, and extracts a tag generated from the same storage keyword as the search keyword 2003.
The index value 2004 is an entropy code value obtained from the search keyword 2003 by the procedure of FIG.

  FIG. 5 shows an example of the data structure of the registration data 2301 according to this embodiment.

Here, this configuration example is registered data A.
The registration data A includes document information 2302, a tag 2303, and an index value 2305.
The document information 2302 is, for example, a document itself encrypted with a different encryption from the search system, a document name, location information of a database storing the document, and the like, and browsing the document itself from the document information Can not.
A tag 2303 is data obtained by encrypting a meaningless plaintext using a storage keyword 2304 for the document information 2302 and a public key stored in the document / key storage area 202 as keys, which are given by the user.
The index value 2305 is an entropy code value obtained from the storage keyword 2304 by the procedure of FIG.

The index value in the present embodiment is a binary bit string.
As for the structure of the index information, the tag ID to be searched may be obtained from the index value.
In the present embodiment, the index information uses the simplest form of an inverted index as an example, but an index tree using a binary tree or a B-tree may be configured.

FIG. 6 shows an example of the data structure of the index information 3001 stored in the index storage unit 304.
The index information 3001 includes an index value 3002 and a tag ID 3003.
The index value 3002 is a value (storage index value) obtained by entropy encoding the keyed hash value of the keyword set in the document information.
The tag ID 3003 is an ID corresponding to the storage keyword tag used to generate the index value 3002.
In the search, a tag obtained from a tag ID group associated with the same storage index value as the search index value designated by the searcher is set as a matching check target.

As shown in FIG. 7, the data storage unit 305 stores data in the form of a table having tag IDs 3051, tags 3052, and document information 3053 in columns.
The tag ID 3051 is given by the registration data receiving unit 308 and matches the tag ID stored in the index storage unit 304.

  FIG. 8 is a flowchart for explaining an index value calculation method according to the present embodiment.

First, in step S3061, the index generation unit 208 calculates a hash value using the key input from the user I / F unit 204 using the key stored in the document / key storage area 202 (this embodiment). Although it is a hash value in the form, it may be a common key encrypted value).
At this time, the hash function used when calculating the hash value of the keyword needs to be calculated from the same keyword.
Also, it is desirable that only the data registrant and the searcher hold the encryption key so that the data center cannot calculate the hash value of the keyword.
For example, a deterministic encryption unrelated to the encryption database or a hash function with a key is used.
In the present embodiment, a keyed hash value of a keyword is used to avoid confusion of terms and simplify the explanation.

Next, in step S3062, the index generation unit 208 performs entropy encoding on the value generated in step S3061.
In this embodiment, a Huffman code is used as the entropy code.

Next, in step S3063, the index generation unit 208 transmits the code value output in step S3062 to the communication unit 207 as an index value.
An example using a Huffman code as an entropy code is shown below.

Document information having “original”, “confirm”, and “share” as keywords are D (“original”), D (“confirm”), and D (“share”), respectively.
Further, the tag added to each document information is tag (“original”), tag (“confirm”), tag (“share”), and tag IDs assigned to the tags are 1, 2, 3, respectively. To do.
When expressed as (tag, tag ID), they are (tag ("original"), 1), (tag ("confirm"), 2), (tag ("share"), 3).

Next, hash values of the keywords “original”, “confirm”, and “share” are calculated.
For example, when each hash value is taken with the hash algorithm SHA256, a hexadecimal number (0-9, af) as shown in FIG. 11A is obtained.
Due to the nature of SHA256, keywords cannot be obtained from this hash value.

Next, the obtained hash value is Huffman encoded.
When Huffman coding is performed, binary numerical values can be obtained as shown in FIG.
A binary number obtained by Huffman coding the hash value of this keyword is used as an index value.

The Huffman code value cannot be restored without a conversion table at the time of encoding.
In this embodiment, since the Huffman code conversion table is discarded, the hash value cannot be restored from the code value.
Further, since the index values of “original” and “confirm” are the same, tag (“original”) and tag (“confirm”) are stored in the same entry in the index information of the data center device 301. .
For this reason, the tag distribution cannot be read from the index value as in a simple index technique, so that it is possible to prevent keyword frequency analysis and it is safer.

Next, the operation of the confidential search system 100 will be described.
FIG. 9 is a flowchart illustrating an example of data registration processing according to the present embodiment.
This processing is performed by the data center device 301.

First, in step S 401, the data center device 301 receives registration data A transmitted from the user terminal device 201 via the network 101 by the registration data receiving unit 308.
The registration data A is as the registration data 2301 in FIG.
The registration data receiving unit 308 gives a tag ID to the received tag 2303.
The tag ID, document information 2302, and tag 2303 are transmitted to the data storage unit 305, and the tag ID and index value 2305 are transmitted to the index classification unit 306.

  In step S402, the index classification unit 306 refers to the index storage unit 304 in order to check whether the index value received from the registered data reception unit 308 already exists in the index information.

In step S <b> 403, the index classification unit 306 checks whether the index value received from the registered data reception unit 308 is included in the entry of the index information 3001 stored in the index storage unit 304.
If there is a corresponding entry already (corresponding), the process proceeds to step S404.
If there is no corresponding entry (not applicable), the process proceeds to step S406.

  Next, in step S404, the index classification unit 306 adds the tag ID received from the registered data reception unit 308 to the tag ID 3003 of the entry of the corresponding index information 3001.

  In step S 405, the data storage unit 305 stores the tag ID, document information 2302, and tag 2303 received from the registered data reception unit 308.

  Next, a case where the index value received from the registered data receiving unit 308 does not exist in the index information 3001 stored in the index storage unit 304 in step S403 will be described.

In step S <b> 406, the index classification unit 306 creates a new entry from the tag value corresponding to the index value received from the registered data reception unit 308, and adds a new entry to the index information 3001.
Thereafter, step S405 is executed.

The above is the description of the operation of the data registration process.
Next, the data search process will be described.
FIG. 10 is a flowchart for explaining an example of data search processing according to the present embodiment.

  First, in step S <b> 501, the data center device 301 receives a search request A transmitted from the user terminal device 201 via the network 101 by the search request receiving unit 302.

Next, in step S <b> 502, the search request receiving unit 302 transfers the search request A to the search processing unit 303.
The search processing unit 303 transfers the index value 2004 included in the search request A to the index classification unit 306 in order to refer to the index information.

  In step S <b> 503, the index classification unit 306 checks whether the index information 2004 stored in the index storage unit 304 includes the index value 2004 received from the search processing unit 303.

Next, when the index value 2004 of the search request A does not exist in the index storage unit 304 in the inspection of S503 (not applicable), the index classification unit 306 sends the search request A to the search processing unit 303 in step S504. That the search keyword 2003 included in the data storage unit 305 does not exist.
The search processing unit 303 does not search the data storage unit 305, and replies through the search request response unit 307 that the corresponding data does not exist to the user terminal device 201 that has made the search request.

Next, if the index value 2004 of the received search request A exists in the index storage unit 304 as a result of the inspection in S503 (applicable), the index classification unit 306 changes the index information 3001 to the index value 2004 in step S505. The corresponding tag ID group is returned.
The search processing unit 303 refers to the corresponding tag from the data storage unit 305 using the tag ID group corresponding to the index value 2004, and performs a keyword matching check using the search query 2002 included in the search request A.

Next, if there is a tag that matches the search request A as a result of the search in S505, the search processing unit 303 reads the document information corresponding to the corresponding tag from the data storage unit 305 in step S504, and returns a search request response. A response is made to the user terminal device 201 that has made a search request via the unit 307.
If the data corresponding to the search request does not exist in the data storage unit 305, the search processing unit 303 indicates that there is no corresponding data in the user terminal device 201 that made the search request via the search request answering unit 307. To answer.

  According to the above procedure, the method for searching data in the encrypted database while being encrypted can be safely and rapidly performed.

  According to the above embodiment, by using the entropy code of the hash value of the search keyword, it is possible to configure an index without leaking information related to the search keyword, and an effect that a high-speed search can be performed is achieved. is there.

  Further, the index configured in this embodiment can group search tags corresponding to one or more keywords, and has an effect of concealing the distribution of data corresponding to the keywords from the index.

  Further, it is not necessary to reconstruct the index with respect to an increase in the number of saved keywords, and there is an effect that the amount of calculation for maintaining the index is reduced.

  In the present embodiment, an example is disclosed in which a value obtained by encoding a keyed hash value of a keyword using a Huffman code is used as an index value. (Encryption) may be used.

  In this embodiment, the Huffman code is used as the entropy code. However, any entropy code may be used, and for example, an arithmetic code may be used.

  In this embodiment, the simplest inverted index format is used as an example, but it is sufficient that the tag ID to be searched can be obtained from the index value, and an index tree using a binary tree or a B-tree is constructed. Also good.

As mentioned above, although the index method using the entropy code in the secret search has been disclosed, this is not limited to the keyword search of the document information, but can be applied to any key data (search key) for search corresponding to arbitrary data. Clearly it is possible.
In other words, the keyword described in the present embodiment means not only words and sentences but also all types of key data.
Thus, according to the present embodiment, it is possible to perform a search using a plurality of search keys at a high speed while the data is encrypted.
Therefore, application to image search, video search, voice search, etc. is possible.

As described above, in the present embodiment,
An index generation unit that generates an index value from a search keyword and a keyword set in document information;
A registration data receiving unit for receiving a keyword tag and document information of a new registration target;
A data storage unit for storing all keyword tags and document information received from the registered data receiving unit;
Stores an index that holds a plurality of entries consisting of a value (index value) obtained by entropy encoding a random value (ciphertext or hash value) uniquely obtained from a keyword and a tag ID indicating a keyword tag corresponding to the index value. An index storage unit,
When an index value included in a search request exists in the index storage unit, a search processing unit that takes out a corresponding tag from the tag ID to be searched from the data storage unit and checks whether the keyword matches a tag,
At the time of data retrieval, the corresponding tag ID is extracted from the index storage unit from the index value received from the index processing unit, and at the time of data registration, index information is added to the index storage unit using the index value and tag received from the registered data reception unit A secret search system including an index classification unit to perform was described.

In the present embodiment,
The index generation unit calculates an entropy code value from a keyword set in document information at the time of data registration and a search keyword at the time of data search, and outputs it as an index value.
It has been described that the index classification unit stores and refers to the index value output by the index generation unit and the tag ID indicating the tag corresponding to the index value.

In the present embodiment,
It has been described that the index classification unit stores and refers to the index value output by the index generation unit and the tag ID indicating the tag corresponding to the index value in the index storage unit in a tabular format.

In the present embodiment,
The index classification unit stores and references the index value output by the index generation unit and the tag ID indicating the tag corresponding to the index value in the index storage unit in a tree format (binary tree, B-tree, etc.). Explained.

Finally, a hardware configuration example of the user terminal device 201 and the data center device 301 shown in the present embodiment will be described.
FIG. 12 is a diagram illustrating an example of hardware resources of the user terminal device 201 and the data center device 301 illustrated in the present embodiment.
The configuration of FIG. 12 is merely an example of the hardware configuration of the user terminal device 201 and the data center device 301, and the hardware configuration of the user terminal device 201 and the data center device 301 is described in FIG. It is not limited to this configuration, and other configurations may be used.

In FIG. 12, the user terminal device 201 and the data center device 301 include a CPU 911 (also referred to as a central processing unit, a central processing unit, a processing unit, an arithmetic unit, a microprocessor, a microcomputer, and a processor) that executes a program. .
The CPU 911 is connected to, for example, a ROM (Read Only Memory) 913, a RAM (Random Access Memory) 914, a communication board 915, a display device 901, a keyboard 902, a mouse 903, and a magnetic disk device 920 via a bus 912. Control hardware devices.
Further, the CPU 911 may be connected to an FDD 904 (Flexible Disk Drive) or a compact disk device 905 (CDD). Further, instead of the magnetic disk device 920, a storage device such as an SSD (Solid State Drive), an optical disk device, or a memory card (registered trademark) read / write device may be used.
The RAM 914 is an example of a volatile memory. The storage media of the ROM 913, the FDD 904, the CDD 905, and the magnetic disk device 920 are an example of a nonvolatile memory. These are examples of the storage device.
The document / key storage area 202, the index storage unit 304, and the data storage unit 305 described in the present embodiment are realized by the RAM 914, the magnetic disk device 920, and the like.
The communication board 915, the keyboard 902, the mouse 903, the FDD 904, and the like are examples of input devices.
The communication board 915, the display device 901, and the like are examples of output devices.

As shown in FIG. 1, the communication board 915 is connected to a network.
For example, the communication board 915 may be connected to a WAN (wide area network), a SAN (storage area network), or the like in addition to the LAN and the Internet.

The magnetic disk device 920 stores an operating system 921 (OS), a window system 922, a program group 923, and a file group 924.
The programs in the program group 923 are executed by the CPU 911 using the operating system 921 and the window system 922.

The RAM 914 temporarily stores at least part of the operating system 921 program and application programs to be executed by the CPU 911.
The RAM 914 stores various data necessary for processing by the CPU 911.

The ROM 913 stores a BIOS (Basic Input Output System) program, and the magnetic disk device 920 stores a boot program.
When the user terminal device 201 and the data center device 301 are activated, the BIOS program in the ROM 913 and the boot program in the magnetic disk device 920 are executed, and the operating system 921 is activated by the BIOS program and the boot program.

  The program group 923 stores a program for executing the function described as “˜” in the description of the present embodiment (other than “index storage unit 304 and data storage unit 305”). . The program is read and executed by the CPU 911.

In the description of the present embodiment, the file group 924 includes “determination of”, “calculation of”, “encryption of”, “encoding of”, “comparison of”, and “verification of”. ”,“ Refer to ”,“ search for ”,“ extract ”,“ examine ”,“ generate ”,“ set ”,“ register ”,“ select ”, Information, data, signal values, variable values, and parameters indicating the results of the processing described as “input of”, “reception of”, etc. are stored as items of “˜file” and “˜database”. ing.
The “˜file” and “˜database” are stored in a recording medium such as a disk or a memory.
Information, data, signal values, variable values, and parameters stored in a storage medium such as a disk or memory are read out to the main memory or cache memory by the CPU 911 via a read / write circuit.
The read information, data, signal value, variable value, and parameter are used for CPU operations such as extraction, search, reference, comparison, calculation, calculation, processing, editing, output, printing, and display.
Information, data, signal values, variable values, and parameters are stored in the main memory, registers, cache memory, and buffers during the CPU operations of extraction, search, reference, comparison, calculation, processing, editing, output, printing, and display. It is temporarily stored in a memory or the like.
In addition, the arrows in the flowchart described in this embodiment mainly indicate input / output of data and signals.
Data and signal values are recorded on a recording medium such as a memory of the RAM 914, a flexible disk of the FDD 904, a compact disk of the CDD 905, a magnetic disk of the magnetic disk device 920, other optical disks, a mini disk, and a DVD.
Data and signals are transmitted online via a bus 912, signal lines, cables, or other transmission media.

In addition, what is described as “˜unit” in the description of the present embodiment may be “˜circuit”, “˜device”, “˜device”, and “˜step”, “˜”. “Procedure” and “˜Process” may be used.
That is, the data processing method and the data storage method according to the present invention can be realized by the steps, procedures, and processes shown in the flowchart described in the present embodiment.
Further, what is described as “˜unit” may be realized by firmware stored in the ROM 913.
Alternatively, it may be implemented only by software, or only by hardware such as elements, devices, substrates, and wirings, by a combination of software and hardware, or by a combination of firmware.
Firmware and software are stored as programs in a recording medium such as a magnetic disk, a flexible disk, an optical disk, a compact disk, a mini disk, and a DVD.
The program is read by the CPU 911 and executed by the CPU 911.
In other words, the program causes the computer to function as “to part” of the present embodiment. Alternatively, the procedure or method of “˜unit” in the present embodiment is executed by a computer.

As described above, the user terminal device 201 and the data center device 301 shown in the present embodiment are output devices such as a CPU as a processing device, a memory as a storage device, a magnetic disk, a keyboard as an input device, a mouse, a communication board, and the like. A computer including a display device, a communication board, and the like.
Then, as described above, the functions indicated as “˜units” are realized using these processing devices, storage devices, input devices, and output devices.

  DESCRIPTION OF SYMBOLS 100 Secret search system, 101 Network, 102 Internal LAN, 201 User terminal device, 202 Document / key storage area, 203 Document information management part, 204 User I / F part, 205 Search query generation part, 206 Tag generation part, 207 Communication unit, 208 Index generation unit, 301 Data center device, 302 Search request reception unit, 303 Search processing unit, 304 Index storage unit, 305 Data storage unit, 306 Index classification unit, 307 Search request response unit, 308 Registration data reception Department.

Claims (13)

Connected to a data storage device that stores a plurality of encrypted data and tag data that is associated with each encrypted data and that is collated when searching for the encrypted data;
A keyword designating unit for designating a keyword of data to be stored to be stored in the data storage device as a storage keyword;
An index value assigned to the tag data when the tag data associated with the encrypted data of the storage target data is stored in the data storage device by entropy encoding a random value uniquely obtained from the storage keyword An index generation unit for generating
A data processing apparatus comprising: a communication unit that transmits a storage request including encrypted data of the storage target data, the tag data, and the index value to the data storage apparatus. The data processing device includes:
When a search request including a search keyword that is concealed and an index value of tag data that is a target of collation with the concealed search keyword is received, it matches the index value included in the search request The tag data associated with the index value is extracted, connected to the data storage device that searches the encrypted data by comparing the extracted tag data with the concealed search keyword,
The index generation unit
The data processing apparatus according to claim 1, wherein an index value to be compared with an index value included in the search request is generated in the data storage apparatus. The data processing device includes:
Connected to a data storage device that stores encrypted data, tag data, and index values in association with each other,
The keyword designating part is
Specify a search keyword that causes the data storage device to search for encrypted data;
The data processing device further includes:
A search keyword concealment unit that conceals the search keyword;
The index generation unit
A random number value uniquely obtained from the search keyword is entropy-encoded and stored in the data storage device to select tag data to be collated with a concealed search keyword in the data storage device. Generate an index value that is compared with the index value
The communication unit is
The data processing apparatus according to claim 1, wherein a search request including the concealed search keyword and the index value is transmitted to the data storage apparatus. The index generation unit
A hash value of the storage keyword is calculated, the calculated hash value is Huffman-encoded, and tag data associated with the encrypted data of the storage target data is attached to the tag data when stored in the data storage device. Index value to be generated,
The data for calculating the hash value of the search keyword, Huffman encoding the calculated hash value, and selecting tag data to be collated with the concealed search keyword in the data storage device 4. The data processing apparatus according to claim 3, wherein an index value to be compared with an index value stored in the storage apparatus is generated. A data storage device connected to a data processing device and storing encrypted data transmitted from the data processing device,
From the data processing device, the encrypted data to be stored, the tag data that is collated when searching for the encrypted data, and a random value that is uniquely obtained from the storage keyword specified in the encrypted data to be stored A storage request receiving unit that receives a storage request including a storage index value obtained by entropy encoding, and sets an ID (Identification) of tag data included in the received storage request as a tag ID;
An index information generating unit that generates index information that associates a tag ID set by the storage request receiving unit with a storage index value included in the storage request;
An index storage unit for storing the index information generated by the index information generation unit;
A data storage device, comprising: a data storage unit that stores encrypted data to be stored included in the storage request and tag data included in the storage request in association with each other. The index information generation unit
When existing index information describing the same storage index value as the storage index value included in the storage request is stored in the index storage unit, the existing index information is associated with the same storage search value. 6. The data storage device according to claim 5, wherein the tag ID of the tag data included in the storage request is associated with the storage index value in the existing index information together with the other tag IDs. The data storage device is:
Connected to multiple data processing devices,
The data storage device further includes:
Obtained by entropy encoding a concealed search keyword and a random value uniquely obtained from the concealed search keyword from a data processing device that requests retrieval of encrypted data among the plurality of data processing devices A search request receiver for receiving a search request including a search index value;
A tag ID selection unit that selects one or more tag IDs associated with a storage index value that matches a search index value included in the search request with reference to the index information stored in the index storage unit; ,
Tag data corresponding to the tag ID selected by the tag ID selection unit is extracted from the data storage unit, and each extracted tag data is compared with a concealed search keyword included in the search request, A data extraction unit that identifies tag data generated from a storage keyword that matches a search keyword and extracts encrypted data associated with the identified tag data from the data storage unit; The data storage device according to claim 5 or 6. The index information generation unit
8. The data storage device according to claim 5, wherein index information that associates the tag ID with the storage index value in a table format is generated. The index information generation unit
9. The data storage device according to claim 5, wherein index information that associates the tag ID with the storage index value in a tree format is generated. A data processing method performed by a computer connected to a data storage device that stores a plurality of encrypted data and tag data that is associated with each encrypted data and that is collated when searching for encrypted data There,
A keyword specifying step in which the computer specifies a keyword of storage target data to be stored in the data storage device as a storage keyword;
The computer entropy-encodes a random value uniquely obtained from the storage keyword, and is attached to the tag data when tag data associated with the encrypted data of the storage target data is stored in the data storage device. Generating an index value to be generated; and
A data processing method comprising: a communication step in which the computer transmits a storage request including encrypted data of the storage target data, the tag data, and the index value to the data storage device. . A data storage method performed by a computer connected to a data processing device and storing encrypted data transmitted from the data processing device,
The computer uniquely obtains from the data processing device from the encrypted data to be stored, the tag data that is collated when searching for the encrypted data, and the storage keyword specified in the encrypted data to be stored. A storage request receiving step for receiving a storage request including a storage index value obtained by entropy encoding a random value to be obtained, and setting an ID (Identification) of tag data included in the received storage request as a tag ID; ,
An index information generating step for generating index information in which the computer associates the tag ID set in the storage request receiving step with a storage index value included in the storage request;
An index storing step in which the computer stores the index information generated by the index information generating step;
A data storage method, comprising: a data storage step in which the computer stores the encrypted data to be stored included in the storage request in association with the tag data included in the storage request. To a computer connected to a data storage device that stores a plurality of encrypted data and tag data that is associated with each encrypted data and that is collated when searching for encrypted data,
A keyword designating step of designating as a storage keyword a keyword of data to be stored to be stored in the data storage device;
An index value assigned to the tag data when the tag data associated with the encrypted data of the storage target data is stored in the data storage device by entropy encoding a random value uniquely obtained from the storage keyword An index generation step for generating
A program for executing a communication step of transmitting a storage request including encrypted data of the storage target data, the tag data, and the index value to the data storage device. A computer connected to a data processing device and storing encrypted data transmitted from the data processing device,
From the data processing device, the encrypted data to be stored, the tag data that is collated when searching for the encrypted data, and a random value that is uniquely obtained from the storage keyword specified in the encrypted data to be stored A storage request reception step of receiving a storage request including a storage index value obtained by entropy encoding, and setting an ID (Identification) of tag data included in the received storage request as a tag ID;
An index information generating step for generating index information for associating the tag ID set by the storage request receiving step with the storage index value included in the storage request;
An index storage step for storing the index information generated by the index information generation step;
A program for executing a data storage step of storing encrypted data to be stored included in the storage request and tag data included in the storage request in association with each other.

Images