# Usage of pairings in proxy re-encryption algorithm

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.

• 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? Aug 14 '17 at 19:29
• I'm sorry but I didn't understand your answer. Could you explain in a different way? Thank you! Aug 14 '17 at 19:47

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.$$

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