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 QROM, while classical security proofs are in the 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 identify game hops which are used to prove such schemes secure in the ROM and state both simple and sufficient conditions to validate that the proof also holds in the QROM. As a more practical contribution, we apply our framework to the encryption scheme LARA (FC 2019) and the encryption scheme on which the key encapsulation mechanism LIMA (ESORICS 2017) is based. This proves that both schemes are post-quantum secure, which had not been shown before.
Patrick Struck is a PhD student of Juliane Krämer in the CDC group led by Prof. Johannes Buchmann. His research focuses on provable security of lattice-based cryptography against quantum adversaries on which he works within Project P1 of CROSSING.