Problema de solución de números enteros cortos

Los problemas de solución entera corta (SIS) y de anillo-SIS son dos problemas de caso promedio que se utilizan en construcciones criptográficas basadas en retículas . La criptografía basada en retículas comenzó en 1996 a partir de un trabajo seminal de Miklós 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 (donde para alguna constante ) es difícil en un escenario de peor caso. ${\displaystyle \mathrm {SVP} _{\gamma }}$ ${\displaystyle \gamma =n^{c}}$ ${\displaystyle c>0}$

Los problemas de casos promedio son aquellos que son difíciles de resolver para algunas instancias seleccionadas al azar. Para las aplicaciones criptográficas, la complejidad del peor caso no es suficiente y debemos garantizar que la construcción criptográfica sea difícil en función de la complejidad del caso promedio.

Celosías

Una red de rango completo es un conjunto de combinaciones lineales enteras de vectores linealmente independientes , denominados base : ${\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n}}$ ${\displaystyle n}$ ${\displaystyle \{b_{1},\ldots ,b_{n}\}}$

${\displaystyle {\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} \right\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\}}$

donde es una matriz que tiene vectores base en sus columnas. ${\displaystyle B\in \mathbb {R} ^{n\times n}}$

Observación: Dadas dos bases para la red , existen matrices unimodulares tales que . ${\displaystyle B_{1},B_{2}}$ ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle U_{1}}$ ${\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}}$

Celosía ideal

Definición: El operador de cambio rotacional on se denota por y se define como: ${\displaystyle \mathbb {R} ^{n}(n\geq 2)}$ ${\displaystyle \operatorname {rot} }$

${\displaystyle \forall {\boldsymbol {x}}=(x_{1},\ldots ,x_{n-1},x_{n})\in \mathbb {R} ^{n}:\operatorname {rot} (x_{1},\ldots ,x_{n-1},x_{n})=(x_{n},x_{1},\ldots ,x_{n-1})}$

Redes cíclicas

Micciancio introdujo las redes cíclicas en su trabajo al generalizar el problema de la mochila compacta a anillos arbitrarios. ^[2] Una red cíclica es una red cerrada bajo el operador de desplazamiento rotacional. Formalmente, las redes cíclicas se definen de la siguiente manera:

Definición: Una red es cíclica si . ${\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n}}$ ${\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}$

Ejemplos: ^[3]

1. ${\displaystyle \mathbb {Z} ^{n}}$en sí misma es una red cíclica.
2. Las redes correspondientes a cualquier ideal en el anillo polinomial cociente son cíclicas: ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$

considere el anillo polinomial cociente , y sea algún polinomio en , es decir donde para . ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$ ${\displaystyle p(x)}$ ${\displaystyle R}$ ${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}}$ ${\displaystyle a_{i}\in \mathbb {Z} }$ ${\displaystyle i=0,\ldots ,n-1}$

Defina el isomorfismo coeficiente de incrustación-módulo como: ${\displaystyle \mathbb {Z} }$ ${\displaystyle \rho }$

${\displaystyle {\begin{aligned}\quad \rho :R&\rightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}}$

Sea un ideal. La red correspondiente al ideal , denotada por , es una subred de , y se define como ${\displaystyle I\subset R}$ ${\displaystyle I\subset R}$ ${\displaystyle {\mathfrak {L}}_{I}}$ ${\displaystyle \mathbb {Z} ^{n}}$

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

Teorema: es cíclico si y sólo si corresponde a algún ideal en el anillo de polinomios cocientes . ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$ ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle I}$ ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$

Prueba: Tenemos: ${\displaystyle \Leftarrow )}$

${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}}$

Sea un elemento arbitrario en . Luego, defina . Pero como es un ideal, tenemos . Entonces, . Pero, . Por lo tanto, es cíclico. ${\displaystyle (a_{0},\ldots ,a_{n-1})}$ ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I}$ ${\displaystyle I}$ ${\displaystyle xp(x)\in I}$ ${\displaystyle \rho (xp(x))\in {\mathfrak {L}}_{I}}$ ${\displaystyle \rho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}}$ ${\displaystyle {\mathfrak {L}}}$

${\displaystyle \Rightarrow )}$

Sea una red cíclica. Por lo tanto . ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$ ${\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}}$

Definir el conjunto de polinomios : ${\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}\right\}}$

1. Dado que una red y, por lo tanto, un subgrupo aditivo de , es un subgrupo aditivo de . ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle I\subset R}$ ${\displaystyle R}$
2. Dado que es cíclico, . ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle \forall p(x)\in I:xp(x)\in I}$

Por lo tanto, es un ideal, y en consecuencia, . ${\displaystyle I\subset R}$ ${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}}$

Rejillas ideales[4]

Sea un polinomio mónico de grado . Para aplicaciones criptográficas, se suele seleccionar como irreducible. El ideal generado por es: ${\displaystyle f(x)\in \mathbb {Z} [x]}$ ${\displaystyle n}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$

${\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.}$

El anillo de polinomios cociente se divide en clases de equivalencia de polinomios de grado como máximo : ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$ ${\displaystyle \mathbb {Z} [x]}$ ${\displaystyle n-1}$

${\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}}$

donde la suma y la multiplicación se reducen módulo . ${\displaystyle f(x)}$

Consideremos el isomorfismo módulo- coeficiente de incrustación . Entonces, cada ideal en define una subred de llamada red ideal . ${\displaystyle \mathbb {Z} }$ ${\displaystyle \rho }$ ${\displaystyle R}$ ${\displaystyle \mathbb {Z} ^{n}}$

Definición: , la red correspondiente a un ideal , se llama red ideal. Más precisamente, considere un anillo de polinomios cociente , donde es el ideal generado por un polinomio de grado . , es una subred de , y se define como: ${\displaystyle {\mathfrak {L}}_{I}}$ ${\displaystyle I}$ ${\displaystyle R=\mathbb {Z} [x]/(p(x))}$ ${\displaystyle (p(x))}$ ${\displaystyle n}$ ${\displaystyle p(x)\in \mathbb {Z} [x]}$ ${\displaystyle {\mathfrak {L}}_{I}}$ ${\displaystyle \mathbb {Z} ^{n}}$

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

Observación: ^[5]

1. Resulta que incluso los valores pequeños suelen ser fáciles en los retículos 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. ${\displaystyle {\text{GapSVP}}_{\gamma }}$ ${\displaystyle \gamma =\operatorname {poly(n)} }$
2. Al explotar las simetrías algebraicas proporcionadas en redes ideales, se puede convertir un vector corto distinto de cero en vectores linealmente independientes de (casi) la misma longitud. Por lo tanto, en redes ideales, y son equivalentes con una pequeña pérdida. ^[6] Además, incluso para algoritmos cuánticos, y se cree que son muy difíciles en el peor de los casos. ${\displaystyle n}$ ${\displaystyle \mathrm {SVP} _{\gamma }}$ ${\displaystyle \mathrm {SIVP} _{\gamma }}$ ${\displaystyle \mathrm {SVP} _{\gamma }}$ ${\displaystyle \mathrm {SIVP} _{\gamma }}$

Problema de solución de números enteros cortos

El problema de la solución entera corta (SIS) es un problema de caso promedio que se utiliza en construcciones criptográficas basadas en retículas. La criptografía basada en retículas comenzó en 1996 a partir de un trabajo seminal de Ajtai ^[1] , quien presentó una familia de funciones unidireccionales basadas en el problema SIS. Demostró que es seguro en un caso promedio si (donde para alguna constante ) es difícil en un escenario de peor caso. Junto con las aplicaciones en criptografía clásica, el problema SIS y sus variantes se utilizan en varios esquemas de seguridad postcuánticos, incluidos CRYSTALS-Dilithium y Falcon . ^{[7] [8]} ${\displaystyle \mathrm {SVP} _{\gamma }}$ ${\displaystyle \gamma =n^{c}}$ ${\displaystyle c>0}$

SISq , n , m , β

Sea una matriz con entradas en que consta de vectores uniformemente aleatorios : . Encuentre un vector distinto de cero tal que para alguna norma : ${\displaystyle A\in \mathbb {Z} _{q}^{n\times m}}$ ${\displaystyle n\times m}$ ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle m}$ ${\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}}$ ${\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}$ ${\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}}$ ${\displaystyle \|\cdot \|}$

• ${\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta }$,
• ${\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}}$.

Es fácil calcular una solución de SIS sin la restricción requerida sobre la longitud de la solución ( ) utilizando la técnica de eliminación gaussiana . También requerimos que , de lo contrario es una solución trivial. ${\displaystyle \|{\boldsymbol {x}}\|\leq \beta }$ ${\displaystyle \beta <q}$ ${\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}$

Para garantizar una solución breve y no trivial, necesitamos: ${\displaystyle f_{A}({\boldsymbol {x}})}$

• ${\displaystyle \beta \geq {\sqrt {n\log q}}}$, y
• ${\displaystyle m\geq n\log q}$

Teorema: Para cualquier , cualquier , y cualquier suficientemente grande (para cualquier constante ), resolver con una probabilidad no despreciable es al menos tan difícil como resolver y para algunos con una alta probabilidad en el peor de los casos. ${\displaystyle m=\operatorname {poly} (n)}$ ${\displaystyle \beta >0}$ ${\displaystyle q\geq \beta n^{c}}$ ${\displaystyle c>0}$ ${\displaystyle \operatorname {SIS} _{n,m,q,\beta }}$ ${\displaystyle \operatorname {GapSVP} _{\gamma }}$ ${\displaystyle \operatorname {SIVP} _{\gamma }}$ ${\displaystyle \gamma =\beta \cdot O({\sqrt {n}})}$

R-SISq , n , m , β

El problema SIS resuelto sobre un anillo ideal también se denomina problema Ring-SIS o R-SIS. ^{[2] [9]} Este problema considera un anillo de polinomios cociente con para algún entero y con alguna norma . De particular interés son los casos en los que existe un entero tal que como esto restringe el cociente a polinomios ciclotómicos. ^[10] ${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$ ${\displaystyle f(x)=x^{n}-1}$ ${\displaystyle n}$ ${\displaystyle \|\cdot \|}$ ${\displaystyle k}$ ${\displaystyle n=2^{k}}$

Definimos entonces el problema de la siguiente manera:

Seleccione elementos aleatorios uniformes e independientes . Defina un vector . Encuentre un vector distinto de cero tal que: ${\displaystyle m}$ ${\displaystyle a_{i}\in R_{q}}$ ${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}}$ ${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$,
• ${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}}$.

Recordemos que para garantizar la existencia de una solución al problema SIS, necesitamos . 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, necesitamos . ${\displaystyle m\approx n\log q}$ ${\displaystyle m\approx \log q}$

Definición: La matriz negacirculante de se define como: ${\displaystyle b}$

${\displaystyle {\text{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in R,\quad \operatorname {rot} (b):={\begin{bmatrix}b_{0}&-b_{n-1}&\ldots &-b_{1}\\[0.3em]b_{1}&b_{0}&\ldots &-b_{2}\\[0.3em]\vdots &\vdots &\ddots &\vdots \\[0.3em]b_{n-1}&b_{n-2}&\ldots &b_{0}\end{bmatrix}}}$

Cuando el anillo polinomial cociente es para , la multiplicación del anillo se puede calcular de manera eficiente formando primero , la matriz negacirculante de , y luego multiplicando con , el vector de coeficientes de incrustación de (o, alternativamente con , el vector de coeficientes canónicos. ${\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)}$ ${\displaystyle n=2^{k}}$ ${\displaystyle a_{i}.p_{i}}$ ${\displaystyle \operatorname {rot} (a_{i})}$ ${\displaystyle a_{i}}$ ${\displaystyle \operatorname {rot} (a_{i})}$ ${\displaystyle \rho (p_{i}(x))\in Z^{n}}$ ${\displaystyle p_{i}}$ ${\displaystyle \sigma (p_{i}(x))\in Z^{n}}$

Además, el problema R-SIS es un caso especial del problema SIS donde la matriz en el problema SIS está restringida a bloques negacirculantes: . ^[10] ${\displaystyle A}$ ${\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}$

M-SISq , n , d , m , β

El problema SIS resuelto sobre una red de módulos también se denomina problema Módulo-SIS o M-SIS. Al igual que R-SIS, este problema considera el anillo de polinomios cociente y para con un interés especial en los casos donde es una potencia de 2. Entonces, sea un módulo de rango tal que y sea una norma arbitraria sobre . ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$ ${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$ ${\displaystyle f(x)=x^{n}-1}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle d}$ ${\displaystyle M\subseteq R^{d}}$ ${\displaystyle \|\cdot \|}$ ${\displaystyle R_{q}^{m}}$

Definimos entonces el problema de la siguiente manera:

Seleccione elementos aleatorios uniformes e independientes . Defina un vector . Encuentre un vector distinto de cero tal que: ${\displaystyle m}$ ${\displaystyle a_{i}\in R_{q}^{d}}$ ${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d\times m}}$ ${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$,
• ${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}^{d}}$.

Si bien el M-SIS es una variante menos compacta del SIS que el R-SIS, el problema del M-SIS es asintóticamente al menos tan difícil como el R-SIS y, por lo tanto, ofrece un límite más estricto para el supuesto de dureza del SIS. Esto hace que asumir la dureza del M-SIS sea un supuesto subyacente más seguro, pero menos eficiente en comparación con el R-SIS. ^[10]

Véase también

• Criptografía basada en celosía
• Cifrado homomórfico
• Aprendizaje de anillos con intercambio de claves de errores
• Criptografía post-cuántica
• Problema de celosía

Referencias

1. Ajtai, Miklós. [Generación de instancias difíciles de problemas de red.] Actas del vigésimo octavo simposio anual de la ACM sobre teoría de la computación. ACM, 1996.
2. Micciancio, Daniele. [Mochilas compactas generalizadas, redes cíclicas y funciones unidireccionales eficientes a partir de supuestos de complejidad en el peor de los casos.] Fundamentos de la informática, 2002. Actas. 43.º Simposio anual del IEEE sobre. IEEE, 2002.
3. Fukshansky, Lenny y Xun Sun. [Sobre la geometría de redes cíclicas.] Geometría discreta y computacional 52.2 (2014): 240–259.
4. Craig Gentry. Cifrado totalmente homomórfico utilizando redes ideales. En el 41.º Simposio ACM sobre teoría de la computación (STOC) , 2009.
5. Peikert, Chris. [Una década de criptografía en red.] Archivo de criptografía electrónica, Informe 2015/939, 2015.
6. Peikert, Chris y Alon Rosen. [Hash eficiente resistente a colisiones a partir de supuestos de casos peores en redes cíclicas.] Theory of Cryptography. Springer Berlin Heidelberg, 2006. 145–166.
7. Bai, Shi; Ducas, Léo; Kiltz, Eike; Lepoint, Tancrède; Lyubashevsky, Vadim; Schwabe, Peter; Seiler, Grego4; Stehlé, Damien (1 de octubre de 2020). "CRYSTALS-Dilithium: Especificaciones del algoritmo y documentación complementaria" (PDF) . PQ-Crystals.org . Consultado el 13 de noviembre de 2023 .{{cite web}}: CS1 maint: numeric names: authors list (link)
8. Fouque, Pierre-Alain; Hoffstein, Jeffrey; Kirchner, Paul; Lyubashevsky, Vadim; Pornin, Thomas; Prest, Thomas; Ricosset, Thomas; Seiler, Gregor; Whyte, William; Zhang, Zhenfei (1 de octubre de 2020). «Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU» (Falcon: Firmas compactas basadas en red Fast-Fourier sobre NTRU). Consultado el 13 de noviembre de 2023 .
9. Lyubashevsky, Vadim, et al. [SWIFFT: una modesta propuesta para el hash FFT.] Fast Software Encryption. Springer Berlin Heidelberg, 2008.
10. Langlois, Adeline y Damien Stehlé. [Reducciones del peor caso al caso promedio para redes de módulos.] Diseños, códigos y criptografía 75.3 (2015): 565–599.