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 Graph Search.
Concept
Random oracle
Summary
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).
Official source
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 courses (2)
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
PHYS-758: Advanced Course on Quantum Communication
The aim of this doctoral course by Nicolas Sangouard is to lay the theoretical groundwork that is needed for students to understand how to take advantage of quantum effects for communication technolog
Related lectures (12)
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.
Related publications (36)
On Quantum Secure Compressing Pseudorandom Functions
In this paper we characterize all 2n-bit-to-n-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to n-bit-to-n-bit PRFs and arbitrary number of linear functions. First, we show that all two-round constructions are either classic ...
2023Security in the Presence of Quantum Adversaries
With the looming threat of large-scale quantum computers, a fair portion of recent cryptographic research has focused on examining cryptographic primitives from the perspective of a quantum adversary. Shor's 1994 result revealed that quantum computers can ...
EPFL2023On Succinct Non-interactive Arguments in Relativized Worlds
Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfort ...
SPRINGER INTERNATIONAL PUBLISHING AG2022Related people (9)
Related units (1)
Related concepts (2)
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