Practical Signing-Right Revocation


Michael Till Beck (Ludwig-Maximilians-Universit√§t M√ľnchen),¬†Stephan Krenn (AIT Austrian Institute of Technology),¬†Franz-Stefan Preiss (IBM Reserach Zurich),¬†Kai Samelin (IBM Research Zurich and Technische Universit√§t Darmstadt)


One of the key features that must be supported by every modern PKI is an efficient way to determine (at verification) whether the signing key had been revoked. In most solutions, the verifier periodically contacts the certificate authority (CA) to obtain a list of blacklisted, or whitelisted, certificates. In the worst case this has to be done for every signature verification. Besides the computational costs of verification, after revocation all signatures under the revoked key become invalid. In the solution by Boneh et al. at USENIX ’01, the CA holds a share of the private signing key and contributes to the signature generation. After revocation, the CA simply denies its participation in the interactive signing protocol. Thus, the revoked user can no longer generate valid signatures. We extend this solution to also cover privacy, non-trusted setups, and time-stamps. We give a formal definitional framework, and provide elegantly simple, yet provably secure, instantiations from efficient standard building blocks such as digital signatures, commitments, and partially blind signatures. Finally, we propose extensions to our scheme.


9th International Conference of Trust and Trustworthy Computing, TRUST 2016 (

Place and Date

Vienna, Austria, 29-30 August 2016

Publication Reference

Michael Till Beck, Stephan Krenn, Franz-Stefan Preiss, and Kai Samelin. “Practical Signing-Right Revocation“, in: Michael Franz and Panos Papadimitratos (eds.) TRUST 2016, pp. 21-39, LNCS 9824, Vienna/Austria, Springer.



Author     = {Michael Till Beck and Stephan Krenn and Franz-Stefan Preiss and Kai Samelin},
Title     = {{Practical Signing Right Revocation}},
Booktitle  = {TRUST 2016},
Publisher  = {Springer},
editor     = {M. Franz and P. Papadimitratos}, year = {2016}, series = {LNCS}, volume = {9824}, pages = {21--39} }