Autor: BALBÁS GUTIÉRREZ, David

Título: Cryptography for a Verifiable World: Foundations and Applications of Succinct Proof Systems

Fecha: 2025

Materia: ---

Escuela: E.T.S DE INGENIEROS INFORMÁTICOS

Departamento: SIN DEPARTAMENTO DEFINIDO

Acceso electrónico: https://oa.upm.es/91808/

Director/a(s):

• Director/a: FIORE, Dario

Resumen: Cryptographic proof systems enable an entity, the prover, to convince another entity, the verifier, about the validity of a statement. To be useful in practice, cryptographic proof systems must be expressive, enabling proofs for a large class of statements (such as those in the complexity class NP). A highly desirable property is succinctness, meaning that the size of the proof (and the time required to verify it) is much smaller than the size of the witness for the given statement. Nowadays, succinct cryptographic proof systems find a broad range of applications both within and beyond cryptography, such as outsourcing computation, anonymous credentials, signature aggregation, blockchain protocols, and many others. Generally, they provide a trust generation mechanism based on enabling the efficient verification of third-party claims. In this thesis, we study both foundational and practical aspects of succinct proof systems. In the first part, we focus on building succinct proof systems from standard assumptions, a problem for which there exist impossibility results for so-called succinct non-interactive arguments (SNARGs). To circumvent these impossibilities, we seek to relax the power of SNARGs in different ways, focusing on three families of proof systems: functional commitments, batch arguments for NP, and homomorphic signatures. For functional commitments, we present the first construction of this primitive from falsifiable assumptions that supports the evaluation of arbitrary arithmetic circuits of unbounded depth. To this end, we introduce a novel concept called chainable functional commitments, which we instantiate both from lattice-based and from pairing-based assumptions. Later, we present a pairing-based construction that improves on our original result by achieving more compact public parameters. For batch arguments, we present the first algebraic construction that achieves circuit-succinctness, i.e., where the proof size scales linearly in the size of a single witness and is independent of the size of the circuit that decides the NP relation. For homomorphic signatures, we achieve the first homomorphic signature for unbounded-depth circuits, as well as the first multi-key homomorphic signature scheme that is fully-succinct, i.e., where the proof size scales sublinearly on the number of messages, the circuit size, and the number of signing parties. In the second part of the thesis, we focus on building and implementing efficient proof systems with practical applications. The main goal is to bridge the gap between general-purpose and special-purpose proof systems: while the former are universally applicable, the latter provide better concrete efficiency. To this end, we present a family of sumcheck-based proof systems for verifiable computation of sequential computations which are modularly composable at the information-theoretic level, including a novel proof system for multi-channel convolutions. Our schemes yield both asymptotic and concrete performance improvements over the state-of-the-art techniques for verifiable machine learning and image processing. RESUMEN Los sistemas de pruebas criptográficas permiten que una entidad, llamada probador, convenza a otra entidad, llamada verificador, de la validez de una afirmación. Para ser útiles en la práctica, los sistemas de pruebas criptográficas deben ser expresivos, permitiendo pruebas para una amplia clase de instancias (como aquellas en la clase de complejidad NP). Una propiedad altamente deseable es la concisión, lo que significa que el tamaño de la prueba (y el tiempo requerido para verificarla) es mucho menor que el tamaño del testigo correspondiente a la instancia. Hoy en día, los sistemas de pruebas criptográficas concisas encuentran innumerables aplicaciones tanto dentro como fuera de la criptografía, incluyendo la computación delegada, las credenciales anónimas, la agregación de firmas, los protocolos de blockchain, y muchas otras. En términos generales, ofrecen una forma de generar confianza, ya que permiten verificar afirmaciones realizadas por terceros de forma eficiente. En esta tesis, abordamos cuestiones fundamentales y prácticas en torno a los sistemas de pruebas concisas. En la primera parte, nos centramos en construir sistemas de pruebas concisas a partir de supuestos criptográficos estándar, un problema para el cual existen resultados de imposibilidad en el caso de los denominados ``succinct non-interactive arguments'' (SNARGs). Para sortear estas imposibilidades, buscamos relajar la definición de los SNARGs desde distintos ángulos, centrándonos en tres familias de sistemas de prueba: los esquemas de compromiso funcionales (``functional commitments''), los argumentos en tandas para NP (``batch arguments for NP'') y las firmas homomórficas (``homomorphic signatures''). En cuanto a functional commitments, presentamos la primera construcción de esta primitiva a partir de supuestos criptográficos refutables que soporta la evaluación de circuitos arbitrarios de profundidad no acotada. Para ello, introducimos el concepto de esquema funcional de compromiso encadenable, del cual presentamos construcciones tanto basadas en retículos (``lattices'') como en emparejamientos (``pairings''). Posteriormente, presentamos una construcción que mejora nuestro resultado original consiguiendo parámetros públicos más concisos. En cuanto a batch arguments, presentamos la primera construcción algebraica que logra ser concisa en el circuito, es decir, donde el tamaño de la prueba escala linealmente en el tamaño del testigo de la instancia correspondiente y no depende del tamaño del circuito que decide la relación NP. En cuanto a homomorphic signatures, en primer lugar logramos la primera construcción que soporta circuitos de profundidad no acotada. Además, presentamos el primer esquema multi-clave que es completamente conciso, es decir, en el que el tamaño de la prueba es sublineal en el número de firmas, en el tamaño del circuito, y en el número de partes firmantes. En la segunda parte de la tesis, nos enfocamos en construir e implementar sistemas de pruebas eficientes con aplicaciones prácticas. El principal objetivo es cerrar la brecha entre los sistemas de prueba de propósito general y los específicos: mientras que los primeros son aplicables universalmente, los segundos ofrecen mejor rendimiento para problemas determinados. Con este fin, presentamos una familia de sistemas de prueba ``sumcheck'' (instanciados a partir de sumas sobre polinomios multilineales) para la computación verificable de operaciones secuenciales. Estos sistemas son modulares y componibles a bajo nivel, e incluyen un nuevo sistema de prueba específico para convoluciones multi-canal. Nuestras propuestas mejoran tanto la complejidad asintótica como el rendimiento concreto de las técnicas actuales para verificar algoritmos de inteligencia artificial y de procesado de imágenes.