Succinct arguments: efficiency, assumptions and trade-offs

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Zacharakis, Alexandros
• dc.contributor.other Daza, Vanesa
• dc.contributor.other Rafols, Carla
• dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
• dc.date.accessioned 2024-03-16T02:34:27Z
• dc.date.available 2024-03-16T02:34:27Z
• dc.date.issued 2022-10-20T07:09:24Z
• dc.date.issued 2022-10-20T07:09:24Z
• dc.date.issued 2022-10-10
• dc.date.modified 2024-03-15T10:58:04Z
• dc.description.abstract Succinct non-interactive arguments (snarks) are cryptographic constructions that allow a prover to convince a verifier about the validity of a statement regarding some computation. We consider these objects from the perspectives of efficiency and assumptions. We modify the folding technique of Bootle et al. (Eurocrypt 16) to exponentially reduce the verifier’s complexity at the expense of an updatable setup instead of a transparent one. Next, we construct a delegation scheme –which is a snark for efficiently decidable languages– using simple and well understood cryptographic assumptions. On the verification side, the construction competes in efficiency constructions that use “non-standard” assumptions. Furthermore, we consider other cryptographic constructions that are relevant to snarks. First, we explore vector commitments and consider combinatorial techniques to construct them. One of our constructions allows flexible time/memory tradeoffs. Second, we introduce folding schemes with selective verification which allows a prover to amortize the cost of producing multiple proofs addressed to different verifiers.
• dc.description.abstract Los argumentos sucintos no interactivos (snarks por sus siglas en Inglés) son construcciones criptográficas que permiten a un probador convencer un verificador sobre la validez de una declaración con respecto a algún cálculo. Consideramos estos objetos desde el punto de vista de la eficiencia y los problemas que se asumen intractables. Modificamos la técnica de plegado de Bootle et al. (Eurocrypt 16) para reducir exponencialmente la complejidad del verificador a expensas de la seguridad en generación de parámetros públicos: en lugar de ser transparentes, serán actualizables. A continuación, construimos un esquema de delegación –que es un snark para lenguajes eficientemente decidibles– usando suposiciones criptográficas simples y bien entendidas. Por el lado de la verificación, la eficiencia de nuestra construcción compite con la de aquellas que usan asunciones “no estándares”. Además, consideramos otras construcciones criptográficas que son relevantes para los snarks. Primero, exploramos compromisos a vectores y consideramos técnicas combinatorias para construirlos. Una de nuestras construcciones permite concesiones flexibles entre tiempo y memoria. En segundo lugar, introducimos esquemas de plegado con verificación selectiva que le permite a un probador amortizar el costo de producir múltiples pruebas dirigidas a diferentes verificadores.
• dc.description.abstract Programa de doctorat en Tecnologies de la Informació i les Comunicacions
• dc.format 198 p.
• dc.format application/pdf
• dc.format application/pdf
• dc.identifier http://hdl.handle.net/10803/675736
• dc.identifier.uri http://hdl.handle.net/10230/54525
• 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 Protocols
• dc.subject.keyword Zero knowledge proofs
• dc.subject.keyword Succinct arguments
• dc.subject.keyword Vector commitments
• dc.subject.keyword Delegation
• dc.subject.keyword Criptografía
• dc.subject.keyword Protocolos
• dc.subject.keyword Prueba de conocimiento zero
• dc.subject.keyword Argumentos sucintos
• dc.subject.keyword Compromisos a vectores
• dc.subject.keyword Delegación
• dc.subject.keyword 62
• dc.title Succinct arguments: efficiency, assumptions and trade-offs
• dc.type info:eu-repo/semantics/doctoralThesis
• dc.type info:eu-repo/semantics/publishedVersion