GGM ⇒ KEA

Free reduction · generic group model · Den06 · security loss: the adversary beats the extractor with probability $O(m^2/q)$ for $m$ group-oracle queries, $q$ the group order

Statement

The knowledge-of-exponent assumption KEA1 (Damgård’s DHK problem) holds against every adversary in the generic group model — Den06.

Sketch

${\mathcal{E}}_{\mathcal{A}}$ follows $\mathcal{A}$‘s group-oracle queries and records, for each label, the affine polynomial in an indeterminate $X$ standing for $\alpha$ that the label represents, starting from $1$ for $g$ and $X$ for $g^{\alpha }$; if $\mathcal{A}$‘s output $A$ is recorded as a constant $c$, ${\mathcal{E}}_{\mathcal{A}}$ outputs $c$. Otherwise, with $A$ and $B$ recorded as $a(X)$ and $b(X)$, $B=A^{\alpha }$ makes the nonzero quadratic $Xa(X)-b(X)$ vanish at $\alpha$. As in GGM ⇒ DLOG, $\mathcal{A}$‘s view is independent of $\alpha$ unless two distinct recorded polynomials agree at $\alpha$, so after $m$ queries in a group of order $q$, $\mathcal{A}$ wins with probability $O(m^2/q)$.