Paper 2018/368

Encryption with Untrusted Keys: Security against Chosen Objects Attack

Shashank Agrawal, Shweta Agrawal, and Manoj Prabhakaran

Abstract

In Public-Key Encryption, traditionally no security is expected if honest parties use keys provided by an adversary. In this work, we re-examine this premise. While using untrusted keys may seem nonsensical at first glance, we argue the use of providing certain security guarantees even in such situations. We propose Chosen Object Attack (COA) security as a broad generalization of various notions of security that have been considered in the literature, including CCA security, key anonymity and robustness, along with concerns arising from untrusted keys. The main premise of this definition is that any of the objects in a cryptographic scheme could be adversarialy generated, and that should not compromise the security of honest parties in a way an idealized scheme would not have. Our contributions are threefold. • Firstly, we develop a comprehensive security definition for PKE in the real/ideal paradigm. Our definition subsumes CCA2 security, Anonymity and Robustness as special cases, and also addresses security concerns in complex application scenarios where the keys may be malicious (without having to explicitly model the underlying attack scenarios). To avoid impossibility results associated with simulation-based security, we use the notion of indistinguishability-preserving security (IND-PRE) from the “Cryptographic Agents” framework (Agrawal et al., EUROCRYPT 2015). Towards this, we extend this framework to accommodate adversarially created objects. Our definition can alternately be interpreted as the union of all possible game-based security definitions. We remark that the agents framework as extended in this work is applicable to primitives other than Public-Key Encryption, and would be of broader significance. • Secondly, and somewhat surprisingly, we show that in the case of PKE, the above comprehensive definition is implied by a simpler definition (which we call COA security) that combines a traditional game-based definition with a set of consistency requirements. The proof of this implication relies on an extensive analysis of all possible executions involving arbitrarily many keys and ciphertexts, generated, transferred between parties and used in an arbitrary and adaptive manner. • Thirdly, we consider constructions. Interestingly, using the above security definition, we show that the Cramer-Shoup cryptosystem (with minor modifications) already meets our definition. Further, we present transformations from any Anonymous CCA2-secure PKE scheme to a COA-secure PKE. Under mild correctness conditions on the Anonymous CCA2-secure PKE scheme, our transformation can be instantiated quite efficiently and is arguably a viable enhancement for PKE schemes used in practice.