10
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You may want to add that not every protocol/scheme that somehow uses a hash function requires random oracles. The scheme could rely on another property of the hash function (e.g., second preimage resistance) and random oracles only come into play if the hash functions needs to be modeled as a random oracle in the security proof. $\endgroup$ – DrLecter Jan 13 '15 at 8:56
  • 1
    $\begingroup$ This answer misses the connection to the referenced paper: In that paper, they do not use random oracles to show anything. They use the collision resistance property of a hash function. The Proof of security is not in the random oracle model, if you don't use random oracles in the security proof. And they don't. $\endgroup$ – tylo Jan 13 '15 at 14:58
  • $\begingroup$ Thank you all for your explanations. May sound dumb, can anyone please point me out any simple (as simple as possible) cryptographic scheme which rely on random oracle for its security proof, so that I can compare and contrast? $\endgroup$ – Holmes.Sherlock Jan 13 '15 at 15:23
  • $\begingroup$ @Holmes.Sherlock A good example is the RSA Full-Domain Hash to create signatures using RSA. You will find that in this book: cs.umd.edu/~jkatz/imc.html I hope this still helps you even though the original post is several years old. $\endgroup$ – Dave Mar 9 '17 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.