Welcome to the resource topic for 2015/353
Title:
Matrix Computational Assumptions in Multilinear Groups
Authors: Paz Morillo, Carla Ràfols, 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).
ePrint: https://eprint.iacr.org/2015/353
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .