SHARED INFORMATION DISTRIBUTING DEVICE, HOLDING DEVICE, CERTIFICATE AUTHORITY DEVICE, AND SYSTEM
1 Assignment
0 Petitions
Accused Products
Abstract
A distributing device for generating private information correctly even if shared information is destroyed or tampered with. A shared information distributing device for use in a system for managing private information by a secret sharing method, including: segmenting unit that segments private information into a first through an nth pieces of shared information; first distribution unit that distributes the n pieces of shared information to n holding devices on a one-to-one basis; and second distribution unit that distributes the n pieces of shared information to the n holding devices so that each holding device holds an ith piece of shared information distributed by the first distribution unit, as well as a pieces of shared information being different from the ith piece of shared information in ordinal position among n pieces of shared information, “i” being an integer in a range from 1 to n.
-
Citations
54 Claims
-
1-32. -32. (canceled)
-
33. A holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device comprising; a storage unit; a first writing unit operable to obtain the ith piece of shared information having been assigned to the ith holding device, and write the ith piece of shared information into the storage unit; an obtaining unit operable to obtain one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and a second writing unit operable to write the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, the obtaining unit obtains an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device,either the (i−
1)th or the (i+1)th holding device is a withdrawal-target holding device that is to withdraw from a group composed of the first through the nth holding devices, andthe ith holding device further comprises; a receiving unit operable to receive a segmentation instruction; a reading unit operable to, after the receiving unit receives the segmentation instruction, read out either the (i−
1)th or the (i+1)th piece of shared information assigned to the withdrawal-target holding device from the storage unit;a shared information segmenting unit operable to segment the read-out (i−
1)th or (i+1)th piece of shared information into (n−
1) pieces of partial shared information; andan output unit operable to output the (n−
1) pieces of partial shared information to (n−
2) holding devices, which are remaining holding devices after the ith holding device and the withdrawal target holding device are excluded, such that a plurality of pieces of partial shared information are assigned to a plurality of pieces of shared information held by the (n−
2) holding devices that are arranged at same ordinal positions as the plurality of pieces of partial shared information. - View Dependent Claims (34)
- i”
-
35. A holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device comprising; a storage unit; a first writing unit operable to obtain the ith piece of shared information having been assigned to the ith holding device, and write the ith piece of shared information into the storage unit; an obtaining unit operable to obtain one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and a second writing unit operable to write the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, the obtaining unit obtains an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device,a pth holding device, which is other than the (i−
1)th through the (i+1)th holding devices, is a withdrawal-target holding device that is to withdraw from a group composed of the first through the nth holding devices, andthe ith holding device further comprises; a receiving unit operable to receive a plurality of pieces of partial shared information that are respectively to be assigned to the (i−
1)th through the (i+1)th pieces of shared information, from holding devices associated with nodes that are adjacent to a node associated with the withdrawal-target holding device; anda calculating unit operable to add the received pieces of partial shared information and a plurality of pieces of shared information corresponding to the received pieces of partial shared information among the (i−
1)th through the (i+1)th pieces of shared information stored in the storage unit, whereinthe received pieces of partial shared information have been generated by segmentation of a pth piece of shared information having been assigned to the withdrawal-target holding device. - View Dependent Claims (36)
- i”
-
37. A holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device comprising; a storage unit; a first writing unit operable to obtain the ith piece of shared information having been assigned to the ith holding device, and write the ith piece of shared information into the storage unit; an obtaining unit operable to obtain one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and a second writing unit operable to write the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, the obtaining unit obtains an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device,a node is to be newly added adjacent to the ith node associated with the ith holding device in the same closed path, and an additional holding device is to be associated with the newly added node, and the ith holding device further comprises; a receiving unit operable to receive a notification that the additional holding device is to be added; a reading unit operable to, after the receiving unit receives the notification, read out an ith piece of shared information having been assigned to the ith holding device from the storage unit; a generating unit operable to generate additional partial information; a calculating unit operable to perform a calculation onto the read-out ith piece of shared information by using the generated additional partial information, and write a result of the calculation into the storage unit as a new ith piece of shared information to replace the read-out ith piece of shared information; and an output unit operable to output the generated additional partial information to the additional holding device. - View Dependent Claims (38, 39, 40, 41, 42)
- i”
-
43. A holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device comprising; a storage unit; a first writing unit operable to obtain the ith piece of shared information having been assigned to the ith holding device, and write the ith piece of shared information into the storage unit; an obtaining unit operable to obtain one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and a second writing unit operable to write the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, the obtaining unit obtains an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device,a node is to be newly added adjacent to the (i−
1)th or the (i+1)th node in the same closed path, the (i−
1)th and the (i+1)th nodes being adjacent to the ith node associated with the ith holding device, and an additional holding device is to be associated with the newly added node, andthe ith holding device further comprises; a receiving unit operable to receive additional partial information from the (i−
1)th or the (i+1)th holding device that is associated with the (i−
1)th or the (i+1)th that is adjacent to the newly added node;a reading unit operable to read out, from the storage unit, the (i−
1)th or the (i+1)th piece of shared information assigned to the (i−
1)th or the (i+1)th holding device from which the additional partial information was received; anda calculating unit operable to perform a calculation onto the read-out (i−
1)th or (i+1)th piece of shared information by using the received additional partial information, and write a result of the calculation into the storage unit as a new (i−
1)th or (i+1)th piece of shared information assigned to the (i−
1)th or the (i+1)th holding device, to replace the read-out (i−
1)th or (i+1)th piece of shared information. - View Dependent Claims (44)
- i”
-
45. A holding device to be newly added to a group composed of a first through an nth holding devices which respectively hold a first through an nth pieces of shared information, the holding device comprising:
-
a receiving unit operable to receive a piece of additional partial information from each of at least two existing holding devices; a generating unit operable to generate a piece of shared information to be assigned to the holding device itself, by using all pieces of additional partial information received by the receiving unit; and a storage unit operable to store the generated piece of shared information. - View Dependent Claims (46, 47)
-
-
48. A certificate authority device comprising:
-
a receiving unit operable to receive n pieces of shared information having no redundancy from stored shared information which has been assigned redundantly to a first through an nth holding devices; a restoring unit operable to restore private information temporarily by using the received n pieces of shared information; a verifying unit operable to verify whether or not restored private information is authentic; and an identifying unit operable to, when the verifying unit judges that the restored private information is not authentic, identify a holding device holding shared information that has been tampered with in an unauthentic manner, by using remaining pieces of shared information held by each holding device and the n pieces of shared information used in the restoration. - View Dependent Claims (49, 50)
-
-
51. A holding method for use in a holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device including a storage unit, the holding method comprising the steps of; obtaining the ith piece of shared information having been assigned to the ith holding device, and writing the ith piece of shared information into the storage unit; obtaining one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and writing the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, and the holding method further comprises the steps of; obtaining an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device;receiving a segmentation instruction when either the (i−
1)th or the (i+1)th holding device is a withdrawal-target holding device that is to withdraw from a group composed of the first through the nth holding devices;reading out, after the segmentation instruction is received, either the (i−
1)th or the (i+1)th piece of shared information assigned to the withdrawal-target holding device from the storage unit;segmenting the read-out (i−
1)th or (i+1)th piece of shared information into (n−
1) pieces of partial shared information; andoutputting the (n−
1) pieces of partial shared information to (n−
2) holding devices, which are remaining holding devices after the ith holding device and the withdrawal target holding device are excluded, such that a plurality of pieces of partial shared information are assigned to a plurality of pieces of shared information held by the (n−
2) holding devices that are arranged at same ordinal positions as the plurality of pieces of partial shared information.
- i”
-
52. A computer-readable recording medium storing a computer program for holding for use in a holding device being an ith holding device among n holding devices to which n pieces of shared information, a first through an nth pieces of shared information, have been assigned on a one-to-one basis, an ith piece of shared information having been assigned to the ith holding device, the n pieces of shared information having been generated by segmentation of one piece of private information, “
- i”
being an integer in a range from 1 to n,the ith holding device including a storage unit, the computer program causing a computer to execute the steps of; obtaining the ith piece of shared information having been assigned to the ith holding device, and writing the ith piece of shared information into the storage unit; obtaining one or more pieces of shared information having been assigned to one or more holding devices that are different from the ith holding device, the one or more pieces of shared information being different from the ith piece of shared information in ordinal position among the n pieces of shared information; and writing the obtained one or more pieces of shared information into the storage unit, wherein a first through an nth holding devices have been associated with n nodes that have been virtually arranged to form one or more closed paths, and the computer program further causes the computer to execute the steps of; obtaining an (i−
1)th and an (i+1)th pieces of shared information having been assigned to an (i−
1)th and an (i+1)th holding devices which have respectively been associated with an (i−
1)th and an (i+1)th nodes that are adjacent, in a same closed path, to an ith node associated with the ith holding device;receiving a segmentation instruction when either the (i−
1)th or the (i+1)th holding device is a withdrawal-target holding device that is to withdraw from a group composed of the first through the nth holding devices;reading out, after the segmentation instruction is received, either the (i−
1)th or the (i+1)th piece of shared information assigned to the withdrawal-target holding device from the storage unit;segmenting the read-out (i−
1)th or (i+1)th piece of shared information into (n−
1) pieces of partial shared information; andoutputting the (n−
1) pieces of partial shared information to (n−
2) holding devices, which are remaining holding devices after the ith holding device and the withdrawal target holding device are excluded, such that a plurality of pieces of partial shared information are assigned to a plurality of pieces of shared information held by the (n−
2) holding devices that are arranged at same ordinal positions as the plurality of pieces of partial shared information.
- i”
-
53. A method for use in a certificate authority device, the method comprising the steps of:
-
receiving n pieces of shared information having no redundancy from stored shared information which has been assigned redundantly to a first through an nth holding devices; restoring private information temporarily by using the received n pieces of shared information; verifying whether or not restored private information is authentic; and identifying, when the verifying step judges that the restored private information is not authentic, a holding device holding shared information that has been tampered with in an unauthentic manner, by using remaining pieces of shared information held by each holding device and the n pieces of shared information used in the restoration.
-
-
54. A computer-readable recording medium storing a computer program for holding for use in a certificate authority device, the computer program causing a computer to execute the steps of:
-
receiving n pieces of shared information having no redundancy from stored shared information which has been assigned redundantly to a first through an nth holding devices; restoring private information temporarily by using the received n pieces of shared information; verifying whether or not restored private information is authentic; and identifying, when the verifying step judges that the restored private information is not authentic, a holding device holding shared information that has been tampered with in an unauthentic manner, by using remaining pieces of shared information held by each holding device and the n pieces of shared information used in the restoration.
-
Specification