Paper 2021/230

Subversion-Resilient Public Key Encryption with Practical Watchdogs

Pascal Bemmann, Rongmao Chen, and Tibor Jager


Restoring the security of maliciously implemented cryptosystems has been widely considered challenging due to the fact that the subverted implementation could arbitrarily deviate from the official specification. Achieving security against adversaries that can arbitrarily subvert implementations seems to inherently require trusted component assumptions and/or architectural properties. At ASIACRYPT 2016, Russell et al. proposed an attractive model where a watchdog is used to test and approve individual components of an implementation before or during deployment. Such a detection-based strategy has been useful for designing various cryptographic schemes that are provably resilient to subversion. We consider Russell et al.'s watchdog model from a practical perspective regarding watchdog efficiency. We find that the asymptotic definitional framework, while permitting strong positive theoretical results, does not yet guarantee practical watchdogs, due to the fact that the running time of a watchdog is only bounded by an abstract polynomial. Hence, in the worst case, the running time of the watchdog might exceed the running time of the adversary, which seems impractical for most applications. We adopt Russell et al.'s watchdog model to the concrete security setting and design the first subversion-resilient public-key encryption scheme which allows for extremely efficient watchdogs with only linear running time. At the core of our construction is a new variant of a combiner for key encapsulation mechanisms (KEMs) by Giacon et al. (PKC'18). We combine this construction with a new subversion-resilient randomness generator that also can be checked by an efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes. Our work thus shows how to apply Russell et al.'s watchdog model to design subversion-resilient cryptography with efficient watchdogs. We insist that this work does not intend to show that the watchdog model outperforms other defense approaches, but to demonstrate that practical watchdogs are practically achievable.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2021
Subversion-ResilienceWatchdogRandomness GeneratorPublic Key Encryption.
Contact author(s)
bemmann @ uni-wuppertal de
chromao @ nudt edu cn
tibor jager @ uni-wuppertal de
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Pascal Bemmann and Rongmao Chen and Tibor Jager},
      title = {Subversion-Resilient Public Key Encryption with Practical Watchdogs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/230},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.