AGM ⇒ KEA

Free reduction · algebraic group model · FKL18 · security loss: none: the extractor succeeds whenever the algebraic adversary outputs a pair with $B=A^{\alpha }$

Statement

In the AGM, the knowledge-of-exponent assumption KEA1 holds unconditionally: an algebraic adversary that, given $(g,g^{\alpha })$, outputs $(A,B)$ with $B=A^{\alpha }$ also outputs representations $A=g^{c_1}(g^{\alpha }{)}^{c_2}$ and $B=g^{y_1}(g^{\alpha }{)}^{y_2}$, and an efficient extractor recovers $r$ with $A=g^r$ from them; the knowledge KEA postulates is part of the model’s definition — FKL18.

Sketch

If $c_2=0$ the extractor outputs $c_1$. Otherwise $B=A^{\alpha }$ forces $c_2{\alpha }^2+(c_1-y_2)\alpha -y_1=0$ in ${\mathbb{Z}}_q$, a nonzero quadratic; the extractor computes its roots, identifies $\alpha$ by comparing with $g^{\alpha }$, and outputs $c_1+c_2\alpha$.