In the paper New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts from Waters and Lewko, how can the elements $R_3$ and $R'_3$ be eliminated in the decryption algorithm?


It uses an artifact of pairings over groups of composite order.

Specifically, if the order of $G$ is $p_1$ and the order of $H$ is $p_3$ and $p_1, p_3$ are relatively prime, then $e(G, H) = 1$.

This can be easily seen by considering the order of $e(G, H)$; we know that $e(G, H)^{p_1} = e(G^{p_1}, H) = e(1, H) = 1$, hence the order of $e(G, H)$ must be a divisor of $p_1$. Similar logic shows us that the order must also be a divisor of $p_3$. Because $p_1, p_3$ are relatively prime, the only common divisor they have is 1; hence the order of $e(G, H)$ must be 1.

Section 2.2 of the paper gives a different derivation of the same result.

Once we have that, we can see that $e(K_1, C_1) = e(g^r R_3, (u^{id}h)^s) = e(g_r, (u^{id}h)^s) \cdot e(R_3, (u^{id}h)^s)$. Since the order of $R_3$ (which $p_3$) and the order of $(u^{id}h)^s$ (which is $p_1$) are relatively prime, the second half is a constant factor 1, and so this reduces to $e(g_r, (u^{id}h)^s)$ (and thus $R_3$ disappears). Similar logic gets rid of $R'_3$ as well...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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