IACR News item: 22 April 2015
Paz Morillo, Carla R\\`afols, Jorge L. Villar
ePrint Reportthat 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.
Additional news items may be found on the IACR news page.