¿Qué idiomas han sido criptográficamente exitosamente atrapados?

Una observación asociada con la criptografía asimétrica es que algunas funciones son (se cree que son) fáciles de realizar en una dirección pero difíciles de invertir. Además, si existe alguna información de 'trampa' que permite que la operación inversa se calcule rápidamente, entonces el problema se convierte en candidato para un esquema de criptografía de clave pública.

Los problemas clásicos de trampillas, hechos famosos por RSA, incluyen el problema de factorización y el problema de registro discreto. Casi al mismo tiempo que se publicó RSA, Rabin inventó un criptosistema de clave pública basado en la búsqueda de raíces cuadradas discretas (más tarde se demostró que era al menos tan difícil como factorizar).

Otros candidatos han surgido a lo largo de los años. KNAPSACK (poco después de RSA), los "Logaritmos" de curva elíptica con parámetros específicos y los problemas de base más corta de Lattice son ejemplos de problemas cuyos problemas de puerta trampa se utilizan en otros esquemas publicados. También es fácil ver que tales problemas deben residir en algún lugar de NP.

Esto agota mi conocimiento de las funciones de trampillas. También parece agotar la lista en Wikipedia también.

Espero que podamos obtener una lista wiki comunitaria de idiomas que admitan trampillas y literatura relevante. La lista te será útil. Las demandas cambiantes de la criptografía también cambian qué funciones de trampillas pueden ser la base de los criptosistemas. La explosión del almacenamiento en las computadoras hace posible esquemas con grandes tamaños de clave. El espectro que se avecina perpetuamente de la computación cuántica invalida los esquemas que pueden romperse con un oráculo para encontrar subgrupos abelianos ocultos. El criptosistema totalmente homomórfico de Gentry funciona solo porque hemos descubierto funciones de trampillas que respetan los homomorfismos.

Estoy especialmente interesado en problemas que no son NP-Complete.

Es importante distinguir entre las funciones de trampillas y el cifrado de clave pública. Si bien las funciones de trapdoor producen esquemas de cifrado de clave pública, algunos de los candidatos que mencionó solo implican cifrado de clave pública y no necesariamente le proporcionan funciones de trapdoor. De hecho, Gertner, Malkin y Reingold muestran que no existe una construcción de recuadro negro de una función trapdoor a partir de un "predicado trapdoor" (que puede considerarse como un esquema de cifrado de clave pública de un bit).

Ejemplos clásicos de funciones trapdoor son las funciones RSA y Rabin. Un ejemplo clásico de un predicado de trampilla es decidir el módulo de Residuosidad cuadrática como compuesto, debido a Goldwasser y Micali. Las construcciones basadas en registros discretos y enrejados que usted menciona producen cifrado de clave pública directamente, sin pasar por las funciones de trampilla.

A continuación se muestra una lista (no exhaustiva) de construcciones de esquemas de cifrado de clave pública, la mayoría de los cuales no se sabe que pasan por funciones de trampillas.

• El criptosistema de clave pública El Gamal (incluidas las variantes de curva elíptica). La seguridad se basa en la suposición Decisional Diffie Hellman. No pasa por las funciones de trampilla (pero vea el artículo de Peikert-Waters a continuación para ver una función de trampilla cuya seguridad se basa en la seguridad semántica de El Gamal).

  [Taher El Gamal: un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. La seguridad se basa en un SVP único en redes. No se sabe que implica funciones de trampillas.

  [Miklós Ajtai, Cynthia Dwork: un criptosistema de clave pública con equivalencia de peor caso / caso promedio. STOC 1997: 284-293]

  [Oded Regev: Nuevas construcciones criptográficas basadas en redes. STOC 2003: 407-416]

• Regev, Peikert. La seguridad se basa en la dureza del aprendizaje con errores (esto incluye una reducción de SVP). No se sabe que implica funciones de trampillas.

  [Oded Regev: en redes, aprendizaje con errores, códigos lineales aleatorios y criptografía. STOC 2005: 84-93]

  [Chris Peikert: criptosistemas de clave pública del peor problema de vector más corto: resumen extendido. STOC 2009: 333-342]

• Peikert, Waters. La seguridad se basa en Diffie Hellman decisivo y en problemas de red. Se sabe que implica funciones de trampillas (a través de funciones de trampillas con pérdida).

  [Chris Peikert, Brent Waters: funciones de puerta trampa con pérdida y sus aplicaciones. STOC 2008: 187-196]

• Lyubashevsky, Palacio, Segev. La seguridad se basa en Subset-Sum. No se sabe que implica funciones de trampillas.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: primitivas criptográficas de clave pública demostrablemente tan seguras como la suma de subconjuntos. TCC 2010: 382-400]

• Stehlé, Steinfeld, Tanaka, Xagawa y Lyubashevsky, Peikert, Regev. La seguridad se basa en la dureza del anillo LWE. La ventaja de estos sobre las propuestas anteriores es su tamaño de clave más pequeño. No se sabe que implica funciones de trampillas.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Cifrado de clave pública eficiente basado en redes ideales. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: sobre redes ideales y aprendizaje con errores sobre anillos. EUROCRYPT 2010: 1-23]