Paper 2024/1737
Embedded Curves and Embedded Families for SNARK-Friendly Curves
, French Institute for Research in Computer Science and AutomationAbstract
Based on the CM method for primality testing (ECPP) by Atkin and Morain published in 1993, we present two algorithms: one to generate embedded elliptic curves of SNARK-friendly curves, with a variable discriminant D; and another to generate families (parameterized by polynomials) with a fixed discriminant D. When D = 3 mod 4, it is possible to obtain a prime-order curve, and form a cycle. We apply our technique first to generate more embedded curves like Bandersnatch with BLS12-381 and we propose a plain twist-secure cycle above BLS12-381 with D = 6673027. We also devise about the scarcity of Bandersnatch-like CM curves, and show that with our algorithm, it is only a question of core-hours to find them. Second, we obtain families of prime-order embedded curves of discriminant D = 3 for BLS and KSS18 curves. Our method obtains families of embedded curves above KSS16 and can work for any KSS family. Our work generalizes the work on Bandersnatch (Masson, Sanso, and Zhang, and Sanso and El Housni).
Note: The paper is not published yet but under review for PKC2025.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- elliptic curvesSNARKembedded curvescycles of curves
- Contact author(s)
-
aurore guillevic @ inria fr
simon masson @ protonmail com - History
- 2024-10-25: approved
- 2024-10-24: received
- See all versions
- Short URL
- https://ia.cr/2024/1737
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1737,
author = {Aurore Guillevic and Simon Masson},
title = {Embedded Curves and Embedded Families for {SNARK}-Friendly Curves},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1737},
year = {2024},
url = {https://eprint.iacr.org/2024/1737}
}
