Paper 2016/1016

Deterring Certificate Subversion: Efficient Double-Authentication-Preventing Signatures

Mihir Bellare, Bertram Poettering, and Douglas Stebila


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
signaturessubversionmass surveillanceimplementation
Contact author(s)
stebilad @ mcmaster ca
2016-10-27: received
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Bertram Poettering and Douglas Stebila},
      title = {Deterring Certificate Subversion: Efficient Double-Authentication-Preventing Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1016},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.