Knowledge of exponent assumption

The knowledge of exponent assumption (KEA) is a non-falsifiable assumption used in constructions of SNARKs and other efficient proof systems. It asserts that any efficient algorithm which produces a valid “DH pair” $(A,B)$ satisfying $B=A^{\alpha }$ — given the challenge pair $(g,g^{\alpha })$ — must “know” the discrete log $r$ such that $A=g^r$, in the sense that a formal extractor can recover $r$ from the algorithm’s code. Originally introduced by Damgård and extended in various forms for pairing-based SNARKs.

Assumption

Let $\mathsf{GrGen}(1^{\lambda })$ output a group $\mathbb{G}$ of prime order $q$ with generator $g$. KEA1 of BP04 is the following game, in which the extractor ${\mathcal{E}}_{\mathcal{A}}$ receives the input and random coins $\rho$ of $\mathcal{A}$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{kea}}_{\GrGen,\calA,\calE_\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG, q, g) \gets \GrGen(1^\secpar)$
\State $\alpha \getsr \ZZ_q^*$; $\rho \getsr \bits^{*}$
\State $(A, B) \gets \calA(g, g^\alpha; \rho)$
\State $r \gets \calE_\calA(g, g^\alpha, \rho)$
\Comment{$\calE_\calA$ gets $\calA$'s input and coins}
\Return $[B = A^\alpha \wedge A \ne g^r]$
\end{algorithmic}
\end{algorithm}

KEA holds for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$ there exists an efficient ${\mathcal{E}}_{\mathcal{A}}$ such that

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A},{\mathcal{E}}_{\mathcal{A}}}^{\mathrm{kea}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A},{\mathcal{E}}_{\mathcal{A}}}^{\mathrm{kea}}(\lambda )=1\right]$$

is negligible.

Known Results

• KEA is not falsifiable in the sense of Naor: its $\forall \mathcal{A}\exists {\mathcal{E}}_{\mathcal{A}}$ form means no efficient challenger can certify that an adversary breaks it — Nao03
• For an NP language with a sub-exponentially hard subset-membership problem, a black-box reduction from a falsifiable assumption to the adaptive soundness of a SNARG for that language exists only if the assumption is false — GW11; see no-falsifiable-assumption-to-snark-gro16

Variations

$q$-Power KEA

Let $(\mathbb{G},{\mathbb{G}}_T,e,g)$ be a bilinear group of prime order $p$, let $x,\alpha \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p^{\ast }$, and give $\mathcal{A}$ the elements $(g^{x^i},g^{\alpha x^i}{)}_{i=0}^q$. The $q$-power knowledge of exponent assumption ($q$-PKE) states that for all efficient $\mathcal{A}$ there is an efficient ${\mathcal{E}}_{\mathcal{A}}$ (given $\mathcal{A}$‘s input and coins) such that the probability that $\mathcal{A}$ outputs $(c,\hat{c})$ with $\hat{c}=c^{\alpha }$ while ${\mathcal{E}}_{\mathcal{A}}$ fails to output $a_0,\dots ,a_q$ with $c=g^{{\sum }_i{a}_i{x}^i}$ is negligible — Gro10.

$q$-PKE is used in the pairing-based SNARKs of Gro10 and GGPR13; Groth16 instead proves knowledge soundness in the generic bilinear group model — Gro16.

Algebraic Group Model (AGM)

In the AGM, every algorithm must explicitly output the representation of any group element it computes. This is a heuristic model that makes KEA-like extraction implicit: any output group element is accompanied by its algebraic derivation from the inputs.

Attacks

• No attack on KEA1 without auxiliary input is known
• Assuming indistinguishability obfuscation, KEA with respect to arbitrary auxiliary input of unbounded polynomial length is false — BCPR14
• The KEA2 assumption of Hada–Tanaka is false — BP04

Participates in

Produces Knowledge of exponent assumption

• AGM ⇒ KEA
• GGM ⇒ KEA