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 ...
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.
+
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 ...
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.
+
Programa de doctorat en Tecnologies de la Informació i les Comunicacions