**Matrix Computational Assumptions in Multilinear Groups**

*Paz Morillo and Carla Ràfols and Jorge L. Villar*

**Abstract: **We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. Given some matrix $\mathbf{A}$ sampled from some distribution $\mathcal{D}$, the kernel assumption says that it is hard to find "in the exponent" a nonzero vector in the kernel of $\mathbf{A}^\top$. This family is the 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 computational assumptions.

The $k$-Decisional Linear Assumption is an example of a family of decisional 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 flexible problems (i.e., computational problems with a non unique solution).

**Category / Keywords: **foundations / matrix assumptions, computational problems, black-box reductions, structure preserving cryptography

**Original Publication**** (with minor differences): **IACR-ASIACRYPT-2016
**DOI: **10.1007/978-3-662-53887-6_27

**Date: **received 20 Apr 2015, last revised 1 Feb 2017

**Contact author: **jorge villar at upc edu

**Available format(s): **PDF | BibTeX Citation

**Note: **This is the full version of the paper with the same title presented in Asiacrypt 2016.

**Version: **20170201:140601 (All versions of this report)

**Short URL: **ia.cr/2015/353

[ Cryptology ePrint archive ]