Apparatuses and methods for certificate generation, certificate revocation and certificate verification are provided. The certificate generation and revocation apparatus includes: a key set computation unit receiving a secret value and a hash function set and generating a key set of an entity; a hash function unit generating the hash function set; a certificate generation unit generating certificates corresponding to the public/private key pairs and the key set; a certificate revocation unit acquiring derived secret key corresponding to a revoked certificate set and updating a certificate revocation list; and a certificate revocation list broadcast unit broadcasting the certificate revocation list; wherein the secret value corresponds to a root of a key tree, wherein the key set is generated by leaves of the key tree, wherein each node of the key tree is generated by a randomly selected hash function.