Paper 2021/1446

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

Dmitrii Koshelev, École Normale Supérieure de Lyon
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 $\mathbb{F}_{\!q}$. Finally, the cases of four and more points from $E_b(\mathbb{F}_{\!q})$ are commented on as well.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
batch point compressioncubic and sextic rootselliptic curves of $j$-invariant $0$generating "independent" points
Contact author(s)
dimitri koshelev @ gmail com
History
2023-09-21: last of 8 revisions
2021-10-27: received
See all versions
Short URL
https://ia.cr/2021/1446
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1446,
      author = {Dmitrii Koshelev},
      title = {Batch point compression in the context of advanced pairing-based 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.