It is well known that two MDDH problems described by matrices with a different number of rows are separated by an oracle computing certain multilinear map. Thus, we put the focus on MDDH problems of the same size. Then, we show that MDDH problems described with a different number of parameters are also separated (meaning that a successful reduction cannot decrease the amount of randomness used in the problem instance description).
When comparing MDDH problems of the same size and number of parameters, we show that they are either equivalent or incomparable. This suggests that a complete classification into equivalence classes could be done in the future. In this paper we give some positive and negative partial results about equivalence, in particular solving the open problem of whether the Linear and the Cascade MDDH problems are reducible to each other.
The results given in the paper are limited by some technical restrictions in the shape of the matrices and in the degree of the polynomials defining them. However, these restrictions are also present in most of the work dealing with MDDH Problems. Therefore, our results apply to all known instances of practical interest.Category / Keywords: Matrix Diffie-Hellman Problems, Black-Box Reductions, Decisional Linear Assumption, Black-Box Separations Original Publication (in the same form): IACR-PKC-2017 Date: received 2 Jan 2017 Contact author: jorge villar at upc edu Available format(s): PDF | BibTeX Citation Version: 20170103:014151 (All versions of this report) Short URL: ia.cr/2017/001 Discussion forum: Show discussion | Start new discussion