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 $$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 $$ if the computational cost of cofactor multiplication for $$ is only considered, while the improved method is up to $$ faster than the general one for the whole process.