Paper 2022/1074

On Quantum Ciphertext Indistinguishability, Recoverability, and OAEP

Juliane Krämer, University of Regensburg
Patrick Struck, University of Regensburg

The qINDqCPA security notion for public-key encryption schemes by Gagliardoni et al. (PQCrypto'21) models security against adversaries which are able to obtain ciphertexts in superposition. Defining this security notion requires a special type of quantum operator. Known constructions differ in which keys are necessary to construct this operator, depending on properties of the encryption scheme. We argue—for the typical setting of securing communication between Alice and Bob—that in order to apply the notion, the quantum operator should be realizable for challengers knowing only the public key. This is already known to be the case for a wide range of public-key encryption schemes, in particular, those exhibiting the so-called recoverability property which allows to recover the message from a ciphertext using the randomness instead of the secret key. The open question is whether there are real-world public-key encryption schemes for which the notion is not applicable, considering the aforementioned observation on the keys known by the challenger. We answer this question in the affirmative by showing that applying the qINDqCPA security notion to the OAEP construction requires the challenger to know the secret key. We conclude that the qINDqCPA security notion might need to be refined to eventually yield a universally applicable PKE notion of quantum security with a quantum indistinguishability phase.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. The 13th International Conference on Post-Quantum Cryptography (PQCrypto 2022)
Quantum Ciphertext Indistinguishability qINDqCPA OAEP
Contact author(s)
juliane kraemer @ ur de
patrick struck @ ur de
2022-08-21: approved
2022-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juliane Krämer and Patrick Struck},
      title = {On Quantum Ciphertext Indistinguishability, Recoverability, and OAEP},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1074},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.