Point-Halving and Subgroup Membership in Twisted Edwards Curves

Thomas Pornin

Paper 2022/1164

Point-Halving and Subgroup Membership in Twisted Edwards Curves

Thomas Pornin, NCC Group

Abstract

In this short note, we describe a process for halving a point on a twisted Edwards curve. This can be used to test whether a given point is in the subgroup of prime order $\ell$, which is used by some cryptographic protocols. On Curve25519, this new test is about twice faster than the classic method consisting of multiplying the source point by $\ell$.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: twisted Edwards curve subgroup point halving
Contact author(s): thomas pornin @ nccgroup com
History: 2022-09-06: approved; 2022-09-06: received; See all versions
Short URL: https://ia.cr/2022/1164
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1164,
      author = {Thomas Pornin},
      title = {Point-Halving and Subgroup Membership in Twisted Edwards Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1164},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1164}
}