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.

KEA3

Let $\mathsf{GrGen}$ be as in the KEA1 game above. KEA3 gives the adversary a Diffie–Hellman triple and asks it for a pair $(C,Y)$ with $Y=C^a$; the extractor must express $C$ in the base elements $g$ and $g^b$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{kea3}}_{\GrGen,\calA,\calE_\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG, q, g) \gets \GrGen(1^\secpar)$
\State $a, b \getsr \ZZ_q$; $\rho \getsr \bits^{*}$
\State $(C, Y) \gets \calA(g, g^a, g^b, g^{ab}; \rho)$
\State $(c_1, c_2) \gets \calE_\calA(g, g^a, g^b, g^{ab}, \rho)$
\Comment{$\calE_\calA$ gets $\calA$'s input and coins}
\Return $[Y = C^a \wedge C \ne g^{c_1} (g^b)^{c_2}]$
\end{algorithmic}
\end{algorithm}

KEA3 holds for $\mathsf{GrGen}$ if the discrete logarithm is hard for $\mathsf{GrGen}$ and 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}}}^{kea3}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A},{\mathcal{E}}_{\mathcal{A}}}^{kea3}(\lambda )=1\right]$$

is negligible — BP04. BP04 state the extraction condition alone and assume hardness of the discrete logarithm separately, for the same $\mathsf{GrGen}$. The extraction condition alone holds trivially for a generator whose discrete logarithms are easy, since ${\mathcal{E}}_{\mathcal{A}}$ can output $c_1={\log }_{g}C$ and $c_2=0$ — standard. Under KEA3 and that hardness, the three-message protocol of HT98, with a fix to its soundness, is a zero-knowledge argument for $\mathbf{NP}$ (DLOG + KEA3 ⇒ Three-message ZK arguments for NP) — BP04.

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, no extractable one-way function exists with respect to auxiliary input of unbounded polynomial length — BCPR14. For a group generator whose discrete logarithm is hard, KEA with such auxiliary input would make $r\mapsto (g^r,g^{\alpha r})$, keyed by $(g,g^{\alpha })$, an extractable one-way function, so under iO it fails for every such generator — BCPR13; for a generator whose discrete logarithm is easy it holds trivially — standard
• The KEA2 assumption of Hada–Tanaka is false — BP04

Participates in

Builds on Knowledge of exponent assumption

• DLOG + KEA3 ⇒ Three-message ZK arguments for NP (via KEA3)

Produces Knowledge of exponent assumption

• AGM ⇒ KEA
• GGM ⇒ KEA