An Algebraic Framework for Diffie-Hellman Assumptions

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}\mathsf{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

DDH

,

Lin

2 (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

$\mathcal{D}_{\ell,k}$

. We use the hardness results to find new distributions for which the

$\mathcal{D}_{\ell,k}\mathsf{MDDH}$

-Assumption holds generically in

m

-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

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$

, 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.