One-Way Permutations without Trapdoor

Question

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 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. 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]<n^{-c}$

(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]<n^{-c}$

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

Answer 1

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" 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 not to hold wrt black-box constructions/reductions, and is open in general (see my comment in the thread above).

Answer 2

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!)