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

Juliane Krämer; Patrick Struck

Paper 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.

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. The Eleventh International Conference on Post-Quantum Cryptography (PQCrypto 2020)
Keywords: QROM game-based proofs code-based cryptography lattice-based cryptography
Contact author(s): patrick @ qpc tu-darmstadt de
History: 2021-03-10: last of 2 revisions; 2020-02-10: received; See all versions
Short URL: https://ia.cr/2020/129
License: CC BY

BibTeX

@misc{cryptoeprint:2020/129,
      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},
      url = {https://eprint.iacr.org/2020/129}
}