PROFESOR CO-GUÍA:

Se estudian funciones de hash resistentes a colisiones (FHRC) que permiten validar eficientemente predicados sobre las entradas, usando solamente los valores de hash y certificados cortos. Para los predicados, consideramos conjuntos y cadenas de carac-teres. La idea de computar el valor de hash de un conjunto con el fin de demostrar (no)pertenencia aparece en la literatura bajo el nombre de acumuladores criptográficos (Benaloh y De Mare, CRYPTO 1993). En esa tesis se propone primero un acumu-lador criptográfico que permite manipular conjuntos dinámicos (es decir donde es posible insertar y borrar elementos) y cuya seguridad no depende de ninguna autori-dad de confianza. Luego mostramos que no existe ningún acumulador criptográfico que permite la actualización de todos los certificados en tiempo constante después de varias modificaciones. Este resultado resuelve un problema abierto propuesto por Nicolisi y Fazio en su estado del arte sobre acumuladores criptográficos (2002). La siguiente contribución de esa tesis es una FHRC que permite la comparación de cade-nas largas según el orden lexicográfico. Usamos esa FHRC para construir un esquem