La suposición de ocultación de phi o suposición de ocultación de is es una suposición sobre la dificultad de encontrar factores pequeños de φ ( m ) donde m es un número cuya factorización se desconoce y 's es la función totiente de Euler . La seguridad de muchos criptosistemas modernos proviene de la dificultad percibida de ciertos problemas. Dado que el problema de P frente a NP aún no se ha resuelto, los criptógrafos no pueden estar seguros de que existan problemas computacionalmente intratables. Por lo tanto, los criptógrafos hacen suposiciones sobre qué problemas son difíciles . Comúnmente se cree que si m es el producto de dos grandesprimos , entonces calcular φ ( m ) es actualmente computacionalmente inviable; esta suposición es necesaria para la seguridad del criptosistema RSA . La suposición de Φ-Ocultación es una suposición más fuerte, a saber, que si p 1 y p 2 son números primos pequeños, exactamente uno de los cuales divide a φ ( m ), no existe un algoritmo de tiempo polinómico que pueda distinguir cuál de los primos p 1 y p 2 divide φ ( m ) con una probabilidad significativamente mayor que la mitad.
Esta suposición se estableció por primera vez en el artículo de 1999 Recuperación de información privada computacionalmente con comunicación polilogarítmica, [1] donde se utilizó en un esquema de recuperación de información privada .
Aplicaciones
El supuesto de ocultación de Phi ha encontrado aplicaciones en la construcción de algunas primitivas criptográficas. Algunas de las construcciones incluyen:
- Recuperación de información privada computacionalmente con comunicación polilogarítmica (1999)
- Licitaciones y subastas privadas eficientes con un tercero ajeno (1999)
- Recuperación de información privada de base de datos única con tasa de comunicación constante (2005)
- Intercambio de claves autenticadas con contraseña utilizando subgrupos suaves ocultos (2005)
Referencias
- ^ Cachín, cristiano; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "Recuperación de información privada computacionalmente con comunicación polilogarítmica". Apuntes de conferencias en Ciencias de la Computación . Saltador. 1592 : 402–414. doi : 10.1007 / 3-540-48910-X . ISBN 978-3-540-65889-4. S2CID 29690672 .