I have two statements which I think are correct:

  1. $\beta, s$ are unknown. Only $g^\beta$ is known to the prover but not any of $g^{\beta s^i}$ for $i \ge 1$. If the prover is able to find group elements $A$ and $B$ such that $e(A, g^\beta) = e(B, g)$ then the prover knows a field element $a$ such that $A = g^a$

  2. And a more general statement: $\alpha, s$ are unknown to the prover. $g^\alpha, g^{\alpha s}, g^{\alpha s^2}, \dots ,g^{\alpha s^q}$ are known to the prover. If the prover is able to provide group elements $A$ and $B$ such that $e(A, g^\alpha) = e(B, g)$ then the prover knows coefficients $a_i$ such that $A = g^{\sum^q_{i=0}{a_i}\alpha s^i}$

Both of these statements intuitively seem correct to me but what are the commonly used cryptographic assumptions that I should reduce them to and how should I do that?

  • $\begingroup$ It does not invalidate it as in your example the prover knows a = 1 and that's what the statement is about. So you have to know some a $\endgroup$ Commented Feb 28 at 6:26
  • $\begingroup$ Sorry, I misread. $\endgroup$
    – Maeher
    Commented Feb 28 at 6:28
  • $\begingroup$ Actually, for a type 1 pairing, finding $A, B$ is easy: $A = g, B = g^\beta$ $\endgroup$
    – poncho
    Commented Mar 29 at 18:07

1 Answer 1


I think that both statements are untrue.

If the prover is furnished by a third party (who does not need to know $\alpha$) with $R=g^r$ and $S=g^{\alpha r}$) but not $\alpha$, then they can pick any $x$ and set $A=R^x$, $B=S^x$ without knowing $a=rx$.

In particular a malicious prover could obtain such values from a pair provided by a legitimate prover.

  • $\begingroup$ however this is exactly what is stated. Prover knows x. So the statement is that this is the only way to obtain the pair $\endgroup$ Commented Feb 28 at 8:16
  • $\begingroup$ @NikolayZakirov: No it is not. The prover does know $x$ but this does not furnish them with the knowledge of $a$ such that $g^a=A$. $\endgroup$
    – Daniel S
    Commented Feb 28 at 8:29
  • $\begingroup$ You are right, but I think the problem is that you allow a 3d party into the universe which is not really allowed. I guess I should rewrite my statements in terms of "there exists a polynomial time extractor that given same inputs as prover has which are $g$ and $g^{\beta}$ produces $a$ such that $A=g^a$. I think this is called knowledge of exponent assumption? $\endgroup$ Commented Feb 28 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.