Comunicació presentada a: ASIACRYPT 2016, celebrat a Hanoi, Vietnam, del 4 al 6 de desembre de 2016.

We put forward a new family of computational assumptions, the Kernel Matrix Diffi-Hellman Assumption. Given some matrix A sampled from some distribution D, the kernel assumption says that it is hard to find \in the exponent" a nonzero vector in the kernel of A>. This family is a natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala et al. As such it allows to extend the advantages of their algebraic framework to com- putational assumptions. The k-Decisional Linear Assumption is an example of a family of de- cisional assumptions of strictly increasing hardness when k grows. We show that for any such family of MDDH assumptions, the corresponding Kernel assumptions are also strictly increasingly weaker. This requires ruling out the existence of some black-box reductions between exible problems (i.e., computational problems with a non unique solution).