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
-
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}
}