Patent ID: 8473737

Claim:
An authentication device, comprising: a volatile memory; a non-volatile memory which stores a plurality of electronic certificate files; a list structured entity creation unit which creates, upon start-up, a hierarchical relationship information between the plurality of electronic certificate files that is structured by a bidirectional list having a plurality of nodes linked bidirectionally, each of which stores certificate information for the electronic certificate files and has a backward pointer which specifies the previous node, a forward pointer which specifies the next node, and a parent pointer which specifies the parent node of the node, in the volatile memory, based upon the plurality of electronic certificate files in the non-volatile memory; an authentication processing unit which searches for a desired electronic certificate file from the plurality of electronic certificate files in the non-volatile memory, based upon the hierarchical relationship information between the plurality of electronic certificate files, the hierarchical relationship information being structured by the bidirectional list comprising the parent pointer and being present in the volatile memory, and which performs authentication using the electronic certificate file which has been found by the search, wherein the list structured entity creation unit is implemented by a computer.