Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.


Postby hyksos on April 16th, 2017, 5:01 pm 

You might have noticed that I use the word "Oracle" in some of my posts on this forum. The resident forum mathematicians already know what I mean when I use that word -- but I realize now that some forum users may not be familiar with this part of of higher math. I'm not talking about some young girl in Athenian Greece at Delphi. For the benefit of those who have not sat through uni courses covering Algorithmic Information Theory.

Random Oracles are a certain type of function that is presumed to exist in order to flesh out some proofs in information theory and cryptography.

I present some prerequisite reading and some related articles about Oracles
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 decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.

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 are typically used as an ideal replacement for cryptographic hash functions in schemes where strong randomness assumptions are needed of the hash function's output.

This is unfortunate, because our primary interest is usually the unrelativized case. It is hard to imagine a more "unintentional" oracle than a random one. In the words of Bennett and Gill:

random oracles, by their very structurelessness, appear more benign and less likely to distort the relations among complexity classes than the other oracles used in complexity theory and recursive function theory, which are usually designed expressly to help or frustrate some class of computations.

This led Bennett and Gill to formulate the random oracle hypothesis. Intuitively, this hypothesis states that any "acceptable" statement about relativized computational complexity classes which holds with probability one relative to a random oracle also holds in the unrelativized case.
User avatar
Active Member
Posts: 1574
Joined: 28 Nov 2014

Return to Mathematics

Who is online

Users browsing this forum: No registered users and 2 guests