Hispanopedia Wiki
Articulo de referencia

Problema de retículo

En informática , los problemas de retículos son una clase de problemas de optimización relacionados con objetos matemáticos llamados retículos . La intratabilidad conjeturada de...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , los problemas de retículos son una clase de problemas de optimización relacionados con objetos matemáticos llamados retículos . La intratabilidad conjeturada de tales problemas es fundamental para la construcción de criptosistemas seguros basados ​​en retículos : los problemas de retículos son un ejemplo de problemas NP-difíciles que se ha demostrado que son difíciles en el caso promedio , proporcionando un caso de prueba para la seguridad de los algoritmos criptográficos. Además, algunos problemas de retículos que son difíciles en el peor caso pueden usarse como base para esquemas criptográficos extremadamente seguros. El uso de la dificultad en el peor caso en tales esquemas los convierte en uno de los pocos esquemas que son muy probablemente seguros incluso contra computadoras cuánticas . Para aplicaciones en tales criptosistemas , los retículos sobre espacios vectoriales (a menudoQnorte{\displaystyle \mathbb {Q} ^{n}}) o módulos gratuitos (a menudoZnorte{\displaystyle \mathbb {Z} ^{n}}) se consideran generalmente.

Para todos los problemas que se presentan a continuación, supongamos que se nos proporciona (además de otros datos de entrada más específicos) una base para el espacio vectorial V y una norma N. La norma que se suele considerar es la norma euclidiana L² . Sin embargo, también se consideran otras normas (como Lp ) y aparecen en diversos resultados. [ 1 ]

A lo largo de este artículo, permítanosλ(L){\displaystyle \lambda (L)}denotamos la longitud del vector no nulo más corto en la red L : es decir,

λ(L)=minv∈L∖{0}‖v‖norte.{\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 da una base de un espacio vectorial V y una norma N (a menudo L² ) para una red L , y se debe encontrar el vector no nulo más corto en V , medido por N , en L. En otras palabras, el algoritmo debe generar un vector no nulo v tal que‖v‖norte=λ(L){\displaystyle \|v\|_{N}=\lambda (L)}⁠ . A continuación, el tamañodel problema se especifica mediante n , la dimensión del espacio vectorial V.

En la versión de aproximación γ SVP γ , se debe encontrar un vector de red no nulo de longitud como máximoγ⋅λ(L){\displaystyle \gamma \cdot \lambda (L)}para dadoγ≥1{\displaystyle \gamma \geq 1}.​

Resultados de dureza

Se sabe que la versión exacta del problema es NP-difícil únicamente para reducciones aleatorias. [ 2 ] [ 3 ] Por el contrario, se sabe que el problema correspondiente con respecto a la norma uniforme es NP-difícil . [ 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 (2ω(norte){\displaystyle 2^{\omega (n)}}) yescuela politécnica⁡(norte){\displaystyle \operatorname {poly} (n)}memoria y algoritmos que requieren tanto tiempo como espacio exponenciales (2Θ(norte){\displaystyle 2^{\Theta (n)}}) en la dimensión de la red. La primera clase de algoritmos incluye notablemente la enumeración de la red [ 5 ] [ 6 ] [ 7 ] y la reducción de muestreo aleatorio, [ 8 ] [ 9 ] mientras que la segunda incluye el tamizado de la red, [ 10 ] [ 11 ] [ 12 ] el cálculo de la celda de Voronoi de la red, [ 13 ] [ 14 ] y el muestreo gaussiano discreto. [ 15 ] Un problema abierto es si existen algoritmos para resolver SVP exactos que se ejecuten en tiempo exponencial simple (2O(norte){\displaystyle 2^{O(n)}}) y que requiere escalado de memoria polinomial en la dimensión de la red. [ 16 ]

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

Vicepresidente sénior de Gap

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

Otra versión del problema es GapSVP ζ,γ para algunas funciones ζ y γ. La entrada al algoritmo es una base.B{\displaystyle B}y un númerod{\displaystyle d}. Se asegura que todos los vectores en la ortogonalización de Gram-Schmidt tienen una longitud de al menos 1, y queλ(L(B))≤ζ(norte){\displaystyle \lambda (L(B))\leq \zeta (n)}y eso1≤d≤ζ(norte)/γ(norte){\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}, dondenorte{\displaystyle n}es la dimensión. El algoritmo debe aceptar si ⁠λ(L(B))≤d{\displaystyle \lambda (L(B))\leq d}, y rechazar siλ(L(B))≥γ(norte)⋅d{\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}⁠ . Para grandesζ{\displaystyle \zeta }(es decirζ(norte)>2norte/2{\displaystyle \zeta (n)>2^{n/2}}⁠ ), 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, ⁠ζ{\displaystyle \zeta }) redundante.

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 proporciona una base de un espacio vectorial V y una métrica M (a menudo L² ) 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 elγ{\displaystyle \gamma }-versión de aproximación CVP γ , se debe encontrar un vector de red a una distancia como máximoγ{\displaystyle \gamma }.

Relación con el vicepresidente sénior

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 más adelante), se puede resolver SVP γ realizando 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 potencialmente arrojar  0.

La reducción de SVP γ a CVP γ es la siguiente: Supongamos que la entrada a SVP γ es la base para la redB=[b1,b2,…,bnorte]{\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}Consideremos la base.Bi=[b1,…,2bi,…,bnorte]{\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}y dejarincógnitai{\displaystyle x_{i}}sea ​​el vector devuelto por CVP γ ( B i , b i ) . La afirmación es que el vector más corto en el conjunto{incógnitai−bi}{\displaystyle \{x_{i}-b_{i}\}}es el vector más corto en la red dada.

Resultados de dureza

Goldreich et al. demostraron que cualquier dureza de SVP implica la misma dureza para CVP. [ 22 ] Utilizando herramientas PCP , Arora et al. demostraron que CVP es difícil de aproximar dentro de un factor2registro1−ϵ⁡(norte){\displaystyle 2^{\log ^{1-\epsilon }(n)}}a menos quenotario público⊆DTIME⁡(2escuela politécnica⁡(registro⁡norte)){\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}. [ 23 ] Dinur et al. reforzaron esto al dar un resultado de dureza NP conϵ=(registro⁡registro⁡norte)do{\displaystyle \epsilon =(\log \log n)^{c}}parado<1/2{\displaystyle c<1/2}. [ 24 ]

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 entrada múltiple y salida múltiple ( MIMO ) (para señales codificadas y no codificadas). [ 25 ] [ 13 ] En este contexto se denomina decodificación esférica debido al radio utilizado internamente en muchas soluciones CVP. [ 26 ]

Resolución de ambigüedad entera de GNSS de fase portadora

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

GapCVP

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

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

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

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 paraβ=2O(norte(registro⁡registro⁡norte)2/registro⁡norte){\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}. [ 28 ] Ajtai et al. demostraron que los algoritmos probabilísticos pueden lograr un factor de aproximación ligeramente mejor deβ=2O(norteregistro⁡registro⁡norte/registro⁡norte){\displaystyle \beta =2^{O(n\log \log n/\log n)}}. [ 10 ]

En 1993, Banaszczyk demostró que GapCVP n está ennortePAG∩doonortePAG{\displaystyle {\mathsf {NP\cap coNP}}}. [ 29 ] En 2000, Goldreich y Goldwasser demostraron queβ=norte/registro⁡norte{\displaystyle \beta ={\sqrt {n/\log n}}}plantea el problema tanto en NP como en coAM . [ 30 ] En 2005, Aharonov y Regev demostraron que para alguna constantedo{\displaystyle c}, el problema conβ=donorte{\displaystyle \beta =c{\sqrt {n}}}está ennortePAG∩doonortePAG{\displaystyle {\mathsf {NP\cap coNP}}}. [ 31 ]

Para cotas inferiores, Dinur et al. demostraron en 1998 que el problema es NP-difícil paraβ=norteo(1/registro⁡registro⁡norte){\displaystyle \beta =n^{o(1/\log {\log {n}})}}. [ 32 ]

Problema de vectores independientes más cortos (SIVP)

Dado un retículo L de dimensión n , el algoritmo debe generar n linealmente independientes.v1,v2,…,vnorte{\displaystyle v_{1},v_{2},\ldots ,v_{n}}de modo quemáximo‖vi‖≤máximoB‖bi‖{\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}donde el lado derecho considera todas las basesB={b1,…,bnorte}{\displaystyle B=\{b_{1},\ldots ,b_{n}\}}de la red.

En elγ{\displaystyle \gamma }-Versión aproximada: dado un retículo L de dimensión n , se deben encontrar n vectores linealmente independientes.v1,v2,…,vnorte{\displaystyle v_{1},v_{2},\ldots ,v_{n}}de longitudmáximo‖vi‖≤γλnorte(L){\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}, dondeλnorte(L){\displaystyle \lambda _{n}(L)}es el ⁠norte{\displaystyle n}⁠ el mínimo sucesivo de ⁠L{\displaystyle L}.​

Decodificación de distancia limitada

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

Problema del radio de cobertura

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

Problema de la 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 la Base Más Corta (SBP) debe, dada una base reticular ⁠B{\displaystyle B}⁠ , generar una base equivalenteB′{\displaystyle B'}de tal manera que la longitud del vector más largo enB′{\displaystyle B'}es lo más breve posible.

La versión aproximada del problema SBP γ consiste en encontrar una base cuyo vector más largo sea como máximoγ{\displaystyle \gamma }veces más largo que el vector más largo en la base más corta.

Uso en criptografía

La dificultad 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 solo sean difíciles en el peor de los casos. Se ha conjeturado o demostrado que muchos problemas de retículos son difíciles en el caso promedio, lo que los convierte en una clase atractiva de problemas sobre los que basar esquemas criptográficos. Además, la dificultad en el peor de los casos de algunos problemas de retículos se ha utilizado para crear esquemas criptográficos seguros. El uso de la dificultad en el peor de los casos en dichos esquemas los sitúa entre los pocos esquemas que son muy probablemente seguros incluso frente a ordenadores cuánticos .

Los problemas de retículos mencionados anteriormente son fáciles de resolver si se proporciona al algoritmo una base "buena". Los algoritmos de reducción de retículos buscan, dada una base para un retículo, generar una nueva base que consista en vectores relativamente cortos y casi ortogonales . El algoritmo de reducción de bases de retículos de Lenstra-Lenstra-Lovász (LLL) fue uno de los primeros algoritmos eficientes para este problema, capaz de generar una base de retículo casi reducida en tiempo polinomial. [ 33 ] Este algoritmo y sus posteriores refinamientos se utilizaron para romper varios esquemas criptográficos, estableciendo su estatus como una herramienta muy importante en criptoanálisis . El éxito de LLL en datos experimentales llevó a la creencia de que la reducción de retículos 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 dificultad de los problemas de retículos, comenzando con el resultado de Ajtai . [ 2 ]

En sus trabajos fundamentales, Ajtai demostró que el problema SVP era NP-difícil y descubrió algunas conexiones entre la complejidad del peor caso y la complejidad del caso promedio de algunos problemas de retículos. [ 2 ] [ 3 ] Partiendo de estos resultados, Ajtai y Dwork crearon un criptosistema de clave pública cuya seguridad podía probarse utilizando únicamente la dificultad del peor caso de una determinada versión de SVP, [ 34 ] convirtiéndose así en el primer resultado en utilizar la dificultad del peor caso para crear sistemas seguros. [ 35 ]

Véase también

Referencias

  1. ↑ Khot, Subhash (2005). "Dificultad de aproximar el problema del vector más corto en retículos". J. ACM . 52 (5): 789– 808. doi : 10.1145/1089023.1089027 . S2CID 13438130 . 
  2. 1 2 3 Ajtai, M. (1996). "Generación de instancias difíciles de problemas reticulares" . Actas del vigésimo octavo simposio anual de la ACM sobre teoría de la computación . Filadelfia, Pensilvania, Estados Unidos: ACM. págs. 99–108 . doi : 10.1145/237814.237838 . ISBN  978-0-89791-785-8. S2CID 6864824 . 
  3. 1 2 Ajtai, Miklós (1998). "El problema del vector más corto en L 2 es NP -difícil para reducciones aleatorias" . Actas del trigésimo simposio anual de la ACM sobre Teoría de la Computación . 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 del cálculo de vectores cortos en una red" . Informe técnico 8104. Universidad de Ámsterdam, Departamento de Matemáticas, Países Bajos.
  5. ↑ Kannan, Ravi (1983). «Algoritmos mejorados para programación entera y problemas de retículos relacionados». Actas del decimoquinto simposio anual de la 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-0-89791-099-6. S2CID 18181112 . 
  6. 1 2 Fincke, U.; Pohst, M. (1985). "Métodos mejorados para calcular vectores de longitud corta en una red, incluyendo un análisis de complejidad" . Math. Comp . 44 (170): 463– 471. doi : 10.1090/S0025-5718-1985-0777278-8 .
  7. ↑ Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded (30 de mayo de 2010). "Enumeración de retículos mediante poda extrema" . Avances en criptología – EUROCRYPT 2010. Notas de clase en 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 retículos mediante muestreo aleatorio y métodos de cumpleaños". Stacs 2003. Lecture Notes in Computer Science. Vol. 2607. Springer, Berlín, Heidelberg. pp. 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 reticular con poda discreta". Avances en criptología – EUROCRYPT 2017 (PDF) . Notas de clase en ciencias de la computación. 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. 1 2 Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "Un algoritmo de criba para el problema del vector reticular más corto" . Actas del trigésimo tercer simposio anual de la ACM sobre Teoría de la Computación . Hersonissos, Grecia: ACM. pp. 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 . SODA '10. Filadelfia, PA, EE. UU.: Society for Industrial and Applied Mathematics. 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 del vecino más cercano con aplicaciones al cribado reticular». Actas del Vigésimo Séptimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 10–24 . doi : 10.1137/1.9781611974331.ch2 . ISBN  978-1-61197-433-1.
  13. 1 2 Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Búsqueda del punto más cercano en retículos" (PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201– 2214. doi : 10.1109/TIT.2002.800499 .
  14. ↑ Micciancio, Daniele; Voulgaris, Panagiotis (2010). "Un algoritmo determinista de tiempo exponencial simple para la mayoría de los problemas de retículos basado en cálculos de celdas de Voronoi". Actas del cuadragésimo segundo simposio de la 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   978-1-4503-0050-6. S2CID 2449948 . 
  15. ↑ Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). «Resolución del problema del vector más corto en 2n tiempo mediante muestreo gaussiano discreto». Actas del cuadragésimo séptimo simposio anual de la 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  978-1-4503-3536-2. S2CID 10214330 . 
  16. ↑ Micciancio, Daniele (2017-07-01). "Criptografía reticular: problema del vector más corto" .
  17. ↑ Schnorr, CP (1987-01-01). "Una jerarquía de algoritmos de reducción de bases reticulares de tiempo polinomial" . Theoretical Computer Science . 53 (2): 201– 224. doi : 10.1016/0304-3975(87)90064-8 .
  18. ↑ Schnorr, CP; Euchner, M. (1994-08-01). "Reducción de base reticular: algoritmos prácticos mejorados y resolución de problemas de suma de subconjuntos" (PDF) . Mathematical Programming . 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 retículos". Avances en criptología – ASIACRYPT 2011. Notas de clase en ciencias de la computación. 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). «Sistemas criptográficos de clave pública a partir del problema del vector más corto en el peor de los casos: resumen extendido» . Actas del 41.º simposio anual de la ACM sobre Teoría de la Computación . Bethesda, MD, EE. UU.: 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 de red más cortos no es más difícil que aproximar los vectores de red más cercanos". Inf. Process. Lett . 71 (2): 55– 61. doi : 10.1016/S0020-0190(99)00083-6 . 
  23. ↑ Arora, Sanjeev; et al. (1993). "Actas de la 34.ª Conferencia Anual sobre Fundamentos de la Informática del IEEE de 1993". J. Comput. Syst. Sci . Vol. 54. pp. 317–331 . doi : 10.1109/SFCS.1993.366815 . ISBN    978-0-8186-4370-5. S2CID 44988406 . 
  24. ↑ Dinur, I.; et al. (2003). "Aproximar CVP con factores casi polinomiales es NP-difícil". 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.; Poor, HV (2007). Comunicaciones inalámbricas MIMO . Cambridge: Cambridge UP
  26. ↑ Wang, Ping; Le-Ngoc, Tho (2011). "Un algoritmo de decodificación de esfera de lista con estrategias mejoradas de configuración de radio". 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". IEEE Trans. Sig. Proc . 46 (11): 2938– 2952. Bibcode : 1998ITSP...46.2938H . CiteSeerX 10.1.1.114.7246 . doi : 10.1109/78.726808 . 
  28. ↑ Schnorr, CP "Factorización de enteros y cálculo de 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". Math. Ann. 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 la ACM sobre Teoría de la Computación . 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∩{\displaystyle \cap }coNP". J. ACM . 52 (5): 749– 765. CiteSeerX 10.1.1.205.3730 . doi : 10.1145/1089023.1089025 . S2CID 1669286 .  
  32. ↑ Dinur, I.; Kindler, G.; Safra, S. (1998). "Aproximar CVP con factores casi polinomiales es NP-difícil" . Actas del 39.º Simposio Anual sobre Fundamentos de la Informática . IEEE Computer Society. pág. 99. ISBN  978-0-8186-9172-0.
  33. ↑ Lenstra, AK; Lenstra, HW Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients" (PDF) . Math. Ann. 261 (4): 515– 534. doi : 10.1007/BF01457454 . S2CID 5701340. Archivado del original (PDF) el 17 de julio de 2011. 
  34. ↑ Ajtai, Miklós; Dwork, Cynthia (1997). «Un criptosistema de clave pública con equivalencia entre el peor y el caso promedio» . Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación . 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 reticulares". Teoría algorítmica de números . Notas de clase en ciencias de la computación. Vol. 1838. págs. 1–32 . doi : 10.1007/10722028_1 . ISBN   978-3-540-67695-9.

Lecturas adicionales

  • Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Búsqueda del punto más cercano en retículos" (PDF) . IEEE Trans. Inf. Theory . 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 con una constante" . SIAM Journal on Computing . 30 (6): 2008– 2035. CiteSeerX 10.1.1.93.6646 . doi : 10.1137/S0097539700373039 . S2CID 42794945 .  
  • Nguyen, Phong Q.; Stern, Jacques (2000). «Reducción reticular en criptología: una actualización» . Actas del 4.º Simposio Internacional sobre Teoría Algorítmica de Números . Springer-Verlag. págs. 85-112 . ISBN  978-3-540-67695-9.