problema de celosía

Problema de optimización en informática.

En informática , los problemas de celosía son una clase de problemas de optimización relacionados con objetos matemáticos llamados celosías . La intratabilidad conjeturada de tales problemas es central para la construcción de criptosistemas seguros basados ​​en celosías : los problemas de celosías son un ejemplo de problemas NP-difíciles que han demostrado ser difíciles en promedio , proporcionando un caso de prueba para la seguridad de los algoritmos criptográficos. Además, algunos problemas de red, que en el peor de los casos son difíciles, pueden utilizarse como base para esquemas criptográficos extremadamente seguros. El uso de la dureza del peor de los casos en tales esquemas los convierte en uno de los pocos esquemas que probablemente sean seguros incluso contra computadoras cuánticas . Para aplicaciones en tales criptosistemas , generalmente se consideran redes sobre espacios vectoriales (a menudo ) o módulos libres (a menudo ). ${\displaystyle \mathbb {Q} ^{n}}$ ${\displaystyle \mathbb {Z} ^{n}}$

Para todos los problemas siguientes, supongamos que se nos da (además de otras entradas más específicas) una base para el espacio vectorial V y una norma N. La norma habitualmente considerada es la norma euclidiana L 2 . Sin embargo, también se consideran otras normas (como L p ) y aparecen en una variedad de resultados. ^[1]

A lo largo de este artículo, denotemos la longitud del vector distinto de cero más corto en la red L : es decir, ${\displaystyle \lambda (L)}$

${\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}.}$

Problema del vector más corto (SVP)

Esta es una ilustración del problema del vector más corto (vectores base en azul, vector más corto en rojo).

En el SVP, se dan una base de un espacio vectorial V y una norma N (a menudo L 2 ) para una red L y se debe encontrar el vector distinto de ^cero más corto en V , medido por N , en L. En otras palabras, el algoritmo debería generar un vector v distinto de cero tal que . ${\displaystyle \|v\|_{N}=\lambda (L)}$

En la versión de aproximación γ SVP _γ , se debe encontrar un vector de red distinto de cero de longitud como máximo para dado . ${\displaystyle \gamma \cdot \lambda (L)}$ ${\displaystyle \gamma \geq 1}$

Resultados de dureza

Solo se sabe que la versión exacta del problema es NP-difícil para reducciones aleatorias. ^{[2] [3]} Por el contrario, se sabe que el problema correspondiente con respecto a la norma uniforme es NP-duro . ^[4]

Algoritmos para la norma euclidiana

Para resolver la versión exacta del SVP bajo la norma euclidiana, se conocen varios enfoques diferentes, que se pueden dividir en dos clases: algoritmos que requieren tiempo superexponencial ( ) y memoria, y algoritmos que requieren tiempo y espacio exponencial ( ) en la dimensión reticular. . La primera clase de algoritmos incluye más notablemente la enumeración reticular ^{[5] [6] [7]} y la reducción de muestreo aleatorio, ^{[8] [9]} mientras que la última incluye el tamizado reticular, ^{[10] [11] [12]} calculando la celda de Voronoi de la red, ^{[13] [14]} y muestreo gaussiano discreto. ^[15] Un problema abierto es si existen algoritmos para resolver SVP exacto que se ejecuten en un tiempo exponencial único ( ) y requieran un escalado de memoria polinomial en la dimensión de la red. ^[dieciséis] ${\displaystyle 2^{\omega (n)}}$ ${\displaystyle \operatorname {poly} (n)}$ ${\displaystyle 2^{\Theta (n)}}$ ${\displaystyle 2^{O(n)}}$

Para resolver la versión de aproximación γ SVP _γ para la norma euclidiana, los enfoques más conocidos se basan en el uso de reducción de base reticular . Para grandes , el algoritmo Lenstra-Lenstra-Lovász (LLL) puede encontrar una solución en un polinomio de tiempo en la dimensión de la red. Para valores más pequeños , se usa comúnmente el algoritmo Block Korkine-Zolotarev (BKZ) ^{[17] [18] [19]} , donde la entrada al algoritmo (el tamaño del bloque ) determina la complejidad del tiempo y la calidad de la salida: para factores de aproximación grandes , un Un tamaño de bloque pequeño es suficiente y el algoritmo termina rápidamente. Para pequeños , se necesitan más grandes para encontrar vectores reticulares suficientemente cortos, y el algoritmo tarda más en encontrar una solución. El algoritmo BKZ utiliza internamente un algoritmo SVP exacto como subrutina (que se ejecuta en redes de dimensión como máximo ), y su complejidad general está estrechamente relacionada con los costos de estas llamadas SVP en dimensión . ${\displaystyle \gamma >1}$ ${\displaystyle \gamma =2^{\Omega (n)}}$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$

GapSVP

El problema GapSVP _β consiste en distinguir entre las instancias de SVP en las que la longitud del vector más corto es como máximo o mayor que , donde puede ser una función fija de la dimensión de la red . Dada una base para la red, el algoritmo debe decidir si o . Al igual que otros problemas de promesas , el algoritmo puede cometer errores en todos los demás casos. ${\displaystyle 1}$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \lambda (L)\leq 1}$ ${\displaystyle \lambda (L)>\beta }$

Otra versión más del problema es GapSVP _ζ,γ para algunas funciones ζ y γ. La entrada al algoritmo es una base y un número . Se asegura que todos los vectores en la ortogonalización de Gram-Schmidt tienen una longitud de al menos 1, y que y que , donde es la dimensión. El algoritmo debe aceptar if y rechazar if . Para grandes (es decir , ), el problema es equivalente a GapSVP _γ porque ^[20] un preprocesamiento realizado utilizando el algoritmo LLL hace que la segunda condición (y por lo tanto, ) sea redundante. ${\displaystyle B}$ ${\displaystyle d}$ ${\displaystyle \lambda (L(B))\leq \zeta (n)}$ ${\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}$ ${\displaystyle n}$ ${\displaystyle \lambda (L(B))\leq d}$ ${\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}$ ${\displaystyle \zeta }$ ${\displaystyle \zeta (n)>2^{n/2}}$ ${\displaystyle \zeta }$

Problema del vector más cercano (CVP)

Esta es una ilustración del problema del vector más cercano (vectores base en azul, vector externo en verde, vector más cercano en rojo).

En CVP, se dan una base de un espacio vectorial V y una métrica M (a menudo L 2 ) para una red L , así como un vector v en V pero no necesariamente en L . Se desea encontrar el vector en L más cercano a v (medido por M ). En la versión de aproximación CVP _γ , se debe encontrar un vector reticular a una distancia máxima . ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Relación con vicepresidente senior

El problema del vector más cercano es una generalización del problema del vector más corto. Es fácil demostrar que dado un oráculo para CVP _γ (definido a continuación), se puede resolver SVP _γ haciendo algunas consultas al oráculo. ^[21] El método ingenuo para encontrar el vector más corto llamando al oráculo CVP _γ para encontrar el vector más cercano a 0 no funciona porque 0 es en sí mismo un vector de red y el algoritmo podría potencialmente generar 0.

La reducción de SVP _γ a CVP _γ es la siguiente: Supongamos que la entrada a SVP _γ es la base de la red . Considere la base y sea el vector devuelto por CVP _γ ( B ⁱ , b _i ) . La afirmación es que el vector más corto del conjunto es el vector más corto de la red dada. ${\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}$ ${\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}$ ${\displaystyle x_{i}}$ ${\displaystyle \{x_{i}-b_{i}\}}$

Resultados de dureza

Goldreich et al. demostró que cualquier dureza de SVP implica la misma dureza para CVP. ^[22] Utilizando herramientas PCP , Arora et al. demostró que el CVP es difícil de aproximar dentro del factor a menos que . ^[23] Dinur et al. fortaleció esto dando un resultado de dureza NP con for . ^[24] ${\displaystyle 2^{\log ^{1-\epsilon }(n)}}$ ${\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}$ ${\displaystyle \epsilon =(\log \log n)^{c}}$ ${\displaystyle c<1/2}$

Decodificación de esferas

Los algoritmos para CVP, especialmente la variante de Fincke y Pohst, ^[6] se han utilizado para la detección de datos en sistemas de comunicación inalámbrica de múltiples entradas y múltiples salidas ( MIMO ) (para señales codificadas y no codificadas). ^{[25] [13]} En este contexto se llama decodificación de esfera debido al radio utilizado interno en muchas soluciones CVP. ^[26]

Se ha aplicado en el campo de la resolución de ambigüedad de números enteros del GNSS en fase portadora (GPS). ^[27] Se llama método LAMBDA en ese campo. En el mismo campo, el problema general de CVP se denomina Mínimos cuadrados enteros .

GapCVP

Este problema es similar al problema de GapSVP. Para GapSVP _β , la entrada consta de una base reticular y un vector , y el algoritmo debe responder si se cumple alguna de las siguientes condiciones: ${\displaystyle v}$

• existe un vector reticular tal que la distancia entre él y es como máximo 1, y ${\displaystyle v}$
• cada vector de red está a una distancia mayor que la de . ${\displaystyle \beta }$ ${\displaystyle v}$

La condición opuesta es que el vector reticular más cercano esté a una distancia , de ahí el nombre Gap CVP. ${\displaystyle 1<\lambda (L)\leq \beta }$

Resultados conocidos

El problema está trivialmente contenido en NP para cualquier factor de aproximación.

Schnorr , en 1987, demostró que los algoritmos deterministas de tiempo polinomial pueden resolver el problema . ^[28] Ajtai et al. demostró que los algoritmos probabilísticos pueden lograr un factor de aproximación ligeramente mejor de . ^[10] ${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}$ ${\displaystyle \beta =2^{O(n\log \log n/\log n)}}$

En 1993, Banaszczyk demostró que GapCVP _n está en . ^[29] En 2000, Goldreich y Goldwasser demostraron que el problema se sitúa tanto en NP como en coAM . ^[30] En 2005, Aharonov y Regev demostraron que para algunas constantes , el problema está en . ^[31] ${\displaystyle {\mathsf {NP\cap coNP}}}$ ${\displaystyle \beta ={\sqrt {n/\log n}}}$ ${\displaystyle c}$ ${\displaystyle \beta =c{\sqrt {n}}}$ ${\displaystyle {\mathsf {NP\cap coNP}}}$

Para límites inferiores, Dinur et al. demostró en 1998 que el problema es NP-difícil para . ^[32] ${\displaystyle \beta =n^{o(1/\log {\log {n}})}}$

Problema de vectores independientes más cortos (SIVP)

Dada una red L de dimensión n , el algoritmo debe generar n linealmente independiente de modo que , donde el lado derecho considera todas las bases de la red. ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ ${\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}$ ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$

En la versión aproximada, dada una red L con dimensión n , se deben encontrar n vectores de longitud linealmente independientes , donde es el ^enésimo mínimo sucesivo de . ${\displaystyle \gamma }$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ ${\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}$ ${\displaystyle \lambda _{n}(L)}$ ${\displaystyle n}$ ${\displaystyle L}$

Decodificación de distancia limitada

Este problema es similar al CVP. Dado un vector tal que su distancia desde la red sea como máximo , el algoritmo debe generar el vector de red más cercano a él. ${\displaystyle \lambda (L)/2}$

Problema de radio de cobertura

Dada una base para la red, el algoritmo debe encontrar la distancia más grande (o en algunas versiones, su aproximación) desde cualquier vector a la red.

problema de base más corta

Muchos problemas se vuelven más fáciles si la base de entrada consta de vectores cortos. Un algoritmo que resuelve el problema de la base más corta (SBP) debe, dada una base reticular , generar una base equivalente tal que la longitud del vector más largo sea lo más corta posible. ${\displaystyle B}$ ${\displaystyle B'}$ ${\displaystyle B'}$

La versión de aproximación del problema SBP _γ consiste en encontrar una base cuyo vector más largo sea, en la mayoría de los casos, más largo que el vector más largo en la base más corta. ${\displaystyle \gamma }$

Uso en criptografía

La dureza promedio de los problemas constituye la base de las pruebas de seguridad para la mayoría de los esquemas criptográficos. Sin embargo, la evidencia experimental sugiere que la mayoría de los problemas NP-difíciles carecen de esta propiedad: probablemente sólo sean difíciles en el peor de los casos. Se ha conjeturado o se ha demostrado que muchos problemas de red son difíciles en promedio, lo que los convierte en una clase atractiva de problemas en los que basar esquemas criptográficos. Además, se ha utilizado la dureza del peor de los casos de algunos problemas de red para crear esquemas criptográficos seguros. El uso de la dureza del peor de los casos en tales esquemas los convierte en uno de los pocos esquemas que probablemente sean seguros incluso contra computadoras cuánticas .

Los problemas de red anteriores son fáciles de resolver si el algoritmo cuenta con una "buena" base. Los algoritmos de reducción de celosías tienen como objetivo, dada una base para una celosía, generar una nueva base que consta de vectores relativamente cortos y casi ortogonales . El algoritmo de reducción de la base reticular (LLL) de Lenstra-Lenstra-Lovász fue uno de los primeros algoritmos eficientes para este problema que podía generar una base reticular casi reducida en tiempo polinomial. ^[33] Este algoritmo y sus mejoras posteriores se utilizaron para romper varios esquemas criptográficos, estableciendo su estatus como una herramienta muy importante en el criptoanálisis. El éxito de LLL con datos experimentales llevó a la creencia de que la reducción de la red podría ser un problema fácil en la práctica; sin embargo, esta creencia fue cuestionada a finales de la década de 1990, cuando se obtuvieron varios resultados nuevos sobre la dureza de problemas reticulares, comenzando con el resultado de Ajtai . ^[2]

En sus artículos fundamentales, Ajtai demostró que el problema SVP era NP-difícil y descubrió algunas conexiones entre la complejidad del peor de los casos y la complejidad del caso promedio de algunos problemas de red. ^{[2] [3]} Sobre la base de estos resultados, Ajtai y Dwork crearon un criptosistema de clave pública cuya seguridad podría demostrarse utilizando sólo la dureza del peor de los casos de una determinada versión de SVP, ^[34] convirtiéndose así en el primer resultado que ha utilizado dureza del peor de los casos para crear sistemas seguros. ^[35]

Ver también

• Aprendiendo con errores
• Problema de solución de entero corto

Referencias

1. Khot, Subhash (2005). "Dureza de aproximación del problema del vector más corto en celosías". J. ACM . 52 (5): 789–808. doi :10.1145/1089023.1089027. S2CID  13438130.
2. Ajtai, M. (1996). "Generando casos difíciles de problemas de celosía". Actas del vigésimo octavo simposio anual de ACM sobre teoría de la informática . Filadelfia, Pensilvania, Estados Unidos: ACM. págs. 99-108. doi :10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID  6864824.
3. Ajtai, Miklós (1998). "El problema del vector más corto en L2 es NP-difícil para reducciones aleatorias". Actas del trigésimo simposio anual de ACM sobre teoría de la informática . Dallas, Texas, Estados Unidos: ACM. págs. 10-19. doi :10.1145/276698.276705. ISBN 978-0-89791-962-3. S2CID  4503998.
4. van Emde Boas, Peter (1981). "Otro problema NP-completo y la complejidad de calcular vectores cortos en una red". Informe Técnico 8104 . Universidad de Amsterdam, Departamento de Matemáticas, Países Bajos.
5. Kannan, Ravi (1983). "Algoritmos mejorados para programación entera y problemas de red relacionados". Actas del decimoquinto simposio anual de ACM sobre teoría de la informática - STOC '83 . Nueva York, NY, Estados Unidos: ACM. págs. 193-206. doi : 10.1145/800061.808749. ISBN 978-0-89791-099-6. S2CID  18181112.
6. Fincke, U.; Pohst, M. (1985). "Métodos mejorados para calcular vectores de longitud corta en una red, incluido un análisis de complejidad". Matemáticas. comp . 44 (170): 463–471. doi : 10.1090/S0025-5718-1985-0777278-8 .
7. Gama, Nicolás; Nguyen, Phong Q.; Regev, Oded (30 de mayo de 2010). "Enumeración en celosía mediante poda extrema". Avances en Criptología – EUROCRYPT 2010 . Apuntes de conferencias sobre informática. vol. 6110. Springer, Berlín, Heidelberg. págs. 257–278. doi :10.1007/978-3-642-13190-5_13. ISBN 978-3-642-13189-9. S2CID  1938519.
8. Schnorr, Claus Peter (27 de febrero de 2003). "Reducción de celosía mediante métodos de cumpleaños y muestreo aleatorio". Estadísticas 2003 . Apuntes de conferencias sobre informática. vol. 2607. Springer, Berlín, Heidelberg. págs. 145-156. CiteSeerX 10.1.1.137.4293 . doi :10.1007/3-540-36494-3_14. ISBN  978-3-540-36494-8.
9. Aono, Yoshinori; Nguyen, Phong Q. (30 de abril de 2017). "Muestreo aleatorio revisado: enumeración de celosía con poda discreta". Avances en criptología - EUROCRYPT 2017 (PDF) . Apuntes de conferencias sobre informática. vol. 10211. Springer, Cham. págs. 65-102. doi :10.1007/978-3-319-56614-6_3. ISBN 978-3-319-56613-9. S2CID  39082279.
10. Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "Un algoritmo de tamiz para el problema del vector reticular más corto". Actas del trigésimo tercer simposio anual de ACM sobre teoría de la informática . Hersonissos, Grecia: ACM. págs. 601–610. doi :10.1145/380752.380857. ISBN 1-58113-349-9. S2CID  14982298.
11. Micciancio, Daniele; Voulgaris, Panagiotis (2010). "Algoritmos de tiempo exponencial más rápidos para el problema del vector más corto". Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos . Refresco '10. Filadelfia, PA, EE.UU.: Sociedad de Matemáticas Industriales y Aplicadas. págs. 1468-1480. doi : 10.1137/1.9781611973075.119 . ISBN 978-0-89871-698-6. S2CID  90084.
12. Becker, A.; Ducas, L.; Gama, N.; Laarhoven, T. (21 de diciembre de 2015). "Nuevas direcciones en la búsqueda de vecinos más cercanos con aplicaciones al tamizado en celosía". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos. Sociedad de Matemática Industrial y Aplicada. págs. 10-24. doi :10.1137/1.9781611974331.ch2. ISBN 978-1-61197-433-1.
13. Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Búsqueda de puntos más cercanos en celosías" (PDF) . Traducción IEEE. inf. Teoría . 48 (8): 2201–2214. doi :10.1109/TIT.2002.800499.
14. Micciancio, Daniele; Voulgaris, Panagiotis (2010). "Un algoritmo determinista de tiempo exponencial único para la mayoría de los problemas de red basado en cálculos de celdas de Voronoi". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la informática . ESTOC '10. Nueva York, NY, Estados Unidos: ACM. págs. 351–358. CiteSeerX 10.1.1.705.3304 . doi :10.1145/1806689.1806739. ISBN  978-1-4503-0050-6. S2CID  2449948.
15. Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). "Resolver el problema del vector más corto en 2 ⁿ tiempo utilizando muestreo gaussiano discreto". Actas del cuadragésimo séptimo simposio anual de ACM sobre Teoría de la Computación. STOC '15. Nueva York, NY, Estados Unidos: ACM. págs. 733–742. doi :10.1145/2746539.2746606. ISBN 978-1-4503-3536-2. S2CID  10214330.
16. Micciancio, Daniele (1 de julio de 2017). "Criptografía de celosía: problema del vector más corto".
17. Schnorr, CP (1 de enero de 1987). "Una jerarquía de algoritmos de reducción de base de red de tiempo polinomial". Informática Teórica . 53 (2): 201–224. doi : 10.1016/0304-3975(87)90064-8 .
18. Schnorr, CP; Euchner, M. (1 de agosto de 1994). "Reducción de la base de celosía: algoritmos prácticos mejorados y resolución de problemas de suma de subconjuntos" (PDF) . Programación Matemática . 66 (1–3): 181–199. doi :10.1007/bf01581144. ISSN  0025-5610. S2CID  15386054.
19. Chen, Yuanmi; Nguyen, Phong Q. (4 de diciembre de 2011). "BKZ 2.0: mejores estimaciones de seguridad de celosía". Avances en Criptología – ASIACRYPT 2011 . Apuntes de conferencias sobre informática. vol. 7073. Springer, Berlín, Heidelberg. págs. 1–20. doi :10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
20. Peikert, Chris (2009). "Criptosistemas de clave pública del problema del vector más corto en el peor de los casos: resumen ampliado". Actas del 41º simposio anual de ACM sobre Teoría de la Computación. Bethesda, MD, Estados Unidos: ACM. págs. 333–342. doi :10.1145/1536414.1536461. ISBN 978-1-60558-506-2. S2CID  1864880.
21. Micciancio, Daniele; Goldwasser, Shafi (2002). Complejidad de los problemas de celosía . Saltador.
22. Goldreich, O.; et al. (1999). "Aproximar los vectores reticulares más cortos no es más difícil que aproximar los vectores reticulares más cercanos". inf. Proceso. Lett . 71 (2): 55–61. doi :10.1016/S0020-0190(99)00083-6.
23. Arora, Sanjeev; et al. (1993). "Actas de la 34ª edición anual de Fundamentos de Ciencias de la Computación del IEEE de 1993". J. Computación. Sistema. Ciencia . vol. 54, págs. 317–331. doi :10.1109/SFCS.1993.366815. ISBN 978-0-8186-4370-5. S2CID  44988406.
24. Dinur, yo; et al. (2003). "Aproximar el CVP a factores casi polinomiales es NP-difícil". Combinatoria . 23 (2): 205–243. doi :10.1007/s00493-003-0019-y. S2CID  45754954.
25. Biglieri, E.; Calderbank, R.; Constantinides, Anthony G .; Orfebre, A.; Paulraj, A.; Pobre, HV (2007). Comunicaciones inalámbricas MIMO . Cambridge: Cambridge UP
26. Wang, ping; Le-Ngoc, Tho (2011). "Un algoritmo de decodificación de esferas de lista con estrategias de configuración de radio mejoradas". Comunicaciones personales inalámbricas . 61 (1): 189-200. doi :10.1007/s11277-010-0018-4. S2CID  30919872.
27. Hassibi, A.; Boyd, S. (1998). "Estimación de parámetros enteros en modelos lineales con aplicaciones al GPS". Traducción IEEE. Sig. Proc . 46 (11): 2938–2952. Código Bib : 1998ITSP...46.2938H. CiteSeerX 10.1.1.114.7246 . doi : 10.1109/78.726808. 
28. Schnorr, CP "Factorizar números enteros y calcular logaritmos discretos mediante aproximación diofántica". Avances en criptología: actas de Eurocrypt '91 .
29. Banaszczyk, W. (1993). "Nuevos límites en algunos teoremas de transferencia en geometría de números". Matemáticas. Ana. 296 (1): 625–635. doi :10.1007/BF01445125. S2CID  13921988.
30. Goldreich, Oded; Goldwasser, Shafi (1998). "Sobre los límites de la no aproximabilidad de los problemas reticulares". Actas del trigésimo simposio anual de ACM sobre teoría de la informática . Dallas, Texas, Estados Unidos: ACM. págs. 1–9. doi :10.1145/276698.276704. ISBN 0-89791-962-9. S2CID  3051993.
31. Aharonov, Dorit; Oded Regev (2005). "Problemas de celosía en NP coNP". J. ACM . 52 (5): 749–765. CiteSeerX 10.1.1.205.3730 . doi :10.1145/1089023.1089025. S2CID  1669286. ${\displaystyle \cap }$ 
32. Dinur, yo; Kindler, G.; Safra, S. (1998). "Aproximar el CVP a factores casi polinomiales es NP-difícil". Actas del 39º Simposio Anual sobre Fundamentos de la Informática . Sociedad de Computación IEEE. pag. 99.ISBN​ 978-0-8186-9172-0.
33. Lenstra, Alaska; Lenstra, HW Jr.; Lovász, L. (1982). «Factorizar polinomios con coeficientes racionales» (PDF) . Matemáticas. Ana. 261 (4): 515–534. doi :10.1007/BF01457454. S2CID  5701340. Archivado desde el original (PDF) el 17 de julio de 2011.
34. Ajtai, Miklós; Dwork, Cynthia (1997). "Un criptosistema de clave pública con equivalencia en el peor de los casos/caso promedio". Actas del vigésimo noveno simposio anual de ACM sobre teoría de la informática . El Paso, Texas, Estados Unidos: ACM. págs. 284-293. doi :10.1145/258533.258604. ISBN 0-89791-888-6. S2CID  9918417.
35. Cai, Jin-Yi (2000). "La complejidad de algunos problemas de celosía". Teoría algorítmica de números . Apuntes de conferencias sobre informática. vol. 1838, págs. 1–32. doi :10.1007/10722028_1. ISBN 978-3-540-67695-9.

Otras lecturas

• Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Búsqueda de puntos más cercanos en celosías" (PDF) . Traducción IEEE. inf. Teoría . 48 (8): 2201–2214. doi :10.1109/TIT.2002.800499.
• Micciancio, Daniele (2001). "El problema del vector más corto es {NP} difícil de aproximar dentro de una constante". Revista SIAM de Computación . 30 (6): 2008-2035. CiteSeerX  10.1.1.93.6646 . doi :10.1137/S0097539700373039. S2CID  42794945.
• Nguyen, Phong Q.; Stern, Jacques (2000). "Reducción de celosía en criptología: una actualización". Actas del IV Simposio Internacional sobre Teoría Algorítmica de Números . Springer-Verlag. págs. 85-112. ISBN 978-3-540-67695-9.