The Kernel Matrix Diffie-Hellman Assumption
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 exponen
- PDF / 562,391 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 213 Views
Universitat Polit`ecnica de Catalunya, Barcelona, Spain {paz.morillo,jorge.villar}@upc.edu 2 Universitat Pompeu Fabra, Barcelona, Spain [email protected]
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). Keywords: Matrix assumptions · Computational problems · Black-box reductions · Structure preserving cryptography
1
Introduction
It is commonly understood that cryptographic assumptions play a crucial role in the development of secure, efficient protocols with strong functionalities. For instance, upon referring to the rapid development of pairing-based cryptography, X. Boyen [8] says that “it has been supported, in no small part, by a dizzying array of tailor-made cryptographic assumptions”. Although this may be a reasonable price to pay for constructing new primitives or improve their efficiency, one should not lose sight of the ideal of using standard and simple assumptions. This is an important aspect of provable security. Indeed, Goldreich [16], for instance, cites “having clear definitions of one’s assumptions” as one of the three main ingredients of good cryptographic practice. There are many aspects to this goal. Not only it is important to use clearly defined assumptions, but also to understand the relations between them: to see, Work supported by the Spanish research project MTM2013-41426-R and by a Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation and the German Federal Ministry for Education and Research. c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 729–758, 2016. DOI: 10.1007/978-3-662-53887-6 27
730
P. Morillo et al.
for example, if two assumptions are equivalent or one is weaker than the other. Additionally, the definitions should allow to make accurate security claims. For instance, although technically it is correct to say that unforgeability of the Waters’ signature scheme [42] is implied by the DDH Assumption, defining the CDH Assumption allows to make a much more precise security claim. A notable effort in reducing the “dizzying array” of cryptographic assumptions is the work of Escala et al. [11]. They put forward a new family of decisional
Data Loading...
