Doubly Aggregatable Signatures

Attribute-based anonymous credentials offer users fine-grained access control in a privacy-preserving manner. However, in such schemes obtaining a user's credentials requires knowledge of the issuer's public key, which obviously reveals the issuer's identity that must be hidden from users in certain scenarios. Moreover, verifying a user's credentials also requires the knowledge of issuer's public key, which may infer the user's private information from their choice of issuer. In this article, we introduce the notion of double issuer-hiding attribute-based credentials (<inline-formula><tex-math notation="LaTeX">${\sf DIHAC}$</tex-math><alternatives>mml:math<mml:mi mathvariant="sans-serif">DIHAC</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq1-3314019.gif"/></alternatives></inline-formula>) to tackle these two problems. In our model, a central authority can issue public-key credentials for a group of issuers, and users can obtain attribute-based credentials from one of the issuers without knowing which one it is. Then, a user can prove that their credential was issued by one of the authenticated issuers without revealing which one to a verifier. We provide a generic construction, as well as a concrete instantiation for <inline-formula><tex-math notation="LaTeX">${\sf DIHAC}$</tex-math><alternatives>mml:math<mml:mi mathvariant="sans-serif">DIHAC</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq2-3314019.gif"/></alternatives></inline-formula> based on structure-preserving signatures on equivalence classes (JOC's 19) and a novel primitive which we call <inline-formula><tex-math notation="LaTeX">$tag$</tex-math><alternatives>mml:mathmml:mrowmml:mit</mml:mi>mml:mia</mml:mi>mml:mig</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq3-3314019.gif"/></alternatives></inline-formula>-<inline-formula><tex-math notation="LaTeX">$based$</tex-math><alternatives>mml:mathmml:mrowmml:mib</mml:mi>mml:mia</mml:mi>mml:mis</mml:mi>mml:mie</mml:mi>mml:mid</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq4-3314019.gif"/></alternatives></inline-formula> <inline-formula><tex-math notation="LaTeX">$aggregatable$</tex-math><alternatives>mml:mathmml:mrowmml:mia</mml:mi>mml:mig</mml:mi>mml:mig</mml:mi>mml:mir</mml:mi>mml:mie</mml:mi>mml:mig</mml:mi>mml:mia</mml:mi>mml:mit</mml:mi>mml:mia</mml:mi>mml:mib</mml:mi>mml:mil</mml:mi>mml:mie</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq5-3314019.gif"/></alternatives></inline-formula> <inline-formula><tex-math notation="LaTeX">$mercurial$</tex-math><alternatives>mml:mathmml:mrowmml:mim</mml:mi>mml:mie</mml:mi>mml:mir</mml:mi>mml:mic</mml:mi>mml:miu</mml:mi>mml:mir</mml:mi>mml:mii</mml:mi>mml:mia</mml:mi>mml:mil</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq6-3314019.gif"/></alternatives></inline-formula> <inline-formula><tex-math notation="LaTeX">$signatures$</tex-math><alternatives>mml:mathmml:mrowmml:mis</mml:mi>mml:mii</mml:mi>mml:mig</mml:mi>mml:min</mml:mi>mml:mia</mml:mi>mml:mit</mml:mi>mml:miu</mml:mi>mml:mir</mml:mi>mml:mie</mml:mi>mml:mis</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq7-3314019.gif"/></alternatives></inline-formula>. Our construction is efficient without relying on zero-knowledge proofs. We provide rigorous evaluations on personal laptop and smartphone platforms, respectively, to demonstrate its practicability.