### Matrix Computational Assumptions in Multilinear Groups

Paz Morillo, 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).

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

##### Metadata
Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2016
DOI
10.1007/978-3-662-53887-6_27
Keywords
matrix assumptionscomputational problemsblack-box reductionsstructure preserving cryptography
Contact author(s)
jorge villar @ upc edu
History
2017-02-01: last of 2 revisions
2015-04-23: received
See all versions
Short URL
https://ia.cr/2015/353
License

CC BY

BibTeX

@misc{cryptoeprint:2015/353,
author = {Paz Morillo and Carla Ràfols and Jorge L.  Villar},
title = {Matrix Computational Assumptions in Multilinear Groups},
howpublished = {Cryptology ePrint Archive, Paper 2015/353},
year = {2015},
doi = {10.1007/978-3-662-53887-6_27},
note = {\url{https://eprint.iacr.org/2015/353}},
url = {https://eprint.iacr.org/2015/353}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.