I am having trouble understanding one part of the AFGH algorithm for proxy re-encryption (my background in discrete mathematics is lacking a bit).

The paper describes the algorithm setup the following way:

"To minimize a user’s secret storage and thus become key optimal, we present the BBS [Blaze et al. 1998], Elgamal-based [Elgamal 1984] scheme operating over two groups $\mathbb{G_1}$, $\mathbb{G_2}$ of prime order $q$ with a bilinear map $e$ : $\mathbb{G_1} × \mathbb{G_1}$ → $\mathbb{G_2}$. The system parameters are random generators $g \in \mathbb{G_1}$ and $Z=e(g,g) ∈ \mathbb{G_2}$."

Both the key and re-encryption key generation parts are easy to understand, they're the same as in a regular ElGamal scheme. My question is in the first level encryption description, where the authors state that a $c$ must be computed such that $c = (Z^{ak}, mZ^k)$, where $k$ is a randomly selected element from $\mathbb{Z_q}$.

I don't understand exactly what $(Z^{ak}, mZ^k)$ are. Is $Z^{ak}$ the same as $e(g^a, g^k) = e(g,g)^{ak}$ ?

And is $mZ^k$ the same as $e(g^k, g^k) = e(g,g)^{k^2}$ ?

EDIT: The paper can be found here.

EDIT: To clarify further:

While I can break down the maths behind an ElGamal scheme as

${c_1^{p-b-1}}{c_2} = ({g^k})^{p-b-1}m{(g^b)^k} = m[({g^{p-1})^k}{({g^k})^{-b}}]({g^k})^b = m1^k(g^k)^{-b}(g^k)^b = m$

I can't do that for $(Z^{ak}, mZ^k)$ or $mZ^k$. I would like to understand the intermediate steps like I have for an ElGamal.

  • 1
    $\begingroup$ The message space is probably the group $\mathbb{G}_2$ (and hence $mZ^k$ is the group operation). Could you add the reference/link please? $\endgroup$
    – ckamath
    Commented Aug 14, 2017 at 19:29
  • $\begingroup$ I'm sorry but I didn't understand your answer. Could you explain in a different way? Thank you! $\endgroup$
    – mcansado
    Commented Aug 14, 2017 at 19:47

1 Answer 1


Is $Z^{ak}$ the same as $e(g^a,g^k)=e(g,g)^{ak}$?

That's correct: by the bilinearity property of the pairing $Z^{ak}=e(g,g)^{ak}=e(g^a,g^k)$.

And is $mZ^k$ the same as $e(g^k,g^k)=e(g,g)^{k^2}$?

No it is not. $mZ^k$ is the group operation of $\mathbb{G}_2$ applied to $m$ and $Z^k$.

I would like to understand the intermediate steps like I have for an ElGamal.

The first-level decryption algorithm, given a ciphertext $c_a=(\alpha,\beta)$, as per their specification involves computing $\beta/\alpha^{1/a}$. If the ciphertext is properly formed then $\alpha=Z^{ak}$ and $\beta=mZ^k$ and therefore $$\frac{\beta}{\alpha^{1/a}}=\frac{mZ^k}{(Z^{ak})^{1/a}}=\frac{mZ^k}{Z^k}=m.$$

  • $\begingroup$ Sorry but I didn't quite understand the explanation for the $mZ^k$ part, could you clarify? Thank you, really appreciate it! $\endgroup$
    – mcansado
    Commented Aug 15, 2017 at 10:07
  • $\begingroup$ I edited the question to provide more clarification my comment. $\endgroup$
    – mcansado
    Commented Aug 15, 2017 at 10:39

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.