Anonymous credential systems allow users to obtain a certified credential (a driving license, a student card, etc.) from one organization and then later prove possession of this certified credential to another party, while minimizing the information given to the latter. At CANS 2010, Guajardo, Mennink and Schoenmakers have introduced the concept of anonymous credential schemes with encrypted attributes, where the attributes to be certified are encrypted and unknown to the user and/or issuing organization. Their construction is secure in the random oracle model and based on blind signatures, which, unfortunately, restrict the credentials to be used only once (one-show) to remain unlinkable. In their paper, Guajardo
left as an open problem to construct
credential schemes with encrypted attributes, or to show the impossibility of such a construction. We here provide a positive answer to this problem: our multi-show anonymous credential scheme with encrypted attributes relies on the non-interactive Groth-Sahai proof system and the recent work on commuting signatures from Fuchsbauer (Eurocrypt 2011) and is proven secure in the standard model.