Funciones unidireccionales con complejidad de inversión polinómica

8

¿Existe una función similar a una trampilla cuya complejidad de codificación es el tiempo polinomial nk1 y la complejidad inversora (sin clave secreta) también es una función polinómica en la longitud de entrada con (digamos que y es incondicionalmente demostrable estar limitado por ) ¿Cuáles son las implicaciones de tales funciones si ? k 1 < < k 2 k 1 = 2 k 2 1000 V N P = V Pnortek2k1<<k2k1=2k21000VnortePAGS=VPAGS

vs
fuente

Respuestas:

8

F(X)=sol22Xmodificaciónnorte

N es un producto de dos números primos grandes. Sin conocer la factorización de N, lo mejor que se conoce es la cuadratura repetida, un cálculo muy secuencial en la naturaleza.

Si , la factorización se puede realizar de manera eficiente y, por lo tanto, no tenemos que recurrir a la cuadratura repetida. Sin embargo, realizar la factorización para alguien que no conoce los factores de N incurre en una sobrecarga polinómica.VnortePAGS=VPAGS

También puede interesarle el concepto de funciones unidireccionales débiles , aunque no están exactamente relacionadas con la pregunta.

Ver también las siguientes referencias:

  1. Precios a través de Procesamiento -o-- Combatiendo el correo basura de Dwork y Naor.
  2. Funciones moderadamente difíciles: desde la complejidad hasta la lucha contra el spam por Naor.
  3. Conocimiento cero simultáneo: reducción de la necesidad de restricciones de tiempo por Dwork y Sahai.
  4. Compromisos cronometrados por Boneh y Naor.
MS Dousti
fuente
Gracias. ¿Se descomponen si ? VnortePAGS=VPAGS
vs
2
@vs: Lo siento, olvidé mencionar eso. Ver la respuesta editada.
MS Dousti