Paper 2021/1446
Batch point compression in the context of advanced pairingbased protocols
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 compressiondecompression 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 realworld pairingbased protocols such as Groth16. As a byproduct, when $q \equiv 2 \ (\mathrm{mod} \ 3)$ (in particular, $E_b$ is supersingular), we obtain a twodimensional analogue of BonehFranklin'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})$.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint.
 Keywords
 batch point compression BonehFranklin's encoding conic bundle structure cubic and sextic roots elliptic curves of $j$invariant $0$ Freeman's transformation generalized Kummer varieties high $2$adicity rationality problems recursive proof systems
 Contact author(s)
 dimitri koshelev @ gmail com
 History
 20220626: last of 4 revisions
 20211027: received
 See all versions
 Short URL
 https://ia.cr/2021/1446
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1446, author = {Dmitrii Koshelev}, title = {Batch point compression in the context of advanced pairingbased protocols}, howpublished = {Cryptology ePrint Archive, Paper 2021/1446}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1446}}, url = {https://eprint.iacr.org/2021/1446} }