Succinct arguments: efficiency, assumptions and trade-offs

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.

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.