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 & 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:

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.

  • $\begingroup$ Thanks Sadeq. So the idea is that in a relativized world we show that one side is true but the other side is equivalent to a difficult to prove result. But doesn't existence of OWP imply that $\mathsf{P} \neq \mathsf{NP}$ in the relativized world? $\endgroup$
    – Kaveh
    Jul 22 '11 at 0:02
  • $\begingroup$ btw, is there a survey paper about these techniques to prove negative results about construction of crypto primites? $\endgroup$
    – Kaveh
    Jul 22 '11 at 0:03
  • 2
    $\begingroup$ @Kaveh: You're welcome! The techniques vary, some of them are unconditional. Please see the edited answer for another technique and more pointers. Regarding the second point: I think the catch is that IR do not assume the existence of an OWP; rather they assume an RPO. It is well-known that relative to an RPO, P≠NP with probability 1. Yet, using this fact alone, there are countably infinite permutation oracles relative to which P=NP. $\endgroup$ Jul 22 '11 at 0:34
  • 2
    $\begingroup$ Very informative, thanks for writing that up, @Sadeq $\endgroup$ Jul 22 '11 at 3:05

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.