Problema de celosía

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 fundamental para la construcción de criptosistemas seguros basados ​​en celosía: los problemas de celosía son un ejemplo de problemas NP-hard que se ha demostrado que son de caso medio difícil, proporcionando un caso de prueba para la seguridad de los algoritmos criptográficos. Además, algunos problemas de celosía que son difíciles en el peor de los casos se pueden utilizar 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 celosías sobre espacio vectorial (a menudo ) o módulos libres (a menudo ).${\displaystyle \mathbb {Q} ^{n}}$${\displaystyle \mathbb {Z} ^{n}}$

Para todos los problemas abajo, suponemos que se nos da (además de otros insumos más específicos) una base para el espacio vectorial V y una norma N . La norma generalmente considerada es la norma euclidiana L ² . Sin embargo, otras normas (como L ^p ) también se consideran y aparecen en una variedad de resultados. ^[1] Let denotar la longitud del vector más corto no es cero en la red L , es decir,${\displaystyle \lambda (L)}$

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

Problema de vector más corto (SVP)

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

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

En la versión de aproximación _γ SVP _γ , se debe encontrar un vector reticular 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-hard para reducciones aleatorias. ^{[2] [3]}

Por el contrario, se sabe que el problema correspondiente con respecto a la norma uniforme es NP-hard . ^[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 de celosía. . La primera clase de algoritmos incluye más notablemente la enumeración de celosía ^{[5] [6] [7]} y la reducción de muestreo aleatorio, ^{[8] [9]} mientras que el último incluye el tamizado de celosía, ^{[10] [11] [12]} computando la celda de Voronoi de la celosía, ^{[13] [14]} y muestreo gaussiano discreto. ^[15]${\displaystyle 2^{\omega (n)}}$${\displaystyle \operatorname {poly} (n)}$${\displaystyle 2^{\Theta (n)}}$Un problema abierto es si existen algoritmos para resolver SVP exactos que se ejecutan en un tiempo exponencial único ( ) y requieren escalado de memoria polinomialmente en la dimensión de celosía. ^[dieciséis]${\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 la reducción de la base de celosía . Para grandes , el algoritmo Lenstra – Lenstra – Lovász (LLL) puede encontrar una solución en el polinomio de tiempo en la dimensión de celosía. 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 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 , grandes${\displaystyle \gamma >1}$${\displaystyle \gamma =2^{\Omega (n)}}$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$son necesarios para encontrar vectores de celosía 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 celosías de dimensión como máximo ), y su complejidad general está estrechamente relacionada con los costos de estas llamadas SVP en dimensión .${\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 celosía, el algoritmo debe decidir si o . Al igual que otros problemas de promesa , el algoritmo puede errar 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 . La entrada al algoritmo es una base y un número . Se asegura que todos los vectores en la ortogonalización de Gram-Schmidt son de longitud al menos 1, y eso y aquello donde está la dimensión. El algoritmo debe aceptar si y rechazar si . Para large ( ), el problema es equivalente a GapSVP _γ porque ^[20] un preprocesamiento realizado usando el algoritmo LLL hace que la segunda condición (y por lo tanto ) sea redundante.${\displaystyle \zeta ,\gamma }$${\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).d}$${\displaystyle \zeta }$${\displaystyle \zeta (n)>2^{n/2}}$${\displaystyle \zeta }$

Problema de vector más cercano (CVP)

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

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

Relación con SVP

El problema de vector más cercano es una generalización del problema de vector más corto. Es fácil demostrar que dado un oráculo para CVP _γ (definido a continuación), uno 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 reticular y el algoritmo podría generar potencialmente 0.

La reducción de SVP _γ a CVP _γ es la siguiente: Suponga que la entrada al problema de 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 y col. mostró que cualquier dureza de SVP implica la misma dureza de CVP. ^[22] Utilizando herramientas de PCP , Arora et al. mostró que CVP es difícil aproximarse dentro de factor de menos . ^[23] Dinur y col. reforzó 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

Se han utilizado algoritmos para CVP, especialmente la variante Fincke y Pohst, ^[6] 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 denomina decodificación de esferas debido al radio utilizado en el interior de muchas soluciones CVP. ^[26]

Se ha aplicado en el campo de la resolución de ambigüedad de 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 conoce como mínimos cuadrados enteros .

GapCVP

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

• hay un vector de celosía tal que la distancia entre él y es como máximo 1.${\displaystyle v}$
• cada vector de celosía está a una distancia mayor que lejos de .${\displaystyle \beta }$${\displaystyle v}$

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

Resultados conocidos

El problema está contenido trivialmente 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 y col. mostró 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 plantea el problema tanto en NP como en coAM . ^[30] En 2005, Aharonov y Regev demostraron que, para algunas constantes , el problema con 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 de resolver . ^[32]${\displaystyle \beta =n^{o(1/\log {\log {n}})}}$

Problema de los vectores independientes más cortos (SIVP)

Dada una celosía L de dimensión n , el algoritmo debe generar n linealmente independientes de modo que donde el lado derecho considere todas las bases de la celosía.${\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 celosía L con dimensión n , encuentre n vectores de longitud linealmente independientes , donde es el 'é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 es 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 celosía, el algoritmo debe encontrar la mayor distancia (o en algunas versiones, su aproximación) desde cualquier vector a la celosía.

Problema de base más corta

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

La versión aproximada 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

Artículo principal: criptografía basada en celosía

La dureza promedio de los casos de los problemas forma una base para 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-hard carecen de esta propiedad: probablemente solo sean difíciles en el peor de los casos. Se han conjeturado o probado muchos problemas de celosía, lo que los convierte en una clase atractiva de problemas en los que basar esquemas criptográficos. Además, la dureza del peor de los casos de algunos problemas de celosía se ha utilizado 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 celosía anteriores son fáciles de resolver si el algoritmo se proporciona con una "buena" base. Los algoritmos de reducción de celosía tienen como objetivo, dada una base para una celosía, generar una nueva base que consiste en vectores relativamente cortos, casi ortogonales . El algoritmo de reducción de la base de celosía (LLL) de Lenstra-Lenstra-Lovász fue un algoritmo eficiente temprano para este problema que podría generar una base de celosía casi reducida en tiempo polinomial. ^[33]Este algoritmo y sus refinamientos 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 en datos experimentales llevó a la creencia de que la reducción de celosía podría ser un problema fácil en la práctica. Sin embargo, esta creencia fue desafiada cuando, a fines de la década de 1990, se obtuvieron varios resultados nuevos sobre la dureza de los problemas de celosía, comenzando con el resultado de Ajtai . ^[2]

En sus artículos seminales, Ajtai mostró que el problema de SVP era NP-hard y descubrió algunas conexiones entre la complejidad del peor de los casos y la complejidad del caso promedio de algunos problemas de celosía. ^{[2] [3]} Basándose en estos resultados, Ajtai y Dwork crearon un criptosistema de clave pública cuya seguridad podría demostrarse utilizando solo la dureza del peor de los casos de una determinada versión de SVP, ^[34] convirtiéndolo en el primer resultado que se ha utilizado dureza en el 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 aproximar el problema de 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 instancias duras de problemas de celosía" . Actas del vigésimo octavo simposio anual de ACM sobre teoría de la computación . Filadelfia, Pensilvania, Estados Unidos: ACM. págs. 99–108.
3. Ajtai, Miklós (1998). "El problema de vector más corto en L 2 es NP -difícil para reducciones aleatorias" . Actas del trigésimo simposio anual de ACM sobre teoría de la computación . Dallas, Texas, Estados Unidos: ACM. págs. 10-19.
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 la programación de enteros y problemas de celosía relacionados". Actas del decimoquinto simposio anual de ACM sobre teoría de la computación - STOC '83 . Actas del Decimoquinto Simposio Anual ACM sobre Teoría de la Computación . STOC '83. Nueva York, NY, EE.UU .: ACM. págs. 193-206. doi : 10.1145 / 800061.808749 . ISBN 978-0897910996. S2CID  18181112 .
6. Fincke, U .; Pohst, M. (1985). "Métodos mejorados para calcular vectores de longitud corta en una celosía, 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 de celosía mediante poda extrema . Avances en Criptología - EUROCRYPT 2010 . Apuntes de conferencias en Ciencias de la Computación. 6110 . Springer, Berlín, Heidelberg. págs. 257–278. doi : 10.1007 / 978-3-642-13190-5_13 . ISBN 978-3-642-13189-9.
8. Schnorr, Claus Peter (27 de febrero de 2003). "Reducción de celosía por métodos de muestreo aleatorio y cumpleaños". Stacs 2003 . Apuntes de conferencias en Ciencias de la Computación. 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-3540364948.
9. Aono, Yoshinori; Nguyen, Phong Q. (30 de abril de 2017). Muestreo aleatorio revisado: enumeración de celosía con poda discreta (PDF) . Avances en Criptología - EUROCRYPT 2017 . Apuntes de conferencias en Ciencias de la Computación. 10211 . Springer, Cham. págs. 65-102. doi : 10.1007 / 978-3-319-56614-6_3 . ISBN  978-3-319-56613-9.
10. Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "Un algoritmo de tamiz para el problema de vector de celosía más corto" . Actas del trigésimo tercer simposio anual ACM sobre teoría de la computación . Hersonissos, Grecia: ACM. págs. 601–610.
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 . SODA '10. Filadelfia, PA, EE.UU .: Sociedad de Matemáticas Industriales y Aplicadas. págs. 1468-1480. doi : 10.1137 / 1.9781611973075.119 . ISBN 9780898716986. 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 para tamizado en celosía". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos . Actas. Sociedad de Matemáticas Industriales y Aplicadas. 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 del punto más cercano en celosías" . IEEE Trans. Inf. Teoría . 48 (8): 2201–2214. doi : 10.1109 / TIT.2002.800499 .
14. Micciancio, Daniele; Voulgaris, Panagiotis (2010). Un algoritmo de tiempo exponencial único determinista para la mayoría de los problemas de celosía basado en cálculos de células de Voronoi . Actas del cuadragésimo segundo simposio ACM sobre teoría de la computación . STOC '10. Nueva York, NY, EE.UU .: ACM. págs. 351–358. CiteSeerX 10.1.1.705.3304 . doi : 10.1145 / 1806689.1806739 . ISBN  9781450300506. S2CID  2449948 .
15. Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). Resolver el problema de vector más corto en tiempo 2N usando muestreo gaussiano discreto: Resumen extendido . Actas del 47º Simposio Anual ACM sobre Teoría de la Computación . STOC '15. Nueva York, NY, EE.UU .: ACM. págs. 733–742. doi : 10.1145 / 2746539.2746606 . ISBN 9781450335362. S2CID  10214330 .
16. Micciancio, Daniele (1 de julio de 2017). "Criptografía de celosía - Problema de vector más corto" .
17. Schnorr, CP (1 de enero de 1987). "Una jerarquía de algoritmos de reducción de base de celosía 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 en Ciencias de la Computación. 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 del peor de los casos: resumen extendido" . Actas del 41º simposio anual de ACM sobre teoría de la computación . Bethesda, MD, Estados Unidos: ACM. págs. 333–342.
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. (1997). "La dureza de óptimos aproximados en celosías, códigos y sistemas de ecuaciones lineales". Actas de 1993 IEEE 34th Annual Foundations of Computer Science . J. Comput. Syst. Sci . 54 . págs. 317–331. doi : 10.1109 / SFCS.1993.366815 . ISBN 978-0-8186-4370-5. S2CID  44988406 .
24. Dinur, I .; et al. (2003). "Aproximación de CVP dentro de los factores casi polinomiales es NP-Hard". Combinatorica . 23 (2): 205–243. doi : 10.1007 / s00493-003-0019-y . S2CID 45754954 . 
25. Biglieri, E .; Calderbank, R .; Constantinides, Anthony G .; Goldsmith, 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 ajuste 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 a GPS". IEEE Trans. Sig. Proc . 46 (11): 2938–2952. Código Bibliográfico : 1998ITSP ... 46.2938H . CiteSeerX 10.1.1.114.7246 . doi : 10.1109 / 78.726808 . 
28. Schnorr, CP "Factorizar 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 la geometría de los 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 de celosía" . Actas del trigésimo simposio anual de ACM sobre teoría de la computación . Dallas, Texas, Estados Unidos: ACM. págs. 1–9.
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, I .; Kindler, G .; Safra, S. (1998). "Aproximación de CVP dentro de los factores casi polinomiales es NP-Hard" . Actas del 39º Simposio Anual sobre Fundamentos de las Ciencias de la Computación . Sociedad de Informática IEEE. pag. 99. ISBN 978-0-8186-9172-0.
33. Lenstra, AK; 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 la equivalencia del peor caso / caso medio" . Actas del vigésimo noveno simposio anual de ACM sobre teoría de la computación . El Paso, Texas, Estados Unidos: ACM. págs. 284-293.
35. Cai, Jin-Yi (2000). "La complejidad de algunos problemas de celosía". Teoría algorítmica de números . Apuntes de conferencias en Ciencias de la Computación. 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 del punto más cercano en celosías" . IEEE Trans. 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 alguna constante" . Revista SIAM de Computación . 30 (6): 2008-2035. CiteSeerX  10.1.1.93.6646 . doi : 10.1137 / S0097539700373039 .
• Nguyen, Phong Q .; Stern, Jacques (2000). "Reducción de celosía en criptología: una actualización" . Actas del IV Simposio Internacional de Teoría Algorítmica de Números . Springer-Verlag. págs. 85–112. ISBN 978-3-540-67695-9.