Paper 2021/1446

Batch point compression in the context of advanced pairing-based protocols

Abstract

This paper continues previous ones about compression of points on elliptic curves $E_b:y^2=x^3+b$ (with $j$-invariant $0$) over a finite field ${\mathbb{F}}_q$ of characteristic $p>3$. It is shown in detail how any two (resp., three) points from $E_b({\mathbb{F}}_q)$ can be quickly compressed to two (resp., three) elements of ${\mathbb{F}}_q$ (apart from a few auxiliary bits) in such a way that the corresponding decompression stage requires to extract only one cubic (resp., sextic) root in ${\mathbb{F}}_q$. As a result, for many fields ${\mathbb{F}}_q$ occurring in practice, the new compression-decompression methods are more efficient than the classical one with the two (resp., three) $x$ or $y$ coordinates of the points, which extracts two (resp., three) roots in ${\mathbb{F}}_q$. As a by-product, it is also explained how to sample uniformly at random two (resp., three) ``independent'' ${\mathbb{F}}_q$-points on $E_b$ essentially at the cost of only one cubic (resp., sextic) root in $$. Finally, the cases of four and more points from $$ are commented on as well.