You are looking at a specific version 20211231:193905 of this paper. See the latest version.

Paper 2021/1446

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

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. 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 \grqq 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)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
batch point compressionBoneh--Franklin's encodingconic bundle structurecubic and sextic rootselliptic curves of $j$-invariant $0$Freeman's transformationgeneralized Kummer varietieshigh $2$-adicityrationality problemsrecursive proof systems
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.