Prime-order DDH ⇒ Matrix DH
Statement
If DDH is hard in prime-order groups for , then -MDDH is hard for , with the same advantage, where the matrix distribution outputs for ; DDH is the -MDDH assumption — EHK+13.
Sketch
has rank . The MDDH input is for and for , with independent and uniform in : the two DDH distributions with and .