International Association
for Cryptologic Research

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 a very useful model where a watchdog is used to test and approve individual components of implementation before or during deployment. Such a detection-based strategy has been shown very useful for designing a broad class of cryptographic schemes that are provable resilient to subversion. We consider Russell et al.'s watchdog model from a practical perspective. We find that the asymptotic definitional framework, while permitting strong positive theoretical results, does not yet provide practical solutions, 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 not very practical. We adopt Russell et al.'s watchdog model to the concrete security setting. We design the first subversion-resilient public-key encryption scheme, which additionally 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 a very efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes with practical watchdogs. Our work thus shows how to apply Russell et al.'s watchdog model to design subversion-resilient cryptography with efficient and very practical watchdogs.