6
$\begingroup$

I am studying about RO model and just got this question that what are the factors that make it not possible to instantiate a RO with a Hash function. To give a reference on how far I know about them and other specification, I've followed this series of blog posts, so far. So, e.g. I know that one factor is that a RO size is exponentially grows on input but is this the only factor that one cannot instantiate it in the real world?

(hash functions are deterministic functions whereas RO is a random one, is this the most significant factor?)

$\endgroup$
  • $\begingroup$ One reason (IIRC): You can not learn the result of a RO call prior to making it (i.e. you need a full call to the RO). You can (theoretically) learn the result of a hash function call without fully evaluating the hash function (i.e. take shortcuts) $\endgroup$ – SEJPM Jan 14 '16 at 12:42
  • $\begingroup$ The only thing I can think of is that in the case of hash functions the adversary knows the output of a query beforehand, while in the RO model no one knows the output until the query is made. This way an adversary can pre-compute hashes and use correlations between them to break most security proofs. All RO proofs require that the adversary cannot do any pre-compution on the hashes without knowledge of the challenger (the system). $\endgroup$ – Jus12 Jan 15 '16 at 5:20
2
$\begingroup$

As you already mentioned, you cannot efficiently instantiate a random oracle because it would require an exponentially large description. This is the simple reason.

In general, a random oracle is just a random function sampled from the set of all functions with a given domain and range. If you consider inefficient constructions, you can actually instantiate a random oracle: Simply sample a table that contains a random value from the range for each value of the domain. This table becomes the function description and evaluating the function is a table look-up.

So, the uninstantiability only holds if we require efficient (= poly sized description) functions (which we do - of course - in practice).

Now, obviously any efficient function cannot be a random function. To be more precise we would have to talk about families of functions. For the random oracle model (ROM) we assume as function family the set of all functions with a given domain and range and the RO is random function sampled from this set. For (cryptographic) hash functions we consider a smaller set of functions that have a common description that takes as second input a key or index (think of the IV) and by sampling a random key, you get a random element from this family. However, as the set of these functions is comparatively small, there exist functions which are not in the family. Hence, there must exist biases of some kind. E.g., most cryptographic hash function families will not contain any constant function. In practice we rely on the assumption that these biases are not exploitable.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Well the idea of a cryptographically secure hash function (and often functions within them), is to mimic the Random Oracle model as closely as we can. Now, short of a little gremlin (perhaps?), some perfectly unbiased dice, a magical orb and a magic way to store all the possible outcomes from each input, we need these functions. I'm going to assume you know this and what you're asking is why do we need, "magic"?

Some points worth bearing on the Random Oracle:

  • The Oracle, would need infinite memory to memorise every query it ever received (as well as the truly-random reply).
  • The Oracle is truly random, this is enough of a challenge already.
  • The Oracle would not only need the infinite memory, previously referenced but eventually infinite power, both ideas, violate some physical constants.
  • The Oracle ... is already debunked. (it's a useful model but it is magic)

So the next best thing to see is Crypto-Secure-DRBGs. - They and the hash functions based around are at the heart of everything the RO attempts to recreate... apart from we should note, with a computer algorithm anyone with access to the algorithm, can query "the oracle" (this isn't really a problem, though and to expect differently is ludicrous).

(hash functions are deterministic functions whereas RO is a random one, is this the most significant factor?)

Basically, no: the most significant is the first one you mentioned, you can't memorise the outcome of every input, this is a physics issue or a maths issue, either-way, I don't think it needs dragging out.

| improve this answer | |
$\endgroup$

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.