Patent ID: 7373503

Claim:
An authentication system comprising a revocation list generation apparatus and a revocation judgement apparatus, wherein the revocation list generation apparatus includes: a tree system storage unit having a plurality of nodes that compose a tree system and a plurality of node flags that correspond to the plurality of nodes, the plurality of nodes including a root node and a plurality of leaf nodes, each leaf node in the tree system being in correspondence with a different public key certificate, each leaf node having a leaf identifier for identifying the corresponding public key certificate, at least one of the public key certificates being revoked, all nodes on a path being revoked, the path being from the root node to the leaf node shown by the leaf identifier that identifies the revoked public key certificate, and each one of the node flags showing whether the corresponding node is revoked or not; a revocation list generation unit operable to, for each revoked node excluding the leaf nodes, read node flags corresponding to each directly subordinate node of the revoked node from the tree system storage unit, generate node revocation information from the read node flags, thereby obtaining a plurality of pieces of revocation information equal in number to the revoked nodes excluding the leaf nodes, and generate the revocation list by placing the obtained pieces of node revocation information in an order determined according to placement positions of the revoked nodes in the tree system, the root node being a starting point of the order; and an output unit operable to output the generated node revocation list, and wherein the revocation judgement apparatus includes: 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 node revocation list; a judgement unit operable to judge that the obtained public key certificate is revoked when, in the acquired node revocation list, a piece of node revocation information exists that includes a node flag showing revocation of a node on a path from the root node to the leaf node having the leaf node identifier identifying the obtained public key certificate, and judge that the obtained public key certificate is valid when the piece of node revocation information does not exist; and a prohibition unit operable to, upon a judgment that the obtained public key certificate is revoked, prohibit use of the corresponding public key.