We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Algebraic Framework for Diffie-Hellman Assumptions.
- Authors
Escala, Alex; Herold, Gottfried; Kiltz, Eike; Ràfols, Carla; Villar, Jorge
- 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 $$\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}$$ Assumption states that it is hard to decide whether a vector in $$\mathbb {G}^\ell $$ is linearly dependent of the columns of some matrix in $$\mathbb {G}^{\ell \times k}$$ sampled according to distribution $$\mathcal {D}_{\ell ,k}$$ . It covers known assumptions such as $$\textsf {DDH},\, 2\text{- }\textsf {Lin}$$ (Linear Assumption) and $$k\text{- }\textsf {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 $$\mathcal {D}_{\ell ,k}$$ . We use the hardness results to find new distributions for which the $$\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}$$ Assumption holds generically in m-linear groups. In particular, our new assumptions $$2\text{- }\textsf {SCasc}$$ and $$2\text{- }\textsf {ILin}$$ are generically hard in bilinear groups and, compared to $$2\text{- }\textsf {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\text{- }\textsf {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 $$\textsf {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 efficient NIZK and NIWI proofs for membership in a subgroup of $$\mathbb {G}^\ell $$ . The results imply very significant efficiency improvements for a large number of schemes.
- Subjects
DATA encryption; ALGEBRA; HARDNESS testing equipment; IRREDUCIBILITY (Philosophy); POLYNOMIALS
- Publication
Journal of Cryptology, 2017, Vol 30, Issue 1, p242
- ISSN
0933-2790
- Publication type
Article
- DOI
10.1007/s00145-015-9220-6