Reto sobre retículos: ¿sabrías explicar por qué el ejemplo no es correcto?

 Buscando recursos en Internet sobre retículos y sus aplicaciones encontré dos trabajos de final de grado muy interesantes. Sin desmerecer lo más mínimo la calidad de los mismos, en dichos trabajos, para ejemplificar el problema que conté aquí sobre que el vector devuelto por el algoritmo de Babai no tiene por qué ser el más cercano incluyen las siguientes imágenes (en realidad son el mismo ejemplo).

Chen, J. (2023): GGH: un criptosistema basat en reticles. Treball Final del Grau de Matemàtiques, p. 16. Universitat de Barcelona.

Guitart Torra, J. (2024): Didàctica del criptosistema GGH. Treball Final del Grau de Matemàtiques, p. 12. Universitat de Barcelona.

 En ambos trabajos justifican el fallo del algoritmo de Babai por ser una base "mala" (poco ortogonal).

 Pero este ejemplo no es correcto dado que los vectores representados como base del retículo, aunque son linealmente independientes, no son en realidad una base del retículo representado. Es decir, no es que sea una base "mala" y por eso no funcione bien el algoritmo de Babai, sino que no es ni tan siquiera base. ¿Sabrías explicar por qué? 

Problema del vector más cercano (CVP) en un retículo

Definición del problema: 

Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$ y sea $\vec{w} \in \mathbb{R}^n$.

Queremos encontrar un vector $\vec{z} \in \varLambda$ tal que:

$$\|\vec{w}-\vec{z}\| = mín\{\|\vec{w}-\vec{b}\|, \forall \vec{b} \in \varLambda\}$$

Es decir, dado un vector del espacio queremos encontrar el vector del retículo más cercano al primero. Esto se conoce como el Problema del Vector más Cercano (CVP, por las siglas en inglés "Closest Vector Problem").

 

Teniendo en cuenta que la región fundamental de un retículo es un n-paralelepípedo, es inmediato ver la relación con las entradas anteriores (1 y 2) en las que se plantea encontrar el vértice del n-paralelepípedo más cercano a un punto.

Resumiendo, para dimensiones altas el método exhaustivo consistente en calcular la distancia con todos los vértices del n-paralelepípedo tiene un coste computacional demasiado elevado. 

Por otra parte, el algoritmo de Babai solo ofrece garantías de obtener la solución correcta si la base es lo "suficientemente ortogonal". Pero a esto además le añadimos que con bases que tienen mucho defecto de ortogonalidad (muy "lejos" de ser ortogonales) resulta que el vector más cercano ni tan siquiera tiene porqué ser vértice del n-paralelepípedo que lo contiene.

Puede verse que hay un punto naranja (del retículo) más próximo a $Q$ que los vértices del n-paralelepípedo que lo contiene

Con todo lo anterior, podemos concluir lo siguiente sobre la resolución del problema del vector más próximo en un retículo: una persona que conozca una base "bastante próxima" a ser ortogonal podrá realizar los cálculos de manera relativamente sencilla, mientras que otra persona que conozca una base "suficientemente lejos" de ser ortogonal tendrá mucha más dificultad para resolverlo.

Algoritmo de Babai con Python

 En la entrada anterior expliqué y ejemplifiqué el Algoritmo de Babai para encontrar el vértice del n-paralelepípedo más cercano a un punto.

Podemos realizar un script en Python para dicho algoritmo. Utilizando la librería NumPy queda muy sencillo:

 

import numpy as np

def babai(B, w):
    # Calculamos los coeficientes del vector w en la base B
    v = np.linalg.solve(B, w)
    # Devolvemos el producto matricial de B por las coordenadas de v redondeadas
    return B @ np.round(v).astype(int) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

PD: Podéis encontrar en uno de mis repositorios de Github un script para probar el Algoritmo de Babai y la razón de Hadamard.