Tesis:
Succinct Cryptographic Commitments with Fine-Grained Openings for Decentralized Environments
- Autor: KOLONELOS, Dimitrios Stylianos
- Título: Succinct Cryptographic Commitments with Fine-Grained Openings for Decentralized Environments
- Fecha: 2024
- Materia:
- Escuela: E.T.S DE INGENIEROS INFORMÁTICOS
- Departamentos: SIN DEPARTAMENTO DEFINIDO
- Acceso electrónico: https://oa.upm.es/80577/
- Director/a 1º: FIORE, Dario
- Resumen: Cryptography has always been the science of Secure Communication. The past decade has been epitomized by the emergence of Blockchain Technology, without leaving Cryptography unaffected. The manifesto of Blockchains is Decentralization, making it inevitable that the information is stored and verified in real-time by thousands of participants. This spotlighted two necessities: information should be as concise as possible and verification of processes should be fast.
From a cryptographic perspective, this translates to a central desideratum: Succinctness. A cryptographic construction is called Succinct if its algorithm is generating outputs that are (exponentially) smaller than the inputs. This allows the cryptosystem to treat large data and produce concise outputs that, nevertheless, preserve the desired functionality of the system.
In this thesis, we are concerned with a specific type of Succinct cryptographic primitives: Succinct Commitments. Cryptographic commitments are objects that allow one to commit to some data, providing a binding representative. Then at any later point they can open back the (committed) data providing an opening proof, but without being able to open differently the representative. In more detail, in our work we deal with commitments with more fine-grained openings, where one can generate an opening proof of the commitment to a function f (m) of the initial data m.
Firstly, we deal with set commitments with private (non-)memberhsip openings. We construct succinct zero-knowledge proofs for the problem of set (non-)membership. Intuitively, a zero- knowledge proof is a cryptographic primitive that allows one to prove a statement, in a sound way, without leaking any other information except for the fact that the statement holds. In a zero-knowledge proof for set membership first one commits to a public set and then a party can prove membership to the set but without betraying which element of the set exactly is. Such (set) commitments with this type of fine-grained openings are the cornerstone of Anonymous Cryptocurrencies such as Zcash. In particular we provide efficient zero-knowledge proofs for the opening of RSA accumulators, one of the most popular set commitments. First, we show efficient protocols for membership and non-membership of a single element. Then we construct succinct zero-knowledge membership proofs for multiple elements, where the size of the proof is independent of the number of elements proven. The two techniques are qualitatively different.
Secondly, we switch our attention to Vector Commitments, with local positional openings. We put forth the notion of Incremental Aggregation, in which one can arbitrarily aggregate opening proofs of any positions into a single (concise) proof and inversely disaggregate a proof of multiple points to many. We show applications of this notion (1) to speeding up the proof computation by using precomputation and moderate-sized precomputed values and (2) to Verifiable Decentralized Storage. Finally, we provide efficient construction of Incrementally Aggregatable Vector Commitments from Groups of Unknown Order.
Thirdly, we turn to Functional Commitments, for linear functions, where one commits to a vector v and then can open f(v) = y, for a public f. We construct functional commitments that admit constant-sized public parameters and proofs. To this end, our core technique is a novel succinct protocol of cardinality for a set committed with an RSA accumulator, which is in turn based on a Range Proof.
Finally, we show a generic way to turn any Vector Commitment into a Key-Value Map Commitment for arbitrary keys. A Key-Value Map resembles a Vector but the ordering of the values is not characterized by subsequent indices but by arbitrary keys. Key-Value Maps are the core data-structures in Cryptocurrencies like Ethereum. Our construction of Key-Value Map Commitments is generic and is based on a novel cryptographic application of Cuckoo-Hashing.
RESUMEN
La última década se ha caracterizado por la aparición de la tecnología Blockchain, afectando la criptografía. El manifiesto de Blockchains es la Descentralización, en la que la información es guardada y verificada en tiempo real por miles de participantes. Esto centra la atención en dos necesidades: la información debe ser lo más concisa posible y la verificación de los procesos debe ser rápida. Desde una perspectiva criptográfica, esto se traduce en un desiderátum central: la Compacidad.
En esta tesis, nos ocupamos de un tipo específico de primitivas criptográficas compactas: Compromisos Compactos. Los compromisos criptográficos son objetos que permiten comprom- eterse con algunos datos, proporcionando un representante vinculante, de modo que en cualquier momento posterior se pueden volver a abrir, proporcionando una prueba de apertura. En nuestro trabajo tratamos compromisos con aperturas más detalladas, donde se puede generar una prueba de apertura del compromiso con una función f (m) de los datos iniciales m.
En primer lugar, nos ocupamos de compromisos de conjuntos con aperturas privadas de (no) pertenencia. Construimos pruebas compactas de conocimiento cero para el problema de la (no) pertenencia a conjuntos. Una prueba de conocimiento cero es una primitiva criptográfica que permite probar una afirmación, de forma sólida, sin filtrar ninguna otra información excepto el hecho de que la afirmación es cierta. En una prueba de conocimiento cero para la pertenencia a un conjunto, primero uno se compromete con un conjunto público y luego una parte puede demostrar la pertenencia al conjunto, pero sin revelar qué elemento del conjunto es exactamente. Estos compromisos de conjuntos con este tipo de aperturas detalladas son la piedra angular de las criptomonedas anónimas como Zcash. En particular, proporcionamos pruebas eficientes de conocimiento cero para la apertura de acumuladores RSA, uno de los compromisos establecidos más populares. Primero, mostramos protocolos eficientes para la membresía y no membresía de un solo elemento. Luego construimos pruebas compactas de membresía de conocimiento cero para múltiples elementos, donde el tamaño de la prueba es independiente del número de elementos probados. Las dos técnicas son cualitativamente diferentes.
En segundo lugar, centramos nuestra atención en los compromisos de vectores, con aperturas posicionales locales. Presentamos la noción de Agregación Incremental, en la que se pueden agregar arbitrariamente pruebas de apertura de cualquier posición en una prueba única (concisa) e inversamente desagregar una prueba de múltiples puntos en muchos. Mostramos aplicaciones de esta noción (1) para acelerar el cálculo de la prueba mediante el uso de precómputo y valores precalculados de tamaño moderado y (2) para el Almacenamiento Descentralizado Verificable. Finalmente, proporcionamos una construcción eficiente de compromisos vectoriales incrementalmente agregables a partir de grupos de orden desconocido.
En tercer lugar, pasamos a los compromisos funcionales, para funciones lineales, donde uno se compromete con un vector v y luego puede abrir f(v) = y, para un f público. Construimos compromisos funcionales que admiten pruebas y parámetros públicos de tamaño constante. Con este fin, nuestra técnica principal es un protocolo novedoso y compacto de cardinalidad para un conjunto comprometido con un acumulador RSA, que a su vez se basa en una prueba de rango.
Finalmente, mostramos una forma genérica de convertir cualquier compromiso de vector en un compromiso de mapa-de-valores-clave para claves arbitrarias. Un mapa-de-valores-clave se parece a un vector, pero el orden de los valores no se caracteriza por índices posteriores sino por claves arbitrarias. Los mapas-de-valores-clave son las estructuras de datos centrales en criptomonedas como Ethereum. Nuestra construcción de compromisos de mapas de valores clave es genérica y se basa en una novedosa aplicación criptográfica de Cuckoo-Hashing.