An attribute-based access control policy (e.g., XACML policy) for a set of elements depends on attributes carried by elements in one of several predefined categories. In order to evaluate such policy for a set of elements, the invention provides a method including the steps of (I) selecting a primary category; (II) partitioning the elements in the primary category into equivalence classes with respect to their influence on the policy; and (III) using the equivalence classes to replace at least one policy evaluation by a deduction. The result of the evaluation may be represented as an access matrix in backward-compatible format. The efficiency of the policy evaluation may be further improved by applying partial policy evaluation at intermediate stages, by forming combined equivalence classes containing n-tuples of elements and/or by analyzing the influence of each element by extracting functional expressions of maximal length from the policy.