Computing today is moving away from the desktop and becoming diffused into our surroundings and on palmtops. Moreover, ad-hoc networks such as bluetooth provide for spontaneous connectivity between computationally enabled devices in a vicinity. In such pervasive computing environments, users expect to access resources and services at any time from anywhere. This results in serious security issues, since devices are constantly interacting with others outside of their ``home'' environments. We describe the security challenges in pervasive computing, and point out why traditional security mechanisms fail to meet the demands of these environments. We use an agent-oriented paradigm to model the interactions between computationally enabled entities in such dynamic environments, and present an infrastructure that combines existing authentication features like Simple Public Key Infrastructure (SPKI) with notions of policy driven interaction and distributed trust, in order to provide a highly flexible approach for enforcing security policies in pervasive computing environments. We present an implementation of the system on a variety of handheld/laptop devices and Bluetooth/802.11, and includes an ontology to describe principals, credentials and policies.