International Association
for Cryptologic Research

We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. This family abstracts and includes as a special case several assumptions used in the literature under different names. Given some matrix $\\matrA$ sampled from some distribution $\\mathcal{D}_{\\ell,k}$, the kernel assumption says

that it is hard to find ``in the exponent\'\' a nonzero vector in the kernel of $\\mathbf{A}^\\top$. Our assumption is the natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala \\textit{et al}.

We show that the $\\mathcal{D}_{\\ell,k}$ Kernel DH Assumption is a strictly increasing family of weaker computational assumptions when $k$ grows. This requires ruling out the existence of some black-box reductions between flexible problems (\\textit{i.e.}, computational problems with a non unique solution), which is specially subtle.

As opposed to the decisional MDDH Assumption, our kernel assumption might hold in the recent candidate multilinear groups.

Kernel assumptions have implicitly been used in recent works on QA-NIZK and structure-preserving signatures. We also provide a new construction of commitments to group elements in the multilinear setting, based on any kernel assumption.