Paper 2015/353

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)
PDF
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
Creative Commons Attribution
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.