Deterring certificate subversion: efficient double-authentication-preventing signatures

DAPS efficiency. We show performance indications for the DAPS obtained by our H2 and ID2 transforms applied to the GQ and MR trapdoor identification schemes. The first two rows show the prior scheme of PS and the scheme of RKS.


This paper presents highly efficient designs of double authentication preventing signatures (DAPS). In a DAPS, signing two messages with the same first part and differing second parts reveals the signing key. In the context of PKIs we suggest that CAs who use DAPS to create certificates have a court-convincing argument to deny big-brother requests to create rogue certificates, thus deterring certificate subversion. We give two general methods for obtaining DAPS. Both start from trapdoor identification schemes. We instantiate our transforms to obtain numerous specific DAPS that, in addition to being efficient, are proven with tight security reductions to standard assumptions. We implement our DAPS schemes to show that they are not only several orders of magnitude more efficient than prior DAPS but competitive with in-use signature schemes that lack the double authentication preventing property.

Keywords: signatures, subversion, mass surveillance, implementation


Mihir Bellare, Bertram Poettering, Douglas Stebila. Deterring certificate subversion: efficient double-authentication-preventing signatures. In Serge Fehr, editor, Proc. 20th International Conference on Practice and Theory of Public-Key Cryptography (PKC) 2017, LNCS, vol. 10175, pp. 121-151. Springer, March 2017.





This research was supported by:
  • Australian Research Council (ARC) Discovery Project grant DP130104304
  • Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
  • NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146
  • NSF grants CNS-1228890 and CNS-1526801
  • a gift from Microsoft corporation
  • ERC Project ERCC (FP7/615074)