Privacy has been a central concern of ubiquitous (pervasive) computing. Although the boundary between privacy and publicity dynamically moves depending on the context in which the issue is considered, access control, which is one of the most fundamental functionality constituting ubiquitous computing, is required to support perfect privacy, that is, anonymity and unlinkability. This paper presents a concrete protocol for anonymous access control that supports compliance to the distributed trust management model introduced by Blaze et al., efficiency for continual verification and provable security. In addition, the protocol is based on a practical trust model that models the heterogeneous structure of trust in the real world. The model defines a service provider, a service appliance, users and a device that users carry or wear as independent players, and further assumes that trust between them is independently established only based on their arbitrary mutual agreements.