Is the post-quantum scheme quantum-resistant without regard to QROM

Question

There are many "post-quantum" schemes have been proposed.

The security of most of them is only proven under random oracle model or uses forking lemma.

As described by Boneh et al. (Random Oracles in a Quantum World), post-quantum schemes should further consider the "quantum-accessible" random oracle (QROM).

However, many schemes that do not take QROM into account claim that they are quantum-resistant because their security is based on certain assumptions, such as LWE or SIS.

In addition, these schemes may only be proven under ROM and the security reduction depending on the time of Hash query.

So, are these scheme really quantum-resistant?

I have known that in some situation the ROM secure schemes can apply to QROM secure schemes (Survey on the Security of the Quantum ROM).

Answer 1

I think you are somewhat confused, so I'll try to briefly describe the state-of-the-art to see if it helps.

The general design paradigm of a post-quantum KEM is separated into two steps:

1. Build an IND-CPA secure PKE, generally based solely [1] on the hardness of some computational problem.

2. Apply a general transformation (usually some variant of the Fujisaki-Okamoto transform) to convert the IND-CPA-secure PKE into an IND-CCA secure KEM

The only part where hashing (or any kind of ROM type stuff) strictly needs to enter the picture is in the second step. Is this step done solely in the ROM, or the QROM as well? This is relatively straightforward to check --- many authors rely on A modular analysis of the Fujisaki-Okamoto Transformation, which has a section on transformations in the QROM.

Do the authors use this? You can check their design specifications --- here is the specification for KYBER, a NIST PQC round 3 finalist. Section 4 discusses their security analysis, which includes analysis in the QROM. This is typical of "serious" constructions.

Note that the underlying IND-CPA-secure PKE that KYBER is building on does not mention QROM (or ROM for that matter) analysis, as one only really needs it (and the security modelling of hashing overall) in the transformation from IND-CPA security to IND-CCA security.

Also note that in general the QROM results tend to be weaker than the ROM results - the reductions are generally not tight without making some slightly less standard assumptions. This is of course a much different statement than there being no QROM analysis though.

---

[1] This is not strictly true, often practitioners reach for other primitives (say PRGs / extendible output functions) for efficiency purposes, but these are not strictly required if one is ok with a slightly less efficient construction.