SHARED INFORMATION DISTRIBUTING DEVICE, HOLDING DEVICE, CERTIFICATE AUTHORITY DEVICE, AND SYSTEM

• US 20100235588A1
• Filed: 01/31/2008
• Published: 09/16/2010
• Est. Priority Date: 02/16/2007
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Yoshida, Masaki, Hasegawa, Shingo, Maeda, Manabu, Futa, Yuichi, Yokota, Kaoru, Shizuya, Hiroki, Matsuzaki, Natsume, Isobe, Shuji, Nonaka, Masao, Koizumi, Eisuke, Sakai, Masao
• Granted Patent: US 8,930,660 B2
• Time in Patent Office: Days
• US Class Current: 711/147
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

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 n^th 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 i^th piece of shared information distributed by the first distribution unit, as well as a pieces of shared information being different from the i^th piece of shared information in ordinal position among n pieces of shared information, “i” being an integer in a range from 1 to n.

Claims

1-32. -32. (canceled)

33. A holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device comprising;

a storage unit;

a first writing unit operable to obtain the i^th piece of shared information having been assigned to the i^th holding device, and write the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th 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 n^th holding devices, and

the i^th 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; and

an 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 i^th 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.

34. The holding device of claim 33, wherein

the read-out (i−

1)^th piece of shared information is obtained by adding up, by a predetermined method, all pieces of partial shared information having been obtained by the shared information segmenting unit.

35. A holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device comprising;

a storage unit;

a first writing unit operable to obtain the i^th piece of shared information having been assigned to the i^th holding device, and write the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th holding device,

a p^th 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 n^th holding devices, and

the i^th 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; and

a 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, wherein

the received pieces of partial shared information have been generated by segmentation of a p^th piece of shared information having been assigned to the withdrawal-target holding device.

36. The holding device of claim 35, wherein

the p^th piece of shared information is obtained by adding up, by a predetermined method, all pieces of partial shared information obtained by the segmentation.

37. A holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device comprising;

a storage unit;

a first writing unit operable to obtain the i^th piece of shared information having been assigned to the i^th holding device, and write the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th holding device,

a node is to be newly added adjacent to the i^th node associated with the i^th holding device in the same closed path, and an additional holding device is to be associated with the newly added node, and

the i^th 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 i^th piece of shared information having been assigned to the i^th 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 i^th 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 i^th piece of shared information to replace the read-out i^th piece of shared information; and

an output unit operable to output the generated additional partial information to the additional holding device.

38. The holding device of claim 37, wherein

the calculating unit obtains the result of the calculation by subtracting the additional partial information from the read-out i^th piece of shared information by a predetermined method.

39. The holding device of claim 37, wherein

in the i^th holding device,

the output unit further outputs the generated additional partial information to one or more other holding devices that hold the i^th piece of shared information having been assigned to the i^th holding device.

40. The holding device of claim 37, wherein

the receiving unit further receives second additional partial information from the (i−

1)^th or the (i+1)^th holding device, the (i−

1)^th and the (i+1)^th holding devices having been respectively associated with the (i−

1)^th and the (i+1)^th nodes that are adjacent to the newly added node, and

the calculating unit further generates additional shared information to be assigned to the additional holding device by performing a calculation onto the additional partial information generated by the generating unit and the second additional partial information received by the receiving unit, and writes the generated additional shared information into the storage unit as shared information assigned to the additional holding device to replace the (i−

1)^th or the (i+1)^th piece of shared information, the (i−

1)^th and the (i+1)^th pieces of shared information having been respectively assigned to the (i−

1)^th and the (i+1)^th holding devices which have been associated with the (i−

1)^th and the (i+1)^th nodes that are adjacent to the i^th node associated with the i^th holding device before the addition of the additional holding device.

41. The holding device of claim 40, wherein

the calculating unit obtains the additional shared information by adding the additional partial information and the second partial information by a predetermined method.

42. The holding device of claim 37, wherein

the reading unit further reads out a new i^th piece of shared information having been newly assigned to the i^th holding device from the storage unit;

the calculating unit further segments the read-out new i^th piece of shared information into (n+1) pieces of partial shared information,

the output unit further outputs, in accordance with a predetermined assignment rule, the (n+1) pieces of partial shared information to other holding devices being holding devices that remain after excluding the i^th holding device from (n+1) holding devices that include the additional holding device, and

the predetermined assignment rule is that a plurality of pieces of partial shared information should be assigned on a one-to-one basis to a plurality of pieces of shared information held by the other holding devices except for the i^th piece of shared information, and all of the plurality of pieces of partial shared information should be assigned to the i^th piece of shared information.

43. A holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device comprising;

a storage unit;

a first writing unit operable to obtain the i^th piece of shared information having been assigned to the i^th holding device, and write the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th 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 i^th node associated with the i^th holding device, and an additional holding device is to be associated with the newly added node, and

the i^th 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; and

a 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.

44. The holding device of claim 43, wherein

the receiving unit further receives, from an adjacent holding device that is a holding device associated with a node adjacent to the newly added node, one or more pieces of partial shared information that are to be assigned to the (i−

1)^th through the (i+1)^th pieces of shared information stored in the storage unit, and

the calculating unit further performs a calculation onto the (i−

1)^th through the (i+1)^th pieces of shared information stored in the storage unit by using the received one or more pieces of partial shared information, and writes a result of the calculation into the storage unit as new (i−

1)^th through (i+1)^th pieces of shared information, wherein

the received one or more pieces of partial shared information have been generated by segmentation of a piece of shared information having been assigned to the adjacent holding device.

45. A holding device to be newly added to a group composed of a first through an n^th holding devices which respectively hold a first through an n^th 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.

46. The holding device of claim 45, wherein

the generating unit generates the piece of shared information by adding up the all pieces of additional partial information received by the receiving unit, by a predetermined method.

47. The holding device of claim 46, wherein

the receiving unit further receives additional partial information from at least one of the two existing holding devices from which pieces of additional partial information have been received, and

the generating unit further performs a calculation onto the shared information stored in the storage unit by using the received additional partial information, and writes a result of the calculation into the storage unit as new shared information assigned to the holding device itself, wherein

the received additional partial information has been generated from the shared information assigned to the existing holding device.

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 n^th 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.

49. The certificate authority device of claim 48, wherein

the first through the n^th holding devices have respectively been associated with n nodes that are arranged to form one or more closed paths,

an i^th holding device holds an i^th piece of shared information having been assigned to the i^th holding device and 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 i^th node associated with the i^th holding device, “

i”

being an integer in a range from 1 to n,

the receiving unit receives the n pieces of shared information having no redundancy by receiving a first through an n^th pieces of shared information respectively assigned to the first through the n^th holding devices, and

the identifying unit includes;

a first classifying unit operable to obtain remaining pieces of shared information held by each holding device, and classify all of the pieces of shared information received from each holding device into a first through an n^th groups such that the i^th piece of shared information having been assigned to the i^th holding device and the i^th piece of shared information assigned to the i^th holding device and held by the (i−

1)^th and the (i+1)^th holding devices belong to an i^th group as a same piece of information;

a second classifying unit operable to classify, for each of the first through the n^th groups, a plurality of pieces of shared information included in each group into sub-groups so that each sub-group includes a same piece of shared information;

a combination generating unit operable to select one sub-group from each of the first through the n^th groups, select one piece of shared information from each of selected n sub-groups, and generate combinations of n pieces of shared information;

a verifying unit operable to verify whether or not shared information is authentic by generating private information by using all pieces of shared information included in the generated combinations;

an excluding unit operable to, when the verifying unit verifies that shared information included in the sub-group is authentic, recognizes a holding device that holds shared information included in the sub-groups, as authentic, and excludes the authentic holding device, wherein

the identifying unit identifies a holding device that holds shared information having been tampered with, from among remaining holding devices.

50. The certificate authority device of claim 49, wherein

the restoring unit further restores the private information by using the n pieces of shared information having no redundancy among a plurality of pieces of shared information received from holding devices excluding the holding device identified by the identifying unit as holding shared information having been tampered with.

51. A holding method for use in a holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device including a storage unit,

the holding method comprising the steps of;

obtaining the i^th piece of shared information having been assigned to the i^th holding device, and writing the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th 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 n^th 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; and

outputting the (n−

1) pieces of partial shared information to (n−

2) holding devices, which are remaining holding devices after the i^th 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.

52. A computer-readable recording medium storing a computer program for holding for use in a holding device being an i^th holding device among n holding devices to which n pieces of shared information, a first through an n^th pieces of shared information, have been assigned on a one-to-one basis, an i^th piece of shared information having been assigned to the i^th 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 i^th holding device including a storage unit,

the computer program causing a computer to execute the steps of;

obtaining the i^th piece of shared information having been assigned to the i^th holding device, and writing the i^th 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 i^th holding device, the one or more pieces of shared information being different from the i^th 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 n^th 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 i^th node associated with the i^th 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 n^th 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; and

outputting the (n−

1) pieces of partial shared information to (n−

2) holding devices, which are remaining holding devices after the i^th 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.

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 n^th 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 n^th 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.