Compartición de secretos en criptografía

COMPARTICIÓN DE SECRETOS EN CRIPTOGRAFÍA Jorge Villar Santo s, Ca rI es Padró Laimón y Germán Sáez Moreno Profesores de/ Dpto. de Matemática Aplicada y Telemática. Universitat Po/itecnica de Cata/unya e-mail:[email protected] En la criptogra fí a clásica, tanto en el ámbito de clave púb li ca co mo en el de cl ave privada, los prot oco los criptogr áf i cos cuentan só lo co n dos participantes: el poseedor de la inf ormación o ri ginal y el r ece ptor de dicha información. En la actualidad, co n el d esa rr o ll o de las red es info rmá ti cas y la n eces idad de seg uridad y pri vac idad resp ec to a la inf ormación que és tas c ur sa n, se re qui ere el u so de prot oco l os qu e in vo lucr en un núm ero m ayo r de participant es [D es88 ]. Un ejemplo se ncillo es la r ea lización de una co nf erencia a tr es en la qu e se requiera pri vac idad. Por otra parte, la información secreta no es generada exclusivamente por personas físicas sino por e mpr esas o entidades. En este último caso, no está claro que la re sponsabilidad so br e la inf ormación s ecr eta generada pueda o de ba r ecae r so bre una úni ca per so na. Por ejemplo, cualq ui er movimiento imp ortante de ca pital en una e mpr esa debería requerir la participación de varios empl ea dos. 1. ESQUEMAS PARA COMPARTIR SECRETOS U n es quema para compa rti r secretos es un prot oco lo cr ipt og r áf i co en el que, como su no mbr e indica. se divide un de terminado secreto en fr ag mentos que se reparten entre los participa nt es. Por ejemplo, el secreto po dr ía ser la clave de acceso a una cuenta ban ca ri a. Este reparto de inf ormación se r ea li za de modo que: (1) sólo ciertos co njuntos de par ti cipa nt es autorizados pu ede n r eco nstruir el secreto o ri g in a l. (2) un conjunto de pa rti cipant es no aut or izado no puede obtener información alguna so br e el secreto original. De la segun da condición se despren de que el secreto no se divide literalmente en fragmentos sino que los fragme nt os entr ega dos a ca da participante r es ultan de la ejecución de un al go ritmo más sofis ti cado. Asimismo , la reconst ru cc ión de l secreto no cons is ti rá en la yuxtaposición de los fragmentos de lo participantes sino en la ejecución de cierto algoritmo cu yas entradas sean los fragme nt os ante ri ores. .. R AMAS DE E STU DI ANTES DEL I EEE Los primeros esquemas par a co mpartir secretos fu eron introducidos en 1979 por Sh a mir en [Sha79] y por Bl ac kl ey en [ Bl a79]. El primero de e ll os es tá ba sado en interpolación polinómi ca sobre un cuerpo finito. Dado un secreto k, e toma un polino mi o secreto p de grado no superior a fJ, tal que prO) = k. A c ada uno de los n Un protocolo debe ser rob usto tanto frente a personas externas al mismo como frente a usos ilícitos de la información repartida partici pantes, que se car a ct eriza por cierto número ~ , "" O, se le asigna el fr ag mento S¡ = p( ~ ). Se puede demo strar que si se reúne una ca ntidad igual o mayor que t participantes, existe un único polinomio p de gra do inf e ri or a { que pa se por los puntos ( ~ ¡ ,S) corr es pondient es a dichos participante s. Además, el secreto o ri ginal coincide con p rO). Por otra parte. dado un co njunto con menos de 1 participantes, existen var ios polinomios q que pasan por los puntos ( ~ , .S) co rr es pondientes a di chos participantes y q(O) toma todos los valores posibl es con la mjsma fr ecuencia. Así, todos los valores posibl es del secreto k resultan e quipr obables, y los pa rti cipant es ti enen la mi sma inf ormación so br e el secreto que cualquier per so na ajena al protocolo. Este tipod ees quem ase n los que seex ige un número mínimo de participant es para r eco nstruir el secreto se d enom inan esquemas de umbra l. Estos esquemas no son los únicos existe nt es pero sí los más ampliamente es tudiados. 2. ESQUEMAS ROB US TOS FRENTE A MENTIROSOS En el mundo de la c ri ptografía. un protocolo debe ser robusto tanto frente a personas externas al mi smo co mo fre nt e a usos il íc it os de la inf ormación repartid a_ 53 Por ejemplo, un participante de un esquema para compartir secretos podría intentar engañar a otros suministrando un fragmento incorrecto durante el proceso de reconstrucción. Si el esquema no cuenta con un algoritmo de verificación de los fragmentos, se reconstruye un secreto incorrecto. En el caso peor, con el fragmento correcto y el secreto incorrecto, el participante tramposo podría recuperar por sí mismo el secreto original. Esto es exactamente el inconveniente del esquema de Sharnir. Un participante de un esquema para compartir secretos podría intentar engañar a otros suministrando un fragmento incorrecto durante el proceso de reconstrucción Una manera de dotar de cierta robustez al esquema de Sharnir es además de repartir el secreto original k, repartir por un procedimiento análogo su cuadrado F. Así, a cada participante se le otorgan los fragmentos Si y ti correspondientes respectivamente a k ya F. En el proceso de reconstrucción, se recuperan ambos secretos k] y k2• Si todos los participantes son honrados, resulta k] = k Y k2 = k2• En caso contrario, con alta probabilidad sucederá que k/ "" k2, Y los participantes deducirán que el secreto k] reconstruido no es válido. Por otra parte, un participante no puede (salvo casualidad improbable) modificar sus fragmentos S y 1. de modo que J J se cumpla la relación k] 2 = k2, sin conocer previamente los fragmentos de t-1 participantes más. Esta mejora del esquema de Shamir fue introducida por Padró en [Pad96]. Existen otros requisitos de robustez más severos que el anterior que, por ejemplo, consiguen llegar a identificar al participante tramposo a partir de los fragmentos suministrados [Car95]. En general, cuanto más robusto es un esquema para compartir secretos, mayor resulta el tamaño de los fragmentos repartidos a los participantes. En el esquema de Padró, el tamaño de los fragmentos es el doble del tamaño del secreto. Se puede demostrar que este tamaño es casi el mínimo posible [Oga96]. Los esquemas para compartir secretos pueden aparecer como un componente de otros protocolos criptográficos como la generación compartida de firmas digitales o la verificación compartida de la autenticidad de un documento [Soe90, Fra95]. En ambos casos se évita 54 concentrar toda la responsabilidad de un acto determinado en una única persona. Otra aplicación de los esquemas para compartir secretos se halla en los sistemas de votación electrónica, en los que la apertura de la urna requiere la reconstrucción de una clave secreta compartida entre los miembros de la mesa electoral. 3. SEGURIDAD COMPUTACIONAL VS. INCONDICIONAL Además de los esquemas para compartir secretos descritos anteriormente y denominados incondicionalmente seguros, existe una versión menos estricta de los mismos, denominados computacionalmente seguros. Las exigencias de un esquema tal son: (1) sólo ciertos conjuntos de participantes autorizados pueden reconstruir el secreto original. (2) un conjunto de participantes no autorizado no puede obtener información alguna sobre el secreto original, usando los recursos computacionales actuales. En este tipo de esquemas se asume la existencia de una función f unidireccional, es decir, calculable con relativa facilidad y cuya inversa no se puede calcular a partir de los recursos computacionales actuales. Un ejemplo de función unidireccional es la exponenciaciónf(x) = Ef' en un cuerpo finito. Por ejemplo, dado el fragmento Si entregado a cada participante en un esquema incondicionalmente seguro, podemos publicar Si = f( S) sinrevelar el valor concreto de si" De este modo, si un participante intenta dar un fragmento falso S*i' éste sería inmediatamente detectado dado que Si ""f(s'). Los esquemas computacionalmente seguros son, en general, más versátiles que los incondicionalmente seguros dado que permiten añadir dinámicamente participantes sin tener que modificar los fragmentos repartidos, así como reutilizar los fragmentos para compartir un segundo secreto [Cac95, Gh097]. Para las mismas prestaciones, los fragmentos de un esquema computacionalmente seguro tienen menortamaño que los fragmentos de un esquema incondicionalmente seguro. Por último, la seguridad computacional demuestra ser suficiente para las aplicaciones prácticas. 4. CRIPTOGRAFIA VISUAL Recientemente se ha introducido una generalización de los esquemas para compartir secretos que se conoce como criptografía visual [Na094]. En este caso, tanto el -" ,. BÜI'."NN"tODICIE~llffi 1997 ji f: secreto compartido como los fragmentos que se entregan a los participantes son imágenes en blanco y negro. La restricción que se introduce es que en el proceso de reconstrucción los fragmentos se superponen como si fueran transparencias. Es decir, el resultado de superponer dos imágenes es la «OR» lógica punto a punto de ambas, considerando el color negro (opaco) como «1» y el color blanco (transparente) como «O» lógico. Desde el punto de vista de esquemas para compartir secretos, lo que se hace es descomponer la imagen secreta en un conjunto de bits, cada uno correspondiente a un pixel de la imagen. Cada bit se reparte independientemente de los demás bits de la imagen, de modo que los fragmentos tienen un tamaño fijo de m bits por pixel original. De este modo, los fragmentos requieren una resolución mayor que la imagen secreta original. La reconstrucción por superposición de los fragmentos no es exacta pero el ojo humano es capaz de distinguir la imagen original si esta no es excesivamente recargada. La ventaja de este protocolo es que el algoritmo de reconstrucción no requiere realizar cálculo alguno. BIBLIOGRAFÍA [Bei94] A. BEIMEL y B. CROR «lnteraction inkey distribution schemes» Advances in Cryptology, Crypto '93 444-457 (1994) [Bla79] G.R. BLAKLEY «Safeguarding cryptographickeys» AFIPS Conference Proceedings 48 313-317 (1979) [Cac95] C. CACHIN y C. BOYD «On-line secret sharing» Cryptography and Coding, lMA '96 190-198 (1995) [Car95] M. CARPEl\l"fIERJ «A perfect threshold secret sharing scheme to identify cheaters» Design, Codes and Cryptography5183-187(1995) [Des88] Y. DESMEDT «Society and group oriented cryptography: A new concept» Advances· in Cryptology,Crypto '87120-127 (1988) [Fra95] M.K. FRANKLlNY M.K. REITER« Verifiable signature sharing» Advances in Cryptology, EUROCRYPT '9550-63 (1995) [Gh097] H. GRODOSI, l PIEPRZYK, G.R. CHAUDRRY y l SEBERRY «How to prevent cheating in Pinch's scheme» Electronics Letters 33 (1997) 1453-1454 [Na094] M. NAOR y A. SHAMIR «Visual cryptography» Advances in Cryptology, EUROCRYPT '941-12 (1994) [Oga96] W. OGATA y K. KUROSAWA «Optimum Secret Sharing Scheme Secure against Cheating» Advances in Cryptology, EUROCRYPT '96 200211(1996) [Pad96] C. PADRÓ, G. SÁEZ y lL. VILLAR «Detection of cheaters in vector space secret sharing schemes» Proc. of the 1 st lnt. Conf. on the Theory and Appl. ofCryptology, PRAGOCRYPT'96 (1996) 359-369 [Sha79] A. SHAMIR «How to share a secret» Commun. of theACM22612-613 (1979) [Soe90] M. DE SOETE, 1.1. QUISQUATER y K. VEDDER «A signature with shared verification scheme» AdvancesinCryptology,Crypto '89253-262 (1990) VENTANA AL CAMPUS Inauguramos en este número una sección en la cual trataremos temas relacionados con el Campus. Os invitamos a colaborar enviando vuestras sugerencias a la edición de la revista. Como ya sabéis, una de las características del Campus N ord de la UPC es la existencia de un centro comercial que está situado entre los edificios C3, C4 y B4. Este hecho, tan habitual en las universidades del resto del mundo, se está reproduciendo en los nuevos campus, como el de la Autónoma y el de la Vall d'Hebron, pero en ninguno de estos casos se ha conseguido una integración urbana como en el caso de La CUP. Se ofrecen servicios de todo tipo, unos más directamente relacionados con la vida estudiantil (Self Sevice PoliMenu, la librería técnica Díaz de Santos, cooperativa de papeleríaAbacus, Cooperativa de Publicaciones del Campus Nord CPET), y otros que nos ayudan a encontrar más cómoda y agradable nuestra estancia en el campus, permitiéndonos ahorrarnos el incómodo trayecto al centro de la ciudad (como puede ser el RACC, una óptica, una peluquería, oficinas bancarias, agencias de viajes, servicio de fotocopias, servicio de limpieza, servicio de mensajería, una tienda de deportes, restaurantes y un quiosco). La intención de los gestores de La CUP ha sido siempre la de mejorar la calidad de vida en el Campus. Como hemos podido apreciar, no solo nos han acercado los servicios comerciales, sino que también participan en las actividades culturales y sociales, apoyando las iniciativas de los estudiantes, ya sea para realizar fiestas, revistas, congresos, etc. En parte, gracias a ellos se mantiene el espíritu universitario, tan necesario para desconectar de la rutina estudiantil. La CUP pone a disposición de los estudiantes (que en el fondo somos sus clientes) un despacho a donde podemos acudir siempre que surja cualquier problema con locales de La CUP, o tengamos alguna sugerencia o queja al respecto (recordemos el caso del Nyam-Nyam). Desde aquí os animamos a descubrir lo que La CUP nos ofrece, no sólo sus comercios, sino también su apoyo a nuestras iniciativas . • RAMAS DE ESTUDIANTES DEL IEEE 55