For random replies to random questions, see Internet Oracle.
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 first appeared in the context of complexity theory, in which they were used to argue that complexity class separations may face relativization barriers, with the most prominent case being the P vs NP problem, two classes shown in 1981 to be distinct relative to a random oracle almost surely.[1] They made their way into cryptography by the publication of Mihir Bellare and Phillip Rogaway in 1993, which introduced them as a formal cryptographic model to be used in reduction proofs.[2]
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.
Applications
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.[3]
In 1989, Russell Impagliazzo and Steven Rudich[6] showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange.
In 1993, Mihir Bellare and Phillip Rogaway[2] were the first to advocate their use in cryptographic constructions. In their definition, the random oracle produces a bit-string of infinite length which can be truncated to the length desired.
When a random oracle is used within a security proof, it is made available to all players, including the adversary or adversaries.
Domain separation
A single oracle may be treated as multiple oracles by pre-pending a fixed bit-string to the beginning of each query (e.g., queries formatted as "1|x" or "0|x" can be considered as calls to two separate random oracles, similarly "00|x", "01|x", "10|x" and "11|x" can be used to represent calls to four separate random oracles). This practice is usually called domain separation. Oracle cloning is the re-use of the once-constructed random oracle within the same proof (this in practice corresponds to the multiple uses of the same cryptographic hash within one algorithm for different purposes).[7] Oracle cloning with improper domain separation breaks security proofs and can lead to successful attacks.[8]
Limitations
According to the Church–Turing thesis, no function computable by a finite algorithm can implement a true random oracle (which by definition requires an infinite description because it has infinitely many possible inputs, and its outputs are all independent from each other and need to be individually specified by any description).
In fact, certain contrived signature and encryption schemes are known which are proven secure in the random oracle model, but which are trivially insecure when any real function is substituted for the random oracle.[9][10] Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the practical security of the protocol.[11]
In general, if a protocol is proven secure, attacks to that protocol must either be outside what was proven, or break one of the assumptions in the proof; for instance if the proof relies on the hardness of integer factorization, to break this assumption one must discover a fast integer factorization algorithm. Instead, to break the random oracle assumption, one must discover some unknown and undesirable property of the actual hash function; for good hash functions where such properties are believed unlikely, the considered protocol can be considered secure.
Although the Baker–Gill–Solovay theorem[12] showed that there exists an oracle A such that PA = NPA, subsequent work by Bennett and Gill,[13] showed that for a random oracle B (a function from {0,1}n to {0,1} such that each input element maps to each of 0 or 1 with probability 1/2, independently of the mapping of all other inputs), PB ⊊ NPB with probability 1. Similar separations, as well as the fact that random oracles separate classes with probability 0 or 1 (as a consequence of the Kolmogorov's zero–one law), led to the creation of the Random Oracle Hypothesis, that two "acceptable" complexity classes C1 and C2 are equal if and only if they are equal (with probability 1) under a random oracle (the acceptability of a complexity class is defined in BG81[13]). This hypothesis was later shown to be false, as the two acceptable complexity classes IP and PSPACE were shown to be equal[14] despite IPA ⊊ PSPACEA for a random oracle A with probability 1.[15]
Ideal cipher
An ideal cipher is a random permutation oracle that is used to model an idealized block cipher. A random permutation decrypts each ciphertext block into one and only one plaintext block and vice versa, so there is a one-to-one correspondence. Some cryptographic proofs make not only the "forward" permutation available to all players, but also the "reverse" permutation.
Recent works showed that an ideal cipher can be constructed from a random oracle using 10-round[16] or even 8-round[17]Feistel networks.
Ideal permutation
An ideal permutation is an idealized object sometimes used in cryptography to model the behaviour of a permutation whose outputs are indistinguishable from those of a random permutation. In the ideal permutation model, an additional oracle access is given to the ideal permutation and its inverse. The ideal permutation model can be seen as a special case of the ideal cipher model where access is given to only a single permutation, instead of a family of permutations as in the case of the ideal cipher model.
Quantum-accessible random oracles
Post-quantum cryptography studies quantum attacks on classical cryptographic schemes. As a random oracle is an abstraction of a hash function, it makes sense to assume that a quantum attacker can access the random oracle in quantum superposition.[18] Many of the classical security proofs break down in that quantum random oracle model and need to be revised.
In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.
In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.
A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.
Articles related to cryptography include:
In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square.
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently standardized in PKCS#1 v2 and RFC 2437.
Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.
In cryptography, concrete security or exact security is a practice-oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow. It quantifies the security of a cryptosystem by bounding the probability of success for an adversary running for a fixed amount of time. Security proofs with precise analyses are referred to as concrete.
In cryptography, the Full Domain Hash (FDH) is an RSA-based signature scheme that follows the hash-and-sign paradigm. It is provably secure in the random oracle model. FDH involves hashing a message using a function whose image size equals the size of the RSA modulus, and then raising the result to the secret RSA exponent.
In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.
In cryptography the standard model is the model of computation in which the adversary is only limited by the amount of time and computational power available. Other names used are bare model and plain model.
In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non-negligible advantage, subject to specified bounds on the adversary's computational resources. "Negligible" usually means "within O(2−p)" where p is a security parameter associated with the algorithm. For example, p might be the number of bits in a block cipher's key.
In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.
In cryptography, format-preserving encryption (FPE), refers to encrypting in such a way that the output is in the same format as the input. The meaning of "format" varies. Typically only finite sets of characters are used; numeric, alphabetic or alphanumeric. For example:
In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.
Shabal is a cryptographic hash function submitted by the France-funded research project Saphir to NIST's international competition on hash functions.
↑ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizations of the P =? NP Question". SIAM J. Comput. SIAM. 4 (4): 431–442. doi:10.1137/0204037.
1 2 Bennett, Charles; Gill, John (1981). "Relative to a Random Oracle A, P!= NP!= co-NP with Probability 1". SIAM J. Comput. SIAM. 10 (1): 96–113. doi:10.1137/0210008.
↑ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). "10-Round Feistel is Indifferentiable from an Ideal Cipher". EUROCRYPT 2016. Springer. pp.649–678. doi:10.1007/978-3-662-49896-5_23.
↑ Dai, Yuanxi; Steinberger, John (2016). "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016. Springer.
↑ Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry (2011). "Random oracles in a quantum world". Advances in Cryptology – ASIACRYPT 2011. Lecture Notes in Computer Science. Vol.7073. Springer. pp.41–69. arXiv:1008.0931. doi:10.1007/978-3-642-25385-0_3. ISBN978-3-642-25384-3.{{cite conference}}: CS1 maint: multiple names: authors list (link)
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
