Show simple item record

Professor Advisordc.contributor.advisorHevia Angulo, Alejandro
Professor Advisordc.contributor.advisorRáfols Salvador, Carla
Authordc.contributor.authorGonzález Ulloa, Alonso Emilio 
Associate professordc.contributor.otherBarbay, Jeremy
Associate professordc.contributor.otherLibert, Benoit
Associate professordc.contributor.otherPérez Rojas, Jorge
General notedc.descriptionDoctor en Ciencias, Mención Computaciónes_ES
Abstractdc.description.abstractNon-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.es_ES
Patrocinadordc.description.sponsorshipEste trabajo ha sido parcialmente financiado por CONICYT, CONICYT-PCHA/Doctorado Nacional/2013-21130937es_ES
Publisherdc.publisherUniversidad de Chilees_ES
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link to Licensedc.rights.uri*
Keywordsdc.subjectCriptografía - Procesamiento de datoses_ES
Keywordsdc.subjectProcesamiento electrónico de datoses_ES
Keywordsdc.subjectPruebas no interactivases_ES
Títulodc.titleEfficient non-interactive zero-knowledge Proofses_ES
Document typedc.typeTesis
Departmentuchile.departamentoDepartamento de Ciencias de la Computación
Facultyuchile.facultadFacultad de Ciencias Físicas y Matemáticases_ES

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile