Public key authentication is necessary to prevent a valid public key of a user from being compromised by a malicious user. Namely, if it is not provided, an adversary can read all encrypted messages between a sender and a receiver by substituting the public key of the receiver with her public key. In general, a certificate issued from and digitally signed by a publicly trusted certificate authority (CA) guarantees public key authentication under the assumption that all users can get the public key of the CA to verify the validity of certificates,
, the signatures of the CA. The assumption is practical and widely used in the real world. However, if the CA is down by a system faults or destroyed by a terror or a war, the assumption can not be preserved. In this paper, we propose a simple and practical scheme for public key authentication without any trusted third party. The scheme basically uses a message authentication code (MAC) taking a short random value as a key to authenticate the exchanged public keys. Our scheme also can be adopted in the environments such as ad-hoc or ubiquitous in which it is hard to settle a publicly trusted authority.