Título:
|
The Kernel Matrix Diffie-Hellman assumption
|
Autor/a:
|
Morillo Bosch, M. Paz; Ràfols Salvador, Carla; Villar Santos, Jorge Luis
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. MAK - Matemàtica Aplicada a la Criptografia |
Abstract:
|
The final publication is available at https://link.springer.com/chapter/10.1007%2F978-3-662-53887-6_27 |
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 a 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). |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències -Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta -Artificial intelligence -Computer science--Mathematics -Matrix assumptions -Computational problemsBlack-box reductions -Structure preserving cryptography -Intel·ligència artificial -Informàtica--Matemàtica -Classificació AMS::68 Computer science::68T Artificial intelligence -Classificació AMS::68 Computer science::68R Discrete mathematics in relation to computer science |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión presentada Objeto de conferencia |
Editor:
|
Springer
|
Compartir:
|
|