Access control based on anonymous credentials allows users to prove to a service provider in a privacy-friendly manner that they possess the credentials required to access a resource. To achieve optimal privacy, the information that service providers can learn from the access control protocol should in principle be just a single event, namely that a user is granted access. However, existing anonymous credential schemes reveal additional information to the service provider such as the identity of the credential issuer, the credential type, and constraints on the attributes of the credential that reveal more than the access decision itself. In addition, the efficiency of selective attribute disclosure is not optimal. Our contribution is both cryptographic and conceptual. First, we extend existing vector commitment schemes with efficient zero-knowledge protocols to prove correct generation of a new commitment, to prove that a secret value is committed at a secret position, and to prove that a secret position was updated to a new secret value. Second, we employ these protocols along with structure preserving signatures and conceptual techniques from logic-based access control to design a private access control protocol with efficient selective attribute disclosure that achieves our optimality criteria. © 2013 ACM.