Paper 2022/996

Fast Hashing to $\mathbb{G}_2$ on Pairing-friendly Curves with the Lack of Twists

Abstract

Pairing-friendly curves with the lack of twists, such as BW13-P310 and BW19-P286, have been receiving attention in pairing-based cryptographic protocols as they provide fast operation in the first pairing subgroup $\mathbb{G}_1$ at the 128-bit security level. However, they also incur a performance penalty for hashing to $\mathbb{G}_2$ simultaneously since $\mathbb{G}_2$ is totally defined over a full extension field. Furthermore, the previous methods for hashing to $\mathbb{G}_2$ focus on pairing-friendly curves admitting a twist, which can not be employed for our selected curves. In this paper, we propose a general method for hashing to $\mathbb{G}_2$on curves with the lack of twists. More importantly, we further optimize the general algorithm on curves with non-trival automorphisms, which is certainly suitable for BW13-P310 and BW19-P286. Theoretical estimations show that the latter would be more efficient than the former. For comparing the performance of the two proposed algorithms in detail, high speed software implementation over BW13-P310 is also provided on a 64-bit processor. Experimental results show that the general algorithm can be sped up by up to $88\%$ if the computational cost of cofactor multiplication for $\mathbb{G}_2$ is only considered, while the improved method is up to $71\%$ faster than the general one for the whole process.