Cryptology ePrint Archive: Report 2021/230

Subversion-Resilient Public Key Encryption with Practical Watchdogs

Pascal Bemmann and Rongmao Chen and Tibor Jager

Abstract: 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.

Category / Keywords: public-key cryptography / Subversion-Resilience, Watchdog, Randomness Generator, Public Key Encryption.

Original Publication (with minor differences): IACR-PKC-2021

Date: received 1 Mar 2021

Contact author: bemmann at uni-wuppertal de, chromao@nudt edu cn, tibor jager@uni-wuppertal de

Available format(s): PDF | BibTeX Citation

Version: 20210302:203132 (All versions of this report)

Short URL: ia.cr/2021/230


[ Cryptology ePrint archive ]