Functional credentials

A functional credential allows a user to anony- mously prove possession of a set of attributes that fulfills a certain policy. The policies are arbitrary polynomially computable predicates that are evaluated over arbitrary attributes. The key feature of this primitive is the dele- gation of verification to third parties, called designated verifiers. The delegation protects the privacy of the pol- icy: A designated verifier can verify that a user satisfies a certain policy without learning anything about the pol- icy itself. We illustrate the usefulness of this property in different applications, including outsourced databases with access control. We present a new framework to construct functional credentials that does not require (non-interactive) zero-knowledge proofs. This is impor- tant in settings where the statements are complex and thus the resulting zero-knowledge proofs are not effi- cient. Our construction is based on any predicate en- cryption scheme and the security relies on standard as- sumptions. A complexity analysis and an experimental evaluation confirm the practicality of our approach.