Cryptology ePrint Archive: Report 2020/129

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

Juliane Krämer and Patrick Struck

Abstract: 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.

Category / Keywords: public-key cryptography / QROM, game-based proofs, code-based cryptography, lattice-based cryptography

Original Publication (with minor differences): The Eleventh International Conference on Post-Quantum Cryptography (PQCrypto 2020)

Date: received 6 Feb 2020, last revised 3 Mar 2020

Contact author: pstruck at cdc tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20200303:090122 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]