Public key certificate revocation list generation apparatus, revocation judgement apparatus, and authentication system

A revocation list generation apparatus that generates a revocation list showing a revoked public key certificate, comprising:

• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate;
• a revocation list generation unit operable to generate for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and generate the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system;
• and
• an output unit operable to output the generated revocation list.

A revocation list generation apparatus that generates a revocation list showing a revoked public key certificate, comprising:

• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, none of the public key certificates being revoked, and none of the nodes being revoked;
• a revocation list generation unit operable to judge that none of the nodes is revoked, and generate a node revocation list showing that no revoked public key certificate exists;
• and
• an output unit operable to output the generated revocation list.

A revocation judgement apparatus that judges whether an obtained public key certificate is revoked, with use of a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate, and, on judging that the obtained public key certificate is revoked, prevents use of a public key corresponding to the revoked public key certificate, wherein

• the revocation list generation apparatus (a) has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, (b) generates for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and (c) generates the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system,
• the revocation judgement apparatus, comprising:
• a certificate obtaining unit operable to obtain a public key certificate identified by one of the leaf identifiers;
• a list obtaining unit operable to obtain the revocation list;
• and
• a judgement unit operable to attempt to construct a path from the root to a leaf identified by the leaf identifier, with use of the pieces of revocation information in the obtained revocation list, and when the leaf is included in the constructed path, judge that the obtained public key certificate is revoked, and when the leaf is not included in the path, judge that the obtained public key certificate is valid.

A revocation judgement apparatus that judges whether an obtained public key certificate is revoked, with use of a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate, and, on judging that the obtained public key certificate is revoked, prevents use of a public key corresponding to the revoked public key certificate, wherein

• the revocation list generation apparatus (a) has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, and none of the public key certificates being revoked, none of the nodes having been revoked, (b) judges that all the nodes that compose the tree system are not revoked, (c) generates a revocation list showing that no revoked public key certificates exist, and (d) outputs the generated revocation list,
• the revocation judgement apparatus comprising:
• a certificate obtaining unit operable to obtain a public key certificate identified by one of the leaf identifiers;
• a list obtaining unit operable to obtain the revocation list;
• and
• a judgement unit operable to judge, with use of the obtained revocation list, that the public key certificate is revoked.

A revocation list generation method used in a revocation list generation apparatus that generates a revocation list showing a revoked public key certificate,

• the revocation list generation apparatus including:
• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, and
• the revocation list generation method comprising:
• a revocation list generation step of generating for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and generating the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system;
• and
• an output step of outputting the generated revocation list.

A revocation list generation program used in a revocation list generation apparatus that generates a revocation list showing a revoked public key certificate,

• the revocation list generation apparatus including:
• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, and
• the revocation list generation program comprising:
• a revocation list generation step of generating for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and generating the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system;
• and
• an output step of outputting the generated revocation list.

A computer-readable recording medium having recorded thereon a revocation list generation program used in a revocation list generation apparatus that generates a revocation list showing a revoked public key certificate,

• the revocation list generation apparatus including:
• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, and
• the revocation list generation program comprising:
• a revocation list generation step of generating for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and generating the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system;
• and
• an output step of outputting the generated revocation list.

A revocation judgement method used in a revocation judgement apparatus that judges whether an obtained public key certificate is revoked, with use of a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate, and, on judging that the obtained public key certificate is revoked, prevents use of a public key corresponding to the revoked public key certificate, wherein

• the revocation list generation apparatus (a) has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, (b) generates for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and (c) generates the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system,
• the revocation judgement method comprising:
• a certificate obtaining step of obtaining a public key certificate identified by one of the leaf identifiers;
• a list obtaining step of obtaining the revocation list;
• and
• a judgement step of attempting to construct a path from the root to a leaf identified by the leaf identifier, with use of the pieces of revocation information in the obtained revocation list, and when the leaf is included in the constructed path, judging that the obtained public key certificate is revoked, and when the leaf is not included in the path, judging that the obtained public key certificate is valid.

A revocation judgement program used in a revocation judgement apparatus that judges whether an obtained public key certificate is revoked, with use of a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate, and, on judging that the obtained public key certificate is revoked, prevents use of a public key corresponding to the revoked public key certificate, wherein

• the revocation list generation apparatus (a) has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, (b) generates for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and (c) generates the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree-system,
• the revocation judgement program comprising:
• a certificate obtaining step of obtaining a public key certificate identified by one of the leaf identifiers;
• a list obtaining step of obtaining the revocation list;
• and
• a judgement step of attempting to construct a path from the root to a leaf identified by the leaf identifier, with use of the pieces of revocation information in the obtained revocation list, and when the leaf is included in the constructed path, judging that the obtained public key certificate is revoked, and when the leaf is not included in the path, judging that the obtained public key certificate is valid.

A computer-readable recording medium having stored thereon a revocation judgement program used in a revocation judgement apparatus that judges whether an obtained public key certificate is revoked, with use of a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate, and, on judging that the obtained public key certificate is revoked, prevents use of a public key corresponding to the revoked public key certificate, wherein

• the revocation list generation apparatus (a) has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate, (b) generates for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and (c) generates the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system,
• the revocation judgement program comprising:
• a certificate obtaining step of obtaining a public key certificate identified by one of the leaf identifiers;
• a list obtaining step of obtaining the revocation list;
• and
• a judgement step of attempting to construct a path from the root to a leaf identified by the leaf identifier, with use of the pieces of revocation information in the obtained revocation list, and when the leaf is included in the constructed path, judging that the obtained public key certificate is revoked, and when the leaf is not included in the path, judging that the obtained public key certificate is valid.

A computer readable recording medium having recorded thereon a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate,

• the revocation list generation apparatus comprising:
• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system being in correspondence with a different public key certificate, an identifier of each leaf identifying the corresponding public key certificate, at least one of the public key certificates being revoked, and all nodes on a path being revoked, the path being from a root to the leaf shown by the leaf identifier that identifies the revoked public key certificate;
• and
• a revocation list generation unit operable to generate for each revoked node, excluding the leaves, revocation information showing whether each directly subordinate node of the revoked node is revoked or not, thereby obtaining a plurality of pieces of revocation information, and generate the revocation list by arranging the pieces of revocation information in an order relating to the structure of the tree system,
• wherein the generated revocation list is recorded on the recording medium.

A computer readable recording medium having recorded thereon a revocation list that has been generated by a revocation list generation apparatus and that shows a revoked public key certificate,

• the revocation list generation apparatus including:
• a tree system storage unit that has a plurality of nodes that compose a tree system, each leaf in the tree system corresponding to a different public key certificate, a leaf identifier of each leaf identifying the corresponding public key certificate, none of the public key certificates being revoked, and none of the nodes being revoked;
• and
• a revocation list generation unit operable to judge that none of the nodes is revoked, and generate a node revocation list showing that no revoked public key certificate exists,
• wherein the generated revocation list is recorded on the recording medium.

An authentication system comprising:

• a revocation list generation apparatus operable to generate a revocation list showing a revoked public key certificate, the revocation list generation apparatus comprising:
• a tree system storage unit storing a data tree structure of a plurality of nodes, among which are a root node and a plurality of leaf nodes, arranged in hierarchical levels, the tree structure having a plurality of node paths from the root node to the leaf nodes through the hierarchical levels,
• each leaf node corresponding to a different public key certificate and including identification information that identifies the corresponding public key certificate and including a flag indicating whether or not the leaf node has been revoked,
• each node including a flag indicating whether or not the node has been revoked,
• wherein when a leaf node is revoked, every node along a path from the root node to the revoked leaf node is also revoked;
• a revocation list generation unit operable to generate revocation information for each revoked node, excluding the leaf nodes, indicating whether or not each directly subordinate node of the revoked node is revoked, and to arrange the revocation information of the revoked nodes in an order relating to the hierarchical levels of the tree structure, thereby generating a revocation list;
• and
• an output unit operable to output the generated revocation list;
• and
• a revocation judgement apparatus operable to judge, based on the revocation list, whether an obtained public key certificate is revoked, preventing use of a public key corresponding to a revoked public key certificate, the revocation judgement apparatus comprising:
• a certificate obtaining unit operable to obtain a public key certificate identified by the identification information of one of the leaf nodes;
• a list obtaining unit operable to obtain the revocation list;
• and
• a judgement unit operable to:
• attempt to construct a path from the root node to the leaf node corresponding to the public key certificate obtained by the certificate obtaining unit based on the revocation information in the obtained revocation list;
• judge that the obtained public key certificate is revoked when the leaf node corresponding to the obtained public key certificate is included in the constructed path;
• and
• judge that the obtained public key certificate is not revoked when the leaf node corresponding to the obtained public key certificate is not included in the constructed path.