Group Signatures with VLR Revocation Check

Question

I was reading the paper by Boneh et al. Link. The scheme describes what is called a Verifier Local Revocation Technique. The Scheme assumes that a Revocation List [RL] allows each verifier to check the validity of the signature. The revocation check works as follows:

• $e(T_2/A,\hat{u}) =^{?}e(T_1,\hat{v})$, Given $T_1 = A_iv^\alpha,T_2 = u^\alpha$
• $e(A_iv^\alpha/A,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

In the case that $A_i\in$[RL], $A = A_i$, then,

• $e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

The author then claims that these pairings are equal, The $(\hat{u},\hat{v})$ are generated as follows:

• $(\hat{u},\hat{v}) \leftarrow H_0 = (gpk,M,r) \in G_2^2$ , Given that:
• $u\leftarrow\psi(\hat{u})$, $v\leftarrow\psi(\hat{v})$,

I have three questions:

1. Why the $(\hat{u},\hat{v}) \in G_2^2$ not $G_2$.
2. What is the Hash Function that generates two parameters and is there a relation between them?
3. How the check $e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$ is valid.

Answer 1

I do not have access to the paper you have linked, but I certanly can answer the first question and maybe answer the third question:

1. $(\hat{u}, \hat{v}) \in G_2^2$ is a short version of $(\hat{u}, \hat{v}) \in (G_2 \times G_2)$ which is a short version of "$\hat{u} \in G_2$ and $\hat{v} \in G_2$".

2. Since I don't have access to the paper I'm gonna make some assumptions to answer the third question:

   • $e$ is a bi-linear mapping of the form $G_1 \times G_2 \rightarrow G_3$. I make this assumption based on the fact the second parameter is element of a group called $G_2$ which hints at the existence of a group $G_1$.
   • $\psi$ is a linear homomorphism from $G_2$ to $G_1$. This would make sense as the first parameter of $e$ would be an element of $G_1$ under the first assumption. Also $\psi(g_2)$ must be $g_1$ for the math below to check out.

Be $x, y \in Z_q$ with $\hat{u} = g_2^x$ and $\hat{v} = g_2^y$, then $u = g_1^x$ and $v = g_1^y$ since $\psi(g_2) = g_1$. This leads to:

$e(v^{\alpha}, \hat{u}) = e((g_1^y)^{\alpha}, g_2)^x = e(g_1^{\alpha y}, g_2)^x = e(g_1, g_2)^{(\alpha y) x} = e(g_1, g_2)^{(\alpha x) y} = e(g_1 ^ {\alpha x}, g_2^y) = e((g_1^x)^{\alpha}, g_2^y) = e(u^{\alpha}, \hat{v})$

AS stated above, this only works under the assumptions above, which are assumptions. If these are not correct feel free to leave a comment or edit.