Prime-order DDH ⇒ Matrix DH

Fully-black-box reduction · standard model · EHK+13 · security loss: none

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 .