Algebraic techniques for universal succinct arguments

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Zapico Barrionuevo, Victoria Arantxa
• dc.contributor.other Daza, Vanesa
• dc.contributor.other Ràfols, Carla
• dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
• dc.date.accessioned 2024-03-16T02:34:25Z
• dc.date.available 2024-03-16T02:34:25Z
• dc.date.issued 2022-11-02T11:53:14Z
• dc.date.issued 2022-11-02T11:53:14Z
• dc.date.issued 2022-10-13
• dc.date.modified 2024-03-15T10:57:59Z
• dc.description.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.
• dc.description.abstract 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.
• dc.description.abstract 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.
• dc.description.abstract Programa de doctorat en Tecnologies de la Informació i les Comunicacions
• dc.format 154 p.
• dc.format application/pdf
• dc.format application/pdf
• dc.identifier http://hdl.handle.net/10803/675840
• dc.identifier.uri http://hdl.handle.net/10230/54686
• dc.language.iso eng
• dc.publisher Universitat Pompeu Fabra
• dc.rights L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-sa/4.0/
• dc.rights http://creativecommons.org/licenses/by-nc-sa/4.0/
• dc.rights info:eu-repo/semantics/openAccess
• dc.source TDX (Tesis Doctorals en Xarxa)
• dc.subject.keyword Cryptography
• dc.subject.keyword Zero-knowledge
• dc.subject.keyword Succinct Arguments
• dc.subject.keyword SNARKs
• dc.subject.keyword Vector commitments
• dc.subject.keyword Cryptografía
• dc.subject.keyword Conocimiento nulo
• dc.subject.keyword Argumentos sucintos
• dc.subject.keyword Compromisos a vectores
• dc.subject.keyword 62
• dc.title Algebraic techniques for universal succinct arguments
• dc.type info:eu-repo/semantics/doctoralThesis
• dc.type info:eu-repo/semantics/publishedVersion