Pervasive computing environments offer a multitude of information services that provide potentially complex types of information. Therefore, when running access control for sensitive information, these environments need to take relationships between information into account. Other approaches to relationship-aware access control (e.g., based on Semantic Web rule engines) are often expensive and based on a centralized design. In this paper, we identify three types of information relationships (bundling-based, combination-based, and granularity-based) that are common and important in pervasive computing, and we integrate support for them in a distributed, certificate-based access control architecture. In our approach, access control is fully distributed while sophisticated rule engines can still be used to deal with more complex access control cases. To demonstrate the feasibility of our design, we give a complexity analysis of the architecture and a performance analysis of a prototype implementation.