JP3871996B2 - Data division management method and program - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a technique for dividing and storing data.
[0002]
[Prior art]
When important confidential data (hereinafter referred to as original data) is stored, there is a threat of loss, destruction, theft and privacy infringement. These problems cannot be solved by simply encrypting data that should be kept secret. Also, making multiple copies in preparation for loss or destruction increases the risk of theft.
[0003]
As a means for solving such a problem, there is a secret sharing method (see Non-Patent Document 1). In the threshold secret sharing method (see Non-Patent Document 2), which is one of secret sharing methods, the original data S can be obtained by encoding the original data S into n pieces of divided data and collecting any k pieces of divided data. Can be restored, but S cannot be restored with any k−1 pieces of divided data.
[0004]
Accordingly, even if up to k-1 pieces of divided data are stolen, the original data does not leak, and even if up to nk pieces of divided data are lost or destroyed, the original data S can be restored.
[0005]
In the prior art, management information used for restoring the divided data is managed in one place. When dividing the data, the divided data is read based on the management information and the original data is reconstructed. (See Patent Document 1).
[0006]
[Patent Document 1]
JP 2000-172548 A [Non-Patent Document 1]
Shamir, A "How to Share a Secret" Comm. Assoc. Comput. Mach., Vol.22, no.11, pp.612-613 (Nov.1979)
[Non-Patent Document 2]
Hiroshi Yamamoto: “(k, L, n) threshold secret sharing system” IEICE Transactions, vol.J68-A, no.9, pp.945-952 (Sep.1985)
[0007]
[Problems to be solved by the invention]
However, even if the original data is divided and stored, if the management information on the divided data is collectively managed as described above, the storage location of all the divided data is clear when the information on the storage location is stolen among the management information The confidentiality is weakened. In addition, even if the divided data itself is safe, there is a problem that the original data cannot be recovered when the management information necessary for restoring the original data is destroyed or lost.
[0008]
The present invention has been made in view of the above points, and an object of the present invention is to provide a data management technique that improves confidentiality and restoration by dividing and storing management information.
[0009]
[Means for Solving the Problems]
In order to achieve the above object, the present invention can be configured as follows.
[0010]
The present invention relates to a method in which a data division management device divides original data and stores it in a plurality of storage devices, the step of generating divided data, and a predetermined number of pieces of divided data among the generated divided data Generating first management information in which divided data and a storage device for storing the divided data are associated with each other for each divided data, and storing the first management information in a storage unit of the data division management device; Secondly, for the divided data other than the predetermined number of pieces of divided data among the generated divided data, second data including storage location information in which the divided data is associated with a storage device that stores the divided data for each divided data. Generating the management information, dividing the second management information into a plurality of fragments, and storing the divided data specified by the first management information and the second management information One of the pieces of the second management information is stored in the storage unit of the data division management device, and the other piece of the second management information is specified by the first management information. Storing in a storage device.
[0011]
According to the present invention, the divided data is divided and managed, and the management information is also divided and managed, so that the confidentiality of data storage is improved. In addition, since one piece of divided management information is divided into a plurality of pieces and each piece is stored in a plurality of places, the confidentiality is further improved.
[0012]
In the above method, the divided data is data generated by a secret sharing method. In the secret sharing method, the number of divisions is n (n is a natural number), the number required for restoration is k (k is a natural number), and k <n <2k−1, and the predetermined number is n−k + 1.
[0013]
Further, when restoring the original data from the divided data, the fragment of the second management information stored together with the divided data in the first management information, and the second data stored in the data division management device. The second management information is restored from the pieces of the management information, and k pieces of divided data of the divided data in the first management information and the divided data in the second management information are obtained to obtain the original data To restore.
[0014]
In the above method, the plurality of pieces of the second management information may be two pieces, and the second management information may not be estimated from one of the two pieces.
[0015]
Further, the plurality of pieces of the second management information are pieces divided by a secret sharing method, and in addition to storing the first management information in the data division management device, the other pieces of information are also sent to other devices. And storing one of the plurality of pieces of the second management information in the other device. Thereby, the recoverability with respect to destruction of an apparatus can be improved.
[0016]
Further, according to the present invention, a program suitable for causing a computer to execute the above method is provided.
[0017]
DETAILED DESCRIPTION OF THE INVENTION
(First embodiment)
FIG. 1 is a diagram showing an example of the configuration of the data storage system according to the first embodiment of the present invention.
[0018]
As shown in the figure, the data storage system according to the first embodiment includes a divided management device 1 that divides and stores data and management information, and a storage center 2 (A˜) that stores pieces of divided data and management information. G), and a terminal 3 that requests storage of the original data. The division management device 1 and the storage center 2 are connected by a network 4, and the terminal 3 and the division management device 1 are connected to a network 5.
[0019]
The division management device 1 restores the original data using the authentication unit 11 for authenticating the terminal 3 and the storage center 2, the division unit 12 for dividing the original data and the management information, and the divided data and the management information. And a storage unit 14 for storing management information and fragments of management information.
[0020]
In the first embodiment, a method of dividing and storing divided data management information is divided into two and stored in different locations. In addition, the two can be restored, but the division is performed so that the original contents cannot be understood from one.
[0021]
Hereinafter, a process until the division management apparatus 1 divides data and stores it in the storage center 2 will be described with reference to the flowchart of FIG. In the embodiment of the present invention, divided data is generated using the threshold secret sharing method, where n is the number of divisions of the original data, and the minimum number of data required to restore the original data (hereinafter, The required number) is expressed as k. (N and k are positive integers.)
First, the division management device 1 authenticates the user by the authentication unit 11 when a request for division / storage of the original data is received from the user terminal 3 (step 1). Only a correctly registered user can request to divide and store the original data from the terminal 3, and can restore the original data from the stored divided data and the management information of the divided data. If it is not authenticated that the user is correctly registered, the process is terminated. Although user authentication is not essential, it is desirable to perform authentication.
[0022]
When authenticated, the division unit 12 of the division management apparatus determines the number of divisions and the necessary number necessary for division using the threshold secret sharing method (step 2). In the embodiment of the present invention, the division number n and the necessary number k are determined in a relationship of k <n <2k-1. Either n or k may be determined first. The portion of k <n is a necessary condition for the purpose of restoring the original data even if a certain number of the divided number is lost. The meaning of the portion of n <2k−1 will be described later. .
[0023]
Next, the dividing unit 12 generates n pieces of divided data using the threshold secret sharing method (step 3). It is possible to improve confidentiality by encrypting the generated divided data before storing, but it is not essential. The encryption has the same effect even if it is performed on the original data before dividing the original data.
[0024]
Subsequently, the dividing unit 12 determines each storage location for each piece of divided data (step 4). The determination of the storage location is to specify a storage center and a data storage location in the storage center in order to specify a storage location as data on the computer network.
[0025]
Next, the dividing unit 12 selects n−k + 1 from the n pieces of divided data, creates storage location information regarding the correspondence between the divided data and the storage location, and sets this as management information A. This management information A is stored in the storage unit 14 of the division management device 1 (step 5). The n−k + 1 divided data may be arbitrarily selected.
[0026]
The number of n−k + 1 is n− (k−1), and when this number of divided data is lost due to a disaster or the like, the remaining is k−1, so that the original data can no longer be restored. Here, as will be described later, the fragment of the management information B necessary for restoring the original data is also stored in the storage center that stores n−k + 1 pieces of divided data. Therefore, if the number of pieces of divided data managed by the management information A is less than n−k + 1, when all pieces of divided data managed by the management information A are lost, the remainder becomes k or more, and the number of pieces of divided data is Although all of the fragments of the management information B are lost, the original data cannot be restored even though the number can be restored. On the other hand, if there are n−k + 1, there is a possibility that the original data can be restored even if n−k pieces of divided data are lost. Further, since the relationship of n−k + 1 <k is established because the relationship of n <2k−1 is established, the original data cannot be restored from only n−k + 1, and the divided data managed by the management information A is temporarily Even if everything is stolen, the original data cannot be restored.
[0027]
That is, n−k + 1 is a number for increasing the security against theft of the divided data by reducing the number of divisions to be managed while maintaining the possibility of restoring the original data against the loss of the divided data.
[0028]
Next, for the remaining k−1 pieces of divided data excluding the n pieces of divided data selected in step 5, the dividing unit 12 creates storage location information for the correspondence between the divided data and the storage location. (Step 6). However, this is not stored in the division management device 1.
[0029]
Then, as shown in FIG. 3, the “storage location information” created in step 6, the “required number” defined in step 2, and the “division algorithm type” used in step 3 are defined as management information B. The dividing unit 12 regards this whole as one data and divides it into two to generate “fragment 1 of management information B” and “fragment 2 of management information B” (step 7).
[0030]
Any method of division may be used for this “two division”, but the original management information B is restored from the two divided data, and the original management information B cannot be estimated from one of the divided data. The method. For example, the management information B is regarded as a series of bit strings, and only the odd-numbered bits from the head are extracted to create “fragment 1 of management information B”, and only the even-numbered bits are extracted to “fragment 2 of management information B”. May be created. Furthermore, if each is encrypted or encrypted before being “divided into two”, confidentiality is enhanced.
[0031]
Next, “fragment 1 of management information B” is stored in the storage unit 14 of the division management apparatus together with the management information A created and stored in steps 4 and 5. Further, n−k + 1 pieces of divided data specified by the management information A are transmitted to the storage center determined in step 4 together with “fragment 2 of the management information B” and stored in each storage center. For the other divided data, only the divided data is stored in the storage location determined in step 4 (step 8).
[0032]
In order to allow each user to store and restore a plurality of different original data using the division management device 1, for each original data, the identification name of the original data, the corresponding “management information A”, “ Management is performed for each user using a table or the like that associates information specifying “fragment 1 of management information B”. An example of this table is shown in FIG.
[0033]
Next, a processing procedure when the division management apparatus 1 acquires data stored in the storage center 2 based on a request from the terminal 3 by the user will be described with reference to a flowchart of FIG. The following processing is performed by the restoration unit 13 in the division management device 1.
[0034]
First, in response to a data acquisition request from a user, the authentication unit 11 performs user authentication (step 11). Although user authentication is not essential, it is desirable that only the owner of the original data is access-controlled so that the original data can be restored from the stored divided data and the management information of the divided data. If the original data owner is not authenticated, the process is terminated. If authenticated, the following processing is performed.
[0035]
Next, the restoration unit 13 tries to obtain n−k + 1 pieces of divided data described in the management information A (step 12). If the storage center is destroyed due to a disaster or the like and only one of n−k + 1 is acquired, if k−1 pieces of divided data managed by the management information B can be acquired, k pieces of divided data are obtained. The original data can be restored. Accordingly, even if there is divided data that cannot be acquired in step 12, if one piece of divided data can be acquired, the following processing is performed.
[0036]
Subsequently, in order to acquire k-1 pieces of divided data managed by the management information B, the management information B is restored (step 13). Management information B is derived from “fragment 1 of management information B” stored together with management information A and “fragment 2 of management information B” stored together with n−k + 1 pieces of divided data obtained based on management information A. Can be restored. As shown in FIG. 3, since the management information B includes “necessary number” and “type of division algorithm”, the “necessary number” and “type of division algorithm” can be acquired together with the storage location information.
[0037]
Then, based on the storage location information of the management information B, k−1 pieces of divided data managed by the management information B are acquired (step 14). If all n−k + 1 pieces of divided data can be acquired in step 12, it is sufficient that 2k−n−1 pieces of divided data among the pieces of divided data described in the management information B can be obtained. There is no need to get. In general, if p pieces of data can be acquired in step 12, it is only necessary to obtain kp pieces of k-1 pieces of divided data managed by the management information B.
[0038]
Subsequently, the original data is restored by the threshold secret sharing method based on at least k pieces of divided data acquired in step 12 and step 14 and the “type of division algorithm” acquired in step 13, and returned to the terminal 3 (Step 15).
[0039]
In the first embodiment described above, the user accesses the partition management device 1 from the terminal 3 via the network 5. However, the function of the partition management device 1 is taken into the terminal 3, and the user manages the partition management device 1. It is good also as a form using directly.
[0040]
(Second Embodiment)
Next, a second embodiment of the present invention will be described.
[0041]
In the second embodiment of the present invention, the storage location of the management information A and the method of dividing and storing the management information B are different from the first embodiment.
[0042]
FIG. 6 shows a configuration diagram of a data storage system according to the second embodiment. As shown in the figure, in the second embodiment, the management information A is stored not only in the division management apparatus 1 but also in the storage unit 31 of the terminal 3 in step 5 of the processing flow shown in FIG. The storage unit 31 is preferably access-controlled so that only the owner of the original data can use it.
[0043]
Further, a method of dividing the management information B is as shown in FIG. That is, in step 7 of the processing flow shown in FIG. 2, the management information B is divided by the threshold secret sharing method in which the number of divisions is 3 and the required number is 2, so that “fragment 1 of management information B”, “management information B” B fragment 2 ”and“ management information B fragment 3 ”are generated. Further, as shown in FIG. 6, the storage locations of “Management Information B Fragment 1” and “Management Information B Fragment 2” are the same as those in the first embodiment, and “Management Information B Fragment 3” The information is stored together with the management information A in the storage unit 31 of the terminal 3.
[0044]
By storing the management information A and the management information B as in the second embodiment, any one of the terminal 3, the divided management device 1, and the storage center 2 that stores “the fragment 2 of the management information B” is stored. Management information A and management information B all disappear or cannot be restored even if one (up to nk for the storage center that stores “fragment 2 of management information B”) is destroyed due to a disaster, etc. Therefore, it is possible to restore the original data. For example, in the first embodiment, when the division management device 1 is destroyed, it is impossible to restore the original data, but in the second embodiment, the division management device 1 is destroyed. However, the original data can be restored by using the information stored in the terminal 3.
[0045]
According to each of the above embodiments, even if only the management information A of the divided data is stolen, the total number of divided data is unknown, and the number of divided data necessary for restoring the original data is unknown. Further, only the storage location for the number of pieces of divided data necessary for restoring the original data is known. Furthermore, even if only the divided data managed by the management information A is stolen, the management information of the other divided data is unknown, so the original data cannot be restored.
[0046]
The terminal 3, the division management device 1, and the storage center 2 in the present embodiment can be realized by using a computer that includes a CPU, a memory, a hard disk, a communication device, and the like. In particular, the division management device 1 can be realized using a computer in which a program for executing the above processing procedure is installed. Further, the program can be stored and distributed in a recording medium such as a CD-ROM, or can be distributed via a network.
[0047]
The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.
[0048]
【The invention's effect】
As described above, according to the present invention, it is possible to improve the confidentiality of data by dividing and storing the management information of the divided data.
[Brief description of the drawings]
FIG. 1 is a diagram showing an example of the configuration of a data storage system according to a first embodiment of the present invention.
FIG. 2 is a flowchart showing processing until a division management apparatus divides data and stores it in a storage center.
FIG. 3 is a diagram for describing generation and division of management information B in the first embodiment.
FIG. 4 is a diagram showing an example of a table associating original data, corresponding management information A, and fragment 1 of management information B;
FIG. 5 is a flowchart showing a processing procedure for obtaining stored data.
FIG. 6 is a diagram illustrating an example of a configuration of a data storage system according to a second embodiment of the present invention.
FIG. 7 is a diagram for explaining generation and division of management information B in the second embodiment.
[Explanation of symbols]
1 division management device 2 storage center 3 terminal 4, 5 network 11 authentication unit 12 division unit 13 restoration unit 14, 31 storage unit

Claims (10)

A data division management device divides original data by a secret sharing method and stores it in a plurality of storage devices,
Generating split data; and
Of the generated divided data, for a predetermined number of pieces of divided data smaller than the number of divided data necessary for restoring the original data , the divided data and the storage device for storing the divided data are associated with each divided data. Generating the first management information and storing the first management information in the storage unit of the data division management device;
For the divided data other than the predetermined number of divided data among the generated divided data, the second data includes storage location information that associates the divided data with a storage device that stores the divided data for each divided data. Generating management information and dividing the second management information into a plurality of fragments;
The division data is stored in the storage device specified by the first management information and the second management information, and one of the pieces of the second management information is stored in the storage unit of the data division management device. Storing the other piece of the second management information in a storage device specified by the first management information. In the secret sharing method, the number of divisions of the original data is n (n is a natural number), the number required for restoration is k (k is a natural number), and k <n <2k−1.
The method according to claim 1, wherein the predetermined number is n−k + 1. When restoring original data from the divided data, the second management information fragment stored together with the divided data in the first management information, and the second management information stored in the data division management device The second management information from the fragments of
The method according to claim 2, wherein k pieces of divided data of the divided data in the first management information and the divided data in the second management information are acquired to restore the original data.   The method according to claim 1, wherein the plurality of pieces of the second management information are two pieces, and the second management information cannot be estimated from one of the two pieces. The plurality of pieces of the second management information are pieces divided by a secret sharing method, and in addition to storing the first management information in the data division management device, the pieces of information are also stored in other devices. ,
The method according to claim 1, wherein one of the plurality of pieces of the second management information is stored in the other device. A program that causes a computer to execute a process of dividing original data by a secret sharing method and storing it in a plurality of storage devices,
A procedure for generating split data;
Of the generated divided data, for a predetermined number of pieces of divided data smaller than the number of divided data necessary for restoring the original data , the divided data and the storage device for storing the divided data are associated with each divided data. Generating the first management information and storing the first management information in the storage unit of the computer;
For the divided data other than the predetermined number of divided data among the generated divided data, the second data includes storage location information that associates the divided data with a storage device that stores the divided data for each divided data. A procedure of generating management information and dividing the second management information into a plurality of fragments;
The divided data is stored in the storage device specified by the first management information and the second management information, and one of the pieces of the second management information is stored in a storage unit of the computer, A program for causing a computer to execute a procedure for storing another piece of the management information of 2 in the storage device specified by the first management information. In the secret sharing method, the number of divisions of the original data is n (n is a natural number), the number required for restoration is k (k is a natural number), and k <n <2k−1.
The program according to claim 6, wherein the predetermined number is n−k + 1.   A fragment of the second management information stored together with the divided data in the first management information, and a fragment of the second management information stored in the computer when restoring the original data from the divided data; A procedure for restoring the original management data by restoring the second management information from the computer and obtaining k pieces of divided data of the divided data in the first management information and the divided data in the second management information. The program according to claim 7, wherein the program is executed.   The program according to claim 6, wherein the plurality of pieces of the second management information are two pieces, and the second management information cannot be estimated from one of the two pieces.   The plurality of pieces of the second management information are pieces divided by a secret sharing method. In addition to storing the first management information in the computer, the pieces of the second management information are also stored in another device, and 7. The program according to claim 6, which causes a computer to execute a procedure for storing one of a plurality of pieces of management information of the second management information in the other device.

Images