¿Un problema NP?

Se conoce (a través de una base) un subretículo del retículo de los puntos de coordenadas enteras en el espacio de n dimensiones.
Nos dan un punto.
Averiguar la distancia al hiperplano del retículo que se encuentre a mínima distancia.
Fácil si se tiene una base del subretículo con vectores de coordenadas pequeñas (basta una base con n-1 coordenadas pequeñas y la otra coordenada grande).
Difícil si la base que se conoce es de vectores de coordenadas grandes.

Recuerda la semejanza con el sistema RSA:

¿Problema NP?:
Resolver x^e==M(mod n), siendo e y n números conocidos, n grande (de 200 cifras por ejemplo).
Fácil si se sabe que n=p.q siendo p,q primos (por ejemplo de 100 dígitos cada uno).
Difícil si n=p.q, con p y q primos grandes y se desconocen p y q.

Si existe algún algoritmo que sea capaz de de resolver el problema eficazmente para una fracción de los hiperplanos posibles, existe un algoritmo que resuelve el problema para todos.

También (Ajtai):

Si existe algún algoritmo probabilístico que resuelve el problema con probabilidad mayor que cero, se puede construir uno que resuelve el problema con probabilidad 1.

Una buena aproximación a la conjetura P<NP (es decir que existe algún problema que se puede resolver no determinísticamente [es decir, vale adivinar] en tiempo polinómico pero para el que no existe un algoritmo determinístico que lo resuelva en tiempo polinómico [es decir, cuya complejidad crezca sólo como un polinomio función del tamaño de los datos]). Se podría pensar que el problema del retículo  es un buen candidato para ser NP pero no P, pero esto no se ha demostrado.

El usuario A se fabrica su clave pública y su clave secreta.
A escoge un subretículo.
Para ello toma n-1 vectores de coordenadas pequeñas y otro aleatoriamente de coordenadas grandes. Esta será su clave secreta.
Escoge su clave pública: una base aleatoriamente elegida de su retículo.

El usuario B codifica para A el 0 y el 1.
Para codificar el 0 para A toma un punto del subretículo de A y añade aleatoriamente un vector pequeño del retículo Zⁿ.
Para codificar el 1 toma un punto cualquiera de Zⁿ.
Envía ese punto por conducto abierto a A.

El usuario A descodifica el mensaje.
Él sabe cómo hallar la mínima distancia a su retículo del punto enviado por B. Si la distancia es pequeña, con probabilidad casi 1 se trata de un 0. Si es grande es que se trata de un 1 con probabilidad casi 1.