Stretching Groth-Sahai: NIZK proofs of partial satisfiability

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Ràfols, Carla
• dc.date.accessioned 2019-08-01T13:06:58Z
• dc.date.available 2019-08-01T13:06:58Z
• dc.date.issued 2015
• dc.description Comunicació presentada a: 12th Theory of Cryptography Conference, TCC 2015, celebrada del 23 al 25 de març de 2015 a Varsòvia, Polònia.ca
• dc.description.abstract Groth, Ostrovsky and Sahai constructed a non-interactive Zap for NP-languages by observing that the common reference string of their proof system for circuit satisfiability admits what they call correlated key generation. The latter means that it is possible to create from scratch two common reference strings in such a way that it can be publicly verified that at least one of them guarantees perfect soundness while it is computationally infeasible to tell which one. Their technique also implies that it is possible to have NIWI Groth-Sahai proofs for certain types of equations over bilinear groups in the plain model. We extend the result of Groth, Ostrovsky and Sahai in several directions. Given as input some predicate P computable by some monotone span program over a finite field, we show how to generate a set of common reference strings in such a way that it can be publicly verified that the subset of them which guarantees perfect soundness is accepted by the span program. We give several different avors of the technique suitable for different applications scenarios and different equation types. We use this to stretch the expressivity of Groth-Sahai proofs and construct NIZK proofs of partial satisfiability of sets of equations in a bilinear group and more efficient Groth-Sahai NIWI proofs without common reference string for a larger class of equation types. Finally, we apply our results to significantly reduce the size of the signatures of the ring signature scheme of Chandran, Groth and Sahai or to have a more efficient proof in the standard model that a commitment opens to an element of a public list.en
• dc.format.mimetype application/pdf
• dc.identifier.citation Ràfols C. Stretching Groth-Sahai: NIZK proofs of partial satisfiability. In: Dodis Y, Nielsen JB, editors. Theory of cryptography. 12th Theory of Cryptography Conference TCC 2015 Proceedings, Part II; Warsaw, Poland, 2015 Mar 23-25. Berlin: Springer; 2015. p. 247-76. (LNCS; 9015). DOI: 10.1007/978-3-662-46497-7_10
• dc.identifier.doi http://dx.doi.org/10.1007/978-3-662-46497-7_10
• dc.identifier.issn 0302-9743
• dc.identifier.uri http://hdl.handle.net/10230/42227
• dc.language.iso eng
• dc.publisher Springer
• dc.relation.ispartof Dodis Y, Nielsen JB, editors. Theory of cryptography. 12th Theory of Cryptography Conference TCC 2015 Proceedings, Part II; Warsaw, Poland, 2015 Mar 23-25. Berlin: Springer; 2015. p. 247-76. (LNCS; 9015).
• dc.rights © International Association for Cryptologic Research 2015 The final publication is available at Springer via https://doi.org/10.1007/978-3-662-46497-7_10
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Zero-knowledgeen
• dc.subject.keyword Groth-Sahai proofsen
• dc.subject.keyword Distributed cryptographyen
• dc.subject.keyword Simulation soundnessen
• dc.title Stretching Groth-Sahai: NIZK proofs of partial satisfiability
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/acceptedVersion