Permutación unidireccional finita con dominio infinito

10

Deje que π:{0,1}{0,1} sea ​​una permutación. Tenga en cuenta que mientras π actúa en un dominio infinito, su descripción puede ser finita. Por descripción , me refiero a un programa que describe la funcionalidad de π . (Como en la complejidad de Kolmogorov.) Vea las explicaciones a continuación.

Por ejemplo, la función NOT es una de esas permutaciones:

función NO (x)
    Deje y = x
    Para i = 1 a | x |
        Voltea el i-ésimo bit de y
    volver y

πk() , definido a continuación, es otro caso:

función pi_k (x)
    retorno x + k (mod 2 ^ | x |)

Mi pregunta es sobre una clase especial de permutaciones, llamada permutaciones unidireccionales . Hablando informalmente, estas son permutaciones que son fáciles de calcular, pero difíciles de invertir (para una máquina BPP ). La mera existencia de permutaciones unidireccionales es un problema abierto de larga data en la criptografía y la teoría de la complejidad, sin embargo, en el resto, asumiremos que existen.

n=pqe=65537πn(x)=xemodn

Tenga en cuenta que RSA se define sobre el dominio finito . De hecho, para obtener una permutación de dominio infinito, uno debe considerar una familia de permutaciones RSA , donde es un conjunto infinito de enteros Blum. Tenga en cuenta que es la descripción de la familia y, por definición, es infinita. { π n } n D DDZn{πn}nDDD

Mi pregunta es (suponiendo la existencia de permutaciones unidireccionales):

¿Existen permutaciones unidireccionales de descripción finita sobre un dominio infinito ?

La respuesta puede variar: puede ser positiva, negativa o abierta (es probable que sea positiva o negativa ).

Antecedentes

La pregunta surgió cuando estaba leyendo un artículo de ASIACRYPT 2009 . Allí, el autor implícitamente (y en el contexto de alguna prueba) supuso que tales permutaciones unidireccionales existen.

Seré feliz si este es el caso, aunque no pude encontrar una prueba.

MS Dousti
fuente
¿No podemos describir finitamente a ? Existe un algoritmo finito que busca un número de Blum más pequeño que un número de entrada, por lo que calcular podría describirse, por ejemplo, como "encontrar el número de Blum más pequeño más grande que , luego calcular ". Aún así, no es obvio para mí que la función que obtendrás al unir un número infinito de sea ​​necesariamente una permutación. ¿Podrías explicar? π ( x ) b x π b ( x ) π bDπ(x)bxπb(x)πb
Karolina Sołtys
@Karolina: Gracias por la respuesta. Creo que el algoritmo "encuentra el número de Blum más pequeño más grande que , luego calcula " necesariamente mostrará información adicional sobre , como su factorización. Por lo tanto, dicho algoritmo no puede usarse para describir permutaciones unidireccionales . ¿Estás de acuerdo? x π b ( x ) bbxπb(x)b
MS Dousti
Ok, creo que lo entiendo: desea que la descripción finita describa la función de una manera fácil de calcular. Creo que podríamos codificar la parte "encontrar el número de Blum más pequeño ..." sin revelar ninguna información sobre (simplemente implementar la búsqueda de fuerza bruta para ), pero entonces no sería eficientemente computable. bbb
Karolina Sołtys
Quizás esta pregunta ayude con ideas: cstheory.stackexchange.com/questions/1378
Matt Groff
@ Matt: Gracias. En esa pregunta, la condición "fácil de calcular pero difícil de invertir" no es con respecto a las máquinas con límite de tiempo múltiple.
MS Dousti

Respuestas:

14

El documento Sobre la construcción de 1-1 funciones unidireccionales, de Goldreich, Levin y Nisan, muestra cómo construir longitud preservando 1-1 funciones con dominios infinitos y descripción finita. La dureza de invertir las funciones se basa en suposiciones populares, como la dureza de invertir RSA o encontrar logaritmos discretos.

Su construcción es un giro de la idea directa de convertir una familia, , de funciones unidireccionales en una única función unidireccional estableciendo donde es el La aleatoriedad utilizada para elegir el índice y es la aleatoriedad utilizada para seleccionar la entrada (dado el índice ). f ( r , s ) = f i ( x ) r i s x i{fi}if(r,s)=fi(x)risxi

El problema con la idea anterior es que no es necesariamente 1-1. Modifican este problema modificando ligeramente y argumentando que, bajo ciertas condiciones en la familia , la nueva construcción es de hecho 1-1. Luego muestran que estas condiciones son satisfechas por las funciones basadas en RSA / Discrete-log.f ( r , s ) { f i } if(r,s)f(r,s){fi}i

Alon Rosen
fuente
1
Gracias Alon por tu excelente respuesta. Fuera de tema: Estoy muy feliz de verte aquí. ¡Me encanta tu libro y tus documentos sobre conocimiento cero simultáneo !
MS Dousti
Thans, Sadeq. Me alegra saber que te gusta :-)
Alon Rosen