La solución de entero corto (SIS) y los problemas de SIS en anillo son dos problemas de casos promedio que se utilizan en construcciones criptográficas basadas en celosía . La criptografía basada en celosía comenzó en 1996 a partir de un trabajo fundamental de Ajtai [1], quien presentó una familia de funciones unidireccionales basadas en el problema SIS. Demostró que es seguro en un caso promedio si el problema del vector más corto (dónde por alguna constante ) es difícil en el peor de los casos.
Los problemas de casos promedio son los problemas que son difíciles de resolver para algunos casos seleccionados al azar. Para las aplicaciones de criptografía, la complejidad del peor de los casos no es suficiente, y debemos garantizar que la construcción criptográfica sea dura en función de la complejidad promedio del caso.
Una celosía de rango completo es un conjunto de combinaciones lineales enteras de vectores linealmente independientes , base nombrada :
dónde es una matriz que tiene vectores base en sus columnas.
Observación: Dado dos bases para celosía , existen matrices unimodulares tal que .
Definición: Operador de turno rotatorio en se denota por , y se define como:
Celosías cíclicas
Micciancio introdujo celosías cíclicas en su trabajo al generalizar el problema de la mochila compacta a anillos arbitrarios. [2] Una celosía cíclica es una celosía que se cierra bajo un operador de cambio rotacional. Formalmente, las celosías cíclicas se definen de la siguiente manera:
Definición: una celosía es cíclico si .
Ejemplos: [3]
- en sí mismo es una red cíclica.
- Celosías correspondientes a cualquier ideal en el anillo polinomial del cociente son cíclicos:
considere el anillo polinomial del cociente , y deja ser un polinomio en , es decir dónde por .
Definir el coeficiente de incrustación -isomorfismo del módulo como:
Dejar ser un ideal. La celosía correspondiente al ideal, denotado por , es una subred de , y se define como
Teorema: es cíclico si y solo si corresponde a algún ideal en el anillo polinomial del cociente .
prueba: Tenemos:
Dejar ser un elemento arbitrario en . Entonces, defina. Pero desde es un ideal, tenemos . Luego,. Pero,. Por eso, es cíclico.
Dejar ser una celosía cíclica. Por eso.
Definir el conjunto de polinomios :
- Desde una celosía y, por tanto, un subgrupo aditivo de , es un subgrupo aditivo de .
- Desde es cíclico, .
Por eso, es un ideal y, en consecuencia, .
Rejillas ideales [4] [5]
Dejar ser un polinomio monico de grado . Para aplicaciones criptográficas,generalmente se selecciona para que sea irreducible. El ideal generado por es:
El anillo polinomial del cociente particiones en clases de equivalencia de polinomios de grado como máximo :
donde la suma y la multiplicación se reducen módulo .
Considere el coeficiente de incrustación -isomorfismo del módulo . Entonces, cada ideal en define una subred de llamado celosía ideal .
Definición: , la celosía correspondiente a un ideal , se llama celosía ideal. Más precisamente, considere un anillo polinomial cociente, dónde es el ideal generado por un grado polinomio . , es una subred de , y se define como:
Observación: [6]
- Resulta que incluso para los pequeños suele ser fácil en celosías ideales. La intuición es que las simetrías algebraicas hacen que la distancia mínima de un ideal se encuentre dentro de un rango estrecho y fácilmente computable.
- Al explotar las simetrías algebraicas proporcionadas en redes ideales, se puede convertir un vector corto distinto de cero en linealmente independientes de (casi) la misma longitud. Por lo tanto, en celosías ideales, y son equivalentes con una pequeña pérdida. [7] Además, incluso para algoritmos cuánticos, y son muy difíciles en el peor de los casos.
SIS y Ring-SIS son dos problemas de casos promedio que se utilizan en construcciones criptográficas basadas en celosía. La criptografía basada en celosía comenzó en 1996 a partir de un trabajo fundamental de Ajtai [1], quien presentó una familia de funciones unidireccionales basadas en el problema SIS. Demostró que es seguro en un caso medio si (dónde por alguna constante ) es difícil en el peor de los casos.
SIS n , m , q , β
Dejar frijol matriz con entradas en que consiste en vectores uniformemente aleatorios : . Encuentra un vector distinto de cero tal que:
Una solución para SIS sin la restricción requerida sobre la longitud de la solución () es fácil de calcular utilizando la técnica de eliminación gaussiana . También requerimos, de lo contrario es una solución trivial.
Para garantizar tiene una solución corta y no trivial, requerimos:
- , y
Teorema: para cualquier, alguna , y cualquier lo suficientemente grande (para cualquier constante ), resolviendo con una probabilidad no despreciable es al menos tan difícil como resolver el y para algunos con una alta probabilidad en el peor de los casos.
Anillo-SIS
El problema Ring-SIS, un análogo compacto basado en el anillo del problema SIS, se estudió en. [2] [8] Consideran un anillo polinomial cociente con y , respectivamente, y ampliar la definición de norma sobre vectores en a vectores en como sigue:
Dado un vector dónde son algunos polinomios en . Considere el coeficiente de incrustación-isomorfismo del módulo :
Dejar . Definir norma como:
Alternativamente, se logra una mejor noción de norma explotando la incrustación canónica . La incrustación canónica se define como:
dónde es el raíz compleja de por .
R-SIS m , q , β
Dado el anillo polinomial del cociente , definir
. Seleccione elementos independientes uniformemente aleatorios . Definir vector. Encuentra un vector distinto de cero tal que:
Recuerde que para garantizar la existencia de una solución al problema del SIS, requerimos . Sin embargo, el problema Ring-SIS nos proporciona más compacidad y eficacia: para garantizar la existencia de una solución al problema Ring-SIS, requerimos.
Definición: La matriz nega-circulante de Se define como:
Cuando el anillo polinomial del cociente es por , la multiplicación de anillos se puede calcular de manera eficiente formando primero , la matriz nega-circulante de y luego multiplicar con , el vector de coeficiente de inclusión de (o, alternativamente con , el vector de coeficientes canónicos).
Además, el problema R-SIS es un caso especial de problema SIS donde la matriz en el problema SIS se restringe a bloques negacirculantes: . [9]