The random oracles in security proofs for cryptographic protocols, and its impact in the novel computing models.

Sep 2024

Silvia Ritsch

Today I want to talk a little bit about random oracles in security proofs for cryptographic protocols, and the impact of novel computing models such as quantum computation on them.

Why security proofs

Cryptography is essential for protecting sensitive information and ensuring secure communication in a world where data breaches and cyber threats are ever-present.
In order to be able to trust in the security of our systems, we often use security proofs, which are essentially mathematical guarantees that a cryptographic scheme can withstand specific types of attacks.
Security proofs also help identify potential vulnerabilities in a scheme. If a proof can’t be constructed, it might indicate a weakness that needs addressing.

Security proofs also allow standards bodies and organizations to certify cryptographic protocols. This facilitates widespread adoption and interoperability across different systems and applications.

Methods for security proofs are constantly evolving along with the protocols they are used for. Today we look into how quantum computation effects provable security.

Why ROM

One of the techniques often used in security proofs is the random oracle model (ROM). Essentially, random oracles are idealised descriptions of the behaviour of hash functions that map arbitrarily long inputs to outputs in a fixed domain, where the outputs are chosen uniformly at random and independent from each other.

Hash functions

We take a quick look about how real hash functions work:

An example of the output of the SHA-1 hash function input-output behavior. Note that the hash sums are always the same size, no matter how short or long the input is and that the hash sums look very different even when there are only slight differences in the input.

On the other hand, we describe a random oracle like this:

While random oracle model proofs are widely used, there is some controversy around them: there is a mismatch between the model and reality. Random oracles are theoretical constructs that provide truly random responses to every unique query. Real-world hash functions are used as approximations, but they cannot achieve the same level of randomness and unpredictability.

On the other hand, proponents of the ROM argue that it provides flexibility in designing cryptographic protocols and can help identify potential weaknesses and to this day, there is no evidence that the need for random oracles in a proof indicates a real-world security weakness. (I personally like to think of ROM proofs as “no-footgun” proofs, that essentially show that the protocol is secure in all other aspects and you’re not metaphorically shooting yourself in the foot.)

Overall, the debate revolves around the balance between theoretical convenience and practical applicability. The controversy around random oracles primarily stems from the fact that they are an idealised concept that doesn’t exist in the real world. Now that we understand why we use random oracles

Why QROM

The transition from the Random Oracle Model (ROM) to the Quantum Random Oracle Model (QROM) is driven by the rise of quantum computing and its potential impact on cryptography. The Quantum Random Oracle Model (QROM) extends the ROM to account for adversaries with quantum capabilities.
In this model, the adversary can query the random oracle with quantum states, which means they can use quantum algorithms to interact with the oracle. This is crucial because there are algorithms for quantum computers that solve certain problems much faster than classical computers, potentially breaking cryptographic schemes that are secure in the classical model.

Need for Post-Quantum Cryptography: As quantum computing advances, there’s a growing need for cryptographic schemes that remain secure even against quantum adversaries. The QROM helps in designing and analyzing such post-quantum cryptographic protocol. Separation Between ROM and QROM: Some cryptographic schemes that are secure in the ROM have been shown to be insecure in the QROM. This highlights the importance of considering quantum capabilities when designing cryptographic systems.

The shift to the QROM represents a significant step in ensuring the long-term security of cryptographic systems.