Secure search method and secure search device

Patent metadata

Field	Value
Publication number	US-9311494-B2
Application number	US-201114361593-A
Country	US
Kind code	B2
Filing date	Dec 1, 2011
Priority date	Dec 1, 2011
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

Abstract

In search that uses searchable code, the search query and the secure index is collated in round-robins fashion, registering the required secure index and a characteristic quantity of deposited data in a database server to realize the searchable code. The server uses the characteristic quantity to perform clustering on the secure index. For search, collation is first performed only for representative data of a cluster. For a hit, the collation priority is raised for all the data included in the cluster. When there is no hit, the priority is lowered. After calculating the priority, collation is performed sequentially for all the data on the basis of the priority.

First claim

The invention claimed is:

1. A secure search device that receives data from a registered client and receives information for a search from a search client, the secure search device comprising:
a receiver that receives, from the registered client, a set of encrypted data acquired by encrypting the data, a secure index acquired by securing an index extracted from the data and a characteristic quantity for calculating similarity between data pieces;
a similarity calculator that calculates the similarity of two data pieces based upon the characteristic quantity received from the registered client;
a clustering unit that clusters the encrypted data received from the registered client based upon the similarity calculated by the similarity calculator;
a priority calculator that receives a trapdoor acquired by securing a search keyword included in a search query for searching data registered in the secure search device from the search client and calculates the priority of collation of the clustered encrypted data and the trapdoor based upon a result of clustering generated by the clustering unit;
a collator that collates the secure index received from the registered client and the trapdoor; and
a search unit that collates the encrypted data and the trapdoor by the collator based upon the priority calculated by the priority calculator in the order of clusters having higher priority by a predetermined frequency when the trapdoor is received from the search client, and returns the encrypted data that hits the trapdoor to the search client.

2. The secure search device according to claim 1 ,
wherein the clustering unit generates one or more clusters and sets the center of each cluster at random;
the clustering unit instructs the similarity calculator to calculate the similarity of the centers of all data received from the registered client based upon a characteristic quantity included in each data piece and allocates each data piece to the clusters to which the most similar centers belong;
the clustering unit finishes the processing of all the data received from the registered client when allocation to the clusters is unchanged; and
the clustering unit otherwise repeats processing for acquiring the center after the center of each cluster is recalculated using a characteristic quantity of data which belongs to the corresponding cluster.

3. The secure search device according to claim 1 ,
wherein the clustering unit generates as many clusters including only one of data pieces received from the registered client as the number of the data pieces;
the clustering unit instructs the similarity calculator to calculate distance between clusters using a characteristic quantity of data which belongs to each cluster and successively merges two clusters having the shortest distance; and
the clustering unit repeats the merger until all objects are merged into one cluster.

4. The secure search device according to claim 1 ,
wherein the priority calculator selects one of all data pieces which belong to each cluster as representative data for every cluster;
the collator is instructed to collate a secure index of the representative data of each cluster and the trapdoor;
the priority calculator calculates the priority of the cluster to be higher priority as a rate of coincidence with the trapdoor is larger; and
the priority calculator sorts the order of the collation of data included in the cluster to be higher priority.

5. The secure search device according to claim 1 ,
wherein the collator applies exclusive-OR to the secure index and the trapdoor;
the collator extracts a bit string having the same length as a random number sequence generated in generating the secure index from the head of the exclusive-OR and calculates a message digest of the bit string;
the collator judges that the secure index includes a search query corresponding to the trapdoor when the message digest is coincident with a bit string of which the message digest of the exclusive-OR is not calculated; and
the collator judges that the secure index does not include the search query corresponding to the trapdoor when the message digest is not coincident with the bit string.

6. The secure search device according to claim 1 ,
wherein the search client sets a frequency of collation performed by the search unit.

7. The secure search device according to claim 1 ,
wherein the secure search device sets a frequency of collation performed by the search unit.

Assignees

• Fujii Yasuhiro
• Serita Susumu
• Hitachi Ltd

Inventors

• Fujii Yasuhiro
• Serita Susumu

Classifications

• G06F17/30946

  Physics · mapped topic

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• H04L9/3239 Primary

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• G06F17/30979

  Physics · mapped topic

• G06F17/30386

  Physics · mapped topic