[EHK+13] An Algebraic Framework for Diffie-Hellman Assumptions

Authors: Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, Jorge Villar | Venue: CRYPTO 2013 | Source

Abstract

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our -MDDH assumption states that it is hard to decide whether a vector in is linearly dependent of the columns of some matrix in sampled according to distribution . It covers known assumptions such as , 2-Lin (linear assumption), and -Lin (the -linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in -linear groups to the irreducibility of certain polynomials which describe the output of . We use the hardness results to find new distributions for which the -MDDH-Assumption holds generically in -linear groups. In particular, our new assumptions 2-SCasc and 2-ILin are generically hard in bilinear groups and, compared to 2-Lin, have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements 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 -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 efficient NIZK and NIWI proofs for membership in a subgroup of , for validity of ciphertexts and for equality of plaintexts. The results imply very significant efficiency improvements for a large number of schemes, most notably Naor-Yung type of constructions.

BibTeX

@Inproceedings{C:EHKRV13,
  author = {Alex Escala and Gottfried Herold and Eike Kiltz and Carla R{\`a}fols and Jorge Villar},
  title = {An Algebraic Framework for {Diffie}-{Hellman} Assumptions},
  pages = {129--147},
  editor = {Ran Canetti and Juan A. Garay},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2013, Part~II},
  volume = {8043},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~18--22},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2013},
  doi = {10.1007/978-3-642-40084-1_8},
}