Paper 2023/1491

Subversion-Resilient Signatures without Random Oracles

Pascal Bemmann, University of Wuppertal
Sebastian Berndt, University of Lübeck
Rongmao Chen, National University of Defense Technology

In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security experiment. This paper addresses this pressing concern by introducing novel constructions of subversion-resilient signatures and hash functions while proving the subversion-resilience of existing cryptographic primitives. Our main contribution is the first construction of subversion-resilient signatures under complete subversion in the offline watchdog model (with trusted amalgamation) without relying on random oracles. We demonstrate that one-way permutations naturally yield subversion-resilient one-way functions, thereby enabling us to establish the subversion-resilience of Lamport signatures, assuming a trusted comparison is available. Additionally, we develop subversion-resilient target-collision-resistant hash functions using a trusted XOR. By leveraging this approach, we expand the arsenal of cryptographic tools that can withstand potential subversion attacks. Our research builds upon previous work in the offline watchdog model with trusted amalgamation (Russell et al. ASIACRYPT'16) and subversion-resilient pseudo-random functions (Bemmann et al. ACNS'23), culminating in the formal proof of subversion-resilience for the classical Naor-Yung signature construction.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACNS 2024
SubversionDigital SignaturesPublic-key cryptography
Contact author(s)
bemmann @ uni-wuppertal de
s berndt @ uni-luebeck de
chromao @ nudt edu cn
2023-10-02: approved
2023-09-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pascal Bemmann and Sebastian Berndt and Rongmao Chen},
      title = {Subversion-Resilient Signatures without Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1491},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.