LAS MATEMTICAS EN LA CRIPTOLOGA Paz Morillo Matemtica Aplicada IV. Universidad Politcnica de Catalunya 1.

INTRODUCCIN Aunque se puede afirmar que la Criptologa es casi tan antigua como la escritura, el nacimiento de lo que se conoce como Criptologa cientfica se puede situar en la segunda guerra mundial, y es la matematizacin de la Criptologa el hecho que marca el inicio de esta disciplina como ciencia. As, uno de los momentos clave que se puede destacar en este proceso, es la aparicin de la Teora Matemtica de la Informacin de Shannon y su trabajo sobre el secreto perfecto en los sistemas criptogrficos [Sh49].

Clsicamente, la Criptologa se ha articulado en dos vertientes: la Criptografa, que se encarga del diseo de sistemas de escritura secreta, y el Criptoanlisis, que estudia las debilidades de estos sistemas con el fin de conseguir el secreto. La Criptologa se ocupa no solamente de la escritura secreta sino tambin de otros aspectos directamente relacionados con las nuevas tecnologas y las comunicaciones. As, la Criptografa se encarga de problemas relacionados con la seguridad de las comunicaciones y el Criptoanlisis de la rotura de dicha seguridad. De hecho, el gran avance de la Criptologa en las ltimas dcadas se debe principalmente a la existencia de ordenadores cada vez con mayor potencia de clculo y a la generalizacin de las comunicaciones y la utilizacin de los recursos telemticos para transacciones, gestiones o negocios, que han potenciado el uso de la Criptografa por parte de un nmero de usuarios cada vez mayor. En efecto, ltimamente el volumen de informacin secreta que se debe almacenar o transmitir ha aumentado considerablemente: transacciones bancarias, comercio electrnico, informacin sanitaria, En este entorno, un rasgo en comn entre la Criptologa y otros campos de la informtica y de las comunicaciones es que reas de las matemticas que eran consideradas puras o poco aplicadas, han resultado ser una pieza clave en avances tecnolgicos muy importantes. El objetivo de este artculo es presentar algunos de los problemas que estudia la Criptologa, desde los ms divulgados hasta otros prcticamente desconocidos pero de aplicaciones importantsimas. Tambin se pretende mostrar cmo diferentes ramas de las matemticas intervienen en el estudio y resolucin de esos problemas. Con este fin, el artculo comienza por una visin general de a qu se dedica, qu problemas ataca la Criptologa y cmo los resuelve utilizando matemticas, para pasar despus a estudiar con detalle un problema menos conocido para aqul que no se dedique a la investigacin en estos temas, y mostrar finalmente su solucin. 1

Este trabajo se divide en tres secciones. En la Seccin 2 se presentan las principales ideas de la Criptografa de clave pblica, cuya introduccin en el ao 1976 supuso una revolucin en el diseo de dos sistemas criptogrficos: esquemas de cifrado de mensajes y esquemas de firma digital. La Seccin 3 trata sobre esquemas para compartir secretos, donde un secreto se reparte entre un grupo de usuarios de manera que slo los conjuntos de usuarios autorizados pueden recuperar su valor. Una aplicacin de estos esquemas la podemos encontrar, por ejemplo, en la necesidad de repartir el valor de una clave secreta, con cuyo conocimiento pueden tomarse decisiones o realizar acciones de especial trascendencia. En estas dos primeras secciones se presentan dos herramientas criptogrficas de naturaleza muy distinta. En efecto, mientras que en los criptosistemas de clave pblica la seguridad est basada en la dificultad computacional de problemas matemticos como, por ejemplo, la descomposicin en factores primos de un nmero entero de gran tamao, la seguridad de los esquemas para compartir secretos es incondicional, es decir, no depende de los recursos computacionales del usuario. Otra diferencia importante son las herramientas matemticas utilizadas: mientras que en los sistemas de clave pblica la Teora de Nmeros, los Cuerpos Finitos y la Teora de la complejidad juegan un papel fundamental, en la comparticin de secretos intervienen principalmente la Combinatoria y el lgebra Lineal. Finalmente, en la Seccin 4 se presenta brevemente la computacin multiparte segura. El problema que se trata es el de n participantes (usuarios, ordenadores, procesadores,) que quieren calcular el valor de una funcin de sus entradas de forma segura. Aqu seguridad significa que los datos de cada participante permanecern secretos en todo momento, y el resultado de la funcin debe de ser correcto y obtenido por todos los participantes, incluso en presencia de algunos participantes con comportamiento incorrecto. La computacin multiparte tiene aplicaciones tan importantes como la votacin electrnica, estudios estadsticos de datos confidenciales, gestin de claves de chats en internet 2. CRIPTOGRAFA DE CLAVE PBLICA La Criptografa de clave pblica, introducida por Diffie y Hellman [DH76], ha sido el punto de inflexin ms importante en la Criptologa.

Anteriormente slo se utilizaba la Criptografa de clave privada, en la que se permite la comunicacin secreta entre dos usuarios que comparten una clave de trabajo. La misma clave se usa para cifrar y para descifrar los mensajes, y el emisor y el receptor han de acordar la clave secreta a travs de un canal de comunicacin seguro. sta es la principal dificultad de los sistemas de clave privada. Por ejemplo, en una red de comunicacin con n usuarios, el nmero de claves secretas es n(n2

1)/2, y as, en una red de 1000 usuarios se requeriran 499.500 conexiones totalmente seguras para poder distribuir las claves. Sin embargo, en la Criptografa de clave pblica, cada usuario posee una clave pblica y una privada. Cuando un usuario quiere enviar un mensaje cifrado, lo hace utilizando la clave pblica del receptor y ste es el nico que puede descifrar dicho mensaje, usando para ello su clave secreta. Se puede imaginar que cada usuario tiene un buzn donde cualquiera puede depositar un mensaje, y l es el nico que tiene la llave para abrirlo.

Los criptosistemas de clave pblica se basan en las llamadas funciones unidireccionales con trampa, funciones fciles de calcular pero cuya inversa es difcil de obtener (se requiere de un tiempo excesivo, utilizando el mejor algoritmo conocido y con los mejores recursos computacionales), salvo que se conozca una cierta informacin adicional. As, la seguridad se llama condicional: se basa en la capacidad computacional de los participantes. De hecho, la seguridad incondicional es imposible en este contexto, ya que un participante con recursos computacionales ilimitados siempre podra, a la vista del mensaje cifrado, y dado que el algoritmo de cifrado es pblico, probar todos los posibles valores del texto hasta hallar aquel cuyo cifrado coincidiera con el observado. La seguridad de los criptosistemas de clave pblica se basa pues, en la dificultad de resolver algn problema. Por ejemplo, la seguridad del criptosistema RSA [RSA78] se basa en la dificultad de factorizar un nmero entero producto de dos primos de gran tamao. Otros criptosistemas se basan en la dificultad del clculo del logaritmo discreto en ciertos grupos finitos [E85], como el grupo multiplicativo de un cuerpo finito o el grupo de puntos de una curva elptica. Ms adelante se ver el funcionamiento de dos criptosistemas de clave pblica. En la prctica, la velocidad de cifrado de los sistemas de clave pblica es mucho menor que los de clave privada. Por tanto, para cifrar grandes volmenes de informacin se usan sistemas de clave privada (por ejemplo al emitir TV en canales de pago). El criptosistema de clave pblica se usa para transmitir, de forma secreta, la clave privada de trabajo a travs de canales inseguros, resolviendo as el problema comentado de establecer claves secretas en ausencia de canales seguros de comunicacin. 2.1 El criptosistema RSA

En el ao 1978 Rivest, Shamir y Adleman pusieron en prctica por primera vez, la idea de Criptografa de clave pblica introducida por Diffie y Hellman en 1976.

Sea Zn el conjunto de restos que se obtienen al dividir nmeros enteros entre n. Por ejemplo, Z17={0,1,2,...,15,16}. Si dos enteros a y b dan el mismo resto al dividir entre n, escribimos a=b (mod n). As, 19=2 (mod 17), y tambin -21=13 (mod 17) porque -21=(-2)*17+13. En el sistema de cifrado RSA cada participante elige un nmero entero producto de dos primos grandes, n=pq, y elige dos enteros e,d tal que ed=1 (mod (n)), siendo la funcin de Euler, y por tanto (n)=(p-1)(q-1). La clave pblica del participante ser (n,e) y la clave privada (p,q,d). El mtodo de cifrado y descifrado se basa en el Teorema de Euler, que afirma que si x es un entero primo con n, entonces x(n)=1 (mod n). Cuando A quiere enviar un mensaje cifrado a B, mira su clave pblica (n,e) y codifica el mensaje de forma que sea un elemento x Zn . El mensaje cifrado que A enva a B es c=xe (mod n). Para descifrar el mensaje, B calcula cd (mod n). Por el Teorema de Euler vemos que x=xed (mod n). Observemos que para descifrar es necesaria la clave privada d, pero si un adversario fuera capaz de factorizar n tendra (n) y podra hallar d y descifrar todos los mensajes dirigidos a B. Se ha demostrado que encontrar la clave privada d de un usuario es tan difcil como factorizar n. Ms concretamente, cualquier algoritmo que permita calcular d a partir de n y e, se puede utilizar como subrutina en un algoritmo probabilstico eficiente para factorizar n.

Sin embargo, podra ser que un mensaje se pudiera descifrar sin tener que calcular el valor d. Se tratara de buscar alguna estrategia que permitiera deducir el valor de x, a partir del conocimiento de xe mdulo n. No se ha demostrado que romper el RSA sea equivalente a factorizar, y algunos trabajos indican justamente lo contrario [BV98] y [Co98]. Para evidenciar la dificultad de la cuestin, vale la pena comentar que existen criptosistemas del tipo RSA en los que s se demuestra que hay equivalencia entre su rotura y la factorizacin del entero n [Sc98]. En la actualidad, el tamao de los primos p y q que se considera seguro es de 160 cifras decimales, aunque se empieza a considerar que tal vez esta medida ya no es suficientemente segura. 2.2 Criptosistemas basados en el logaritmo discreto

Otro problema difcil utilizado en el diseo de criptosistemas de clave pblica es el logaritmo discreto. Esto es, dados y en un grupo finito, hallar un entero a tal que a =. Se dice que a es el logaritmo de en base , es decir a=log (). 4

El criptosistema propuesto por ElGamal en 1985 [E85], se basa en la dificultad de resolver el problema del logaritmo discreto en el grupo multiplicativo Zp* (los elementos de Zp distintos del 0), siendo p un primo adecuado. Concretamente, teniendo en cuenta los mtodos y la capacidad de clculo actual, p ha de ser un primo de ms de 150 dgitos decimales y tal que p-1 tenga un factor primo grande. En el criptosistema de ElGamal, cada usuario elige un primo p con las caractersticas mencionadas y un elemento cuyas potencias generen el grupo multiplicativo Zp*. Tal existe y es fcil de encontrar. Adems, elige un entero a tal que a Zp-1 y calcula =a. La clave pblica del usuario es (p,, ) y su clave secreta es a. Para cifrar un mensaje m se elige al azar un elemento r Zp-1 (que se mantiene secreto) y se calcula c=( r,m r). El receptor legtimo puede descifrar el mensaje usando su clave privada a. En efecto, dado el mensaje cifrado c=(c1,c2), se tiene que m=c2/(c1)a. Todos los clculos se realizan en el grupo Zp*. A diferencia del criptosistema RSA, el criptosistema ElGamal no es determinista. De hecho, el mensaje cifrado depende del valor del nmero aleatorio r, y as hay muchos cifrados diferentes correspondientes a un mismo mensaje en claro. Observemos que se puede construir un criptosistema como ElGamal en cualquier grupo finito en el que el problema del logaritmo discreto sea intratable. Por ejemplo, Koblitz [K87] y Miller [M85] propusieron el uso del grupo de puntos de una curva elptica. 2.3 Firmas electrnicas

Una de las ventajas de la Criptografa de clave pblica es que permite implementar otras aplicaciones aparte del cifrado de mensajes, y las firmas electrnicas o los sistemas de identificacin son dos de ellos. Veamos, por ejemplo, cmo utilizar el criptosistema RSA para la firma de mensajes. Supongamos que el usuario A con clave pblica (n,e) y privada (p,q,d) quiere enviar a B un mensaje m firmado. Para ello, el usuario A calcula =md (mod n) y enva (m, ) (recordemos que slo A puede calcular , dado que para ello se necesita su clave secreta). Luego B puede verificar que A ha firmado el mensaje comprobando que e = m (mod n). Una firma debe estar ligada al mensaje que se firma. En un documento escrito la firma est en la misma hoja que el mensaje. En la firma electrnica, la firma debe depender del mensaje y, adems, cualquiera ha de poder verificarla. Observemos que en RSA la firma se verifica utilizando la clave pblica de A. En el criptosistema de ElGamal, dado que no es determinista, la firma no es posible de la manera antes descrita. Sin embargo, en el mismo trabajo de 1985, ElGamal presenta un esquema de firma electrnica basado en la dificultad del clculo del logaritmo discreto. Una modificacin de este esquema, el Digital Signatura Standard (DSS) se adopt como estndar el ao 1994 por el National Institute of Standards and Technology de Estados Unidos [DSS94]. 3. ESQUEMAS PARA COMPARTIR SECRETOS Supongamos que en un colectivo se necesita el acuerdo de un grupo determinado de personas para emprender alguna accin o tomar alguna decisin. Esta situacin se resuelve con un esquema para compartir secretos. En un esquema para compartir secretos se reparte el valor de un secreto en fragmentos entre los participantes de un conjunto P, de forma que slo los subconjuntos autorizados pueden reconstruir el secreto a partir de sus fragmentos. 5

Los esquemas para compartir secretos se introdujeron de forma independiente por Blackley [B79] y Shamir [S79] en 1979. La familia de subconjuntos autorizados se denomina estructura de acceso y ha de ser montona, es decir, si un subconjunto contiene un subconjunto autorizado, tambin debe ser autorizado. En un esquema para compartir secretos, con estructura de acceso y conjunto de posibles secretos K, a partir de un valor secreto k K y de una cierta eleccin aleatoria, cada participante Pi recibe un fragmento si S donde S denota el conjunto de posibles fragmentos, de manera que: 1. Los subconjuntos de P autorizados pueden reconstruir el valor del secreto k a partir de sus fragmentos. Es decir, si Aexiste un nico valor posible k para los fragmentos si dados. 2. Los participantes de un subconjunto no autorizado no pueden obtener ninguna informacin sobre el secreto a partir del valor de sus fragmentos. Es decir, si A todos los valores posibles del secreto son igualmente probables, incluso conociendo los fragmentos si de todos los PiA. 3.1 El esquema de Shamir El esquema de Shamir es, como ya se ha mencionado, uno de los primeros propuestos. La estructura de acceso est formada por los subconjuntos con al menos t participantes de un conjunto con n participantes. Los esquemas con estructura de acceso de este tipo se denominan esquemas de umbral (t , n) .

Consideremos el conjunto de participantes P={P1,P2,,Pn} y un entero t tal que 1 t n. El valor secreto que se reparte es un elemento del cuerpo finito Zp*, siendo p primo. En la fase inicial, a cada participante se le asigna un elemento xi del cuerpo Zp*, donde los valores xi son no nulos y diferentes dos a dos. Los valores xi son pblicos. Para distribuir un secreto k se toma al azar un polinomio de grado menor o igual que t-1, p(x), tal que p(0)=k. Y cada participante recibe como fragmento si=p(xi). Debido a que el valor del secreto y los coeficientes del polinomio han de mantenerse secretos, esta fase la lleva a cabo un participante especial D llamado distribuidor. Veamos cmo efectivamente el esquema de Shamir es un esquema para compartir secretos, de umbral (t,n). Cualquier conjunto de t participantes puede obtener el polinomio p y, por tanto, el secreto p(0). Por ejemplo, esto puede hacerse utilizando la interpolacin de Lagrange que da la frmula para calcular el nico polinomio de grado menor o igual que t-1, que pasa por t puntos conocidos (polinomio interpolador). Por otra parte, si slo se conocen t-1 fragmentos, para cualquier posible 6

valor del secreto k, existe un nico polinomio q(x) con grado menor o igual que t-1 tal que q(0)=k y q(xi)=si para todo i=1,,t-1. Por tanto, los fragmentos de los participantes de un subconjunto no autorizado no dan ninguna informacin sobre el valor del secreto. Veamos un ejemplo. En Z17 diseamos un esquema de umbral (3,4), los participantes son P1, P2, P3, P4 y los elementos asignados son x1=1, x2=2, x3=3, x4=6, respectivamente. El valor secreto a repartir es k=2 y el polinomio elegido por el distribuidor es p(x)=2x2-4x+2. Entonces, los fragmentos de cada participante sern s1=0, s2=2, s3=8, s4=16, respectivamente. Si ahora suponemos que se unen los participantes P1, P2 y P3 y buscan el nico polinomio que pasa por los puntos (1,0), (2,2) y (3,8) obtendrn p(x) y en el trmino independiente tendrn el secreto. En cambio, si slo se unen dos participantes, por ejemplo, P1 y P2, para cualquier valor del secreto s existe un polinomio que pasa por los puntos (1,0) y (2,2) y tiene por trmino independiente s. Efectivamente, basta tomar p(x)=9(2+s)x2+(7s-1)x+s.

Observemos que la seguridad del esquema de Shamir es incondicional, ya que no est basada en ninguna hiptesis computacional. Es decir, un subconjunto no autorizado no obtendra ninguna informacin ni con recursos computacionales infinitos. De hecho, y por definicin, esta propiedad debe tenerla cualquier esquema para compartir secretos. En muchas ocasiones, se necesita el acuerdo de los n participantes para la recuperacin del secreto compartido, y en esta situacin se necesita un esquema de umbral (n,n). Un aspecto a tener en cuenta en la comparticin de secretos es su compatibilidad con las operaciones bsicas, esto es, a partir de los fragmentos de dos secretos a y b, es conveniente poder calcular los fragmentos de su suma a+b y de un mltiplo a (en este caso se habla de esquema lineal), o de su producto ab. Es fcil ver que el esquema de Shamir es un esquema lineal. 3.2 Generacin compartida de secretos Otro tema importante en los esquemas para compartir secretos es la generacin compartida de secretos. En este caso no existe ese participante especial denominado distribuidor y el secreto se genera entre todos los participantes. Este tema es de especial relevancia en entornos en los que no existe una autoridad de confianza. Veamos un ejemplo de reparticin de un secreto generado de forma compartida. Cada participante Pi, elige un valor secreto, ri, y lo reparte mediante un esquema lineal de umbral (t,n) entre el colectivo de participantes (por ejemplo, segn el esquema de Shamir), es decir, 7

cada participante hace de distribuidor de su secreto. A continuacin, cada participante puede sumar los fragmentos obtenidos del resto de participantes y el fragmento que le corresponde de su propio secreto. Es fcil ver que la suma de los fragmentos obtenidos es el fragmento de la suma de los secretos. As el secreto que se tiene compartido, mediante un esquema de umbral (t,n), es la suma de los secretos ri generados por cada participante. Veamos un ejemplo. Supongamos tres participantes P1, P2, P3 y a cada uno le asignamos el valor igual a su ndice xi=i. Ahora cada participante elige un valor secreto, por ejemplo r1=1, r2=3, r3=-1. Vamos a suponer que las operaciones se realizan en Z17, como en el ejemplo anterior, y que el esquema es de umbral (3,3). A continuacin cada participante elige un polinomio y distribuye su secreto entre los dems participantes, tal como se ha descrito anteriormente. As por ejemplo, p1(x)=x2+x+1, p2(x)=2x2-x+3, p3(x)=3x2-1 y, en consecuencia, el participante P1 recibir los fragmentos 4 y 2 de los otros dos participantes, y obtendr el fragmento 3 de su propio secreto; P2 recibir 7 y 11, y 9 ser el fragmento de su propio secreto; y, finalmente, P3 recibir 13 y 1 y calcular 9 (fragmento de su secreto). El ltimo paso a realizar por parte de cada participante ser la suma de los fragmentos que posee, por lo que los fragmentos resultantes sern s1=9, s2=10, s3=6. Podemos comprobar que el polinomio de grado menor o igual que 2, que pasa por los puntos (1,9), (2,10), (3,6), tiene por trmino independiente el valor 3, que es el secreto generado de forma compartida como suma de los valores secretos elegidos por cada participante. En la Seccin siguiente utilizaremos la notacin [a] para una reparticin del valor a, es decir, [a] denota la coleccin de toda la informacin relacionada con a mantenida por todos los participantes. As, si M es una matriz, [M] denotar una reparticin de cada una de las coordenadas de M.
4. COMPUTACIN MULTIPARTE

La computacin multiparte segura puede definirse como el problema de n participantes que quieren calcular una funcin de sus entradas de manera segura. Aqu la seguridad significa obtencin del resultado correcto, as como privacidad de las entradas de los participantes, todo ello incluso en presencia de participantes corruptos. Concretando, tenemos entradas x1, x2, , xn , y cada jugador Pi conoce xi y se quiere calcular (y1,y2,,yn) = f(x1, x2, , xn), de manera que el jugador Pi obtendr yi pero nada ms que eso. Una completa introduccin al tema de la computacin multiparte puede hallarse en [CD05]. Veamos un ejemplo sencillo, un conjunto de 50 personas quiere conocer cul es su sueldo medio sin revelar qu cobra cada una de ellas. En este caso la funcin a calcular es la suma de las 50 entradas (sueldos de cada uno) dividida por 50. Para realizarlo de forma segura, cada uno de los trabajadores debe repartir a todos los dems un fragmento del secreto que es su sueldo. Esto se puede realizar mediante un esquema de Shamir con 50 participantes y umbral 50, es decir, esquema de umbral (50,50). Una vez hechas todas las comunicaciones, cada persona tiene un fragmento de los 50 sueldos y, en privado, puede calcular la media aritmtica de dichos fragmentos. Ahora, uniendo la informacin obtenida por cada usuario y recuperando el secreto segn se ha mostrado anteriormente en el esquema de Shamir, se obtiene el sueldo medio buscado. De forma compartida se pueden realizar operaciones ms complicadas en criptografa, subastas electrnicas, votaciones electrnicas, controles de audiencia (visitas a pginas web), Si estas operaciones no se realizan de forma compartida, deben dejarse en manos de una autoridad de confianza, lo que puede suponer un riesgo elevado para la seguridad, adems de una carga de trabajo excesiva para dicha autoridad. 8

A continuacin vamos a ver un ejemplo en el que el clculo a realizar de forma compartida pertenece al mbito del lgebra Lineal. Supongamos un nmero n de personas que buscan trabajo y un nmero m de trabajos ofertados. Para llevar a cabo la asignacin de trabajos de la manera ms satisfactoria posible se solicita a los trabajadores que manifiesten sus preferencias y esa informacin se quiere mantener en secreto. As, de forma compartida, se va a generar una matriz de preferencias en la que el nmero de filas corresponder al nmero de trabajadores y el nmero de columnas al de trabajos. En la fila i columna j se pondr un 1 si el trabajador i ha manifestado inters por el trabajo j y un 0 en caso contrario. Cada trabajador reparte su fila, por ejemplo con un esquema de umbral (n,n). Se puede demostrar que es posible un emparejamiento (trabajadores-trabajos) si y slo si esta matriz de adyacencia tiene rango mximo. As pues el problema que estamos considerando ahora consiste en: dada una matriz generada de forma compartida, saber si tiene rango mximo, de forma segura, es decir, sin revelar la matriz. 4.1 Rango de una matriz compartida Este es un ejemplo de clculo en el que la exigencia de la seguridad de los datos hace que los algoritmos conocidos, y considerados los mejores, dejen de serlo. Efectivamente, aunque los clculos del Mtodo de eliminacin de Gauss para calcular el rango de una matriz pueden realizarse de forma compartida y segura, este algoritmo es poco o nada eficiente en este contexto. En cada paso de la eliminacin de Gauss, cada uno de los participantes debe comunicarse con todos los dems para intercambiar la informacin obtenida. Es decir, el nmero de rondas del algoritmo depende del nmero n de trabajadores. Se entiende por ronda una etapa en la que cada participante se comunica con los restantes para transmitir los resultados de los clculos hechos privadamente. El nmero de rondas es el principal parmetro para medir la complejidad de un algoritmo de computacin multiparte segura. Por tanto, va a ser necesario considerar otro algoritmo para hallar el rango de una matriz compartida. Presentamos a continuacin un mtodo para el clculo distribuido seguro del rango de una matriz que funciona con un nmero constante de rondas, esto es, independiente del tamao de la matriz. El algoritmo para saber si una matriz compartida, no cuadrada, tiene rango mximo se basa en los algoritmos que se explicarn a continuacin. 4.1.1 Clculo compartido del determinante de una matriz invertible Sea A una matriz compartida, de la que se sabe que el determinante es no nulo. Se quiere calcular el determinante de A de forma segura, es decir, sin revelar nada ms sobre la matriz. Para ello se genera de forma compartida entre todos los participantes otra matriz aleatoria B, tambin invertible, y su determinante. Un protocolo que permite generar una matriz y su determinante ([B],[det(B)]), puede hallarse en [CD01]. A continuacin por un mtodo de inversin segura, por ejemplo el mtodo de Bar-Ilan y Beaver [BB89], se calcula el inverso del determinante de B, [det(B)-1] . En el siguiente paso se calculan los fragmentos del producto de matrices BA, a partir de los fragmentos de ambas, [BA]=[B][A]. Se calcula y se hace pblico el producto BA.

Todos los participantes pueden calcular el determinante det(BA) y con el conocimiento de los fragmentos del inverso del determinante de B, se obtienen ya los fragmentos del determinante de A (haciendo uso de la linealidad del esquema considerado). Observemos que el conocimiento de BA y de su determinante, no da ninguna informacin sobre la matriz A, si se supone que A es invertible. Si estamos en el caso que A pudiera ser no invertible, al hacerse pblica la matriz BA, se filtrara informacin sobre A (por ejemplo, su rango) que debera ser secreta. 4.1.2 Clculo compartido del determinante de una matriz A Ahora se supone desconocido si A es una matriz invertible o no. El protocolo para calcular de forma compartida y segura su determinante consta de los siguientes pasos. Primero se generan de forma segura valores x0,x1,x2,xn aleatorios (siendo n el tamao de A). Notemos que el determinante de A-zId es 0 slo si z es un autovalor de la matriz A, y como mximo A tiene n autovalores, siendo n el tamao de la matriz. As, con alta probabilidad las matrices Ai=A-xiId son invertibles y su determinante puede calcularse con el protocolo explicado en el apartado anterior. Una vez realizado este clculo se tienen n+1 valores del polinomio caracterstico de A, q(x)=det(A-xId), que tiene grado n, y realizando de forma privada una interpolacin se obtiene el valor del polinomio caracterstico en el 0, que coincide con el determinante de A, q(0)=det(A). 4.1.3 Clculo compartido del rango mximo de A Supongamos ahora que la matriz A es no cuadrada, entonces A tiene rango mximo si y slo si el determinante de la matriz de Gramm ATA o AAT es no nulo, segn sea mayor el nmero de columnas que de filas o viceversa. As pues, para saber si una matriz compartida tiene rango mximo basta aplicar el algoritmo del punto 4.1.2 a la matriz ATA o AAT. Debemos tener en cuenta que la condicin necesaria y suficiente de rango mximo de una matriz no cuadrada es vlido si estamos trabajando con elementos del cuerpo de los reales y, sin embargo, no tiene porqu ser cierto sobre cuerpos finitos. En este ltimo caso, debe aplicarse el argumento mencionado, no sobre la matriz A sino sobre una matriz A obtenida como el producto de A por una matriz diagonal de la forma D=diag(1,,2,,n-1) para un cierto valor . Se demuestra que con probabilidad elevada A tiene rango mximo si y slo si su matriz de Gramm tiene determinante no nulo. En resumen, aplicando los tres algoritmos explicados en estos apartados, se consigue un algoritmo para saber si una matriz compartida, no necesariamente cuadrada, tiene rango mximo. El nmero de rondas de este mtodo es constante y, por tanto, es ms eficiente que el conocido mtodo de Gauss.
BIBLIOGRAFA:

[B79] [Link]. Safeguarding cryptographic keys. AFIPS Conference Proc.48, pp.313-317, 1979. [BB89] [Link]-Ilan, [Link]. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. Proc. ACM PODC89, pp.201-209, 1989. [BV98] D. Boneh, [Link]. Breaking RSA may not be equivalent to factoring. Advances in Cryptology EUROCRYPT98, pp.59-71, 1998. 10

[CD01] [Link], [Link]. Secure Distributed Linear Algebra in a Constant Number of rounds. Advances in Cryptology CRYPTO '01, pp.119-136, 2001. [CD05] [Link], [Link]. Multiparty Computation, an Introduction. Contemporary Cryptology, CRM, Birhuser, 2005. [Co98] [Link]. Finding a small root of a univariate modular equation. Advances in Cryptology EUROCRYPT96, pp.155-165, 1996. [DH76] [Link], [Link]. New directions in cryptography. IEEE Trans. on Information Theory, n.22, pp.644-654, 1976. [DSS94] Digital Signature Standard. National Bureau of Standards. FIPS Publication 186, 1994. [E85] [Link]. A public key Cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory, n.31, pp.469-472, 1985. [K87] [Link]. Elliptic curve cryptosystems. Mathematics of Computation, n.48, pp.203-209, 1987. [M85] [Link]. Uses of elliptic curves in cryptography. Advances in Cryptology, CRYPTO85, pp.417-426, 1985. [RSA78] [Link], [Link], [Link]. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, n.21, pp.120-126, 1978. [S79] [Link]. How to share a secret. Communications of the ACM, n.22, pp.612-613, 1979. [Sc98] [Link]. A Public-Key Cryptosystem Using Purely Cubic Fields. Journal of Cryptology, n.11, pp.109-124, 1998. [Sh49] [Link]. Communication Theory of secrecy systems. Bell Systems Technical Journal, n.28, pp.656-715, 1949.

Paz Morillo es Licenciada en Matemticas por la Universidad de Barcelona y Doctora en Informtica por la Universidad Politcnica de Catalua. Sus primeros trabajos de investigacin fueron sobre Teora de Grafos y su aplicacin al diseo de redes de interconexin. En 1992 fund el grupo de investigacin de Matemtica Aplicada a la Criptografa (MAK). Ha trabajado en temas como la aplicacin de curvas elpticas a criptografa, diseo de criptosistemas demostrablemente seguros, criptografa distribuida,

11