Permutaciones unidireccionales sin trampilla

En resumen: suponiendo que existan permutaciones unidireccionales , ¿podemos construir una que no tenga trampilla?

Más información:

Una permutación unidireccional es una permutación $\pi$ que es fácil de calcular, pero difícil de invertir (consulte el wiki de etiqueta de función unidireccional para obtener una definición más formal). Generalmente consideramos familias de permutación unidireccional, $\pi = \{\pi_n\}_{n \in \mathbb{N}}$ , donde cada es una permutación unidireccional, que actúa sobre un dominio finito . Una trampilla unidireccional de permutación se define como anteriormente, excepto que existe un conjunto trampilla y un algoritmo de poli-tiempo invirtiendo , tal que para todoD n { t n } n ∈ N I n | t n | ≤ p o l y ( n ) I π n t $\pi_n$$D_n$$\{t_n\}_{n \in \mathbb{N}}$$I$$n$, , y puedo invertido siempre que se le da .$|t_n| \le {\rm poly}(n)$$I$$\pi_n$$t_n$

Sé permutaciones unidireccionales que se generan para que no sea factible encontrar la trampilla (aunque la trampilla existe). Aquí se da un ejemplo, basado en la suposición de RSA . La pregunta es,

¿Existen (familias de) permutaciones unidireccionales que no tienen una trampilla (conjunto)?

Editar: (Más formalización)

Supongamos que existe alguna permutación unidireccional con dominio (infinito) . Es decir, existe un algoritmo probabilístico de tiempo polinómico (que, en la entrada , induce alguna distribución sobre ), de modo que para cualquier adversario de tiempo polinomial , cualquier , y todos los enteros suficientemente grandes :D ⊆ { 0 , 1 } ∗ D 1 n D n$\pi$$D \subseteq \{0,1\}^*$$\mathcal{D}$$1^n$A c > 0 $D_n=\\{0,1\\}^n \cap D$$\mathcal{A}$$c>0$$n$

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

(La probabilidad se toma sobre los lanzamientos internos de monedas de $\mathcal{D}$ y $\mathcal{A}$ .)

La pregunta es si podemos construir una permutación unidireccional , para la cual existe un algoritmo probabilístico de tiempo polinómico tal que para cualquier familia de circuitos de tamaño polifásico , cualquier y todos los enteros suficientemente grandes :D ′ A ′ = { A ′ n } n ∈ N c > $\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 probabilidad se toma sobre los lanzamientos internos de monedas de , ya que es determinista).A$\mathcal{D}'$$\mathcal{A}'$

Considere los siguientes casos:

1) Existen permutaciones unidireccionales (OWP) pero no existen permutaciones de trampillas (TDP) (es decir, estamos en una variante del mundo de " minicriptos " de Impagliazzo ). En este caso, simplemente toma el OWP que se garantiza que existe, y sabe que no tiene una trampilla.

2) Existen tanto OWP como TDP. Aquí tienes dos opciones:

(a) Cada OWP tiene un algoritmo de generación de claves G que genera la descripción "pública" de la función f junto con una trampilla de muestreo t. En este caso, considere una generación de clave modificada que solo genera f. Esto le da un OWP y, además, no es factible encontrar t dado f (de lo contrario, tiene una manera eficiente de invertir f). Esto también debería ser válido para una variante no uniforme.

(b) Existe un OWP f tal que ningún algoritmo G puede generar tanto f como t de modo que t permita la inversión de f (x) para una x aleatoria. En este caso, f es un OWP que no tiene una trampilla.

Uno de los comentarios en el hilo anterior parece sugerir que su pregunta es en realidad si se sabe que la existencia de OWP implica la existencia de TDP. Se ha demostrado que esto no contiene construcciones / reducciones de caja negra de wrt, y está abierto en general (vea mi comentario en el hilo anterior).

No sé acerca de las construcciones a partir de supuestos generales, pero puede obtener un candidato plausible para una "permutación unidireccional sin trampilla" mediante el uso de un módulo de registro discreto a prime . Es decir, que sea ​​un módulo raíz primitivo , y definag p π ( x ) = g $p$$g$$p$π 1 p - $\pi(x) = g^x\!\mod p$ . Entonces es una permutación en los enteros entre y , y generalmente se supone que es unidireccional. Para la parte "sin trampillas", supongo que debe definir exactamente lo que eso significa, pero que yo sepa, no tenemos ninguna forma de configurar las cosas para permitir la inversión. (Si lo hiciéramos, ¡entonces tendría todo tipo de aplicaciones geniales (positivas) en criptografía!)$\pi$$1$$p-1$