System for generating index resistant against divulging of information, index generation device, and method therefor

Patent metadata

Field	Value
Publication number	US-9690845-B2
Application number	US-201214233662-A
Country	US
Kind code	B2
Filing date	Jul 27, 2012
Priority date	Jul 29, 2011
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

In the present invention, scope search can be effectively performed in a database having encrypted registration information. A plurality of values, first identification information to identify the plurality of values, and a key are accepted as input. A value group is generated from the plurality of values. The value group is treated as a word group, and a secure index is generated from the word group, the first identification information, and the key. On the basis of a value to be retrieved and a key, trapdoor information for the value to be retrieved is generated. With respect to the generated secure index, a secure index assessment process is performed using the trapdoor information. When the value to be retrieved is assessed to be contained in the secure index as a result of the assessment process, second identification information to identify the secure index is output.

First claim

The invention claimed is:

1. A secure index generation device that receives a plurality of values, first identification information for identifying each of the plurality of values, and a key as inputs and generates a secure index based on the inputs, comprising:
a value set generation unit configured to generate a value set based on the plurality of values, the value set being determined so as to correspond to a condition for a scope search; and
a secure index generation unit configured to treat the value set as a word set and generate a secure index based on the word set, the first identification information, and the key,
wherein:
the secure index generation device treats a set of more than one value from the minimum value to the value as a word set and generates a secure index based on the word set, the first identification information, and the key, in a case where a minimum amount that can be taken by the value is defined as a minimum value, or
the secure index generation device treats a set of more than one value from the maximum value to the value as a word set and generates a secure index based on the word set, the first identification information, and the key, in a case where a maximum amount that can be taken by the value is defined as a maximum value.

2. The secure index generation device of claim 1 , wherein
in the case where the minimum amount that can be taken by the value is defined as the minimum value, the secure index generation device treats a set of more than one value from the minimum value to the value as a word set and generates a first secure index based on the word set, the first identification information, and the key, and
in the case where the maximum amount that can be taken by the value is defined as the maximum value, the secure index generation device treats the set of more than one value from the maximum value to the value as the word set, generates a second secure index based on the word set, the first identification information, and the key, and pairs the first secure index with the second secure index.

3. The secure index generation device of claim 1 , wherein the secure index generation device treats, as a word set, a set of all intervals that contain the value within a range of values the value can take and generates the secure index based on the word set, the first identification information, and the key.

4. The secure index generation device of claim 1 , wherein the scope search is performed on a database in which registered information is encrypted.

5. The secure index generation device of claim 1 , wherein an index for executing the scope search is generated for a range of values equal to or greater than a first predetermined value and equal to or less than a second predetermined value.

6. A search system that generates a secure index and performs assessment processing on the generated secure index, the system comprising:
a secure index generation device configured to generate the secure index;
a trapdoor generation unit configured to, based on the key and a value to be searched, generate trapdoor information of the value to be searched; and
a secure index search unit configured to, by use of the trapdoor information, perform secure index assessment processing to the generated secure index and, in a case where it is assessed through the assessment processing that the value to be searched is contained in the secure index, output second identification information for identifying the secure index,
the secure index generation device receiving a plurality of values, first identification information for identifying each of the plurality of values, and a key as inputs and generates a secure index based on the inputs,
the secure index generation device comprising:
a value set generation unit configured to generate a value set based on the plurality of values, the value set being determined so as to correspond to a condition for a scope search; and
a secure index generation unit configured to treat the value set as a word set and generate a secure index based on the word set, the first identification information, and the key,
wherein:
the secure index generation device treats a set of more than one value from the minimum value to the value as a word set and generates a secure index based on the word set, the first identification information, and the key, in a case where a minimum amount that can be taken by the value is defined as a minimum value, or
the secure index generation device treats a set of more than one value from the maximum value to the value as a word set and generates a secure index based on the word set, the first identification information, and the key, in a case where a maximum amount that can be taken by the value is defined as a maximum value.

7. The search system of claim 6 , wherein
a value is assigned to any interval,
a set of intervals to which the value is assigned is treated as a word set in place of the value set and a secure index is generated based on the word set, the first identification information, and the key,
based on an interval assigned to a value to be searched and a key, trapdoor information of the value to be searched is generated, and
by use of the trapdoor information, secure index assessment processing is performed to the generated secure index and, in a case where it is assessed through the assessment processing that the interval that is assigned to the value to be searched is contained in the secure index, second identification information for identifying the secure index is output.

8. A search system that generates a secure index and performs assessment processing on the generated secure index, the system comprising:
a secure index generation device configured to generate the first secure index and the second secure index, and
the system further comprising:
a trapdoor generation unit configured to generate trapdoors t_a and t_b for each of input values a and b which meet the inequality a<b; and
a secure index search unit configured to perform secure index assessment processing using the trapdoor t_a as a trapdoor used in search processing with the first secure index and the trapdoor t_b as a trapdoor used in search processing with the second secure index and outputs a product set of results from each performance of assessment processing,
the secure index generation device receiving a plurality of values, first identification information for identifying each of the plurality of values, and a key as inputs and generates a secure index based on the inputs,
the secure index generation device comprising:
a value set generation unit configured to generate a value set based on the plurality of values, the value set being determined so as to correspond to a condition for a scope search; and
a secure index generation unit configured to treat the value set as a word set and generate a secure index based on the word set, the first identification information, and the key, wherein
in a case where a minimum amount that can be taken by the value is defined as a minimum value, the secure index generation device treats a set of more than one value from the minimum value to the value as a word set and generates a first secure index based on the word set, the first identification information, and the key, and
in a case where a maximum amount that can be taken by the value is defined as a maximum value, the secure index generation device treats a set of more than one value from the maximum value to the value as a word set, generates a second secure index based on the word set, the first identification information, and the key, and pairs the first secure index with the second secure index.

9. A search system that generates a secure index and performs

Assignees

• Araki Toshinori
• Teranishi Isamu
• Nec Corp

Inventors

• Araki Toshinori
• Teranishi Isamu

Classifications

• G06F17/30946

  Physics · mapped topic

• G06F17/30622 Primary

  Physics · mapped topic

• H04L9/30 Primary

  Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy · CPC title

• G06F21/6218

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• G06F16/901

  Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) · CPC title