Análisis comparativo de las firmas digitales postcuánticas basadas en retículos

An´ alisis comparativo de las firmas digitales postcu´ anticas basadas en ret´ ıculos Eva Iglesias Hern´ andez Instituto de Tecnolog´ ıas F´ ısicas y de la Informaci´ on Consejo Superior de Investigaciones Cient´ ıficas C/ Serrano 144, 28006, Madrid ev[email protected] Luis Hern´ andez- ´ Alvarez Instituto de Tecnolog´ ıas F´ ısicas y de la Informaci´ on Consejo Superior de Investigaciones Cient´ ıficas C/ Serrano 144, 28006, Madrid [email protected] Luis Hern´ andez Encinas Instituto de Tecnolog´ ıas F´ ısicas y de la Informaci´ on Consejo Superior de Investigaciones Cient´ ıficas C/ Serrano 144, 28006, Madrid [email protected] Jos´ e Ignacio S´ anchez Garc´ ıa Instituto de Tecnolog´ ıas F´ ısicas y de la Informaci´ on Consejo Superior de Investigaciones Cient´ ıficas C/ Serrano 144, 28006, Madrid [email protected] Resumen—Despu´ es de la publicaci´ on de los algoritmos de Shor, la comunidad criptogr´ afica ha aceptado que una vez que se desarrolle un ordenador cu´ antico con la suficiente capacidad de c´ omputo, la criptograf´ ıa asim´ etrica actual ser´ a vulnerada de modo eficiente. Por ello, el NIST lanz´ o una convocatoria internacional para la elecci´ on de nuevos est´ andares criptogr´ aficos resistentes a la computaci´ on cu´ antica. En 2022, el NIST public´ o un mecanismo de encapsulamiento de claves (CRYSTALS- Kyber) y tres esquemas de firma electr´ onica (CRYSTALS- Dilithium, FALCON y SPHINCS+). En este trabajo se presenta un an´ alisis de los dos primeros esquemas de firma, los basados en ret´ ıculos, con el fin de homogeneizar sus caracter´ ısticas en cuanto a tama˜ no de sus par´ ametros y su rendimiento, habida cuenta que las propuestas originales fueron presentadas utilizando diferentes arquitecturas, lo que dificulta su comparaci´ on en cuanto a los dos aspectos se˜ nalados anteriormente. Index Terms—Criptograf´ ıa postcu´ antica, Firmas digitales, Problema del aprendizaje con errores, Rendimiento computacional. Tipo de contribuci´ on: Investigaci´ on original y en desarrollo I. INTRODUCCI´ ON Como es bien sabido, Peter Shor public´ o en [1] dos algoritmos capaces de resolver en tiempo polin´ omico, caso de existir un ordenador cu´ antico con la suficiente capacidad de c´ omputo, los dos problemas de la Teor´ ıa de N´ umeros m´ as utilizados en la criptograf´ ıa asim´ etrica actual: el problema de la factorizaci´ on de n´ umeros enteros y el problema del logaritmo discreto. La dificultad computacional de ambos problemas con ordenadores no cu´ anticos es lo que garantiza la seguridad de los dos criptosistemas asim´ etricos m´ as empleados a d´ ıa de hoy: el RSA [2] y los basados en curvas el´ ıpticas [3], [4], adem´ as de otros muchos protocolos basados en ellos, como los de firma digital o los de acuerdo de clave, como los de Diffie-Helmman [5]. No es f´ acil aventurar cu´ ando todos estos protocolos criptogr´ aficos dejar´ an de ser seguros, porque no sabemos con certeza cu´ ando existir´ a un ordenador cu´ antico criptoanal´ ıticamente relevante o CRQC ((Cryptanalytically Relevant Quantum Computer); pero lo que s´ ı es seguro es que la criptograf´ ıa actual o precu´ antica tiene los d´ ıas contados. A la vista de esta situaci´ on, el Instituto de est´ andares y tecnolog´ ıa norteamericano o NIST (National Institute for Standards and Technology) realiz´ o, en 2016, una convocatoria internacional para la propuesta y posterior elecci´ on de nuevos est´ andares criptogr´ aficos asim´ etricos, resistentes a la computaci´ on cu´ antica. Esta convocatoria, conocida como criptograf´ ıa postcu´ antica o PQC (Post-Quantum Cryptography), se restring´ ıa a los mecanismos de encapsulamiento de claves o KEM (Key Encapsulation Mechanism) y a los esquemas de firma digital. Despu´ es de varias rondas, en 2022, el NIST public´ o los nuevos est´ andares, que pueden considerarse como los ganadores de esta PQC [6]. Esta lista contiene un ´ unico KEM, a saber, CRYSTALS-Kyber [7], y tres esquemas de firma digital: CRYSTALS-Dilithium [8], FALCON [9] y SPHINCS+[10]. Los tres primeros basan su seguridad en determinados problemas matem´ aticos definidos sobre la estructura de ret´ ıculo; mientras que el ´ ultimo lo hace sobre determinadas funciones hash. En este trabajo vamos a llevar a cabo un an´ alisis comparativo de los dos esquemas de firma digital cuya seguridad se fundamenta en ret´ ıculos, esto es, CRYSTALS-Dilithium y FALCON. Este an´ alisis tiene como objetivo utilizar una misma arquitectura y un mismo marco de referencia para las correspondientes implementaciones, que permita comparar de un modo claro y coherente las caracter´ ısticas de ambos esquemas. As´ ı, el estudio se centrar´ a en analizar los tama˜ nos de las claves p´ ublicas y privadas utilizadas y de las firmas obtenidas por cada uno de los esquemas, como de su rendimiento, tanto en tiempo de ejecuci´ on como en el uso de la CPU. De este modo, el resto de esta comunicaci´ on se estructura de la siguiente manera. En la secci´ on II se presentan, de forma muy resumida, los fundamentos matem´ aticos en los que se basa la seguridad de los esquemas de firma a estudiar. Las caracter´ ısticas y los algoritmos que definen ambos esquemas se incluyen en la secci´ on III. La secci´ on IV contiene los an´ alisis comparativos que hemos llevado a cabo y los resultados correspondientes. Finalmente, en la secci´ on V se incluyen las principales conclusiones de este trabajo. JNIC 2024 ISBN:978-84-09-62140-8 404 II. FUNDAMENTOS Y NOTACI ´ ON En esta secci´ on se presentar´ an, de forma muy elemental, los fundamentos en los que se basan los dos esquemas de firma digital que ser´ an analizados. Dado un conjunto de vectores linealmente independientes del espacio vectorial real de dimensi´ on n,Rn, sea B= {b1,...,bm}, con m≤n. Un ret´ ıculo (lattice), es un subgrupo aditivo discreto de Rnformado por las combinaciones lineales enteras de B. Esta estructura suele denotarse por L ⊂ Rn: L=(m X i=1 ai·bi:ai∈Z) ={B·a:a={a1, . . . , am} ∈ Zm}. Dicho de otro modo, un ret´ ıculo no es m´ as que una malla de puntos en Rnde modo que tales puntos se obtienen como m´ ultiplos enteros de determinado n´ umero de vectores linealmente independientes. Los dos problemas, considerados computacionalmente dif´ ıciles, cl´ asicos definidos en un ret´ ıculo son el problema del vector m´ as corto o SVP (Shortest Vector Problem) y el del vector m´ as cercano o CVP (Closest Vector Problem). El SVP consiste en determinar un vector no nulo, x∈ L, que sea el vector m´ as corto de L, es decir, de modo que ||x|| ≤ ||y||,∀y∈ L, siendo ||·|| la norma definida en L. Por otra parte, dado un vector x∈Rnde modo que x∈ L, el CVP consiste en encontrar un vector v∈ L de modo que ||x−v|| ≤ ||x−w||,∀w∈ L. Al margen de estos dos problemas cl´ asicos existen otros problemas, tambi´ en considerados computacionalmente dif´ ıciles, que son la base de la seguridad de la mayor parte de los est´ andares considerados por el NIST, hasta la fecha. Uno de estos problemas es el problema de la soluci´ on entera corta o SIS (Short Integer Solution), cuyo enunciado es: sean nyqdos n´ umeros enteros y sea β > 0. Dada, adem´ as, una matriz uniformemente aleatoria A∈Zn×m qpara alg´ un m= poly(n), se trata de encontrar un vector entero no nulo z∈ Zm, tal que Az =0(m´od q)y||z|| ≤ β, usando la norma est´ andar. Existe dos variantes del problema anterior, definidas, respectivamente, sobre la estructura de anillo, llamada RSIS, o de m´ odulo, denotada como MSIS. Sea Run anillo (resp. m´ odulo) y sean m, q enteros positivos. Dados los coeficientes de una matriz, A,=ai,j ←$Rm q, se trata de encontrar un vector del anillo (resp. m´ odulo) distinto de cero z∈Rmde norma ||z|| ≤ βtal que Az= 0 (m´od q). Otro problema, de gran importancia criptogr´ afica es el problema del aprendizaje con errores o LWE (Learning With Errors, que ha dado lugar a dos versiones: una definida sobre anillos, RLWE (Ring-Learning With Errors), y otra sobre m´ odulos, MLWE (Module-Learning With Errors). El problema LWE, del que existen dos versiones: de b´ usqueda y de decisi´ on, se parametriza por un entero n, un n´ umero primo q≥2y una distribuci´ on de probabilidad χ sobre Zq. El problema LWE de b´ usqueda es el siguiente: dadas m muestras independientes (ai, bi)∈Zn q×Zqsiguiendo la distribuci´ on As,χ con bi=⟨s,ai⟩+ei(m´od q)∈Zq, se trata de encontrar el vector secreto s∈Zn q, siendo m≥n. El problema LWE de decisi´ on tiene como objetivo es distinguir entre dos conjuntos de m≥npares de vectores (ai, bi)y(¯ ai,¯ bi), donde ai,¯ ai←χZn q,bi=⟨s,ai⟩+ei (m´od q)y¯ bi∈Zq. Es decir, el problema es decidir, para cada par de vectores dados, si el segundo vector, bi, es el producto escalar del primer vector, ai, por alg´ un vector secreto, s, sumado con alg´ un error, ei, o si es un vector uniformemente aleatorio. En el caso del RLWE, la estructura que se considera es la del anillo finito de los polinomios enteros m´ odulo el ideal generado por Φ(x):Rq=Zq[x]/⟨Φ(x)⟩, siendo Φ(x) = xn+1 ∈Z[x], el m-´ esimo polinomio ciclot´ omico de grado φ(m)=2k−1=n. Tambi´ en para el problema RLWE existen las versiones de b´ usqueda y de decisi´ on. El problema MLWE es otra variante del LWE que trata de ser un caso intermedio entre el LWE y el RLWE. El m´ odulo considerado en el MLWE es Rk q= (Zq[x]/⟨xn+ 1⟩)k y puede entenderse como un ret´ ıculo de dimensi´ on k·n, siendo kla dimensi´ on del m´ odulo Rk qsobre el anillo Rq. En general, el valor considerado para ken las propuestas criptogr´ aficas es un n´ umero peque˜ no. De hecho, en CRYSTALS-Kyber se considera k= 2,3,4, seg´ un el nivel de seguridad. Esto es, a mayor k, mayor nivel de seguridad y, por tanto, mayor costo computacional. La idea subyacente en los problemas RLWE y MLWE es considerar que cada polinomio de Rqse puede identificar con un vector cuyas coordenadas son sus ncoeficientes y los elementos de Rk qson vectores de kpolinomios. Por otra parte, a la hora de comparar la seguridad de los problemas LWE, RLWE y MLWE, la idea m´ as extendida es que cuanto m´ as estructurado sea un ret´ ıculo, menos seguridad ofrecer´ a, precisamente porque la existencia de tal estructura permitir´ a ataques m´ as eficientes. Finalmente, es digno de destacar que tanto en el caso del RLWE como del MLWE, dado que se trabaja con polinomios, la operaci´ on b´ asica en las propuestas postcu´ anticas basadas en ret´ ıculos es el producto ordinario de polinomios. Para cada uno de los ncoeficientes afectados en este producto son necesarias nmultiplicaciones. Por ello, su complejidad es On2y para valores grandes de neste c´ omputo es muy costoso. Debido a esta complejidad computacional, es fundamental disponer de un algoritmo que lleve a cabo tal multiplicaci´ on de modo eficiente. Por este motivo se suele recurrir a la transformada de teor´ ıa de n´ umeros o NTT (Number Theoretic Transform). Esta transformada es un algoritmo eficiente que lleva a cabo el producto de polinomios y es, esencialmente, una transformada discreta de Fourier (Discrete Fourier Transform) en un cuerpo finito Fq. Si se considera qprimo, la dimensi´ on del ret´ ıculo, n, sea una potencia de 2yq≡1 (m´od 2n), la complejidad de la multiplicaci´ on de polinomios haciendo uso de la NTT se reduce a O(nlog n). III. FIRMAS POSTCU´ ANTICAS BASADAS EN RET´ ICULOS: DILITHIUM Y FALCON En esta secci´ on se incluyen las principales caracter´ ısticas de los dos esquemas de firma, basadas en ret´ ıculos, que se han analizado: CRYSTALS-Dilithium y FALCON. An´alisis comparativo de las firmas digitales postcu´anticas basadas en ret´ıculos 405 III-A. CRYSTALS-Dilithium CRYSTALS-Dilithium, o simplemente Dilithium, es uno de los dos esquemas de firma basados en ret´ ıculos incluidos en la cuarta ronda del NIST [11]. Puede considerarse como uno de los tres est´ andares de firma electr´ onica, dado que el NIST ya ha publicado el borrador de este esquema [12], denot´ andolo como ML-DSA, y se espera que a lo largo de 2024 se publique la versi´ on definitiva del mismo. Dilithium, es un esquema de firma digital que se basa en la firma de Fiat-Shamir [13] y fue propuesto por Ducas et al. en [14]. Su seguridad se fundamenta en la fortaleza del problema MLWE y del problema MSIS. Dado que Dilithium usa el mismo m´ odulo y anillo para todos los conjuntos posibles de par´ ametros, es relativamente f´ acil de implementar y, como se ver´ a m´ as adelante, presenta un rendimiento equilibrado entre los tama˜ nos de las claves y el de la firma y es eficiente en la ejecuci´ on de los tres algoritmos de los que consta: generaci´ on de claves, elaboraci´ on de la firma y verificaci´ on de la firma. Presentaremos, de forma esquem´ atica, cada uno de estos tres algoritmos de modo que se aprecien las diferentes operaciones y c´ omputos que cada uno de ellos lleva a cabo. No entraremos a detallar las diferentes subrutinas de estos algoritmos por razones de espacio. No obstante, el lector interesado puede recurrir a la propuesta original de Dilithium [8] para obtener m´ as detalles. El Algoritmo 1 lleva a cabo la generaci´ on de las claves, tanto de la p´ ublica, pk, como de la privada, sk. Para ello, se genera una matriz Ade tama˜ no k×lcuyas entradas pertenecen al anillo de polinomios Rq=Zq[x]/⟨xn+ 1⟩, con q= 223− 213+1 yn= 256. Luego de calcular dos vectores aleatorios, s1ys2, de modo que cada coeficiente de tales vectores es un elemento de Rqcon coeficientes peque˜ nos y de tama˜ no, a lo sumo, η. Por ´ ultimo, se determinan la clave p´ ublica, pk, y la clave privada, sk. Algoritmo 1 Dilithium: Generaci´ on de claves 1. A←RRk×l q 2. (s1, s2)←RSl η×Sk η 3. t:= As1+s2 4. pk = (A, t) 5. sk = (A, t, s1, s2) 6. return (pk, sk) Para la elaboraci´ on de la firma (v´ ease el Algoritmo 2), se genera un vector de enmascaramiento del polinomio, y, con coeficientes menores que γ1. El firmante determina Ayy define los bits de orden superior como w1. Cada coeficiente αen Ayse puede escribir como α=w1·2γ2+w0donde |w0| ≤ γ2. El desaf´ ıo cse crea como el hash del mensaje yw1. La salida ces un polinomio en Rqcon exactamente τcoeficientes iguales a ±1y el resto igual a 0. La firma se calcula como z=y+cs1. Como entrada al algoritmo se consideran la clave privada y el mensaje a firmar: sk, M. Por ´ ultimo, el Algoritmo 3 muestra el proceso para la verificaci´ on de la firma. Para ello se calcula w′ 1como los bits de orden superior de Az−ct y se acepta la firma como v´ alida si todos los coeficientes de zson menores que γ1−βy si c es el hash del mensaje y w′ 1. N´ otese que Az−ct =Ay−cs2, Algoritmo 2 Dilithium: Elaboraci´ on de la firma digital 1. z:= ⊥. 2. while z=⊥ a)y←Sl γ1−1 b)w1:= HighBits(Ay, 2γ2) c)c∈Bτ:= H(M||w1) d)z:= y+cs1 3. if ||z||∞≥γ1−β 4. or ||LowBits(Ay−cs2,2γ2)|| ≥ γ2−β 5. then z:= ⊥ 6. return σ= (z, c). por lo que basta con probar que HighBits(Ay, 2γ2) = HighBits(A−cs2,2γ2). Toda firma v´ alida cumple que ||LowBits(Ay−cs2,2γ2)||∞< γ2−β. Adem´ as, como los coeficientes de cs2son m´ as peque˜ nos que β, es claro que sumar cs2no es suficiente para aumentar cualquier coeficiente de orden inferior para que tenga una magnitud de al menos γ2. Algoritmo 3 Dilithium: Verificaci´ on de la firma digital 1. w′ 1:= HighBits(Az −ct, 2γ2) 2. if c=H(M||w′ 1)and coeffs(z)< γ1−β 3. then return “Firma v´ alida” 4. else return “Firma inv´ alida” III-B. FALCON FALCON (FAst-Fourier Lattice-based COmpact signatures over NTRU) es uno de los tres esquemas de firma digital seleccionado por el NIST despu´ es de la tercera ronda [6]; si bien, al igual que Dilithium, su seguridad se basa en un tipo de problema definido sobre ret´ ıculos, en este caso, el problema es el SIS sobre ret´ ıculos NTRU [9]. El dise˜ no de FALCON sigue el enfoque de “resume-y- firma”. Adem´ as, hace uso de la reducci´ on de seguridad de NTRU [15] y de una implementaci´ on pr´ actica de la propuesta GPV (Gentry-Peikert-Vaikuntanathan) sobre ret´ ıculos NTRU [16]. FALCON, como la mayor parte de los esquemas de firma digital, consta de tres algoritmos: generaci´ on de claves, elaboraci´ on de la firma y verificaci´ on de la misma. A continuaci´ on se presenta cada uno de ellos de forma esquem´ atica. Adem´ as, la estructura subyacente a FALCON est´ a definida por el anillo Rq=Z[x]/⟨ϕ⟩, donde ϕ=xn+ 1 el polinomio ciclot´ omico con n= 2k. El Algoritmo 4 muestra c´ omo generar tanto la clave p´ ublica, pk, como privada, sk. El algoritmo utiliza tres subrutinas que, por razones de espacio, no entramos a detallar pero que el lector puede consultar en la documentaci´ on de referencia [9]. Estas son: NTRUGen, FFT y ffLDL∗. NTRUGen genera los cuatro polinomios NTRU que cumplen la siguiente ecuaci´ on: fG −gF = 0 (m´od ϕ),(1) E. Iglesias Hern´andez, L. Hern´andez ´ Alvarez, L. Hern´andez Encinas and J. I. S´anchez Garc´ıa 406 donde f, g, F, G ∈Rq. Es de destacar que los polinomios gyfobtenidos por NTRUGen se generan aleatoriamente y deben verificar determinadas condiciones. Una de ellas es que se pueda calcular la clave p´ ublica h=gf−1(m´od ϕ, q). Adem´ as, hay otra condici´ on que afecta a los polinomios gy fque est´ a relacionada con la longitud de las firmas. NTRUGen incluye la funci´ on NTRUSolve que permite calcular otros dos polinomios, cortos, GyFde modo que verifiquen la ecuaci´ on (1). Algoritmo 4 Falcon: Generaci´ on de claves (ϕ, q) 1. f, g, F, G ←NTRUGen(ϕ, q) 2. B←g−f G−F 3. ˆ B←FFT(B) 4. G←ˆ B׈ B∗ 5. T←ffLDL∗(G) 6. for each leaf of Tdo 7. leaf value ←σ/√leaf value 8. sk ←(ˆ B, T) 9. pk ←gf−1(m´od q) 10. return (pk, sk) La elaboraci´ on de la firma se lleva a cabo tal y como se presenta en el Algoritmo 5. Este algoritmo emplea como entrada el mensaje a firmar, M, la clave privada, sk, y el valor ⌊β2⌋. Adem´ as, hace uso de las funciones HashToPoint, ffSampling, invFF y Compress. Algoritmo 5 Falcon: Elaboraci´ on de la firma (M, sk, ⌊β2⌋) 1. r← {0,1}320 2. c←HashToPoint(r||M, q, n) 3. z←ffSamplingn(f, T ) 4. s′= (t−z)ˆ B 5. while ||s′|| >⌊β2⌋do 6. (s1, s2)←invFF(s′) 7. s←Compress(s2,8·sbytelen −328) 8. return σ= (r, s) El Algoritmo 6 lleva a cabo la verificaci´ on de la firma digital y utiliza las funciones HashToPoint y Decompress. Sus entradas son el mensaje, M, la firma digital correspondiente, σ, la clave p´ ublica, pk, y el valor ⌊β2⌋. Algoritmo 6 Falcon: Verificaci´ on de la firma (M, σ, pk, ⌊β2⌋) 1. c←HashToPoint(r||M, q, n) 2. s2←Decompress(s, 8·sbytelen −328) 3. if s2=⊥ 4. then return “Rechazo” 5. s1←c−s2h(m´od q) 6. if ||(s1, s2)||2≤ ⌊β2⌋ 7. then return “Aceptaci´ on” 8. else return “Rechazo” IV. AN´ ALISIS Y RESULTADOS OBTENIDOS Aunque el NIST ya haya publicado el borrador del est´ andar para ML-DSA (Dilithium), no vamos a comparar esta versi´ on con la de FALCON, dado que el borrador de este ´ ultimo no ha sido publicado. As´ ı pues, en este trabajo vamos a utilizar la propuesta de Dilithium y la de FALCON que pasaron a la cuarta ronda del NIST y cuyas implementaciones han sido publicadas. Como ya hemos mencionado, Dilithium se basa en los problemas MSIS y MLWE para prevenir la falsificaci´ on de las firmas y la recuperaci´ on de claves, respectivamente. Por su parte, FALCON basa su seguridad en la versi´ on no modular de SIS para su dise˜ no esquem´ atico y en el uso de ret´ ıculos NTRU, que tambi´ en le confieren una gran compacidad. Por otra parte, Dilithium proporciona conjuntos de par´ ametros que responden a los niveles de seguridad de fuerza bruta 2, 3 y 5, y FALCON solo presenta dos versiones para alcanzar los niveles 1 y 5, que a veces se denominan FALCON-512 y FALCON-1024. Por lo tanto, para extraer conclusiones m´ as generales, la comparaci´ on que hemos realizado considera todos los conjuntos de par´ ametros de cada esquema, dado que s´ olo considerar solo el nivel m´ as alto de seguridad (el ´ unico com´ un de ambas propuestas) no ser´ ıa tan representativo. IV-A. Software y arquitectura empleados Los resultados del rendimiento que se dan para cada propuesta, en su documentaci´ on original, se obtienen utilizando los criterios y la arquitectura que cada grupo desarrollador ha considerado oportuno. Este hecho es muy destacable y a tener en cuenta dado que, por ejemplo, FALCON utiliza muestreos sobre distribuciones no uniformes y tambi´ en una aritm´ etica de coma flotante cuyo rendimiento est´ a influenciado, en gran medida, por el procesador utilizado. En cualquier caso, el c´ odigo de referencia utilizado para esta comparaci´ on pertenece a la librer´ ıa de software LIBOQS (LIbrary Open-Quantum-Safe), que es una biblioteca de c´ odigo abierto escrita en lenguaje C y que incluye los principales algoritmos criptogr´ aficos poscu´ anticos, en particular los dos esquemas de firma considerados en este trabajo. LIBOQS puede ser utilizada en los sistemas operativos Linux, Windows y macOS y es compatible con varias arquitecturas y compiladores. Todas las implementaciones en esta librer´ ıa se derivan de los c´ odigos de referencia optimizados y enviados por los autores en la convocatoria de estandarizaci´ on del NIST. Por lo tanto, hemos utilizado en esta comparativa el c´ odigo est´ andar optimizado contenido en esta biblioteca. Adem´ as de emplear la misma librer´ ıa, con el fin de obtener una comparaci´ on significativa, hemos considerado la misma arquitectura para los dos esquemas de firma y hemos utilizado la prueba disponible en el c´ odigo dado para medir los tama˜ nos (en bytes) de las claves y la firma y el tiempo medio de ejecuci´ on de cada procedimiento (en ciclos de reloj y microsegundos µ-sec). Todos los resultados que se muestran en este an´ alisis se han obtenido empleando un procesador Intel Core i7-4790 a 3,60 GHz y con sistema operativo Linux. IV-B. Comparaci´ on en tama˜ nos de datos Los tama˜ nos de la clave p´ ublica, la clave privada (secreta) y la firma de cada algoritmo permiten una comparaci´ on de seguridad, ya que los rendimientos muestran la cantidad de datos (y el tama˜ no del secreto) necesarios para alcanzar un determinado nivel de seguridad. Estos datos se obtuvieron de la documentaci´ on de respaldo enviada al NIST por los An´alisis comparativo de las firmas digitales postcu´anticas basadas en ret´ıculos 407 desarrolladores de Dilithium [17] y FALCON [18]. Los resultados que hemos obtenido acerca de los tama˜ nos de los datos mencionados, para cada esquema, se muestran en la Tabla I. Dicha tabla incluye todos los conjuntos de par´ ametros proporcionados en las propuestas enviadas al NIST y, por lo tanto, contiene todos los niveles de seguridad disponibles para ambos esquemas. Tabla I TAMA˜ NO EN BYTES DE LAS CLAVES Y FIRMA SEG ´ UN LOS NIVELES DE SEGURIDAD DE CADA ESQUEMA DE FIRMA. Dilithium FALCON Nivel de seguridad 2 3 5 1 5 Clave p´ ublica 1312 1952 2592 897 1793 Clave privada 2528 4000 4864 7552 13953 Firma 2420 3293 4595 666 1280 Total 6260 9245 12051 9115 17026 Los tama˜ nos de las claves p´ ublica y privada y de la firma para cada uno de los niveles de seguridad de cada esquema analizado se representan gr´ aficamente en la Figura 1, para una mejor visualizaci´ on de los resultados. Figura 1. Tama˜ no de las claves y firma por niveles de seguridad (bytes). En general, todos los tama˜ nos asociados al esquema Dilithium y mostrados en la Tabla I son manejables para los tres niveles. Adem´ as, la clave p´ ublica es la que tiene menor tama˜ no, lo cual es especialmente interesante, dado que es un valor compartido. Los incrementos en tama˜ no para los datos considerados de Dilithium se comportan de manera proporcional a medida que aumenta el nivel de seguridad. La raz´ on de este comportamiento est´ a en los par´ ametros utilizados al modificar la seguridad, dado que dependen, fundamentalmente, de las dimensiones de la matriz A, al margen de la adecuaci´ on correspondiente del resto de valores a considerar. Este dise˜ no proporciona un intercambio de tama˜ nos consistente a la hora de seleccionar un nivel de seguridad u otro. Las diferencias de estos tama˜ nos entre FALCON y Dilithium son notables. Debe recordarse que el uso de ret´ ıculo de tipo NTRU en FALCON tiene como objetivo lograr que los datos sean m´ as compactos. Como se puede ver en la Tabla I, los tama˜ nos de la clave p´ ublica y de la firma son significativamente m´ as peque˜ nos que los correspondientes de Dilithium. De hecho, estos tama˜ nos son notablemente m´ as peque˜ nos incluso para el caso del nivel 5 en FALCON (FALCON-1024), cuya firma es casi la mitad del tama˜ no de la firma para la versi´ on menos segura de Dilithium. No ocurre lo mismo para el caso de la clave privada, donde es FALCON quien sale perjudicado con relaci´ on a Dilithium. Este hecho es el que permite afirmar que la suma de las longitudes de los tres valores para cada esquema hace que Dilithium salga beneficiado en los tres niveles de seguridad. En particular el total del tama˜ no requerido para el FALCON de nivel de seguridad 1 es semejante al del nivel de seguridad 3 de Dilithium. En todo caso, la notable diferencia en los tama˜ nos de las claves privadas podr´ ıa ser asumible a la vista de la reducci´ on en los tama˜ nos de la clave p´ ublica y la firma, dado que los valores que se transmiten son precisamente estos m´ as peque˜ nos; mientras que la clave privada se mantiene en secreto por su propietario. IV-C. Comparaci´ on en rendimiento Dado que los resultados de rendimiento de los algoritmos considerados, FALCON [18] y Dilithium [17], son proporcionados por los equipos desarrolladores utilizando distintos criterios, medidas y arquitecturas, el principal objetivo de esta secci´ on es mostrar algunos datos que permitan realizar una comparaci´ on m´ as adecuada, para lo que se emplear´ an criterios, medidas y arquitecturas an´ alogos. Analizamos, as´ ı, el rendimiento de cada uno de los tres algoritmos de que consta cada uno de los dos esquemas de firma basados en ret´ ıculos, esto es, generaci´ on de claves, elaboraci´ on de la firma y verificaci´ on de la misma, para todos sus niveles de seguridad. Se han realizado dos an´ alisis diferentes en cuanto al rendimiento. El primero de ellos relativo a los tiempos de computaci´ on empleados y el segundo relacionado con el consumo de la CPU. En ambos casos se ha empleado la prueba proporcionada por cada uno de los equipos desarrolladores y que fueron enviadas a la convocatoria del NIST. Como ya se ha indicado, haremos uso de las implementaciones optimizadas que se basan en las propuestas originales y que est´ an incluidas en LIBOQS. En la Tabla II se presentan los resultados obtenidos para el an´ alisis del rendimiento de tiempos medidos en microsegundos (µsec) para cada algoritmo de cada esquema de firma y cada nivel; mientras que la Tabla III muestra los resultados correspondientes para el rendimiento de uso de la CPU medidos en ciclos de reloj. Para proporcionar una comparaci´ on gr´ afica m´ as visual de los resultados obtenidos relativos al uso de CPU, se incluyen varias figuras. Los tiempos de rendimiento totales para cada propuesta (en ciclos de reloj) se presentan en la Figura 2. Por otra parte, debido a la diferencia en el n´ umero de ciclos para cada uno de los algoritmos considerados para cada uno de los dos esquemas de firma, hemos separado el algoritmo de generaci´ on de claves de los de firma y verificaci´ on. As´ ı, la Figura 3 muestra los resultados para el primero de los algoritmos y la Figura 2 presenta los valores obtenidos para los otros dos algoritmos, para los diferentes niveles de seguridad, tanto para Dilithium como para FALCON. Como se puede ver por los resultados generales mostrados en la Figura 2, FALCON es mucho menos eficiente que Dilithium. El primero tiene un tiempo de desempe˜ no mayor, hasta tal punto que la escala necesaria para medirlo no permite apreciar adecuadamente los tiempos empleados de Dilithium. E. Iglesias Hern´andez, L. Hern´andez ´ Alvarez, L. Hern´andez Encinas and J. I. S´anchez Garc´ıa 408 Tabla II RENDIMIENTO DE TIEMPO DE LOS ESQUEMAS DE FIRMA DILITHIUM Y FALCON (µSEC). CRYSTALS-Dilithium FALCON Tiempo medio de ejecuci´ on (µsec) Nivel de seguridad 2 3 5 1 5 Generaci´ on de claves 24,811 46,271 72,938 6790,418 19318,732 Firma 61,026 113,801 140,293 274,317 559,497 Verificaci´ on 24,837 42,864 69,170 43,884 87,906 Total 106,177 173,062 264,140 6996,455 19779,455 Tabla III RENDIMIENTO DE CPU DE LOS ESQUEMAS DE FIRMA DILITHIUM Y FALCON (EN CICLOS DE RELOJ). CRYSTALS-Dilithium FALCON Tiempo medio de ejecuci´ on (ciclos de reloj) Nivel de seguridad 2 3 5 1 5 Generaci´ on de claves 57143 106605 168047 15652763 44532312 Firma 140615 262256 323315 632273 1289647 Verificaci´ on 57204 98751 159387 101105 202576 Total 244699 398871 608812 16126491 45553057 Figura 2. Rendimiento total de CPU de Dilithium y FALCON por niveles. Figura 3. Rendimiento CPU para generar claves de Dilithium y FALCON. Figura 4. Rendimiento de CPU para la firma y la verificaci´ on. Por esa raz´ on, hemos separado cada uno de los algoritmos particulares (ver Figuras 3 y 4), de modo que pueda observarse la influencia de cada uno de ellos en el incremento en el tiempo para FALCON y obtener escalas m´ as apropiadas. La principal causa de esta diferencia se encuentra en el algoritmo de generaci´ on de claves (Figura 3). Como puede verse, este algoritmo provoca un impacto cr´ ıtico en los tiempos de rendimiento de FALCON. Por su parte, Dilithium s´ olo realiza operaciones simples para generar sus claves, siendo la multiplicaci´ on en el entorno de la NTT la m´ as costosa; mientras que FALCON requiere procedimientos mucho m´ as complejos. Adentr´ andonos con m´ as detalle en las causas de esta gran diferencia en el rendimiento, hemos de se˜ nalar, en primer lugar, que FALCON utiliza la soluci´ on (secreta) de una ecuaci´ on NTRU y, por tanto, el algoritmo de generaci´ on de claves debe resolver esta ecuaci´ on para poder obtener su soluci´ on. Este proceso de resoluci´ on supone realizar varias operaciones internas que contribuyen, en gran medida, a incrementar el tiempo de ejecuci´ on. Posteriormente, se calcula la clave privada (secreta) correspondiente y esto significa obtener el ´ arbol FALCON. Tambi´ en este procedimiento recursivo es largo y complejo y, por tanto, provoca el consiguiente aumento en el tiempo de ejecuci´ on. Como resultado, se tiene que la complejidad del esquema de firma FALCON acarrea un aumento muy significativo de eficiencia en t´ erminos de rendimiento. Los resultados de rendimiento del algoritmo de elaboraci´ on de firmas son m´ as f´ acilmente comparables, dado que no hay tanta diferencia como en el caso de la generaci´ on de claves. Se puede observar (Figura 4) que aunque FALCON es significativamente m´ as lento que Dilithium, el n´ umero de ciclos de reloj de ambas son m´ as cercanos. El origen de estas diferencias se deben, principalmente, a dos causas. La primera es que el tama˜ no de la clave privada de FALCON es significativamente mayor que la de Dilithium y en el proceso de elaboraci´ on de la firma se cifra el hash del mensaje haciendo uso de esta clave, por lo que FALCON requiere m´ as tiempo de ejecuci´ on. La segunda es que, adem´ as, FALCON utiliza un muestreador de trampilla (de hecho lleva a cabo un muestreo r´ apido de Fourier) que involucra el ´ arbol FALCON y un redondeo aleatorio seg´ un una distribuci´ on gaussiana discreta. Esta operaci´ on es, en realidad, el n´ ucleo del proceso An´alisis comparativo de las firmas digitales postcu´anticas basadas en ret´ıculos 409 de la elaboraci´ on de las firmas y es, claramente, m´ as compleja que las utilizadas para Dilithium, cuya operaci´ on m´ as costosa es la multiplicaci´ on en el entorno de la NTT. Estas son las razones que explican la diferencia en cuanto al rendimiento de ambos esquemas, en perjuicio de FALCON, en el algoritmo de elaboraci´ on de firmas. En los algoritmos de verificaci´ on de firma, los rendimientos de ambos esquemas son mejores que en los de su elaboraci´ on, lo que es habitual porque este algoritmo suele ser m´ as sencillo que el de la firma en s´ ı. Puede apreciarse (ver Figura 4) que en este caso, la mejora en el rendimiento de FALCON es muy notable, y los resultados son similares a los de Dilithium. Las versiones de mayor nivel de seguridad de Dilithium tienen un tiempo de verificaci´ on incluso mayor que el FALCON de menor nivel. De manera similar a lo que se observ´ o anteriormente para los tama˜ nos, esta caracter´ ıstica puede ser digna de destacar, dado que el proceso de verificaci´ on de una firma digital se puede llegar a realizar varias veces, mientras que la generaci´ on de claves solo se ejecuta una vez en un largo per´ ıodo de tiempo y la elaboraci´ on de la firma solo en contadas ocasiones. La explicaci´ on de estos resultados en la verificaci´ on de la firma es que ambos esquemas realizan operaciones muy similares: sumas, multiplicaciones y comparaciones entre variables. Por tanto, el tama˜ no de estas variables es lo que determina, en gran medida, el tiempo de ejecuci´ on. Debe tenerse en cuenta que, en este caso, no se emplea la clave privada y, aunque las claves p´ ublicas y la firma de FALCON son menores que las de Dilithium (ver Tabla I), sus tiempos en la verificaci´ on no difieren mucho de los de Dilithium, como cabr´ ıa de esperar. La raz´ on de que no exista una diferencia mayor debida a los tama˜ nos de las claves p´ ublicas y las firmas de ambos esquemas se debe a la falta de compensaci´ on en la aritm´ etica a realizar en FALCON, que es m´ as costosa que la de Dilithium. V. CONCLUSIONES El an´ alisis presentado en esta investigaci´ on sugiere que Dilithium es, en circunstancias generales y en los casos regulares de uso, un esquema de firma m´ as seguro y eficiente que FALCON. Se˜ nalamos dos razones para esta conclusi´ on. La primera es que el rendimiento es significativamente mejor, ya que la generaci´ on de claves en FALCON es muy costosa. Incluso considerando que esta generaci´ on se realiza s´ olo de vez en cuando, los resultados de Dilithium para la firma y la verificaci´ on tambi´ en son m´ as eficientes. El dise˜ no conceptual simplificado de Dilithium lo hace m´ as adecuado en t´ erminos de rendimiento. La segunda raz´ on es que, aunque los tama˜ nos de los valores de Dilithium no siempre son menores que los de FALCON, su rango es m´ as manejable y los valores de su rendimiento son proporcionales tanto a los tama˜ nos de los par´ ametros empleados como a los diferentes niveles de seguridad establecidos. Todo ello da a entender que el dise˜ no de Dilithium es m´ as compacto y su seguridad es m´ as f´ acil de ajustar a las necesidades requeridas. Por su parte, FALCON ofrece otras ventajas interesantes para ciertos casos de uso particulares, donde puede ser la mejor opci´ on; a pesar de ser m´ as complejo y ofrezca menos niveles de seguridad que Dilithium. Estos casos de uso son aquellos en los que la generaci´ on de las claves p´ ublica y privada no sea un factor determinante en cuanto al rendimiento del esquema, dado que las mismas no se generan con demasiada frecuencia y, adem´ as, son menores que las claves generadas por Dilithium. Como trabajo futuro se pretende extender este tipo de an´ alisis a otras plataformas, en particular a aquellas que tengan menor capacidad de c´ omputo que un ordenador est´ andar. Es de esperar que los resultados sean similares, en t´ erminos generales, de modo que confirmen las conclusiones obtenidas en este estudio. A la vez, este estudio permitir´ ıa tener una idea m´ as clara sobre las posibles dificultades a la hora de implementar estos esquemas de firma en dispositivos con recursos computacionales limitados, m´ as cercanos a las implementaciones pr´ acticas, como puede ser en los dispositivos empleados en la Internet de las cosas (Internet of Things o IoT). Otra cuesti´ on a considerar en el futuro ser´ ıa la de comparar los resultados obtenidos en este estudio con los obtenidos al realizar un an´ alisis similar sobre los mismos aspectos para otros esquemas de firma postcu´ anticos, no basados en ret´ ıculos, como es el caso de SPHINCS+. AGRADECIMIENTOS Este trabajo ha sido parcialmente financiado por la Agencia Estatal de Investigaci´ on (AEI) del Ministerio de Ciencia e Innovaci´ on (MCIN) y por la Uni´ on Europea NextGerationUE/PRTR en los proyectos P2QProMeTe (PID2020-112586RBI00/AEI/10.13039/501100011033, cofinanciado por el Fondo Europeo de Desarrollo Regional: FSE, FEDER y FEDER, UE); y QURSA (TED2021- 130369BC33, MCIN/AEI/10.13039/501100011033); en parte por el Proyecto ORACLE (PCI2020-120691-2, MCIN/AEI/10.13039/501100011033) y en parte por el programa de investigaci´ on e innovaci´ on Horizonte 2020 de la UE, proyecto SPIRS (Grant Agreement N° 952622). E.I.H y L.H.A. desean agradecer su apoyo a los proyectos del CSIC EFiDiP y SAIACAP, respectivamente. REFERENCIAS [1] P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, 1997, https://doi.org/10.1137/ S0097539795293172. [2] R. Rivest, A. Shamir, and L. M. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978, https://doi.org/10.1145/359340.359342. [3] N. Koblitz, “Elliptic curve cryptosytems,” Math. Comp., vol. 48, no. 177, pp. 203–209, 1987, https://doi.org/10.1090/ S0025-5718-1987-0866109-5. [4] V. S. Miller, “Use of elliptic curves in cryptography,” Lecture Notes Comput. Sci., vol. 218, pp. 417–426, 1986, https://doi.org/10.1007/ 3-540-39799-X 31. [5] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Inform. Theory, vol. 22, pp. 644–654, 1976, htpps://doi.org/10. 1109/TIT.1976.1055638. [6] NIST, “Post-quantum cryptography. Selected algorithms 2022,” On-line publication, 2022, https://csrc.nist.gov/Projects/ post-quantum-cryptography/selected-algorithms-2022. [7] P. Schwabe, R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, G. Seiler, and D. Stehle, “CRYSTALSKYBER,” Online publication, 2020, https://pq-crystals.org/kyber/index. shtml. [8] V. Lyubashevsky, L. Ducas, E. Kiltz, T. Lepoint, P. Schwabe, G. Seiler, and D. Stehle, “CRYSTALS-DILITHIUM,” Online publication, 2020, https://pq-crystals.org/dilithium/index.shtml. E. Iglesias Hern´andez, L. Hern´andez ´ Alvarez, L. Hern´andez Encinas and J. I. S´anchez Garc´ıa 410 [9] T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “FALCON,” Online publication, 2020, https://falcon-sign.info/. [10] A. Hulsing, D. J. Bernstein, C. Dobraunig, M. Eichlseder, S. Fluhrer, S.-L. Gazdag, P. Kampanakis, S. Kolbl, T. Lange, M. M. Lauridsen, F. Mendel, R. Niederhagen, C. Rechberger, J. Rijneveld, P. Schwabe, and J.-P. Aumasson, “SPHINCS+,” Online publication, 2020, https:// sphincs.org/. [11] NIST, “PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates,” Online publication, 2022, https://csrc.nist.gov/News/2022/ pqc-candidates-to-be-standardized-and-round-4. [12] ——, Module-Lattice-Based Digital Signature Standard, National Institute of Standard and Technology, NIST FIPS 204, 2023, https://doi. org/10.6028/NIST.FIPS.204.ipd. [13] V. Lyubashevsly, “Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures,” Lecture Notes Comput. Sci., vol. 5912, pp. 598–616, 2009, https://doi.org/10.1007/978-3-642-10366-7 35. [14] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehl´ e, “CRYSTALS-Dilithium: A lattice-based digital signature scheme,” in IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018, pp. 238– 268, https://doi.org/10.13154/tches.v2018.i1.238-268. [15] D. Stehl´ e and R. Steinfeld, “Making NTRU as secure as worst-case problems over ideal lattices,” in Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology - EUROCRYPT 2011, Lecture Notes Comput. Sci., vol. 6632, 2011, pp. 27–47, https://doi.org/10.1007/978-3-642-20465-4 4. [16] L. Ducas, V. Lyubashevsky, and T. Prest, “Efficient identity-based encryption over NTRU lattices,” in Proc. International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology - ASIACRYPT 2014, Lecture Notes Comput. Sci., vol. 8874, 2014, pp. 22–41, https://doi.org/10.1007/978-3-662-45608-8 2. [17] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevesky, P. Schwabe, G. Seiler, and D. Stehl´ e, “CRYSTALS-Dilithium: Algorithm specifications and supporting documentation,” NIST, Tech. Rep., 2020, https://pq-crystals. org/dilithium/data/dilithium-specification-round3-20210208.pdf. [18] P. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “FALCON: Fast-Fourier lattice-based compact signatures over NTRU,” NIST, Tech. Rep., 2018, https://falcon-sign.info/falcon.pdf. An´alisis comparativo de las firmas digitales postcu´anticas basadas en ret´ıculos 411