Separation between existence of crypto primitives I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My question is how can we show this is not possible? For example, AFAIU, the existence collision resistant hash functions does not follow from the existence of one-way functions (at least not in a black box manner), but how is this formally stated? 



The motivation is to understand what it means to show that DDH against subexponential ($2^{n^\epsilon}$) size circuits does not follow from DDH against polynomial size circuits. Note that the situation is more complicated here because DDH is a hardness assumption about a particular function, so it is not clear what would it meant to relativize it. I would also be interested in references if this is already known.
There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of Impagliazzo &amp; Rudich. Let me describe the Impagliazzo-Rudich (IR) technique at a high level.

In crypto, it is well-known how to construct a secure secret-key exchange protocol from trapdoor one-way permutations. However, all attempts to construct such protocols from general one-way permutations were failed. So, it was an open problem whether such constructions were possible at all.

The hard part of refuting those constructions is as follows: It is believed that both one-way permutations and secure secret-key exchange protocols exist; so how can we refute the latter if we merely assume the former? In IR words:


  The implication, "if one-way permutations exist, then secure secret-key agreement is possible," is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model.


While they were not succeeded to refute the existence of such black-box reductions, they were able to provide strong evidence that the implication is not provable by standard techniques. To this end, IR came up with the following model:

Assume that all parties (including the adversary) have access to a random-permutation oracle (RPO), i.e. a function chosen uniformly from all n-bit to n-bit permutations (where 1n is the security parameter). RPO models the black-box access to some one-way permutation. Now, IR prove that in this model, secure secret-key agreement is possible if and only if P ≠ NP. Since standard techniques cannot resolve the P vs. NP problem, it follows that proving (or disproving) the implication "if one-way permutations exist, then secure secret-key agreement is possible" is as hard as proving (or disproving) P ≠ NP.

Other excellent resources on this topic:


Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions: rules out black-box constructions of collision-resistant hash functions from one-way functions (as pointed out in the question). Excerpt:

  We prove the existence of an oracle relative to which there exist several well-known cryptographic primitives, including one-way permutations, but excluding (for a suitably strong definition) collision-intractable hash functions. Thus any proof that such functions can be derived from these weaker primitives is necessarily non-relativizing; in particular, no provable construction of a collision-intractable hash function can exist based solely on a "black box" one-way permutation.
  Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins.
  Notions of Reducibility between Cryptographic Primitives.
  

The papers are inspired by the work of IR, and extend their techniques.


5 recent papers on the topic can be found in the proceedings of TCC 2011 (see chapters Black-Box Constructions and Separations and Black-Box Separations, pages 541--629).
They have surveys of previous results, which are certainly useful.



An important technique: Black-box reductions are by definition relativizing. So, if relative to some oracle, one primitive exists but the other does not, the existence of the latter cannot be deduced in a black-box manner from the existence of the former.