Matrix Computational Assumptions in Multilinear Groups

Paz Morillo; Carla Ràfols; Jorge L.  Villar

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 $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 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 -Decisional Linear Assumption is an example of a family of decisional assumptions of strictly increasing hardness when 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 assumptions computational problems black-box reductions structure 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},
      url = {https://eprint.iacr.org/2015/353}
}