Systems and methods are described for utilizing a secure environment on a mobile computing device for applying policy-based decision management in response to access requests from untrusted areas. A policy decision processor (PDP) within the secure environment provides a policy decision in response to an access query. A decision cache within the secure environment can be used to store policy decisions for faster resolution of access requests. Policy enforcement points (PEPs) are placed between external devices that are trying to access the device and the secured environment, where the PEPs are used to enforce the policy-based decision, and can be located either inside or outside the secure environment. Decision certificates can be formulated using validity information and timestamps, and used for validation policy certificates. Memory in non-secure areas can also be marked (colored) for use in performing trusted operations in order to optimize system resource usage.