Impossibility of Post-Quantum Shielding Black-Box Constructions of CCA from CPA
Open Access
- 9 April 2024
- journal article
- research article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (1)
Abstract
Proving whether it is possible to build IND-CCA public-key encryption (PKE) from IND-CPA PKE in a black-box manner is a major open problem in theoretical cryptography. In a significant breakthrough, Gertner, Malkin and Myers showed in 2007 that shielding black-box reductions from IND-CCA to IND-CPA do not exist in the standard model. Shielding means that the decryption algorithm of the IND-CCA scheme does not call the encryption algorithm of the underlying IND-CPA scheme. In other words, it implies that every tentative construction of IND-CCA from IND-CPA must have a re-encryption step when decrypting. This result was only proven with respect to classical algorithms. In this work we show that it stands in a post-quantum setting. That is, we prove that there is no post-quantum shielding black-box construction of IND-CCA PKE from IND-CPA PKE. In the type of reductions we consider, i.e. post-quantum ones, the constructions are still classical in the sense that the schemes must be computable on classical computers, but the adversaries and the reduction algorithm can be quantum. This suggests that considering quantum notions, which are stronger than their classical counterparts, and allowing for quantum reductions does not make building IND-CCA public-key encryption easier.Keywords
This publication has 20 references indexed in Scilit:
- Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness2020
- Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World2013
- Notions of Black-Box Reductions, Revisited2013
- Black-Box Separations and Their Adaptability to the Non-uniform ModelLecture Notes in Computer Science, 2013
- Random Oracles in a Quantum World2011
- Towards a Separation of Semantic and CCA Security for Public Key Encryption2007
- Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins?Lecture Notes in Computer Science, 2004
- Notions of Reducibility between Cryptographic Primitives2004
- Secure Integration of Asymmetric and Symmetric Encryption Schemes1999
- Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?1998