Paper 2022/794
Generation of "independent" points on elliptic curves by means of Mordell--Weil lattices
, École Normale Supérieure de LyonAbstract
This article develops a novel method of generating ``independent'' points on an ordinary elliptic curve over a finite field of large characteristic. Such points are actively used, e.g., in the Pedersen vector commitment scheme and its modifications. The conventional generation consists in sampling points successively via a hash function to the elliptic curve. The new generation method equally satisfies the NUMS (Nothing Up My Sleeve) principle, but it works faster on average. In other words, instead of finding each point separately, it is suggested to sample several points at once with a non-small success probability. This means that in practice the new method finishes in polynomial time, unless one is mysteriously unlucky. More precisely, some explicit formulas are represented in the article for deriving up to four ``independent'' points on any curve of $j$-invariant $0$. Such curves are known to be very popular in elliptic curve cryptography.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- elliptic curves"independent" pointsisotrivial elliptic surfacesMordell--Weil latticesvector commitment schemes
- Contact author(s)
- dimitri koshelev @ gmail com
- History
- 2024-03-05: last of 7 revisions
- 2022-06-20: received
- See all versions
- Short URL
- https://ia.cr/2022/794
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/794,
author = {Dmitrii Koshelev},
title = {Generation of "independent" points on elliptic curves by means of Mordell--Weil lattices},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/794},
year = {2022},
url = {https://eprint.iacr.org/2022/794}
}
