Recently, much research has been actively conducted for a new kind of network environment ubiquitous computing. This paper will define the essential technology called ad hoc network and the smart-Tag technology required by a ubiquitous environment. This paper proposes a PRF and a public key scheme based on a secure hash function. The proposed scheme is a secure authentication protocol for complementing the weak security points of the conventional scheme. In particular, the scheme using the PRF makes it possible to renew MITMA and ID using random numbers while the scheme using the public key can perform a secure authentication scheme using a pair of keys which are shared in the reader in advance.