Going through the blog post, I was under the impression that any cryptographic scheme which makes use of hash function is said to be using random oracle. But, I have come across one construction of ring signature scheme which uses hash function, yet the paper is titled as Sub-linear Blind Ring Signatures Without Random Oracles. Where is my understanding incorrect?
The random oracle model is a way to analyze schemes that need a hash function; essentially, you replace the hash function with some black box (the random oracle) which evaluates a function selected uniformly at random from all functions from its input domain to its output domain. Equivalently, it takes input and gives output like this:
- If you give it an input it hasn't seen yet, it gives you an output selected uniformly at random from its possible outputs. It then saves that output for later use.
- If you give it an input it has seen before, it gives you the output it saved previously.
No actual hash function is a random oracle. Hash functions are deterministic; for a given hash function, $H(x)$ in one problem is equal to $H(x)$ in some other problem. With a random oracle, this is not the case: the function used is random. Random oracles are often used to approximate hash functions in security proofs, but no actual hash function can be a random oracle because anything used in a real, sensible security scheme must be a deterministic algorithm.
Random oracles aren't used when analyzing hash functions, they're used when analyzing other things. Unfortunately, for any real, deterministic hash function $H$, you can come up with schemes which are secure when used with a random oracle but not when used with $H$. Essentially, you construct a signature scheme that hashes a bunch of stuff and checks if the hash of $x$ is $H(x)$ for all the $x$ it tested; if not, it outputs a normal signature, if so, it outputs a normal signature and then sticks the private key on the end. With a random oracle, it's extremely unlikely that the hashes represent any pre-specified function (as they're completely random), but if you use $H$ they will obviously always fit the relationship. So, random oracles are an imperfect model, and we generally prefer security proofs not relying on them.