Privacy Preserving Credential Verification
Chaya Ganesh


Anonymous credential systems which allow a user to prove that her credentials contain a set of attributes, and that the attributes in her credential satisfy some policy, are generally built around sigma-protocol ZK proofs. This require that the signatures used for credentials are restricted to specially formed ones. We ask what if we instead use a standard (say, RSA, or (EC)DSA) signature that includes formatting and hashing messages, as a credential, and still ask for anonymity. On the one hand, ZK proofs based on garbled circuits (Jawurek et al. 2013) are good at checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discrete-log, which can be done efficiently with sigma protocols. We design new constructions for obtaining the best of both worlds: efficiency of the garbled circuit approach for non-algebraic statements and that of sigma protocols for algebraic ones. We then show how to use these as building-blocks to construct privacy-preserving credential systems based on standard RSA and (EC)DSA signatures.

Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments (and signatures) in different groups, and secure two-party computation on committed/signed inputs.

Joint work (in submission) with Melissa Chase and Payman Mohassel