5
$\begingroup$

I am currently studying the proof of the Dilithium signature in the quantum random oracle model (QROM). I am curious to hear if anyone have any thoughts on the importance of having proofs in the QROM or if proofs in the standard random oracle model should be sufficient?

Have been exploring the topic briefly with some mates and considered it along the lines that the ROM has stood the test-of-times and if this could suggest it is sufficient for post-quantum (PQC) proofs as well.

$\endgroup$
2
  • $\begingroup$ The Quantum-accessible Random Oracle Model is defined by Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner & Mark Zhandry's Random Oracles in a Quantum World, in proceedings of AsiaCrypt 2011, with full version at eprint and arxiv. TLDR: the QROM makes sense when we assume Cryptographically Relevant Quantum Computers. $\endgroup$
    – fgrieu
    Commented Mar 25, 2023 at 20:15
  • $\begingroup$ In the paper that introduces the QROM cited by fgieu above, the authors prove that there are schemes secure in the ROM, but insecure in the QROM. The ROM is an idealization of hash functions and a quantum computer could evaluate a hash function on superpositions, which is why we need the QROM. The fact that the ROM has stood the test of time is irrelevant; RSA also stood the test of time until Shor showed how quantum computers can cheat at that test. $\endgroup$
    – lamontap
    Commented Apr 14, 2023 at 20:31

1 Answer 1

4
$\begingroup$

All models are wrong, but some are useful - George Box

The random oracle model (ROM) has proven the test of time insofar as it has proven an accurate/useful assessment of an adversaries capabilities against cryptographic primitives that we choose to model as "random oracles". Notable failures have occurred e.g. in the cases of MD5 and SHA1 when adversaries have been able to exhibit properties of the functions that give them capabilities that would not exist for a random oracle. For other functions (e.g. SHA256, SHA-3) the inutility of the model has not yet been demonstrated.

Whether the ROM model will continue to be useful for these functions in the future depends on whether the adversary acquires effective analyses of these functions beyond the ROM model. In particular, if an adversary is able to access an instantiation of the function on a (suitably powerful) quantum computer, they may acquire analytics about the function beyond the ROM due to being able to submit superpositions of inputs. It is not clear how much effective use an adversary can make of this additional capability and this is the purpose of the QROM model. Note that the assumption that an adversary can access a quantum implementation of the function can vary from attack scenario to attack scenario (e.g. anyone can access an implementation of unconstrained input to a standardised hash function; CPA and CCA attacks may permit I/O access to an implementation with additional unknown inputs).

The fact that a hitherto useful model has been effective should not automatically provide confidence that it will continue to do so when adversaries' capabilities and understanding change. For example, the security of elliptic curves such as secp256r1 and Curve25519 is assessed according to the generic group model and no significant classical adversarial analysis has yet proven this model ineffective in those cases. However, Shor's algorithm shows that with moderate quantum capability, any group with cyclic structure whose operands can be accessed in superposition does not have a secure discrete logarithm structure.

TL;DR the future usefulness of any model is not automatic in the face of new adversarial capability; further analysis is appropriate whenever an adversary acquires capability not covered by the existing model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.