International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-interactive Keyed-Verification Anonymous Credentials

Geoffroy Couteau
Michael Reichle
DOI: 10.1007/978-3-030-17253-4_3
Search ePrint
Search Google
Conference: PKC 2019
Abstract: Anonymous credential ($$\mathsf {AC}$$) schemes are protocols which allow for authentication of authorized users without compromising their privacy. Of particular interest are non-interactive anonymous credential ($$\mathsf {NIAC}$$) schemes, where the authentication process only requires the user to send a single message that still conceals its identity. Unfortunately, all known $$\mathsf {NIAC}$$ schemes in the standard model require pairing based cryptography, which limits them to a restricted set of specific assumptions and requires expensive pairing computations. The notion of keyed-verification anonymous credential ($$\mathsf {KVAC}$$) was introduced in (Chase et al., CCS’14) as an alternative to standard anonymous credential schemes allowing for more efficient instantiations; yet, making existing $$\mathsf {KVAC}$$ non-interactive either requires pairing-based cryptography, or the Fiat-Shamir heuristic.In this work, we construct the first non-interactive keyed-verification anonymous credential ($$\mathsf {NIKVAC}$$) system in the standard model, without pairings. Our scheme is efficient, attribute-based, supports multi-show unlinkability, and anonymity revocation. We achieve this by building upon a combination of algebraic $$\mathsf {MAC}$$ with the recent designated-verifier non-interactive zero-knowledge ($$\mathsf {DVNIZK}$$) proof of knowledge of (Couteau and Chaidos, Eurocrypt’18). Toward our goal of building $$\mathsf {NIKVAC}$$, we revisit the security analysis of a $$\mathsf {MAC}$$ scheme introduced in (Chase et al., CCS’14), strengthening its guarantees, and we introduce the notion of oblivious non-interactive zero-knowledge proof system, where the prover can generate non-interactive proofs for statements that he cannot check by himself, having only a part of the corresponding witness, and where the proof can be checked efficiently given the missing part of the witness. We provide an efficient construction of an oblivious $$\mathsf {DVNIZK}$$, building upon the specific properties of the $$\mathsf {DVNIZK}$$ proof system of (Couteau and Chaidos, Eurocrypt’18).
  title={Non-interactive Keyed-Verification Anonymous Credentials},
  booktitle={Public-Key Cryptography – PKC 2019},
  series={Lecture Notes in Computer Science},
  author={Geoffroy Couteau and Michael Reichle},