An Algebraic Framework for Diffie-Hellman Assumptions

Alex Escala; Gottfried Herold; Eike Kiltz; Carla Ràfols; Jorge Villar

Paper 2013/377

An Algebraic Framework for Diffie-Hellman Assumptions

Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, and Jorge Villar

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 $D_{ℓ, k} - M D D H$ assumption states that it is hard to decide whether a vector in $G^{ℓ}$ is linearly dependent of the columns of some matrix in $G^{ℓ \times k}$ sampled according to distribution $D_{ℓ, k}$ . It covers known assumptions such as , (linear assumption), and (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 -Assumption holds generically in -linear groups. In particular, our new assumptions and are generically hard in bilinear groups and, compared to , 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 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.

Note: This version includes a new result on the uniqueness of any one-parameter Matrix DH Asuumption and some typographic corrections.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in CRYPTO 2013
Keywords: Diffie-Hellman assumption generic hardness zero knowledge public-key cryptography
Contact author(s): carla rafols @ rub de
History: 2014-05-23: last of 2 revisions; 2013-06-12: received; See all versions
Short URL: https://ia.cr/2013/377
License: CC BY

BibTeX

@misc{cryptoeprint:2013/377,
      author = {Alex Escala and Gottfried Herold and Eike Kiltz and Carla Ràfols and Jorge Villar},
      title = {An Algebraic Framework for Diffie-Hellman Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/377},
      year = {2013},
      url = {https://eprint.iacr.org/2013/377}
}