Assumption
指数知识假设 (knowledge of exponent assumption, KEA) 是指给定 $p$ 阶群 $\mathbb{G}$ 和群 $\mathbb{G}_T$ 、双线性映射关系 $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T 、 \mathbb{G}$ 上生成元 $g$ 及 $g^\alpha$, 在不知道 $a$ 的情况下难以构造 $\hat{c} 、 c$ 且 $\hat{c}=c^\alpha$, 其中 $c=g^a, \hat{c}=\left(g^\alpha\right)^a$.
$q$ 阶指数知识假设 ( $q$-Power PKE, 即 $q$-PKE 假设)是指给定 $\left(g, g^x, \cdots, g^{x^q}, g^\alpha, g^{\alpha x}, \cdots, g^{\alpha x^q}\right)$, 在不知道 $a_0, a_1, \cdots, a_q$的情况下难以构造 $\hat{c} 、 c$ 且 $\hat{c}=c^\alpha$,其中 $c=\prod_{i=0}^q\left(g^{x^i}\right)^{a_i}, \hat{c}=\prod_{i=0}^q\left(g^{\alpha x^i}\right)^{a_i}$. 值得注意的是, $q$ - PKE 假设是一种不可证伪 (non-falsifiable)的假设.
Proof
Alice 有一个值$a$，她想要 Bob 对其进行任意指数的求幂（这里 $a$ 是一个有限域群的生成元），唯一的要求是只能对 $a$ 进行求幂，为了保证这一点，她要:
- 选择一个随机数$\alpha$
- 计算$a^\prime = a^\alpha (\mod n)$
- 提供一个元组$(a,a^\prime)$给Bob，然后让他对这两个值执行求幂运算，返回结果元组$(b,b^\prime)$，这里的指数”$\alpha -$变换”依然保持不变，即$b^\alpha=b^\prime (\mod n)$
因为 Bob 无法从元组 $(a, a’)$ 中提取 $α$ 的值，通过暴力破解也难以实现，那就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：
- 选择一个值 $c$
- 计算 $b=a^c(mod n)$ 和 $b’ = (a^\prime)^ c (mod n)$
- 回复 $(b,b’)$
有了回复的元组和 α，Alice 就可以验证等式：
结论是：
- Bob 在元组的两个值的计算上都用了同一个指数（即 $c$）
- Bob 只能用 Alice 原本的元组来保持 $α$ 关系
- Bob 知道指数 $c$，因为构造验证值 $(b,b^′)$ 的唯一方式是用同一个指数
- Alice 并不知道 $c$，这和 Bob 不知道 $α$ 的原因一样
- 虽然 $c$ 是被加密的，但它的可能取值范围并不足够大到保持其零知识的性质