Welcome to the resource topic for 2021/1446
Title:
Batch point compression in the context of advanced pairing-based protocols
Authors: Dmitrii Koshelev
Abstract:This paper continues author’s 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}. More precisely, we show 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} (with several multiplications and without inversions). As a result, for many 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}. We explain why the new methods are useful in the context of modern real-world pairing-based protocols such as Groth16. As a by-product, when q \equiv 2 \ (\mathrm{mod} \ 3) (in particular, E_b is supersingular), we obtain a two-dimensional analogue of Boneh–Franklin’s encoding, that is a way to sample two "independent’’ \mathbb{F}_{\!q}-points on E_b at the cost of one cubic root in \mathbb{F}_{\!q}. Finally, we comment on the case of four and more points from E_b(\mathbb{F}_{\!q}).
ePrint: https://eprint.iacr.org/2021/1446
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .