Generation of "independent" points on elliptic curves by means of Mordell--Weil lattices
PDF

Keywords

generation of "independent" points
isotrivial elliptic surfaces
Mordell--Weil lattices
Pedersen hash function
(super)elliptic curves
vector commitment schemes

How to Cite

Koshelev, D. (2024). Generation of "independent" points on elliptic curves by means of Mordell--Weil lattices. Mathematical Cryptology, 4(1), 11–22. Retrieved from https://ojs.test.flvc.org/mathcryptology/article/view/132727

Abstract

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.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2024 Dmitrii Koshelev