<p>There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of <a href="http://cseweb.ucsd.edu/~russell/secret.ps" rel="nofollow">Impagliazzo &amp; Rudich</a>. Let me describe the Impagliazzo-Rudich (IR) technique at a high level.</p>

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

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

<blockquote>
  <p>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 <strong>new model</strong>.</p>
</blockquote>

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

<p>Assume that all parties (including the adversary) have access to a <strong>random-permutation oracle</strong> (RPO), i.e. a function chosen uniformly from all n-bit to n-bit permutations (where 1<sup>n</sup> 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 <strong>P ≠ NP</strong>. 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.</p>

<p>Other excellent resources on this topic:</p>

<ul>
<li><a href="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.136.4654&amp;rep=rep1&amp;type=pdf" rel="nofollow">Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions</a>: rules out black-box constructions of collision-resistant hash functions from one-way functions (as pointed out in the question). Excerpt:
<blockquote>
  <p>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 <strong>non-relativizing</strong>; in particular, no provable construction of a <strong>collision-intractable hash function</strong> can exist based solely on a "black box" <strong>one-way permutation</strong>.</li>
  <li><a href="http://www.cs.bu.edu/~reyzin/papers/hash.ps" rel="nofollow">Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins</a>.</li>
  <li><a href="http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=62DAB1C167002F35D08F768B3F0E21B0?doi=10.1.1.11.1471&amp;rep=rep1&amp;type=pdf" rel="nofollow">Notions of Reducibility between Cryptographic Primitives</a>.</li>
  </ul>

<p>The papers are inspired by the work of IR, and extend their techniques.</p>
</blockquote></p>

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

<hr>

<p>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.</p>

CC BY-SA 3.0
2011-07-22T00:02:10.673Z
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?
Kaveh
CC BY-SA 3.0
2011-07-22T00:03:20.813Z
btw, is there a survey paper about these techniques to prove negative results about construction of crypto primites?
Kaveh
CC BY-SA 3.0
2011-07-22T00:34:05.590Z
@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.
Sadeq Dousti
CC BY-SA 3.0
2011-07-22T03:05:38.803Z
Very informative, thanks for writing that up, @Sadeq
Daniel Apon
CC BY-SA 3.0
2011-07-21T23:54:52.317Z
2011-10-25T09:48:16.273Z
2011-10-25T09:48:16.273Z
Sadeq Dousti
<p>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? </p>

<hr>

<p>The motivation is to understand what it means to show that <a href="http://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption" rel="nofollow">DDH</a> 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.</p>

<cr.crypto-security><reductions><hash-function><relativization><black-box>
Separation between existence of crypto primitives
Kaveh
# Separation between existence of crypto primitives

(Asked by: username_0 on 2011-07-21)

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](http://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption) 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.

**Tags:** cr.crypto-security, reductions, hash-function, relativization, black-box

---

## 1 answers

### Answer by username_1 on 2011-07-21. Score: 10 | Accepted answer

There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of [Impagliazzo & Rudich](http://cseweb.ucsd.edu/~russell/secret.ps). 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](http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.136.4654&rep=rep1&type=pdf): 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](http://www.cs.bu.edu/~reyzin/papers/hash.ps).
* [Notions of Reducibility between Cryptographic Primitives](http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=62DAB1C167002F35D08F768B3F0E21B0?doi=10.1.1.11.1471&rep=rep1&type=pdf).

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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: btw, is there a survey paper about these techniques to prove negative results about construction of crypto primites?  
> **username_1**: @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.  
> **username_2**: Very informative, thanks for writing that up, @Sadeq  

---

