Permutations à sens unique sans trappe

En bref: en supposant qu'il existe des permutations unidirectionnelles , pouvons-nous en construire une qui n'a pas de trappe?

Plus d'informations:

Une permutation unidirectionnelle est une permutation $\pi$ qui est facile à calculer, mais difficile à inverser (voir le wiki de balise de fonction unidirectionnelle pour une définition plus formelle). Nous considérons généralement les familles de permutation unidirectionnelle, $\pi = \{\pi_n\}_{n \in \mathbb{N}}$ , où chaque $\pi_n$ est une permutation unidirectionnelle, agissant sur un domaine fini $D_n$ . Une permutation unidirectionnelle de trappe est définie comme ci-dessus, sauf qu'il existe un ensemble de trappe $\{t_n\}_{n \in \mathbb{N}}$et un algorithme inverseur poly-temps $I$ , tel que pour tout $n$ , $|t_n| \le {\rm poly}(n)$ , et $I$ peux inverser $\pi_n$ condition qu'on lui donne $t_n$ .

Je connais des permutations unidirectionnelles qui sont générées de sorte qu'il est impossible de trouver la trappe (pourtant la trappe existe). Un exemple, basé sur l'hypothèse RSA, est donné ici . La question est,

Existe-t-il des (familles de) permutations unidirectionnelles qui n'ont pas de trappe (ensemble)?

Modifier: (Plus de formalisation)

Supposons qu'il existe une permutation unidirectionnelle $\pi$ avec le domaine (infini) $D \subseteq \{0,1\}^*$ . Autrement dit, il existe un algorithme de temps polynomial probabiliste $\mathcal{D}$ (qui, à l'entrée $1^n$ , induit une certaine distribution sur $D_n=\\{0,1\\}^n \cap D$ ), de sorte que pour tout adversaire polynomial$\mathcal{A}$ , tout$c>0$ et tout entier suffisamment grand$n$:

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

(La probabilité est prise sur les lancers de pièces internes de et .)$\mathcal{D}$$\mathcal{A}$

La question est de savoir si nous pouvons construire une permutation unidirectionnelle , pour laquelle il existe un algorithme à temps polynomial probabiliste tel que pour toute famille de circuits de taille poly , tout et tout entier suffisamment grand :$\pi'$$\mathcal{D}'$ $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$$c>0$$n$

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

(La probabilité est prise sur les lancers de pièces internes de , car est déterministe.)$\mathcal{D}'$$\mathcal{A}'$

Considérez les cas suivants:

1) Il existe des permutations unidirectionnelles (OWP) mais pas les permutations de trappe (TDP) (c'est-à-dire que nous sommes dans une variante du monde " minicrypt " d' Impagliazzo ). Dans ce cas, vous prenez simplement le OWP qui est garanti d'exister, et vous savez qu'il n'a pas de trappe.

2) OWP et TDP existent. Ici, vous avez deux options:

(a) Chaque OWP possède un algorithme de génération de clé G qui produit la description "publique" de la fonction f avec une trappe échantillonnée t. Dans ce cas, considérons une génération de clé modifiée qui ne produit que f. Cela vous donne un OWP, et de plus il est impossible de trouver t donné f (sinon vous avez un moyen efficace d'inverser f). Cela devrait également être valable pour une variante non uniforme.

(b) Il existe un OWP f tel qu'aucun algorithme G ne puisse sortir à la fois f et t de sorte que t permette l'inversion de f (x) pour un x aléatoire. Dans ce cas, f est un OWP qui n'a pas de trappe.

Un des commentaires dans le fil ci-dessus semble suggérer que vous vous demandez en réalité si l'existence de OWP est connue pour impliquer l'existence de TDP. Il a été démontré que cela ne contient pas de constructions / réductions de boîte noire et est ouvert en général (voir mon commentaire dans le fil ci-dessus).

Je ne connais pas les constructions à partir d'hypothèses générales, mais vous pouvez obtenir un candidat plausible pour une "permutation unidirectionnelle sans trappe" en utilisant un modulo log discret a prime . Autrement dit, soit une racine primitive modulo , et définissons . Alors est une permutation sur les entiers entre et , et il est généralement supposé être à sens unique. Pour la partie «sans trappe», je suppose que vous devez définir exactement ce que cela signifie, mais pour autant que je sache, nous n'avons aucun moyen de configurer les choses pour permettre l'inversion. (Si nous le faisions, alors il y aurait toutes sortes d'applications sympas (positives) en cryptographie!)$p$$g$$p$$\pi(x) = g^x\!\mod p$$\pi$$1$$p-1$