Tesis doctoral de Ignacio Cascudo Pueyo
El objetivo principal de esta tesis es el estudio asintótico de familias de esquemas de compartición de secretos lineales e ideales con multiplicación fuerte. Además, como aplicación de algunas técnicas que introducimos para estudiar dicho problema, se estudia la complejidad asintótica de ciertos algoritmos para multiplicar elementos de extensiones finitas de un cuerpo finito. un esquema de compartición de secretos es un objeto combinatorio que se puede utilizar para dividir el conocimiento de un secreto en varios fragmentos, de forma que un número grande de ellos determina el secreto, mientras que un número pequeño no da ninguna in formación acerca de él. Los esquemas de compartición de secretos tienen aplicaciones importantes en criptografía. Algunas de estas aplicaciones requieren esquemas de comparitición de secretos con propiedades algebraicas adicionales. Esta tesis trata acerca de esquemas de compartición de secretos lineales (sobre cierto cuerpo finito) ideales y con t-multiplicación fuerte, que son especialmente útiles en el área criptográfica de la computación multiparte. Esta última propiedad, la t-multiplicación fuerte, depende de un entero t, y para las aplicaciones un esquema de compartición de secretos es mejor si la tolerancia de corrupción, definida como el cociente entre t y el número de fragmentos, es grande. en esta tesis, estudiamos la tolerancia de corrupción de esquemas de compartición de secretos de este tipo asintóticamente, es decir, consideramos familias infinitas de esquemas de compartición de secretos ideales y lineales sobre cierto cuerpo finito fijo donde el número de fragmentos tiende a infinito. Esto está motivado por el hecho de que el valor óptimo para la tolerancia de corrupción sólo se puede alcanzar para esquemas de compartición de secretos en los que el número de fragmentos está acotado superiormente por cierta función del tamaño del cuerpo. Este problema fue estudiado por primera vez por chen y cramer, quienes en 2006 introdujeron los esquemas de compartición de secretos algebraico geométricos (que se basan en los códigos lineales algebraico geométricos) y demostraron que para un número infinito de cuerpos finitos existen familias de esquemas de compartición de secretos lineales ideales cuya tolerancia de corrupción está acotada inferiormente for cierta constante distinta de cero. Sin embargo, no demostraron este hecho para todo cuerpo finito. Aún así, su trabajo ha tenido aplicaciones interesantes en computación multiparte, las pruebas de conocimiento cero y otros problemas criptográficos. en primer lugar introducimos un marco teórico basado en la teoría de códigos con el cual estudiar el problema anteriormente mencionado. Se define formalmente la noción de tolerancia de corrupción asintótica óptima. Se demuestra que este número es distinto de cero para cualquier cuerpo finito, lo que extiende el resultado de chen y cramer. Demostramos también que para todo cuerpo finito, este parámetro está acotado superiormente de forma no trivial, lo que significa que no nos podemos acercar asintóticamente al valor óptimo para la tolerancia de corrupción. después, introducimos una metodología, los sistemas de ecuaciones de riemann-roch, que permite mejorar tanto las cotas inferiores para la tolerancia de corrupción asintótica óptima de algunos cuerpos dadas por chen y cramer como las que encontramos en la primera parte de la tesis. Estas técnicas utilizan algunos resultados acerca de la función zeta de un cuerpo de funciones algebraicas y el tamaño de los subgrupos de torsión del grupo de clases de divisores de grado cero de un cuerpo de funciones algebraicas. Podemos aplicar también estas técnicas a un problema de álgebra computacional, más concretamente para estudiar la complejidad asintótica de ciertos algoritmos para computar productos en las extensiones finitas de un cuerpo finito dado (donde la complejidad se mide como el número de productos en el cuerpo base que uno computa). Enunciamos nuevas cotas superiores para esta complejidad.
Datos académicos de la tesis doctoral «On asymptotically good strongly multiplicative linear secret sharing«
- Título de la tesis: On asymptotically good strongly multiplicative linear secret sharing
- Autor: Ignacio Cascudo Pueyo
- Universidad: Oviedo
- Fecha de lectura de la tesis: 24/07/2010
Dirección y tribunal
- Director de la tesis
- Ronald Cramer
- Tribunal
- Presidente del tribunal: llorení§ Huguet rotger
- ivan bjerre Damgaard (vocal)
- Antonio Campillo lópez (vocal)
- carles Padró laimon (vocal)