An algebraic framework for Diffie-Hellman assumptions

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Escala, Alex
• dc.contributor.author Herold, Gottfried
• dc.contributor.author Kiltz, Eike
• dc.contributor.author Ràfols, Carla
• dc.contributor.author Villar, Jorge L.
• dc.date.accessioned 2019-09-10T13:32:53Z
• dc.date.available 2019-09-10T13:32:53Z
• dc.date.issued 2013
• dc.description Comunicació presentada a: CRYPTO 2013 The 33rd Annual Cryptology Conference, celebrada del 18 al 22 d'agost de 2013 a Santa Bàrbara, Califòrnia, Estats Units d'Amèrica.ca
• dc.description.abstract We put forward a new algebraic framework to generalize and analyze Di_e-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D`;k-MDDH assumption states that it is hard to decide whether a vector in G` is linearly dependent of the columns of some matrix in G`_k sampled according to distribution D`;k. It covers known assumptions such as DDH, 2-Lin (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D`;k. We use the hardness results to _nd new distributions for which the D`;k-MDDH-Assumption holds generically in m-linear groups. In particular, our new assumption 2-SCasc is generically hard in bilinear groups and, compared to 2-Lin, has shorter description size, which is a relevant parameter for e_ciency in many applications. These results support using our new assumption as a natural replacement for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more e_cient NIZK proofs for membership in a subgroup of G`, for validity of ciphertexts and for equality of plaintexts. The results imply very signi_cant e_ciency improvements for a large number of schemes, most notably Naor-Yung type of constructions.en
• dc.description.sponsorship Funded by a Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation and the German Federal Ministry for Education and Research. Partially supported by the Spanish Government through projects MTM2009-07694 and Consolider Ingenio 2010 CDS2007-00004 ARES.en
• dc.format.mimetype application/pdf
• dc.identifier.citation Escala A, Herold G, Kiltz E, Ràfols C, Villar J. An Algebraic Framework for Diffie-Hellman Assumptions. In: Caretti R, Garay JA, editors. Advances in Cryptology – CRYPTO 2013. 33rd Annual Cryptology Conference Proceedings, Part II; 2013 Aug 18-22; Santa Barbara, CA, USA. Berling: Springer; 2013. p. 129-47. (LNCS; no. 8043). DOI: 10.1007/s00145-015-9220-6
• dc.identifier.doi http://dx.doi.org/10.1007/s00145-015-9220-6
• dc.identifier.uri http://hdl.handle.net/10230/42257
• dc.language.iso eng
• dc.publisher Springer
• dc.relation.ispartof Caretti R, Garay JA, editors. Advances in Cryptology – CRYPTO 2013. 33rd Annual Cryptology Conference Proceedings, Part II; 2013 Aug 18-22; Santa Barbara, CA, USA. Berling: Springer; 2013. p. 129-47. (LNCS; no. 8043).
• dc.rights © International Association for Cryptologic Research 2013 The final publication is available at Springer via https://doi.org/10.1007/s00145-015-9220-6
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Diffie-Hellman assumptionen
• dc.subject.keyword Generic hardnessen
• dc.subject.keyword Groth-Sahai proofsen
• dc.subject.keyword Hash proof systemsen
• dc.subject.keyword Public-key encryptionen
• dc.title An algebraic framework for Diffie-Hellman assumptions
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/acceptedVersion