Secret handshakes with revocation support

Revocation of credentials in Secret Handshakes is a difficult challenge, as it mixes the conflicting requirements of tracing revoked users and of the untraceability and unlinkability of legitimate protocol players. The schemes proposed in the literature are either limited versions of secret handshake supporting revocation, or they support more complete versions of secret handshake with no possibility of introducing revocation. In this paper we present a simple protocol that allows a user to prove to a verifier possession of a credential. Credentials can be revoked simply by publishing a value in a revocation list. This protocol is extremely flexible, as with it, we can achieve revocation for each of the different nuances of Secret Handshakes known in the literature. We prove the security of the new scheme without random oracles.