<p>Consider the following cases:</p>

<p>1) One-way permutations (OWP) exist but trapdoor permutations (TDP) do not (i.e. we are in a variant of Impagliazzo's "<a href="http://cseweb.ucsd.edu/~russell/average.ps" rel="noreferrer">minicrypt</a>" world). In this case you just take the OWP that is guaranteed to exist, and you know that it doesn't have a trapdoor.</p>

<p>2) Both OWP and TDP exist. Here you have two options: </p>

<p>(a) Every OWP has a key generation algorithm G that outputs the function's "public" description f along with a sampled trapdoor t. In this case, consider a modified key-generation that only outputs f. This gives you a OWP, and moreover it is infeasible to find t given f (as otherwise you have an efficient way to invert f). This should also hold for a non-uniform variant.</p>

<p>(b) There exists a OWP f such that no algorithm G can output both f and t so that t enables inversion of f(x) for a random x. In this case f is a OWP that doesn't have a trapdoor.</p>

<p>One of the comments in the thread above seems to suggest that you question is actually whether the existence of OWP is known to imply the existence of TDP. This has been <a href="http://cseweb.ucsd.edu/~russell/secret.ps" rel="noreferrer">shown</a> not to hold wrt black-box constructions/reductions, and is open in general (see my comment in the thread above).</p>

CC BY-SA 2.5
2010-12-09T09:51:14.070Z
+1, thank you. David has put a lot of effort in answering, and I'm very thankful to him; but this is *the* answer to what I had in mind.
Sadeq Dousti
CC BY-SA 2.5
2010-12-10T15:50:55.993Z
I thought the question was: is (a) possible. Cryptographically, if every OWP has a trapdoor, then you can't trust somebody who gives you a OWP not to also know the trapdoor. Of course, you could take his OWP and compose it with your own OWP, for which only you know the trapdoor, and get a OWP for which no single party knows the trapdoor.
Peter Shor 
CC BY-SA 2.5
2010-12-10T17:57:02.107Z
@Peter: Yes. Composition seems to do the job. Another option is to use oblivious transfer (which, if (a) holds, is known to exist - modulo some small subltleties). Using OT, the players can construct a secure 2-party computation protocol that lets one of them to learn f without learning the trapdoor and the other not to learn anything. But your solution is indeed simpler.
Alon Rosen
CC BY-SA 2.5
2010-12-09T05:34:30.387Z
2010-12-09T07:00:42.417Z
2010-12-09T07:00:42.417Z
Alon Rosen
<p>I don't know about constructions from general assumptions, but you can get a plausible candidate for a "one-way permutation without a trapdoor" by using discrete log modulo a prime $p$.  That is, let $g$ be a primitive root modulo $p$, and define $\pi(x) = g^x\!\mod p$.  Then $\pi$ is a permutation on the integers between $1$ and $p-1$, and it is generally assumed to be one-way.  For the "no trapdoor" part, I suppose you need to define exactly what that means, but as far as I know, we don't have any way to set things up to enable inversion.  (If we did, then it'd have all sorts of cool (positive) applications in cryptography!)</p>

CC BY-SA 2.5
2010-12-08T21:43:19.227Z
+1. Thanks for the answer. You are assuming the hardness of discrete log against non-uniform adversaries. My question is: Assuming the mere existence of one-way permutations, can we construct one that has no trapdoor?
Sadeq Dousti
CC BY-SA 2.5
2010-12-09T11:47:11.060Z
@Sadeq: Doesn't the existence of one-way permutations imply the hardness of discrete log since P=NP ?
Mohammad Alaggan
CC BY-SA 2.5
2010-12-09T11:49:16.400Z
@Alaggan: I don't think so. It might be the case that there exists one-way permutations, but someone comes up with an efficient algorithm for inverting discrete log.
Sadeq Dousti
CC BY-SA 2.5
2010-12-09T13:36:14.353Z
@Sadeq: That's if P=BQP!=NP.
Mohammad Alaggan
CC BY-SA 2.5
2010-12-09T14:06:57.930Z
@Sadeq: Right or I did get it wrong ?
Mohammad Alaggan
CC BY-SA 2.5
2010-12-09T14:17:19.033Z
@Alaggan: I'm afraid (and ashamed) to say that I know almost nothing about quantum computing, so I can't say the consequences of P=BQP$\ne$NP. You may wait till some expert answers the comment, or even better: start a new question.
Sadeq Dousti
CC BY-SA 2.5
2010-12-08T21:31:54.343Z
2010-12-08T21:31:54.343Z
David Cash
<p><strong>In Short:</strong> Assuming <strong>one-way permutations</strong> exist, can we construct one that has no trapdoor?</p>
<h3>More info:</h3>
<p>A one-way permutation is a permutation <span class="math-container">$\pi$</span> which is easy to compute, but hard to invert (see the <a href="https://cstheory.stackexchange.com/tags/one-way-function/info">one-way-function tag wiki</a> for a more formal definition). We usually consider <strong>families</strong> of one-way permutation, <span class="math-container">$\pi = \{\pi_n\}_{n \in \mathbb{N}}$</span>, where each <span class="math-container">$\pi_n$</span> is a one-way permutation, acting on a <strong>finite</strong> domain <span class="math-container">$D_n$</span>. A <strong>trapdoor</strong> one-way permutation is defined as above, except that there exists a trapdoor set <span class="math-container">$\{t_n\}_{n \in \mathbb{N}}$</span> and an poly-time inverting algorithm <span class="math-container">$I$</span>, such that for all <span class="math-container">$n$</span>, <span class="math-container">$|t_n| \le {\rm poly}(n)$</span>, and <span class="math-container">$I$</span> can invert <span class="math-container">$\pi_n$</span> provided that it is given <span class="math-container">$t_n$</span>.</p>
<p>I know one-way permutations which are generated so that it is <em>infeasible</em> to find the trapdoor (yet the trapdoor exists). An example, based on RSA-assumption, is given <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/PS/gln.ps" rel="nofollow noreferrer">here</a>. The question is,</p>
<blockquote>
<p>Do there exist (families of) one-way permutations which <strong>do not</strong> have a trapdoor (set)?</p>
</blockquote>
<h3>Edit: (More Formalization)</h3>
<p>Assume there exists some one-way permutation <span class="math-container">$\pi$</span> with (infinite) domain <span class="math-container">$D \subseteq \{0,1\}^*$</span>. That is, there exists a probabilistic polynomial-time algorithm <span class="math-container">$\mathcal{D}$</span> (which, on input <span class="math-container">$1^n$</span>, induces some distribution over <span class="math-container">$D_n=\\{0,1\\}^n \cap D$</span>), such that
for any polynomial-time adversary <span class="math-container">$\mathcal{A}$</span>, any <span class="math-container">$c&gt;0$</span>, and all sufficiently large integer <span class="math-container">$n$</span>:</p>
<p><span class="math-container">$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]&lt;n^{-c}$</span></p>
<p>(The probability is taken over the internal coin tosses of <span class="math-container">$\mathcal{D}$</span> and <span class="math-container">$\mathcal{A}$</span>.)</p>
<p>The question, is whether we can construct a one-way permutation <span class="math-container">$\pi'$</span>, for which there exists a probabilistic polynomial-time algorithm <span class="math-container">$\mathcal{D}'$</span> such that for any <strong>poly-size family of circuits</strong> <span class="math-container">$\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$</span>, any <span class="math-container">$c&gt;0$</span>, and all sufficiently large integer <span class="math-container">$n$</span>:</p>
<p><span class="math-container">$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]&lt;n^{-c}$</span></p>
<p>(The probability is taken over the internal coin tosses of <span class="math-container">$\mathcal{D}'$</span>, since <span class="math-container">$\mathcal{A}'$</span> is deterministic.)</p>

CC BY-SA 2.5
2010-12-08T21:09:37.397Z
It sounds like you want a OWP that remains one-way even when given a polynomial amount of advice.  By the way, we don't usually define families of OWPs like that - see Goldreich Vol 1, defs 2.4.4 and 2.4.5.
David Cash
CC BY-SA 2.5
2010-12-08T21:34:43.693Z
@David: Yeah, I know it's not the usual definition, but I felt the formal definition (the one that appears in Goldreich's book) is too  long for this discussion.
Sadeq Dousti
CC BY-SA 2.5
2010-12-08T21:43:58.760Z
@Sadeq:  Fair enough, but I think the change in definitions will be significant here.  For what it's worth, I've tried to think about a similar type of security (no trapdoors) before.  It seemed like a good definition would be to allow unbounded processing of the family index to produce advice before the inversion experiment.
David Cash
CC BY-SA 2.5
2010-12-08T22:03:50.050Z
@David: see if the edited part satisfies the need for further formalization.
Sadeq Dousti
CC BY-SA 2.5
2010-12-08T23:59:14.540Z
@Sadeq:  I don't think your definition makes much sense for crypto.  If you take trapdoors to be non-uniform advice, then how does this model an honest party's power over an adversary?  I think the standard definition makes much more sense.  There, the index and trapdoor are generated at random from a large set of possibilities.  You can still consider uniform and non-uniform versions of TDOWP in this type of definition.
David Cash
CC BY-SA 2.5
2010-12-09T00:01:09.110Z
@Sadeq:  Also, as formulated, you are asking to amplify uniform hardness to non-uniform hardness.  That's quite a challenge!
David Cash
CC BY-SA 2.5
2010-12-09T00:10:20.503Z
@David: They can be used for commitment: To commit to $m$, randomly choose $r$ (of size $|m|$), and send $\pi(r) \oplus m$. To decommit, reveal $r$. You see, there's no need for a trapdoor even for the honest parties. You may ask, however, what's their advantage over those having trapdoors? I don't have an answer yet; my original question has a theoretical flavor rather than a practical one. I want to know whether assuming the "existence of trapdoor OWPs" is stronger than assuming the "existence of OWPs"?
Sadeq Dousti
CC BY-SA 2.5
2010-12-09T00:12:16.210Z
@David: Regarding your comment: "you are asking to amplify uniform hardness to non-uniform hardness. That's quite a challenge," can I infer that the "existence of trapdoor OWPs is a stronger assumption than the existence of OWPs"? Can we prove this, or is it open?
Sadeq Dousti
CC BY-SA 2.5
2010-12-09T01:10:25.760Z
Here is a summary of what I'm trying to say:  First, the intuitive concept of "OWP w/o TD" seems useful and interesting.  Second, I don't think your definition formalizes the intuitive definition in a useful way.  Third, the question you posed in the edit seems likely far beyond known techniques.
David Cash
CC BY-SA 2.5
2010-12-09T01:27:54.960Z
@David: I get most of what I wanted, and accepted the answer. However, since you say my definition doesn't "formalizes the intuitive definition in a useful way," I wanted to kindly ask you to add a formal definition of "OWP w/o TD" in your answer.
Sadeq Dousti
CC BY-SA 2.5
2010-12-09T02:52:38.943Z
@Sadeq: Good idea!  I'll get to that soon.
David Cash
CC BY-SA 2.5
2010-12-09T05:26:12.560Z
@Sadeq: Determining whether trapdoor one-way permutations are implied by one-way permutations or not (though it is not even clear what the latter means, as they could both conceivably exist) is one of the biggest open problems in the theory of cryptography. Impagliazzo and Rudich (http://cseweb.ucsd.edu/~russell/secret.ps) proved that this cannot be achieved using black-box techniques, and current techniques are not known to bypass their separation.
Alon Rosen
<cr.crypto-security><one-way-function>
One-Way Permutations without Trapdoor
Sadeq Dousti
# One-Way Permutations without Trapdoor

(Asked by: username_0 on 2010-12-08)

**In Short:** Assuming **one-way permutations** exist, can we construct one that has no trapdoor?

### More info:

A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the [one-way-function tag wiki](https://cstheory.stackexchange.com/tags/one-way-function/info) for a more formal definition). We usually consider **families** of one-way permutation, $\pi = \{\pi\_n\}\_{n \in \mathbb{N}}$, where each $\pi\_n$ is a one-way permutation, acting on a **finite** domain $D\_n$. A **trapdoor** one-way permutation is defined as above, except that there exists a trapdoor set $\{t\_n\}\_{n \in \mathbb{N}}$ and an poly-time inverting algorithm $I$, such that for all $n$, $|t\_n| \le {\rm poly}(n)$, and $I$ can invert $\pi\_n$ provided that it is given $t\_n$.

I know one-way permutations which are generated so that it is *infeasible* to find the trapdoor (yet the trapdoor exists). An example, based on RSA-assumption, is given [here](http://www.wisdom.weizmann.ac.il/%7Eoded/PS/gln.ps). The question is,

> Do there exist (families of) one-way permutations which **do not** have a trapdoor (set)?

### Edit: (More Formalization)

Assume there exists some one-way permutation $\pi$ with (infinite) domain $D \subseteq \{0,1\}^\*$. That is, there exists a probabilistic polynomial-time algorithm $\mathcal{D}$ (which, on input $1^n$, induces some distribution over $D\_n=\\{0,1\\}^n \cap D$), such that
for any polynomial-time adversary $\mathcal{A}$, any $c>0$, and all sufficiently large integer $n$:

$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]

(The probability is taken over the internal coin tosses of $\mathcal{D}$ and $\mathcal{A}$.)

The question, is whether we can construct a one-way permutation $\pi'$, for which there exists a probabilistic polynomial-time algorithm $\mathcal{D}'$ such that for any **poly-size family of circuits** $\mathcal{A}'=\{\mathcal{A}'\_n\}\_{n \in \mathbb{N}}$, any $c>0$, and all sufficiently large integer $n$:

$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'\_n(\pi'(x))=x]

(The probability is taken over the internal coin tosses of $\mathcal{D}'$, since $\mathcal{A}'$ is deterministic.)

**Tags:** cr.crypto-security, one-way-function
> **Comments:**
> **username_1**: It sounds like you want a OWP that remains one-way even when given a polynomial amount of advice.  By the way, we don't usually define families of OWPs like that - see Goldreich Vol 1, defs 2.4.4 and 2.4.5.  
> **username_0**: @David: Yeah, I know it's not the usual definition, but I felt the formal definition (the one that appears in Goldreich's book) is too  long for this discussion.  
> **username_1**: @Sadeq:  Fair enough, but I think the change in definitions will be significant here.  For what it's worth, I've tried to think about a similar type of security (no trapdoors) before.  It seemed like a good definition would be to allow unbounded processing of the family index to produce advice before the inversion experiment.  
> **username_0**: @David: see if the edited part satisfies the need for further formalization.  
> **username_1**: @Sadeq:  I don't think your definition makes much sense for crypto.  If you take trapdoors to be non-uniform advice, then how does this model an honest party's power over an adversary?  I think the standard definition makes much more sense.  There, the index and trapdoor are generated at random from a large set of possibilities.  You can still consider uniform and non-uniform versions of TDOWP in this type of definition.  
> **username_1**: @Sadeq:  Also, as formulated, you are asking to amplify uniform hardness to non-uniform hardness.  That's quite a challenge!  
> **username_0**: @David: They can be used for commitment: To commit to $m$, randomly choose $r$ (of size $|m|$), and send $\pi(r) \oplus m$. To decommit, reveal $r$. You see, there's no need for a trapdoor even for the honest parties. You may ask, however, what's their advantage over those having trapdoors? I don't have an answer yet; my original question has a theoretical flavor rather than a practical one. I want to know whether assuming the "existence of trapdoor OWPs" is stronger than assuming the "existence of OWPs"?  
> **username_0**: @David: Regarding your comment: "you are asking to amplify uniform hardness to non-uniform hardness. That's quite a challenge," can I infer that the "existence of trapdoor OWPs is a stronger assumption than the existence of OWPs"? Can we prove this, or is it open?  
> **username_1**: Here is a summary of what I'm trying to say:  First, the intuitive concept of "OWP w/o TD" seems useful and interesting.  Second, I don't think your definition formalizes the intuitive definition in a useful way.  Third, the question you posed in the edit seems likely far beyond known techniques.  
> **username_0**: @David: I get most of what I wanted, and accepted the answer. However, since you say my definition doesn't "formalizes the intuitive definition in a useful way," I wanted to kindly ask you to add a formal definition of "OWP w/o TD" in your answer.  
> **username_1**: @Sadeq: Good idea!  I'll get to that soon.  
> **username_2**: @Sadeq: Determining whether trapdoor one-way permutations are implied by one-way permutations or not (though it is not even clear what the latter means, as they could both conceivably exist) is one of the biggest open problems in the theory of cryptography. Impagliazzo and Rudich (http://cseweb.ucsd.edu/~russell/secret.ps) proved that this cannot be achieved using black-box techniques, and current techniques are not known to bypass their separation.  

---

## 2 answers

### Answer by username_2 on 2010-12-09. Score: 8 | Accepted answer

Consider the following cases:

1) One-way permutations (OWP) exist but trapdoor permutations (TDP) do not (i.e. we are in a variant of Impagliazzo's "[minicrypt](http://cseweb.ucsd.edu/~russell/average.ps)" world). In this case you just take the OWP that is guaranteed to exist, and you know that it doesn't have a trapdoor.

2) Both OWP and TDP exist. Here you have two options:

(a) Every OWP has a key generation algorithm G that outputs the function's "public" description f along with a sampled trapdoor t. In this case, consider a modified key-generation that only outputs f. This gives you a OWP, and moreover it is infeasible to find t given f (as otherwise you have an efficient way to invert f). This should also hold for a non-uniform variant.

(b) There exists a OWP f such that no algorithm G can output both f and t so that t enables inversion of f(x) for a random x. In this case f is a OWP that doesn't have a trapdoor.

One of the comments in the thread above seems to suggest that you question is actually whether the existence of OWP is known to imply the existence of TDP. This has been [shown](http://cseweb.ucsd.edu/~russell/secret.ps) not to hold wrt black-box constructions/reductions, and is open in general (see my comment in the thread above).

> **Comments:**
> **username_0**: +1, thank you. David has put a lot of effort in answering, and I'm very thankful to him; but this is *the* answer to what I had in mind.  
> **username_3**: I thought the question was: is (a) possible. Cryptographically, if every OWP has a trapdoor, then you can't trust somebody who gives you a OWP not to also know the trapdoor. Of course, you could take his OWP and compose it with your own OWP, for which only you know the trapdoor, and get a OWP for which no single party knows the trapdoor.  
> **username_2**: @Peter: Yes. Composition seems to do the job. Another option is to use oblivious transfer (which, if (a) holds, is known to exist - modulo some small subltleties). Using OT, the players can construct a secure 2-party computation protocol that lets one of them to learn f without learning the trapdoor and the other not to learn anything. But your solution is indeed simpler.  

---

### Answer by username_1 on 2010-12-08. Score: 7

I don't know about constructions from general assumptions, but you can get a plausible candidate for a "one-way permutation without a trapdoor" by using discrete log modulo a prime $p$. That is, let $g$ be a primitive root modulo $p$, and define $\pi(x) = g^x\!\mod p$. Then $\pi$ is a permutation on the integers between $1$ and $p-1$, and it is generally assumed to be one-way. For the "no trapdoor" part, I suppose you need to define exactly what that means, but as far as I know, we don't have any way to set things up to enable inversion. (If we did, then it'd have all sorts of cool (positive) applications in cryptography!)

> **Comments:**
> **username_0**: +1. Thanks for the answer. You are assuming the hardness of discrete log against non-uniform adversaries. My question is: Assuming the mere existence of one-way permutations, can we construct one that has no trapdoor?  
> **username_4**: @Sadeq: Doesn't the existence of one-way permutations imply the hardness of discrete log since P=NP ?  
> **username_0**: @Alaggan: I don't think so. It might be the case that there exists one-way permutations, but someone comes up with an efficient algorithm for inverting discrete log.  
> **username_4**: @Sadeq: That's if P=BQP!=NP.  
> **username_4**: @Sadeq: Right or I did get it wrong ?  
> **username_0**: @Alaggan: I'm afraid (and ashamed) to say that I know almost nothing about quantum computing, so I can't say the consequences of P=BQP$\ne$NP. You may wait till some expert answers the comment, or even better: start a new question.  

---

