Random oracle | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted. Stated differently, a random oracle is a mathematical function chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output domain. Random oracles as a mathematical abstraction were first used in rigorous cryptographic proofs in the 1993 publication by Mihir Bellare and Phillip Rogaway (1993). They are typically used when the proof cannot be carried out using weaker assumptions on the cryptographic hash function. A system that is proven secure when every hash function is replaced by a random oracle is described as being secure in the random oracle model, as opposed to secure in the standard model of cryptography. Random oracles are typically used as an idealised replacement for cryptographic hash functions in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof often shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some mathematical problem believed hard in order to break it. However, it only proves such properties in the random oracle model, making sure no major design flaws are present. It is in general not true that such a proof implies the same properties in the standard model. Still, a proof in the random oracle model is considered better than no formal security proof at all. Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the standard model (such as collision resistance, , , etc.) can often be proven secure in the standard model (e.g., the Cramer–Shoup cryptosystem).

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (19)

Related people (5)

Serge Vaudenay, Sylvain Pasini, Fatma Betül Durak, Jean Monnerat, Atefeh Mashatan

Related units (1)

Related concepts (3)

Related courses (1)

Related lectures (12)

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it pr

Cryptographic Security Models

Explores cryptographic security models, decryption vs. key recovery, the ideal cipher, MAC construction, key agreement protocol, public-key cryptosystems, and signature scheme security.

Proving Security: Random Oracle Model

Explores the Random Oracle Model, Hybrid ElGamal, and the Fujisaki Okamoto Transform in proving security.

Symmetric Encryption: Physical Limits

Explores the physical limits and security aspects of symmetric encryption schemes, including energy consumption, key recovery, and distinguisher security.

Cryptography

Cryptography, or cryptology (from κρυπτός "hidden, secret"; and γράφειν graphein, "to write", or -λογία -logia, "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others.

Cryptographic hash function

A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of bits) that has special properties desirable for a cryptographic application: the probability of a particular -bit output result (hash value) for a random input string ("message") is (as for any good hash), so the hash value can be used as a representative of the message; finding an input string that matches a given hash value (a pre-image) is unfeasible, assuming all input str

Random oracle

Symmetric Asynchronous Ratcheted Communication with Associated Data

Serge Vaudenay, Hailun Yan

Following up mass surveillance and privacy issues, modern secure communication protocols now seek strong security, such as forward secrecy and post-compromise security, in the face of state exposures.

Springer, Cham2020

Misuse Attacks on Post-quantum Cryptosystems

Serge Vaudenay, Loïs Evan Huguenin-Dumittan, Fatma Betül Durak, Abdullah Talayhan, Ciprian Baetu

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NISI) standardization process follow the same meta-algorithm, but in different algebras

SPRINGER INTERNATIONAL PUBLISHING AG2019

Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity

Serge Vaudenay, Fatma Betül Durak

Following up mass surveillance and privacy issues, modern secure communication protocols now seek more security such as forward secrecy and post-compromise security. They cannot rely on an assumption

Springer2019