Kerberos-type authentication protocols have more to offer when they are founded upon public key cryptosystems. In the current paper we argue and illustrate this point by way of presenting a protocol that implements Kerberos using a recent and promising public key cryptosystem, which is secure against the adaptatively chosen ciphertext attacks. The flexibility of the solution is highlighted by extending the protocol to allow the use of one ticket for multiple services. The issue of hierarchical inter-realm authentication is also considered by way of two protocols based on the notion of localized and globalized keys respectively. These protocols represents a step towards a family of solutions based on the combination of the advantages of private key and public key cryptography.