Patent ID: 7792867

Claim:
An information processing method for generating keys of respective nodes from a parent node on the basis of a hierarchical relationship expressed by a directed graph having no cycles, comprising: a directed graph input step of inputting data of the directed graph; a directed graph division processing step of dividing the input data of the directed graph into subgraphs; a subgraph node key generation step of generating node keys for respective subgraphs divided in the directed graph division processing step; and performing the above steps using at least one processor, wherein the directed graph division processing step is performed so as to satisfy the following three conditions: 1) each subgraph has one root node, 2) when the root node of a given subgraph is not the root of the directed graph, the root node of the given subgraph is a node of another subgraph, and 3) the number of nodes to be shared by another subgraph is one except for a root node, and wherein, in order to generate node keys K 2 _ 1 -K 2 _n for a given subgraph G 2 from a node key K_ 1 of a root node of the subgraph G 2 , the subgraph node key generation step is performed according to any one of following three methods: A) a method of obtaining the K 2 _ 1 -K 2 _n as n random numbers by providing the K_ 1 as a seed to a pseudo random number generator PRNG ( ), wherein the pseudo random number generator PRNG ( ) generates the n random numbers from the seed K_ 1 , B) a method of obtaining the K 2 _ 1 -K 2 _n by calculating K 2 _i =F_i(K_ 1 ) (for 1 ≦i≦n), wherein the F_i( ) are n one-way functions, and C) a method of obtaining the K 2 _ 1 -K 2 _n by calculating K 2 _i =F_i(P_i; K_ 1 ) (for 1 ≦i≦n), wherein P_ 1 -P_n are different public keys and F_ 1 ( ) - F_n( ) are different encryption functions, wherein F_i (P_i; K_ 1 ) encrypts the K_ 1 using P_i to output the K 2 _i as an encryption result.