eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2018/368

Encryption with Untrusted Keys: Security against Chosen Objects Attack

Shashank Agrawal, Shweta Agrawal, and Manoj Prabhakaran


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.

Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Contact author(s)
shweta a @ gmail com
2023-02-26: withdrawn
2018-04-24: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.