Departamento de Computación

Los Esquemas de Compartición de Secretos (ECS) controlan el acceso a sistemas de información, distribuyendo la responsabilidad entre varios usuarios. De esta manera, una transacción se lleva a cabo si y sólo si conjuntos particulares de usuarios acceden al sistema y autorizan esa transacción. La colección de esos conjuntos particulares es la estructura de acceso del ECS. Estos se basan en modelos matemáticos, algunos en matroides rea presentables. Ejemplos típicos de matroides los constituyen las colecciones de conjuntos linealmente independientes en espacios vectoriales. Un matroide representable si es isomorfo a uno de esa forma. Las estructuras de acceso y los matroides se corresponden en cuanto a que los conjuntos complementarios de una estructura de acceso conforman un matroide. Con matroides representables, un conjunto de usuarios queda partido como una unión de clanes disjuntos, y a los elementos de cada clan se les asigna llaves privadas de acceso, o fragmentos del secreto. Con esto, una transacción se realiza si y sólo si al menos se reúnen dos participantes en clanes distintos para acceder al sistema. Esta condición de “umbral 2” no es relevante, pues de manera similar puede construirse ECS o de cualquier umbral. Esta tesis presenta un método para obtener, de manera aleatoria, matroides representables (aquí la aleatoriedad de la selección de matroides representables, coincide con la selección aleatoria de subespacios lineales de un espacio vectorial: cada tal o subespacio da lugar a un matroide de vectores l.i.), los procedimientos de distribución y recuperación de fragmentos en un ECS ideal, así como las relaciones algorítmicas entre las nociones de matroides, estructuras de acceso y ECS. Realizamos algunos procedimientos de conteo en estructuras relevantes, tales como espacios vectoriales sobre campos finitos, bases y matroides. Hacemos también consideraciones en cuanto a la seguridad lograda y las complejidades de las construcciones realizadas. El presente trabajo desarrolla un prototipo computacional para realizar, en la práctica, experimentos de resultados bien conocidos. El énfasis de nuestro trabajo está en el análisis de los métodos. Por un lado, al generar un matroide sobre un conjunto de participantes, ha de darse como la lista de todas sus bases. En la práctica, este recuento es innecesario y aquí es de interés puramente analítico. Por otro lado, nuestra implementación de los ECS, además de efectiva, es, en efecto, incorporable a un sistema de explotación práctica.