Doctor en Ciencias, Mención Computación / Non-Interactive Zero-Knowledge (NIZK) proofs, are proofs that yield nothing beyond their validity. As opposed to the interactive variant, NIZK proofs consist of only one message and are more suited for high-latency scenarios and for building inherently non- interactive schemes, like signatures or encryption. With the advent of pairing-based cryptography many cryptosystems have been built using bilinear groups, that is, three abelian groups G1,G2,GT oforderqtogetherwithabilinear function e : G1 × G2 → GT . Statements related to pairing-based cryptographic schemes are naturally expressed as the satisfiability of equations over these groups and Zq. The Groth-Sahai proof system, introduced by Groth and Sahai at Eurocrypt 2008, provides NIZK proofs for the satisfiability of equations over bilinear groups and over the integers modulo a prime q. Although Groth-Sahai proofs are quite efficient, they easily get expensive unless the statement is very simple. Specifically, proving satisfiability of m equations in n variables requires sending as commitments to the solutions Θ(n) elements of a bilinear group, and a proof that they satisfy the equations, which we simply call the proof, requiring additional Θ(m) group elements. In this thesis we study how to construct aggregated proofs i.e. proofs of size independent of the number of equations for different types of equations and how to use them to build more efficient cryptographic schemes. We show that linear equations admit aggregated proofs of size Θ(1). We then study the case of quadratic integer equations, more concretely the equation b(b − 1) = 0 which is the most useful type of quadratic integer equation, and construct an aggregated proof of size Θ(1). We use these results to build more efficient threshold Groth-Sahai proofs and more efficient ring signatures. We also study a natural generalization of quadratic equations which we call set-membership proofs i.e. show that a variable belongs to some set. We first construct an aggregated proof of size Θ(t), where t is the set size, and of size Θ(logt) if the set is of the form [0,t − 1] ⊂ Zq. Then, we further improve the size of our set-membership proofs and construct aggregated proofs of size Θ(log t). We note that some cryptographic schemes can be naturally constructed as set-membership proofs, specifically we study the case of proofs of correctness of a shuffle and range proofs. Starting from set-membership proofs as a common building block, we build the shortest proofs for both proof systems. / Este trabajo ha sido parcialmente financiado por CONICYT, CONICYT-PCHA/Doctorado Nacional/2013-21130937

El problema de comunicación anónima autentificada consiste en diseñar un protocolo que permita intercambiar mensajes entre un conjunto de participantes, de forma tal que cada emisor de un mensaje determina el destinatario de su mensaje y, una vez que se envía el mensaje, éste es efectivamente recibido por el destinatario determinado. La información que revela el protocolo en su ejecución debe mantener el anonimato, es decir debe ser tal que no permite a ningún adversario determinar información relacionada a las identidades de los participantes. El protocolo debe permitir a cada destinatario determinar con exactitud quién es el autor de cada mensaje que recibe, sin que esto contradiga el anonimato. Adicionalmente el protocolo debe mantener las garantías anteriores inclusive si es ejecutado en un ambiente concurrente, es decir es ejecutado con indeterminados otros protocolos. Las aplicaciones de la comunicación anónima autentificada son variadas. Por ejemplo es útil para diseñar sistemas de denuncia anónima de delitos donde adicionalmente se desea discriminar la información recibida según la identidad del que origina el mensaje. Esto puede ser útil si algunos informantes son más creíbles que otros. En este trabajo se plantea el problema de comunicación anónima autentificada y se muestra constructivamente la existencia de un protocolo que resuelve dicho problema. Para ello se estudian tópicos avanzados de Criptografía como Universal Compossability, Generalized Universal Composability, Anonimato, Desmentibilidad y las distintas primitivas criptográficas asociadas a dichos tópicos. Se definen rigurosamente las propiedades que debe tener un protocolo para resolver el problema planteado. Finalmente se diseña un protocolo eficiente para el cual se puede garantizar matemáticamente que satisface las propiedades necesarias para resolver el problema de comunicación anónima autentificada.