Paper 2020/129

Encryption Schemes using Random Oracles: from Classical to Post-Quantum Security

Juliane Krämer and Patrick Struck


The security proofs of post-quantum cryptographic schemes often consider only classical adversaries. Therefore, whether such schemes are really post-quantum secure remains unknown until the proofs take quantum adversaries into account. Switching to a quantum adversary might require to adapt the security notion. In particular, post-quantum security proofs for schemes which use random oracles have to be in the quantum random oracle model (QROM), while classical security proofs are in the random oracle model (ROM). We remedy this state of affairs by introducing a framework to obtain the post-quantum security of public key encryption schemes which use random oracles. We define a class of encryption schemes, called oracle-simple, and identify game hops which are used to prove such schemes secure in the ROM. For these game hops, we state both simple and sufficient conditions to validate that a proof also holds in the QROM. The strength of our framework lies in its simplicity, its generality, and its applicability. We demonstrate this by applying it to the code-based encryption scheme ROLLO (Round 2 NIST candidate) and the lattice-based encryption scheme LARA (FC 2019). This proves that both schemes are post-quantum secure, which had not been shown before.

Note: Removed a flawed proof from the proceedings version of the paper that was pointed out by Antoine Dallon.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.The Eleventh International Conference on Post-Quantum Cryptography (PQCrypto 2020)
QROMgame-based proofscode-based cryptographylattice-based cryptography
Contact author(s)
patrick @ qpc tu-darmstadt de
2021-03-10: last of 2 revisions
2020-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juliane Krämer and Patrick Struck},
      title = {Encryption Schemes using Random Oracles: from Classical to Post-Quantum Security},
      howpublished = {Cryptology ePrint Archive, Paper 2020/129},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.