9
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – David Cash
    Dec 8, 2010 at 21:09
  • $\begingroup$ @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. $\endgroup$ Dec 8, 2010 at 21:34
  • $\begingroup$ @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. $\endgroup$
    – David Cash
    Dec 8, 2010 at 21:43
  • $\begingroup$ @David: see if the edited part satisfies the need for further formalization. $\endgroup$ Dec 8, 2010 at 22:03
  • 1
    $\begingroup$ @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 (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. $\endgroup$
    – Alon Rosen
    Dec 9, 2010 at 5:26

2 Answers 2

8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ +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. $\endgroup$ Dec 9, 2010 at 9:51
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 10, 2010 at 15:50
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alon Rosen
    Dec 10, 2010 at 17:57
7
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ +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? $\endgroup$ Dec 8, 2010 at 21:43
  • $\begingroup$ @Sadeq: Doesn't the existence of one-way permutations imply the hardness of discrete log since P=NP ? $\endgroup$ Dec 9, 2010 at 11:47
  • $\begingroup$ @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. $\endgroup$ Dec 9, 2010 at 11:49
  • $\begingroup$ @Sadeq: That's if P=BQP!=NP. $\endgroup$ Dec 9, 2010 at 13:36
  • $\begingroup$ @Sadeq: Right or I did get it wrong ? $\endgroup$ Dec 9, 2010 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.