Predicate-preserving collision-resistant hashing

Abstract

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 caracteres. 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 acumulador criptográfico que permite manipular conjuntos dinámicos (es decir donde es posible insertar y borrar elementos) y cuya seguridad no depende de ninguna autoridad 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 cadenas largas según el orden lexicográfico. Usamos esa FHRC para construir un esquema de firma digital transitivo que permite autenticar árboles dirigidos. Esa construcción es la más eficiente a la fecha, y mejora de forma sustancial el resultado de Gregory Neven (Theoretical Computer Science 396). Finalmente usamos una FHRC similar para demostrar que una cadena corresponde a la expansión binaria de un cierto valor. Con la ayuda de técnicas de pruebas de nula divulgación usamos esa construcción para implementar un protocolo que permite revelar gradualmente un secreto. Luego este protocolo se usa para poder intercambiar de forma equitativa firmas cortas de Boneh-Boyen (EUROCRYPT 2004) sin la necesidad de recurrir a una autoridad de confianza. ----------- We study Collision-Resistant Hash Functions (CRHF) that allow to compute proofs related to some predicate on the values that are hashed. We explore this idea with predicates involving sets (membership) and strings (lexicographical order, binary decomposition). The concept of hashing a set in order to prove (non)membership first appears in the literature under the name of cryptographic accumulators (Benaloh and De Mare, CRYPTO 1993). In this thesis we start by introducing a cryptographic accumulator that handles dynamic sets (it is possible to insert and delete elements) and whose security does not involve a trusted third party. Then we show that no cryptographic accumulator can have the property of batch update (efficient refresh of all the proofs after several updates to the set via a single operation) and thus solve an open problem stated by Nicolisi and Fazio in their survey on cryptographic accumulators (2002). We then describe a CRHF that enables efficient comparison of large strings through their lexicographical order. We use this CRHF to build a practical transitive signature scheme to authenticate directed trees. To the best of our knowledge, this is the first practical construction for signing directed trees. In particular, signatures for paths in the tree are of constant size. This dramatically improves the previous better bound by Gregory Neven (Theoretical Computer Science 396). Finally we use a similar CRHF to prove that a binary string corresponds to the binary expansion of some other value. Using zero-knowledge techniques we build upon this construction to obtain a protocol for releasing a secret gradually. This tool is then used to fairly exchange Boneh-Boyen short signatures (EUROCRYPT 2004) without relying on a trusted third party.