Algebraic techniques for universal succinct arguments

Abstract

In this thesis, we make theoretical and practical contributions to the design of succinct arguments with universal setups in the pairing-based setting. We first introduce a new primitive, Checkable Subspace Sampling (CSS) schemes, and use it to build a framework for designing zero-knowledge succinct arguments of knowledge (zkSNARKs) for NP-complete problems. We present several instantiations of CSS that lead to zkSNARKs whose efficiency is competitive, and in most of the cases superior to all previous constructions in the state-of-the-art. Our second contribution is to present a framework for constructing Linear-Map Vector Commitment schemes with updatability and unbounded aggregation from simpler arguments, that prove a committed vector satisfies an inner product relation. We present two constructions of such arguments, that can be used as building blocks in many different succinct arguments, and the first pairing-based maintainable linear-map vector commitment scheme with flexible space/time trade-offs in the univariate, universal SRS model. Finally, we introduce the definition of Position-Hiding linkability for vector commitments and the first scheme that achieves logarithmic prover and constant proof for membership proofs and lookup tables.

En esta tesis, contribuímos en los ámbitos práctico y teórico al desarrollo de argumentos sucintos en grupos bilineales y con parámetros universales. Como primer resultado, definimos esquemas verificables de sampleo en un subespacio (CSS), y los empleamos en la construcción de un marco para el diseño de argumentos de conocimiento, sucintos, no interactivos y de conocimiento nulo (zkSNARKs) para problemas NP completos. Asimismo, presentamos diversos esquemas CSS que conducen a zkSNARKs cuya eficiencia es competitiva, y en la mayoria de los casos superior, a la de todas las construcciones existentes en la literatura. Nuestra segunda contribución es un marco para el diseño de esquemas de compromiso a vectores para mapeos lineales que permite actualizar y agregar pruebas, a partir de argumentos más simples que prueban a partir de su compromiso, que un vector satisface una relación de producto interno. Presentamos dos construcciones de este tipo de argumentos, que pueden ser usadas en diferentes esquemas sucintos, y el primer argumento que, en el escenario de los grupos bilineales con parámetros universales y univariados, permite al probador elegir de manera flexible un equilibrio entre el coste en tiempo y espacio, y actualizar eficientemente las pruebas almacenadas. Finalmente, definimos enlazabilidad con conocimiento nulo para esquemas de compromiso a vectores y el primer esquema con probador logarítmico y prueba de tamaño constante para argumentos de pertenencia a un conjunto y tablas de búsqueda.

En aquesta tesi, contribuïm en els àmbits pràctic i teòric al desenvolupament d’arguments succints en grups bilineals i amb paà`metres universals. Com a primer resultat, definim esquemes verificables de sample en un subespai (CSS), i els fem servir en la construcció d’un marc per al disseny d’arguments de coneixement, succints, no interactius i de coneixement nul (zkSNARKs) per a problemes NP complets. Així mateix, presentem diversos esquemes CSS que condueixen a zkSNARKs l’eficincia dels quals és competitiva, i en la majoria dels casos superior, a la de totes les construccions existents a la literatura. La nostra segona contribucioó és un marc per al disseny d’esquemes de compromís a vectors per a mapeigs lineals que permet actualitzar i afegir proves, a partir d’arguments més simples que proven a partir del seu compromís, que un vector satisfà una relació de producte intern. Presentem dues construccions d’aquest tipus d’arguments, que poden ser usades en diferents esquemes succints, i el primer argument que, a l’escenari dels grups bilineals amb paràmetres universals i univariats, permet al provador escollir de manera flexible un equilibri entre el cost en temps i espai, i actualitzar eficientment les proves emmagatzemades. Finalment, definim enllaabilitat amb conoixement nul a esquemes de compromís a vectors i el primer esquema amb provador local i prova de mida constant per a arguments de pertinença a un conjunt i taules de cerca.