Information processing unit, terminal unit, information processing method, key generation method and program

An information processing unit, in a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, where a number assigned to a leaf node located at a left end is defined as lv and a number assigned to a leaf node located at a right end is defined as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v, for natural numbers i and j (i≦j), it is assumed a set (i→j) is notated as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}}, and a set (i←j) is notated as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}}, a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, the information processing unit comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• a directed graph acquisition section to acquire a directed graph generated by replacing at least one of the directed edges constituting a temporary directed graph formed by arranging a plurality of directed edges with a length of ni/k (i=0, 1, . . . , x−1) on the first to fourth horizontal coordinate axes according to a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k for a given integer k, with a shorter directed edge;
• and
• a key generation section to generate a set key for encrypting or decrypting contents or a contents key based on the directed graph acquired by the directed graph acquisition section.

An information processing unit, comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• establish a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, and, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), set a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• set a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left;
• place one temporary coordinate point each on left of a coordinate point located at a left end of the first to fourth horizontal coordinate axes and on right of a coordinate point located at a right end of the second to fourth horizontal coordinate axes, and set a coordinate point located at a right end of the first horizontal coordinate axis as a temporary coordinate point;
• generate temporary directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by:
• setting a given integer k:
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k;
• and
• for each of integer i=0 to x−1, forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k, forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k, excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and excluding directed edges other than the longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes;
• generate a temporary directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the coordinate point located at the right end of the first horizontal coordinate axis to the temporary directed graph related to the set (1→n−1);
• and
• generate a directed graph by replacing the remaining directed edge with a shorter directed edge.

A terminal unit, comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• generate a set key for decrypting contents or a contents key based on a directed graph, wherein the processor is further configured to obtain the directed graph by:
• configuring a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, and, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}} and a set (i←j) as
• {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), setting a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• setting a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left;
• placing one temporary coordinate point each on left of a coordinate point located at a left end of the first to fourth horizontal coordinate axes and on right of a coordinate point located at a right end of the second to fourth horizontal coordinate axes, and setting a coordinate point located at a right end of the first horizontal coordinate axis as a temporary coordinate point;
• generating temporary directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by:
• setting a given integer k;
• calculating a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k;
• and
• for each of integer i=0 to x−1, forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k, forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k, excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and excluding directed edges other than the longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes;
• generating a temporary directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the coordinate point located at the right end of the first horizontal coordinate axis to the temporary directed graph related to the set (1→n−1);
• determining the longest directed path with the maximum number of directed edges constituting the directed path among directed paths formed by the remaining directed edges;
• and
• replacing the directed edge constituting each directed path with a shorter directed edge in such a way that the number of directed edges of each directed path does not exceed the number of directed edges of the longest directed path.

A computer-implemented method, comprising:

• obtaining information associated with a temporary directed graph, the temporary directed graph comprising a plurality of directed edges, the directed edges forming a plurality of directed paths having corresponding path lengths;
• generating, using a processor, a modified temporary directed graph based on at least a portion of the obtained information, the generating comprising:
• identifying a first one of the directed paths, the first directed path being associated with a maximum of the path lengths;
• determining a subset of the directed paths that fail to include a portion of the first directed path;
• obtaining a second directed path from the subset of directed paths, the second directed path being associated with a path length that is a maximum of the path lengths of the subset;
• and
• modifying the temporary directed graph by replacing the at least one of the directed edges with a shorter directed edge, the replacement being based on at least the path lengths of the first and second directed paths;
• establishing a directed graph based on at least a portion of the modified temporary directed graph;
• and
• calculating, using the processor, at least one of a set key for encrypting or decrypting contents or a contents key for a user of a terminal, based on one or more intermediate keys associated with the directed graph.

A computer-implemented method, in a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, where a number assigned to a leaf node located at a left end is defined as lv and a number assigned to a leaf node located at a right end is defined as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v, for natural numbers i and j (i≦j), it is assumed a set (i→j) is notated as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}}, and a set (i←j) is notated as {{j}, {j, j−1}, . . . , {i, j−1, . . . , i+1, i}}, a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, the method comprising:

• obtaining information associated with a temporary directed graph, the temporary directed graph comprising a plurality of directed edges with lengths of ni/k (i=0, 1, . . . , x−1) on the first to fourth horizontal coordinate axes according to a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k for an integer k;
• generating, using a processor, a modified temporary directed graph based on at least a portion of the obtained information, the generating comprising:
• identifying a first one of the directed paths, the first directed path being associated with a maximum of the path lengths;
• determining a subset of the directed paths that fail to include a portion of the first directed path;
• obtaining a second directed path from the subset of directed paths, the second directed path being associated with a path length that is a maximum of the path lengths of the subset;
• and
• modifying the temporary directed graph by replacing the at least one of the directed edges with a shorter directed edge, the replacement being based on at least the path lengths of the first and second directed paths;
• establishing a directed graph based on at least a portion of the modified temporary directed graph;
• and
• calculating, using the processor, a set key for encrypting or decrypting contents or a contents key for a user of a terminal, based on one or more intermediate keys associated with the directed graph.

An information processing unit, comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• obtain information associated with a temporary directed graph, the temporary directed graph comprising a plurality of left-directed and right-directed edges, the directed edges forming a plurality of directed paths having corresponding path lengths;
• generate a modified temporary directed graph, based on at least a portion of the obtained information, wherein the processor is further configured to:
• identify a first one of the directed paths, the first directed path being associated with a maximum of the path lengths;
• determine a subset of the directed paths that fail to include a portion of the first directed path;
• obtain a second directed path from the subset of directed paths, the second directed path being associated with a path length that is a maximum of the path lengths of the subset;
• and
• modify the temporary directed graph by replacing the at least one of the directed edges with a shorter directed edge, the replacement being based on at least the path lengths of the first and second directed paths;
• generate a directed graph based on at least a portion of the modified temporary directed graph;
• and
• calculate at least one of a set key for encrypting or decrypting contents or a contents key, based on intermediate keys associated nodes of the directed graph.

An information processing unit to process a temporary directed graph formed by arranging a plurality of directed edges with a length of ni/k (i=0, 1, . . . , x−1) on first to fourth horizontal coordinate axes according to a natural number x satisfying n(x−1)/k<(rv−lv+1)≦nx/k for a given integer k, in a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, where a number assigned to a leaf node located at a left end is defined as lv and a number assigned to a leaf node located at a right end is defined as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v, for natural numbers i and j (i≦j), it is assumed a set (i→j) is notated as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}}, and a set (i←j) is notated as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}}, a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right is set, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left is set, the information processing unit comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• acquire the temporary directed graph;
• generate a directed graph by leaving a longer directed edge among a plurality of directed edges constituting the temporary directed graph acquired by the temporary directed graph acquisition section;
• determine a maximum number of the successive directed edges among the plurality of directed edges constituting the directed graph;
• reconstruct the directed graph by replacing at least one directed edge constituting the directed graph with a shorter directed edge so as not to exceed the maximum number of the successive directed edges;
• and
• generate a set key for encrypting contents or a contents key based on the directed graph reconstructed by the directed edge replacement section.

An information processing unit comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• configure a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, and, defining a set (i→j) as {{i}, {i, i+1}, . . . , {i, i+1, . . . , j−1, j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), set a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• set a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1←rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left;
• place two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes;
• set a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and place a second temporary coordinate point on right of the first temporary coordinate point;
• generate temporary directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by setting a given integer k;
• calculate an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k, and
• for each of integer i=0 to x−1, form a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k, form a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k, exclude all directed edges having tails or heads at the temporary, coordinate points for each of the first to fourth horizontal coordinate axes, and exclude directed edges other than the longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes;
• generate a temporary directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the temporary directed graph related to the set (1→n−1);
• determine the longest directed path with the maximum number of directed edges constituting the directed path among the directed paths formed by the successive directed edges;
• and
• generate a directed graph by replacing the directed edge constituting each directed path with a shorter directed edge in such a way that the number of directed edges of each directed path does not exceed the number of directed edges of the longest directed path.

A terminal unit comprising:

• a storage device;
• and
• a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to:
• generate a set key for decrypting contents or a contents key based on a directed graph, wherein the directed graph is obtained by:
• configuring a binary tree made up of n-number of leaf nodes to which numbers 1 to n (n is a natural number) are assigned, a root node and a plurality of intermediate nodes different from the root node and the leaf nodes, and, defining a set (i→j) as {{i}, {i, i+1}, . . . {i, i+1, . . . , j−1, j}} and a set (i←j) as {{j}, {j, j−1}, . . . , {j, j−1, . . . , i+1, i}} for natural numbers i and j (i≦j), setting a number assigned to a leaf node located at a left end as lv and a number assigned to a leaf node located at a right end as rv in a plurality of leaf nodes located lower than a certain intermediate node v or a certain root node v;
• setting a first horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (1→n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, a second horizontal coordinate axis correlated with the root node and having coordinate points correlated respectively with subsets included in a set (2←n) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left, for each of the intermediate nodes, a third horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv→rv−1) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from left to right, and a fourth horizontal coordinate axis correlated with a certain intermediate node v and having coordinate points correlated respectively with subsets included in a set (lv+1→rv) and arranged on a horizontal coordinate axis with a degree of inclusion increasing from right to left;
• placing two temporary coordinate points each on right of a coordinate point located at a right end of the third horizontal coordinate axis and on left of a coordinate point located at a left end of the second and fourth horizontal coordinate axes;
• setting a coordinate point located at a right end of the first horizontal coordinate axis as a first temporary coordinate point and placing a second temporary coordinate point on right of the first temporary coordinate point;
• generating temporary directed graphs respectively related to a set (1→n−1), the set (2←n), the set (lv+1←rv) and the set (lv→rv−1) by:
• setting a given integer k;
• calculating an integer x satisfying n(x−1)/k<(rv−lv+1)≦nx/k;
• and
• for each of integer i=0 to x−1, forming a directed path having a tail at a leftmost coordinate point on the first and third horizontal coordinate axes by coupling one or a plurality of rightward directed edges with a length of ni/k, forming a directed path having a tail at a rightmost coordinate point on the second and fourth horizontal coordinate axes by coupling one or a plurality of leftward directed edges with a length of ni/k, excluding all directed edges having tails or heads at the temporary coordinate points for each of the first to fourth horizontal coordinate axes, and excluding directed edges other than the longest directed edge from the directed edges reaching each coordinate point on the first to fourth horizontal coordinate axes;
• generating a temporary directed graph related to the set (1→n) by adding a directed edge with a length of 1 having a head at the first temporary coordinate point on the first horizontal coordinate axis to the temporary directed graph related to the set (1→n−1);
• determining the longest directed path with the maximum number of directed edges constituting the directed path among directed paths formed by the successive directed edges and
• replacing the directed edge constituting each directed path with a shorter directed edge in such a way that the number of directed edges of each directed path does not exceed the number of directed edges of the longest directed path.

A computer-implemented method, comprising:

• obtaining information associated with a directed graph, the temporary directed graph comprising a plurality of left-directed and right-directed edges, the directed edges forming a plurality of directed paths having corresponding path lengths;
• generating, using a processor, a modified temporary directed graph based on at least a portion of the obtained information, the generating comprising:
• identifying a first one of the directed paths, the first directed path being associated with a maximum of the path lengths;
• determining a subset of the directed paths that fail to include a portion of the first directed path;
• obtaining a second directed path from the subset of directed paths, the second directed path being associated with a path length that is a maximum of the path lengths of the subset;
• and
• modifying the directed graph by leaving longer directed edges among the plurality of directed edges constituting the temporary directed graph and replacing at least one of the left-directed edges with a shorter directed edge, the replacement being based on the path lengths of the first and second directed paths;
• establishing a directed graph based on at least a portion of the modified temporary directed;
• and
• calculating at least one of a set key for encrypting or decrypting contents or a contents key, based on one or more intermediate keys associated with the directed graph.