Annotated literature

One entry per key in references.bib, stating why the work bears on the question this repository asks: how efficient an ECMH checksum for RIBLT cells can be made when the curve is derived from a short-lived public salt (or a shared secret), with 48–64-bit collision resistance and 16-byte identifiers. Within a section, entries are ordered by role: foundational results, attacks and bounds, methods used here, alternatives considered. The chapters cite works by key; in the book, each entry is headed by its citation as formatted from the bibliography, and each key cited links to its entry.

The entries keep four distinctions apart: an encoding, a hash indifferentiable from a random oracle, and a weak encoding with a collision-resistance reduction; a field primitive, a curve map, and a prepared accumulator operand; fixed-time and variable-time implementation; and setup reusable per field against setup per epoch. The module boundaries and the benchmark rows follow the same distinctions.

Curve generation, point counting, Weil descent and discrete-logarithm security

Generic discrete-logarithm bounds and attacks

• [shoup-1997] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. Advances in Cryptology – EUROCRYPT ’97, LNCS 1233, pp. 256–266, 1997. https://doi.org/10.1007/3-540-69053-0_18

  Any generic-group algorithm needs $\Omega (\sqrt{r})$ group operations to compute discrete logarithms in a group of prime order $r$. The reference work factor $2^{n/2}$ for an $n$-bit group is therefore tight for generic attacks, and every attack below it must use structure of the field, the curve or the map.

• [pollard-1978] J. M. Pollard. Monte Carlo Methods for Index Computation (mod p). Mathematics of Computation 32(143), pp. 918–924, 1978. https://doi.org/10.1090/S0025-5718-1978-0491431-9

  The rho method: $\sqrt{\pi r/2}$ expected group operations and constant memory. The reference attack behind every “rho” figure in the report.

• [van-oorschot-wiener-1999] P. C. van Oorschot, M. J. Wiener. Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology 12(1), pp. 1–28, 1999. https://doi.org/10.1007/PL00003816

  Parallel collision search with distinguished points: a linear speedup in the number of processors with negligible communication. It makes the generic cost a machine-time quantity, which is how the 48–64-bit target is to be read.

• [wiener-zuccherato-1998] M. J. Wiener, R. J. Zuccherato. Faster Attacks on Elliptic Curve Cryptosystems. Selected Areas in Cryptography – SAC ’98, LNCS 1556, pp. 190–200, 1999. https://doi.org/10.1007/3-540-48892-8_15
  [duursma-gaudry-morain-1999] I. Duursma, P. Gaudry, F. Morain. Speeding up the Discrete Log Computation on Curves with Automorphisms. Advances in Cryptology – ASIACRYPT ’99, LNCS 1716, pp. 103–121, 1999. https://doi.org/10.1007/978-3-540-48000-6_10

  Rho runs $\sqrt{2}$ faster with the negation map and $\sqrt{2m}$ faster on curves with an automorphism group of order $2m$ (Koblitz curves, curves with efficiently computable endomorphisms). The report divides the reference work factor by these factors where they apply: by $\sqrt{2}$ for every family, and by a further $\sqrt{2}$ for the GLS family over $\mathrm{GF}(2^{122})$, whose endomorphism group has order 4.

• [bernstein-lange-schwabe-2011] D. J. Bernstein, T. Lange, P. Schwabe. On the Correct Use of the Negation Map in the Pollard rho Method. Public Key Cryptography – PKC 2011, LNCS 6571, pp. 128–146. https://doi.org/10.1007/978-3-642-19379-8_8

  How the negation map is used in practice (fruitless cycles and their cost); the source of the practical constant in the rho figures.

• [bernstein-lange-2012] D. J. Bernstein, T. Lange. Computing Small Discrete Logarithms Faster. Progress in Cryptology – INDOCRYPT 2012, LNCS 7668, pp. 317–338. https://doi.org/10.1007/978-3-642-34931-7_19
  [bernstein-lange-2013] D. J. Bernstein, T. Lange. Non-uniform Cracks in the Concrete: The Power of Free Precomputation. Advances in Cryptology – ASIACRYPT 2013, Part II, LNCS 8270, pp. 321–340. https://doi.org/10.1007/978-3-642-42045-0_17

  With a precomputed table of size about $N^{2/3}$, each further discrete logarithm in a group of size $N$ costs about $N^{1/3}$ operations. A fixed curve would let an attacker amortize this across epochs. Deriving the curve from the salt prevents direct reuse of curve-specific tables; field-level arithmetic and work on the candidate space remain reusable. These two papers motivate a curve per namespace.

• [corrigan-gibbs-kogan-2018] H. Corrigan-Gibbs, D. Kogan. The Discrete-Logarithm Problem with Preprocessing. Advances in Cryptology – EUROCRYPT 2018, Part II, LNCS 10821, pp. 415–447. https://doi.org/10.1007/978-3-319-78375-8_14

  Lower bound $S{T}^2=\tilde{\Omega }(\epsilon N)$ for generic discrete-logarithm algorithms with $S$ bits of advice and $T$ online queries. It shows the Bernstein–Lange tradeoff is optimal and lets the report state exactly what a persistent curve would concede.

• [menezes-okamoto-vanstone-1993] A. J. Menezes, T. Okamoto, S. A. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory 39(5), pp. 1639–1646, 1993. https://doi.org/10.1109/18.259647
  [frey-rueck-1994] G. Frey, H.-G. Rück. A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves. Mathematics of Computation 62(206), pp. 865–874, 1994. https://doi.org/10.1090/S0025-5718-1994-1218343-6

  The pairing reductions that move the discrete logarithm into $\mathrm{GF}(q^k)$ when $r$ divides $q^k-1$. They are why every certificate requires an embedding degree above $2^{20}$ (EMBEDDING_MIN in src/curvegen/number.rs).

• [smart-1999] N. P. Smart. The Discrete Logarithm Problem on Elliptic Curves of Trace One. Journal of Cryptology 12(3), pp. 193–196, 1999. https://doi.org/10.1007/s001459900052

  Curves with $|E|=q$ have a polynomial-time discrete logarithm. The Weierstrass policy excludes $r=q$; the binary and cofactor families cannot be anomalous. One clause in the policy documentation.

• [bos-et-al-2012] J. W. Bos, M. E. Kaihara, T. Kleinjung, A. K. Lenstra, P. L. Montgomery. Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles Using Sloppy Reduction. International Journal of Applied Cryptography 2(3), pp. 212–228, 2012. https://doi.org/10.1504/IJACT.2012.045590
  [wenger-wolfger-2014] E. Wenger, P. Wolfger. Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster. Selected Areas in Cryptography – SAC 2014, LNCS 8781, pp. 363–379. https://doi.org/10.1007/978-3-319-13051-4_22
  [bernstein-et-al-2016] D. J. Bernstein, S. Engels, T. Lange, R. Niederhagen, C. Paar, P. Schwabe, R. Zimmermann. Faster Elliptic-Curve Discrete Logarithms on FPGAs. Cryptology ePrint Archive, Paper 2016/382. https://eprint.iacr.org/2016/382
  [bailey-et-al-2009-breaking] D. V. Bailey, L. Batina, D. J. Bernstein, P. Birkner, J. W. Bos, H.-C. Chen, C.-M. Cheng, G. van Damme, G. de Meulenaer, L. J. Dominguez Perez, J. Fan, T. Güneysu, F. Gürkaynak, T. Kleinjung, T. Lange, N. Mentens, R. Niederhagen, C. Paar, F. Regazzoni, P. Schwabe, L. Uhsadel, A. Van Herrewege, B.-Y. Yang. Breaking ECC2K-130. Cryptology ePrint Archive, Paper 2009/541. https://eprint.iacr.org/2009/541
  [certicom-1997] Certicom Research. The Certicom ECC Challenge. Certicom, 1997. Updated 2003; lists ECC2K-108 (GF(2^109), Koblitz) solved 4 April 2000 by R. Harley et al. https://www.certicom.com/content/dam/certicom/images/pdfs/cert_ecc_challenge.pdf
  [bailey-et-al-2009] D. V. Bailey, B. Baldwin, L. Batina, D. J. Bernstein, P. Birkner, J. W. Bos, G. van Damme, G. de Meulenaer, J. Fan, T. Güneysu, F. Gurkaynak, T. Kleinjung, T. Lange, N. Mentens, C. Paar, F. Regazzoni, P. Schwabe, L. Uhsadel. The Certicom Challenges ECC2-X. Cryptology ePrint Archive, Paper 2009/466; SHARCS 2009. https://eprint.iacr.org/2009/466

  The solved instances that calibrate the target: a 112-bit prime-field curve on about 215 PlayStation 3 consoles (2012), a 113-bit Koblitz curve on 18 FPGAs in an extrapolated 24 days (2014), the SECG curve sect113r2 and a 117.35-bit binary instance on FPGAs (2016), and the still-open ECC2K-130 effort with its cost analysis. They place $2^{56}$ to $2^{60}$ group operations within reach of a dedicated effort over months, the reference against which the 48–64-bit target is weighed.

• [galbraith-gaudry-2016] S. D. Galbraith, P. Gaudry. Recent Progress on the Elliptic Curve Discrete Logarithm Problem. Designs, Codes and Cryptography 78(1), pp. 51–72, 2016. https://doi.org/10.1007/s10623-015-0146-7

  Survey of the elliptic-curve discrete logarithm problem: no subexponential algorithm is known for curves over prime fields or over $\mathrm{GF}(2^n)$ with $n$ prime, and the state of index calculus over extension fields. Cited for the statement that generic attacks are the best known.

Weil descent and index calculus over extension fields

• [frey-1998] G. Frey, H. Gangl. How to Disguise an Elliptic Curve (Weil Descent). Talk at ECC ’98, Waterloo. Slides dated 15 September 1998; the conference slides page lists the talk under Frey alone. https://web.archive.org/web/2005/http://cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.html

  The idea of Weil restriction as an attack: an elliptic curve over $\mathrm{GF}(q^n)$ becomes an $n$-dimensional abelian variety over $\mathrm{GF}(q)$.

• [gaudry-hess-smart-2002] P. Gaudry, F. Hess, N. P. Smart. Constructive and Destructive Facets of Weil Descent on Elliptic Curves. Journal of Cryptology 15(1), pp. 19–46, 2002. Preprint: HP Labs Technical Report HPL-2000-10. https://doi.org/10.1007/s00145-001-0011-x

  The GHS construction: the descent gives a hyperelliptic curve over $\mathrm{GF}(q)$ of genus about $2^{m-1}$, $m$ the “magic number” determined by the minimal polynomial of $\sqrt{b}$ under Frobenius. sage/ghs.sage computes $m$ for the binary families and the genus that results.

• [menezes-qu-2001] A. Menezes, M. Qu. Analysis of the Weil Descent Attack of Gaudry, Hess and Smart. Topics in Cryptology – CT-RSA 2001, LNCS 2020, pp. 308–318. https://doi.org/10.1007/3-540-45353-9_23

  For $n$ prime in $[160,600]$ the GHS genus is too large for any attack. The degree 127 lies outside that range and is the exceptional small prime degree: 2 has order 7 modulo 127, so $x^{127}-1$ splits into degree-7 factors over ${\mathbb{F}}_2$ and the minimal genus is $2^6$, so the descent must be examined for $\mathrm{GF}(2^{127})$.

• [galbraith-hess-smart-2002] S. D. Galbraith, F. Hess, N. P. Smart. Extending the GHS Weil Descent Attack. Advances in Cryptology – EUROCRYPT 2002, LNCS 2332, pp. 29–44. ePrint 2001/054 is PostScript only. https://doi.org/10.1007/3-540-46035-7_3

  Isogenous curves have equal order and the attack transfers along isogenies, so the vulnerable set is a union of isogeny classes, not of curves. sage/ghs122.sage checks the class, and the $m=127$ statement counts classes.

• [hess-2003] F. Hess. The GHS Attack Revisited. Advances in Cryptology – EUROCRYPT 2003, LNCS 2656, pp. 374–387. https://doi.org/10.1007/3-540-39200-9_23

  Generalizes GHS: with $\sqrt{b}={\gamma }_1\cdot {\gamma }_2$ for ${\gamma }_1,{\gamma }_2$ in the span of a degree-7 factor’s kernel and ${\mathbb{F}}_2$, the descent still has genus 127 or 128. Over $\mathrm{GF}(2^{127})$ this reaches 4537 Frobenius classes, 65 of them of order $2\cdot \text{prime}$ and so admissible to the certificate, a heuristic $2^{-52}$ of the admissible isogeny classes (Hess’s own estimate $s\cdot q^{2d}/(q^{n/2}\cdot n)$ gives $2^{-52.3}$). Accepted without a check: across $T$ epochs the probability is at most $T$ times this heuristic figure, and a descent compromises only its own epoch.

• [hess-2005] F. Hess. Weil Descent Attacks. In: Advances in Elliptic Curve Cryptography, ed. I. F. Blake, G. Seroussi, N. P. Smart, London Mathematical Society Lecture Note Series 317, Cambridge University Press, pp. 151–180, 2005. https://doi.org/10.1017/CBO9780511546570.010

  Survey chapter covering the above; cited where the problem statement states the Weil-descent conclusion without the derivation.

• [hankerson-karabina-menezes-2009] D. Hankerson, K. Karabina, A. Menezes. Analyzing the Galbraith–Lin–Scott Point Multiplication Method for Elliptic Curves over Binary Fields. IEEE Transactions on Computers 58(10), pp. 1411–1420, 2009. https://doi.org/10.1109/TC.2009.61

  Security analysis of GLS curves over $\mathrm{GF}(2^{2m})$: the GHS descent to $\mathrm{GF}(2^m)$ and the $n=2$ index calculus leave the discrete logarithm at about $2^m$, the rho cost. It is the reference for the $\mathrm{GF}(2^{122})$ family’s security statement.

• [gaudry-2009] P. Gaudry. Index Calculus for Abelian Varieties of Small Dimension and the Elliptic Curve Discrete Logarithm Problem. Journal of Symbolic Computation 44(12), pp. 1690–1702, 2009. https://doi.org/10.1016/j.jsc.2008.08.005

  Index calculus for $E$ over $\mathrm{GF}(q^n)$ in $\tilde{O}(q^{2-2/n})$ for fixed $n\ge 2$: $\tilde{O}(q)$ at $n=2$, which ties rho for every quadratic-extension family here (fp61x2, fp64x2, goldilocks2, and $\mathrm{GF}(2^{122})$ as $\mathrm{GF}(2^{61}{)}^2$). The reason degree 2 is admissible and degree $\ge 3$ is not.

• [diem-2011] C. Diem. On the Discrete Logarithm Problem in Elliptic Curves. Compositio Mathematica 147(1), pp. 75–104, 2011. https://doi.org/10.1112/S0010437X10005075

  The discrete logarithm over $\mathrm{GF}(q^n)$ is subexponential when $n$ grows with $\log q$ within fixed bounds. It does not apply at $n=2$ or at prime $n=127,109,107$; cited to say so.

• [joux-vitse-2012] A. Joux, V. Vitse. Cover and Decomposition Index Calculus on Elliptic Curves Made Practical. Advances in Cryptology – EUROCRYPT 2012, LNCS 7237, pp. 9–26. Full version subtitled “Application to a Previously Unreachable Curve over F_{p^6}”. https://doi.org/10.1007/978-3-642-29011-4_3

  Cover and decomposition attacks made practical for $\mathrm{GF}(q^6)$-type fields; the boundary case showing where composite-degree extensions become dangerous, and that $n=2$ is not among them.

• [semaev-2004] I. Semaev. Summation Polynomials and the Discrete Logarithm Problem on Elliptic Curves. Cryptology ePrint Archive, Paper 2004/031. https://eprint.iacr.org/2004/031
  [faugere-et-al-2012] J.-C. Faugère, L. Perret, C. Petit, G. Renault. Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields. Advances in Cryptology – EUROCRYPT 2012, LNCS 7237, pp. 27–44. https://doi.org/10.1007/978-3-642-29011-4_4
  [petit-quisquater-2012] C. Petit, J.-J. Quisquater. On Polynomial Systems Arising from a Weil Descent. Advances in Cryptology – ASIACRYPT 2012, LNCS 7658, pp. 451–466. https://doi.org/10.1007/978-3-642-34961-4_28

  Summation polynomials and the heuristic index calculus over $\mathrm{GF}(2^n)$, $n$ prime. The authors’ own estimate places the crossover with generic methods near $n\approx 2000$; the degrees used here are far below it, and the heuristics remain unconfirmed. Cited as the reason prime-degree binary fields are still considered generic-secure.

Point counting and curve generation

• [schoof-1995] R. Schoof. Counting Points on Elliptic Curves over Finite Fields. Journal de Théorie des Nombres de Bordeaux 7(1), pp. 219–254, 1995. https://doi.org/10.5802/jtnb.142

  Schoof’s algorithm and the Elkies–Atkin improvements (SEA): polynomial-time point counting over any finite field. PARI’s ellsea runs it for the odd-field families, with the Elkies-prime early abort the pari module uses.

• [satoh-2000] T. Satoh. The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and Its Point Counting. Journal of the Ramanujan Mathematical Society 15(4), pp. 247–270, 2000.
  [mestre-2000] J.-F. Mestre. Lettre adressée à Gaudry et Harley. Letter, December 2000. The arithmetic–geometric mean point-counting method; cited through [gaudry-2002] and [satoh-skjernaa-taguchi-2003].
  [gaudry-2002] P. Gaudry. A Comparison and a Combination of SST and AGM Algorithms for Counting Points of Elliptic Curves in Characteristic 2. Advances in Cryptology – ASIACRYPT 2002, LNCS 2501, pp. 311–327. https://doi.org/10.1007/3-540-36178-2_20

  Canonical lifts and Mestre’s AGM for characteristic 2: counting a curve over $\mathrm{GF}(2^{127})$ in milliseconds. The Rust agm counter is a canonical lift of this kind and PARI’s F2xq_ellcard is Harley’s variant of the AGM; gaudry-2002 is the comparison that established the method.

• [satoh-skjernaa-taguchi-2003] T. Satoh, B. Skjernaa, Y. Taguchi. Fast Computation of Canonical Lifts of Elliptic Curves and its Application to Point Counting. Finite Fields and Their Applications 9(1), pp. 89–101, 2003. https://doi.org/10.1016/S1071-5797(02)00013-8

  The SST variant of the canonical lift, one of the methods gaudry-2002 compares; the method implemented is the AGM.

• [lercier-lubicz-2003] R. Lercier, D. Lubicz. Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time. Advances in Cryptology – EUROCRYPT 2003, LNCS 2656, pp. 360–373. https://doi.org/10.1007/3-540-39200-9_22

  Quasi-quadratic point counting in small characteristic via canonical lifts. The asymptotic improvement does not establish a concrete gain at degree 127; this implementation uses the AGM.

• [fouquet-gaudry-harley-2001] M. Fouquet, P. Gaudry, R. Harley. Finding Secure Curves with the Satoh-FGH Algorithm and an Early-Abort Strategy. Advances in Cryptology – EUROCRYPT 2001, LNCS 2045, pp. 14–29. https://doi.org/10.1007/3-540-44987-6_2

  The early-abort strategy: test small torsion before counting, since most candidates fail on the group order. The direct ancestor of curvegen::sieve, whose witnesses double as certificate rejections.

• [rabin-1980] M. O. Rabin. Probabilistic Algorithm for Testing Primality. Journal of Number Theory 12(1), pp. 128–138, 1980. https://doi.org/10.1016/0022-314X(80)90084-0
  [arnault-1995] F. Arnault. Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases. Journal of Symbolic Computation 20(2), pp. 151–161, 1995. https://doi.org/10.1006/jsco.1995.1042
  [albrecht-et-al-2018] M. R. Albrecht, J. Massimo, K. G. Paterson, J. Somorovsky. Prime and Prejudice: Primality Testing Under Adversarial Conditions. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18), pp. 281–298. https://doi.org/10.1145/3243734.3243787

  The Miller–Rabin test and the constructions of composites that pass it for fixed bases. The certificate accepts $r$ as a probable prime to 24 fixed bases; these papers are why the statement is conditional. The prover cannot skip an admissible candidate, since rejection witnesses exist only for inadmissible ones. For the accepted candidate the verifier takes $r$ from the prover and checks $rQ=O$ for the cofactor-cleared hashed point $Q$, the Hasse window, and the 24 Miller–Rabin bases; the order argument is conditional on $r$ being prime.

• [bernstein-et-al-2015] D. J. Bernstein, T. Chou, C. Chuengsatiansup, A. Hülsing, E. Lambooij, T. Lange, R. Niederhagen, C. van Vredendaal. How to Manipulate Curve Standards: A White Paper for the Black Hat. Security Standardisation Research – SSR 2015, LNCS 9497, pp. 109–139. https://doi.org/10.1007/978-3-319-27152-1_6
  [flori-et-al-2015] J.-P. Flori, J. Plût, J.-R. Reinhard, M. Ekerå. Diversity and Transparency for ECC. Cryptology ePrint Archive, Paper 2015/659. https://eprint.iacr.org/2015/659
  [bos-et-al-2016] J. W. Bos, C. Costello, P. Longa, M. Naehrig. Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis. Journal of Cryptographic Engineering 6(4), pp. 259–286, 2016. https://doi.org/10.1007/s13389-015-0097-y

  Why the curve is derived from a public seed with a verifiable certificate rather than taken from a standard: manipulable standards, transparent generation of many curves, and the efficiency/security tradeoffs of the selection procedure itself. flori-et-al-2015 is the closest prior work on generating a fresh curve per use.

• [ansi-x9-62-1998] Accredited Standards Committee X9. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). American National Standards Institute, ANSI X9.62-1998, 1999.
  [rfc5639] M. Lochter, J. Merkle. Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation. RFC 5639, 2010. https://doi.org/10.17487/RFC5639
  [baigneres-et-al-2015] T. Baignères, C. Delerablée, M. Finiasz, L. Goubin, T. Lepoint, M. Rivain. Trap Me If You Can – Million Dollar Curve. Cryptology ePrint Archive, Paper 2015/1249. https://eprint.iacr.org/2015/1249
  [lenstra-wesolowski-2017] A. K. Lenstra, B. Wesolowski. Trustworthy Public Randomness with Sloth, Unicorn, and Trx. International Journal of Applied Cryptography 3(4), pp. 330–343, 2017. https://eprint.iacr.org/2015/366

  Curves derived from public randomness. X9.62’s verifiably random curves and Brainpool’s verifiably pseudo-random ones hash a published seed, which bernstein-et-al-2015 shows still leaves the seed’s author a choice. The Million Dollar Curve takes its seed from several national lotteries and turns it into parameters by a deterministic filter, for one curve meant to replace P-256 and Curve25519. Lenstra and Wesolowski’s trx derives a stream of curves from the output of their beacon, unicorn: the first acceptable candidate in a fixed enumeration, with data to show that the earlier candidates fail, which is the shape of this repository’s certificate. Both provide curves for general use at the 128-bit level, where trx takes hours per curve; here a new beacon value selects a smaller curve for each namespace.

• [safecurves] D. J. Bernstein, T. Lange. SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography. Fields: https://safecurves.cr.yp.to/field.html. https://safecurves.cr.yp.to
  [bernstein-lange-2024] D. J. Bernstein, T. Lange. Safe curves for elliptic-curve cryptography. Cryptology ePrint Archive, Paper 2024/1265. https://eprint.iacr.org/2024/1265

  The rigidity criterion the selection satisfies by construction, and (paper, §4.4) the batched affine addition cost of about $5M+S$ per step that an attacker’s rho implementation attains, which is the add cost the collision-resistance figures assume for the attacker.

• [syta-et-al-2017] E. Syta, P. Jovanovic, E. Kokoris-Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer, B. Ford. Scalable Bias-Resistant Distributed Randomness. 2017 IEEE Symposium on Security and Privacy, pp. 444–460. https://doi.org/10.1109/SP.2017.45
  [kelsey-et-al-2019] J. Kelsey, L. T. A. N. Brandão, R. Peralta, H. Booth. A Reference for Randomness Beacons: Format and Protocol Version 2. NIST, NIST IR 8213 (draft), 2019. https://doi.org/10.6028/NIST.IR.8213-draft

  Randomness beacons: where an unpredictable public salt comes from, and the unpredictability requirement the precomputation argument depends on.

• [bonneau-clark-goldfeder-2015] J. Bonneau, J. Clark, S. Goldfeder. On Bitcoin as a Public Randomness Source. Cryptology ePrint Archive, Paper 2015/1015. https://eprint.iacr.org/2015/1015

  Bitcoin block hashes as a beacon: a lower bound on each block’s min-entropy, and the cost to a miner of biasing the output by withholding blocks, which is the manipulation this study leaves to the protocol.

• [koblitz-1991] N. Koblitz. CM-Curves with Good Cryptographic Properties. Advances in Cryptology – CRYPTO ’91, LNCS 576, pp. 279–287, 1992. https://doi.org/10.1007/3-540-46766-1_22
  [solinas-2000] J. A. Solinas. Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography 19(2–3), pp. 195–249, 2000. https://doi.org/10.1023/A:1008306223194

  Koblitz (subfield) curves: fast scalar multiplication, which the workload does not use, and a $\sqrt{2m}$ rho speedup, which it cannot afford. Excluded.

• [sutherland-2012] A. V. Sutherland. Constructing elliptic curves over finite fields with prescribed torsion. Mathematics of Computation 81, pp. 1131–1147, 2012. https://doi.org/10.1090/S0025-5718-2011-02538-X

  Constructing curves with prescribed torsion through modular curves: an alternative sampler that would change the canonical candidate stream and its certificate. Not used.

• [pari-gp] The PARI Group. PARI/GP. https://pari.math.u-bordeaux.fr/.
  [sagemath] The Sage Developers. SageMath, the Sage Mathematics Software System. https://www.sagemath.org/.

  The point-counting and primality oracle for fixtures and the pari feature, and the system in which the reference programs under sage/ are written; Sage counts points through PARI.

Hash-to-curve, encodings, ECMH and inversion

Security contract and foundational constructions

• [bellare-micciancio-1997] M. Bellare, D. Micciancio. A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost. Advances in Cryptology – EUROCRYPT ’97, LNCS 1233, pp. 163–192, 1997. https://doi.org/10.1007/3-540-69053-0_13

  Establishes the incremental multiset-hashing framework underlying ECMH. It supplies the algebraic security question for cell checksums; a fast map and group operation must be assessed within that question rather than by mapping speed alone.

• [wegman-carter-1981] M. N. Wegman, J. L. Carter. New Hash Functions and Their Use in Authentication and Set Equality. Journal of Computer and System Sciences 22(3), pp. 265–279, 1981. https://doi.org/10.1016/0022-0000(81)90033-7

  Defines almost-universal hash families and applies them to authentication and to testing sets for equality under insertion and deletion. The salted projection of an item’s unsalted identifier is such a family: its collision bound holds for identifiers fixed before the salt, and after the salt the identifiers’ being hash outputs leaves only a generic search (Adversary).

• [wagner-2002] D. Wagner. A Generalized Birthday Problem. Advances in Cryptology – CRYPTO 2002, LNCS 2442, pp. 288–304. https://doi.org/10.1007/3-540-45708-9_19

  The generalized birthday algorithm combines many independently chosen terms into an additive relation; for an $n$-bit modulus and about $2^{\sqrt{n}}$ lists it takes about $2^{2\sqrt{n}}$ operations, subexponential in $n$. Its list-merging step needs a group representation in which partial sums can be matched on bits, as in $\mathbb{Z}/2^n$ or $\mathbb{Z}/r$. Elliptic-curve groups have no such representation, so without discrete logarithms the $k$-sum bound is not the attack cost for these checksums; with them, the checksum is AdHash modulo $r$ and the algorithm applies (Known weaknesses).

• [meyer-2022] A. Meyer. Range-Based Set Reconciliation. arXiv:2212.13567 [cs.CR], 2022. Section numbers refer to the short version at https://github.com/AljoschaMeyer/rbsr_short. https://arxiv.org/abs/2212.13567

  Range-based set reconciliation with fingerprints combined in a monoid. Section V-B surveys fingerprint groups against an adversary who chooses items, and cites additive hashes of 2688 to 4160 bits for 128-bit security against Wagner’s algorithm and its successors (mihajloska-gligoroski-samardjiska-2015).

• [mihajloska-gligoroski-samardjiska-2015] H. Mihajloska, D. Gligoroski, S. Samardjiska. Reviving the Idea of Incremental Cryptography for the Zettabyte Era Use Case: Incremental Hash Functions Based on SHA-3. Cryptology ePrint Archive, Paper 2015/1028. Also in International Workshop on Open Problems in Network Security (iNetSec 2015), Springer, pp. 97–111. https://eprint.iacr.org/2015/1028

  Incremental hash functions over SHAKE outputs combined by word-wise addition modulo $2^{64}$, with output lengths chosen against Wagner’s algorithm: 2688 bits for 128-bit security when a relation has at most $2^{25}$ terms, 4160 bits without a bound. The security chapter compares these sizes with a checksum whose discrete logarithms are known.

• [phan-wagner-2006] R. C.-W. Phan, D. Wagner. Security Considerations for Incremental Hash Functions Based on Pair Block Chaining. Computers & Security 25, pp. 131–136, 2006. https://doi.org/10.1016/j.cose.2005.12.006

  Collisions in randomize-then-combine hashes of pair-chained message blocks: repeated blocks, coinciding padding and cyclic chaining give distinct messages with equal hashes, in several cases with equal multisets of pair terms, so that modular addition fails as XOR does. They follow from the encoding of a message into terms, not from the combining operation; here each item is hashed whole to one term and the digest of a multiset is meant to be independent of order, so the attacks do not carry over. The paper also records a PCIHF variant proposed with its modulus raised from $2^{160}$ to $2^{1600}$ in response to Wagner’s algorithm.

• [maitin-shepard-et-al-2016] J. Maitin-Shepard, M. Tibouchi, D. F. Aranha. Elliptic Curve Multiset Hash. arXiv:1601.06502 [cs.CR]. Journal version: The Computer Journal, 2016, https://doi.org/10.1093/comjnl/bxw053. https://arxiv.org/abs/1601.06502

  Gives the binary-curve ECMH construction, its weak-encoding collision-security reduction and separate mapping, group-operation and batching measurements. It distinguishes a sufficient ECMH encoding from a hash indifferentiable from a random oracle; applying the reduction to this repository’s adapted map still requires establishing that map’s hypotheses and reduction loss.

• [brier-et-al-2010] E. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, M. Tibouchi. Efficient Indifferentiable Hashing into Ordinary Elliptic Curves. Advances in Cryptology – CRYPTO 2010, LNCS 6223, pp. 237–254. https://doi.org/10.1007/978-3-642-14623-7_13

  Provides constructions and analysis for indifferentiable hashing into ordinary elliptic curves. It explains why a deterministic encoding and a random-oracle hash require different contracts, even when the implementations share mapping formulas.

• [farashahi-pellikaan-sidorenko-2008] R. R. Farashahi, R. Pellikaan, A. Sidorenko. Extractors for Binary Elliptic Curves. Designs, Codes and Cryptography 49(1–3), pp. 171–186, 2008. https://doi.org/10.1007/s10623-008-9187-5

  Deterministic extraction of a subfield coefficient from uniformly distributed points on binary curves of even extension degree. It distinguishes randomness extraction from point encoding; it supplies no proof of the current $x$-plus-sign codec or of the hash-to-curve distribution.

• [shallue-van-de-woestijne-2006] A. Shallue, C. E. van de Woestijne. Construction of Rational Points on Elliptic Curves over Finite Fields. Algorithmic Number Theory (ANTS-VII), LNCS 4076, pp. 510–524, 2006. https://doi.org/10.1007/11792086_36

  Constructs rational points deterministically over finite fields and supplies the lineage of the SW maps used in later hashing work. Its relevance is the point-construction mechanism; the required output-distribution and ECMH-security arguments come from additional analysis.

• [boneh-lynn-shacham-2001] D. Boneh, B. Lynn, H. Shacham. Short Signatures from the Weil Pairing. Advances in Cryptology – ASIACRYPT 2001, LNCS 2248, pp. 514–532. https://doi.org/10.1007/3-540-45682-1_30

  MapToGroup, an early reference for counter-based rejection sampling into a curve group. Here the shared driver curve::h2c samples digest-derived candidate encodings until decoding succeeds; the weak-encoding condition of maitin-shepard-et-al-2016, a sufficient route to collision resistance, may be established from each codec’s accepted preimages, including identity and torsion handling. The variable-time path is evaluated under the project’s public-input assumption.

• [rfc9380] A. Faz-Hernández, S. Scott, N. Sullivan, R. S. Wahby, C. A. Wood. Hashing to Elliptic Curves. RFC 9380, 2023. https://doi.org/10.17487/RFC9380

  Specifies hash-to-field, domain separation, mappings and cofactor handling for hash-to-curve suites. It provides a reference decomposition for the implementation and benchmarks, while its standardized suites do not directly certify arbitrary ephemeral curves or the binary maps used here.

• [bernstein-et-al-2013] D. J. Bernstein, M. Hamburg, A. Krasnova, T. Lange. Elligator: Elliptic-Curve Points Indistinguishable from Uniform Random Strings. Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS ’13), pp. 967–980. https://doi.org/10.1145/2508859.2516734

  Introduces Elligator and the distinction between curve-point encodings and uniform-looking bit strings. Elligator 2 is an applicable mapping reference for suitable odd-characteristic curves with rational two-torsion, but its encoding alone must not be labeled a full random-oracle hash.

• [hamburg-2020] M. Hamburg. Indifferentiable Hashing from Elligator 2. Cryptology ePrint Archive, Paper 2020/1513. https://eprint.iacr.org/2020/1513

  Analyzes indifferentiable constructions from Elligator 2, including hash-twice-and-add. It supports the explicit separation of single-map and two-map interfaces and their costs; the argument must be matched to the actual map and target group.

Binary maps and their implementation

• [aranha-et-al-2014] D. F. Aranha, P.-A. Fouque, C. Qian, M. Tibouchi, J.-C. Zapalowicz. Binary Elligator Squared. Selected Areas in Cryptography – SAC 2014, LNCS 8781. https://doi.org/10.1007/978-3-319-13051-4_2

  Optimizes the characteristic-two SW map through shared inversion and gives preimage analysis, quadratic-solving techniques and implementation measurements. It is a direct comparison for the repository’s binary mapping alternatives; the paper’s full Elligator Squared representation timing must not be mistaken for a single hash-to-point timing.

• [maitin-shepard-2017] J. Maitin-Shepard. Optimal software-implemented Itoh–Tsujii inversion for F_{2^m}. Designs, Codes and Cryptography 82, pp. 301–318, 2017. https://doi.org/10.1007/s10623-016-0260-1

  Optimizes Itoh–Tsujii inversion chains jointly with multi-squaring tables using machine-specific measurements, including degree 127. It closes the gap between minimizing symbolic multiplication counts and minimizing the actual binary-map cost, subject to memory and timing constraints.

• [fong-et-al-2004] K. Fong, D. Hankerson, J. López, A. Menezes. Field Inversion and Point Halving Revisited. IEEE Transactions on Computers 53(8), pp. 1047–1059, 2004. The open copy is the technical-report version. https://doi.org/10.1109/TC.2004.43

  Examines binary-field inversion, division and SIMD implementation costs. These primitives inform the affine/projective and decoding tradeoffs here, although its point-halving scalar-multiplication results do not measure arbitrary RIBLT-cell additions.

Odd-characteristic mapping alternatives

• [chavez-saab-et-al-2022] J. Chávez-Saab, F. Rodríguez-Henríquez, M. Tibouchi. SwiftEC: Shallue–van de Woestijne Indifferentiable Function to Elliptic Curves. Journal of Cryptology 37, 2024. https://doi.org/10.1007/s00145-024-09529-y

  SwiftEC reduces full-point hashing to one square-root extraction on compatible odd-characteristic curves, with per-curve parameter construction and possible isogeny adaptation. For ephemeral curves, compatibility and setup amortization are part of the comparison; its $x$-only output, of lower cost, is insufficient by itself for signed arbitrary additions.

• [aranha-et-al-2023] D. F. Aranha, B. S. Hvass, B. Spitters, M. Tibouchi. Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing. ACM SIGSAC Conference on Computer and Communications Security (CCS 2023), pp. 3228–3238. https://doi.org/10.1145/3576915.3616597

  Gives faster constant-time character computation and concrete SwiftEC measurements. It is the comparison for the variable-time Jacobi and special-prime exponentiation paths used here, without transferring its larger-field speedups to the 48–64-bit collision-security configurations.

• [koshelev-2024] D. Koshelev. Simultaneously Simple, Universal, and Indifferentiable Hashing to Elliptic Curves. Cryptology ePrint Archive, Paper 2024/085. https://eprint.iacr.org/2024/085

  Extends one-root indifferentiable hashing in characteristic greater than three and is a possible way to broaden SwiftEC’s applicability. Its relevance is conditional on checking the exact target-curve construction, exceptional inputs and setup cost; no speedup over the maps implemented here has been established.

• [koshelev-2025] D. Koshelev. Hashing-friendly elliptic curves. Cryptology ePrint Archive, Paper 2025/1926, revised March 2026. https://eprint.iacr.org/2025/1926

  Studies batching root extraction on specially constructed hashing-friendly curves. It represents a joint curve-selection and hashing alternative, with distribution questions that require separate analysis, rather than an optimization already applicable to the repository’s current candidate stream.

Field primitives used by mapping and decoding

• [bernstein-yang-2019] D. J. Bernstein, B.-Y. Yang. Fast constant-time gcd computation and modular inversion. IACR Transactions on Cryptographic Hardware and Embedded Systems 2019(3), pp. 340–398, 2019. https://doi.org/10.13154/tches.v2019.i3.340-398

  Supplies constant-time divsteps algorithms for integer and polynomial inversion. It provides alternatives to exponentiation-based inversion. Its benefit depends on the field size and batch size, since batching amortizes the inversion cost.

• [adj-rodriguez-henriquez-2014] G. Adj, F. Rodríguez-Henríquez. Square Root Computation over Even Extension Fields. IEEE Transactions on Computers 63(11), pp. 2829–2841, 2014. https://doi.org/10.1109/TC.2013.145

  Uses extension-field structure to compute square roots and quadratic characters in odd-characteristic even-degree extensions. It applies to quadratic prime-field alternatives; “even extension” does not mean a binary field.

• [bernstein-2001] D. J. Bernstein. Faster square roots in annoying finite fields. Preprint, 2001, retypeset 2022. https://cr.yp.to/papers/sqroot-20011123-retypeset20220327.pdf

  Gives precomputation/time tradeoffs for square roots when the field order minus one has high two-adicity. It explains a cost specific to Goldilocks-style alternatives, which is absent from the simple square-root exponentiation over the current Mersenne prime fields.

• [pornin-2023-sqrt] T. Pornin. Optimized Discrete Logarithm Computation for Faster Square Roots in Finite Fields. Cryptology ePrint Archive, Paper 2023/828. https://eprint.iacr.org/2023/828

  Improves the subgroup discrete-logarithm stage of square-root extraction in high-two-adicity fields. It is a more recent alternative to assess alongside the preceding method when such fields are considered, including table/setup costs.

• [bernstein-2005] D. J. Bernstein. The Poly1305-AES Message-Authentication Code. Fast Software Encryption – FSE 2005, LNCS 3557, pp. 32–49. https://doi.org/10.1007/11502760_3

  Poly1305 evaluates a message as a polynomial in a clamped key over ${\mathbb{F}}_{2^{130}-5}$, a field chosen for fast integer arithmetic, and bounds the differential probability by the polynomial’s degree. The projection of item identifiers evaluates a two-block message in the same way, unclamped and without the pad; its field is measured beside $\mathrm{GF}(2^{127})$ and ${\mathbb{F}}_{2^{127}-1}$, which are cheaper where their multiplications are (hash).

Field and group arithmetic, set reconciliation and baselines

Set reconciliation and the cell checksum

• [yang-gilad-alizadeh-2024] L. Yang, Y. Gilad, M. Alizadeh. Practical Rateless Set Reconciliation. Proceedings of the ACM SIGCOMM 2024 Conference, pp. 595–612. https://doi.org/10.1145/3651890.3672219

  Rateless IBLTs: a coded-symbol stream whose communication overhead approaches 1.35 symbols per set difference, and the item-to-cell mapping src/riblt.rs implements. Each cell carries a checksum used to decide whether the cell holds exactly one item; the question of what that checksum must resist, raised in yangl1996/riblt#3, is the question this repository answers.

• [goodrich-mitzenmacher-2011] M. T. Goodrich, M. Mitzenmacher. Invertible Bloom Lookup Tables. 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 792–799, 2011. https://doi.org/10.1109/Allerton.2011.6120248
  [eppstein-et-al-2011] D. Eppstein, M. T. Goodrich, F. Uyeda, G. Varghese. What’s the Difference? Efficient Set Reconciliation without Prior Context. Proceedings of the ACM SIGCOMM 2011 Conference, pp. 218–229. https://doi.org/10.1145/2018436.2018462

  Invertible Bloom lookup tables and their use for set difference. They introduce the hash-sum field that decides purity and peeling, which RIBLT inherits and which an ECMH checksum replaces. Under a secret key a short keyed hash suffices; the ECMH checksum is needed when the salt is public and the items may be chosen against it.

• [minsky-trachtenberg-zippel-2003] Y. Minsky, A. Trachtenberg, R. Zippel. Set Reconciliation with Nearly Optimal Communication Complexity. IEEE Transactions on Information Theory 49(9), pp. 2213–2218, 2003. https://doi.org/10.1109/TIT.2003.815784
  [dodis-et-al-2008] Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal on Computing 38(1), pp. 97–139, 2008. https://doi.org/10.1137/060651380
  [naumenko-et-al-2019] G. Naumenko, G. Maxwell, P. Wuille, A. Fedorova, I. Beschastnikh. Erlay: Efficient Transaction Relay for Bitcoin. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ’19), pp. 817–831. https://doi.org/10.1145/3319535.3354237

  Algebraic set reconciliation: characteristic-polynomial interpolation, the PinSketch BCH syndrome, and its use in Erlay (Minisketch), proposed for Bitcoin’s transaction relay and not deployed. Decoding is exact and needs no checksum, so the purity question does not arise, but decoding costs time quadratic in the difference and the capacity is fixed in advance. This is an alternative to rateless IBLTs; the case for RIBLTs rests on rateless, linear-time decoding.

• [riblt-ecmh] D. Buchanan. riblt-ecmh: Go Implementation of Rateless IBLTs with Additional Security Hardening. GitHub repository, commit 11521a4c73ebbbfe80050ec99a4f976eb9ce7147, 2026. https://github.com/DavidBuchanan314/riblt-ecmh

  An independent Go implementation of RIBLT with an elliptic-curve multiset-hash checksum: the nearest prior implementation of the combination evaluated here.

• [meyer-scherer-2024] A. Meyer, K. Scherer. Range-Based Set Reconciliation Without Homomorphic Hashing. Preprint, 2024. https://aljoscha-meyer.de/assets/landing/rbsr_nonhomomorphic.pdf

  Range-based set reconciliation over conventional hashes. It names censorship resistance, that a malicious party cannot generate sets which two honest nodes fail to reconcile, and universality, that a node’s main computation does not depend on its peer’s set; the adversary of Adversary is the one their first property resists. It observes that RIBLTs meet adversarial sets by randomizing the hash for each session, which repeats the hashing in every session; a salt shared by an epoch’s sessions amortizes that work.

• [hoyte-2023] D. Hoyte. Range-Based Set Reconciliation. Web article, December 2023. Sections “Fingerprint Threat Model” and “Security of Incremental Hash Functions”. https://logperiodic.com/rbsr.html

  Range-based reconciliation as deployed in negentropy. Its fingerprint threat model is the third party of Adversary, who inserts crafted elements so that others fail to synchronize. It reports collisions of 256-bit XOR fingerprints in two seconds by Gaussian elimination and of sums modulo $2^{256}$ in about 28 hours with a $k$-dimensional birthday solver, the kind of problem to which known discrete logarithms reduce the checksum (Known weaknesses), and judges ECMH collisions infeasible but ECMH slower, with a single reference implementation.

• [corallo-2016] M. Corallo. Compact Block Relay. Bitcoin Improvement Proposal 152, 2016. https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki

  Compact block relay keys short transaction identifiers with SipHash under a hash of the block header and a nonce. The header commits to the transactions it identifies, so they cannot be chosen against the key. Items reconciled within an epoch can be, which is why a short keyed hash does not serve here although a block hash still bounds the epoch.

• [krohn-freedman-mazieres-2004] M. N. Krohn, M. J. Freedman, D. Mazières. On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution. IEEE Symposium on Security and Privacy, pp. 226–240, 2004. https://doi.org/10.1109/SECPRI.2004.1301326
  [juels-et-al-2015] A. Juels, J. Kelley, R. Tamassia, N. Triandopoulos. Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable). Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1032–1047, 2015. https://doi.org/10.1145/2810103.2813728
  [boneh-freeman-katz-waters-2009] D. Boneh, D. Freeman, J. Katz, B. Waters. Signing a Linear Subspace: Signature Schemes for Network Coding. Public Key Cryptography – PKC 2009, LNCS 5443, pp. 68–87. https://doi.org/10.1007/978-3-642-00468-1_5

  Integrity of coded data against corrupt symbols from participants: homomorphic hashes of a publisher’s blocks verify each block of a rateless erasure code on receipt, Falcon codes authenticate LT-coded symbols with a MAC under a key the sender and receiver share, and signatures on a linear subspace let the nodes of a random linear network code derive and verify signatures on combinations. The first uses a discrete-logarithm homomorphic hash, as the cell checksum does. Each authenticates data against a source or a key from which every legitimate symbol derives; the items of a reconciled set are authored by any party, the adversary included, and carry no such credential, so corrupt symbols from a participating peer remain outside the adversary of Adversary.

• [bolt-7] Lightning Network specification contributors. BOLT #7: P2P Node and Channel Discovery. Basis of Lightning Technology. https://github.com/lightning/bolts/blob/master/07-routing-gossip.md
  [chen-et-al-2026] X. Chen, A. Sinha, D. Starobinski, A. Trachtenberg. Scaling the Lightning Network with Practical Set Reconciliation. arXiv:2608.15921, 2026. https://arxiv.org/abs/2608.15921

  Lightning gossip, a public set of channel and node announcements that any node can extend, and an evaluation of IBLT-based reconciliation for it, which leaves adversarial conditions to future work.

Multiset hashes in deployment, and fixed-group baselines

• [van-der-wansem-2018] T. van der Wansem. ECMH: Elliptic Curve Multiset Hash for UTXO Commitments. Bitcoin Cash specification draft, 2018. https://github.com/tomasvdw/bips/blob/master/ecmh.mediawiki
  [wuille-2020] P. Wuille. MuHash3072: A Multiset Hash for the UTXO Set. Bitcoin Core pull request 19055 and BIP draft, 2020. https://github.com/bitcoin/bitcoin/pull/19055

  The deployed multiset hashes for UTXO-set commitments: ECMH on secp256k1 with try-and-increment, and MuHash3072 in the multiplicative group of a 3072-bit prime field. Both fix one group for all time at 128-bit security; they are the reference for why a curve rather than a modular group, and for what a fixed group costs at full size.

• [certicom-2010] Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography, version 2.0. 27 January 2010. https://www.secg.org/sec2-v2.pdf
  [libsecp256k1] Bitcoin Core contributors. libsecp256k1. GitHub repository. https://github.com/bitcoin-core/secp256k1

  secp256k1’s parameters and the library timed in benches/compare.rs (compressed-point parsing, ElligatorSwift decoding, Jacobian accumulation): the cost of ECMH on a fixed 256-bit curve.

• [bernstein-2006] D. J. Bernstein. Curve25519: New Diffie-Hellman Speed Records. Public Key Cryptography – PKC 2006, LNCS 3958, pp. 207–228. https://doi.org/10.1007/11745853_14
  [hamburg-2015] M. Hamburg. Decaf: Eliminating Cofactors through Point Compression. Advances in Cryptology – CRYPTO 2015, Part I, LNCS 9215, pp. 705–723. https://doi.org/10.1007/978-3-662-47989-6_34
  [rfc9496] H. de Valence, J. Grigg, M. Hamburg, I. Lovecruft, G. Tankersley, F. Valsorda. The ristretto255 and decaf448 Groups. RFC 9496, December 2023. https://doi.org/10.17487/RFC9496
  [curve25519-dalek] I. Lovecruft, H. de Valence. curve25519-dalek. GitHub repository. https://github.com/dalek-cryptography/curve25519-dalek

  Curve25519, the Decaf quotient that removes its cofactor, the ristretto255 specification, and the implementation timed in benches/compare.rs: the second fixed 256-bit baseline. Decaf’s quotient, which removes a cofactor of 4, is the model for the twisted family’s encoding of $E/⟨T⟩$, which removes only the 2-torsion point $T$.

• [fips-180-4] National Institute of Standards and Technology. Secure Hash Standard (SHS). NIST, FIPS PUB 180-4, 2015. https://doi.org/10.6028/NIST.FIPS.180-4
  [aumasson-bernstein-2012] J.-P. Aumasson, D. J. Bernstein. SipHash: A Fast Short-Input PRF. Progress in Cryptology – INDOCRYPT 2012, LNCS 7668, pp. 489–508. https://doi.org/10.1007/978-3-642-34931-7_28

  SHA-256, the digest behind src/hash.rs and every map, and SipHash. XOR of either is the non-adversarial baseline every curve is compared against.

Binary fields and their dependence on carry-less multiplication

• [hankerson-menezes-vanstone-2004] D. Hankerson, A. Menezes, S. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2004. https://doi.org/10.1007/b97644

  Reference for $\mathrm{GF}(2^m)$ arithmetic: the trace, the half-trace that solves $z^2+z=c$ in decoding and hashing, Itoh–Tsujii inversion, and the multiplication-by-constant cost model the operation counts in the module documentation use.

• [taverne-et-al-2011] J. Taverne, A. Faz-Hernández, D. F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, J. López. Software Implementation of Binary Elliptic Curves: Impact of the Carry-Less Multiplier on Scalar Multiplication. Cryptographic Hardware and Embedded Systems – CHES 2011, LNCS 6917, pp. 108–123. https://doi.org/10.1007/978-3-642-23951-9_8
  [bluhm-gueron-2015] M. Bluhm, S. Gueron. Fast Software Implementation of Binary Elliptic Curve Cryptography. Journal of Cryptographic Engineering 5(3), pp. 215–226, 2015. https://doi.org/10.1007/s13389-015-0094-1

  Binary-curve software built on PCLMULQDQ, with measurements of how far the carry-less multiplier decides speed. The binary families are fast only where PMULL or PCLMULQDQ is present; the bench-bins-generic runs time the portable backend that stands in when it is absent, which makes the hardware dependence a deployment condition stated with numbers.

• [crrl] T. Pornin. crrl: Rust Library for Cryptographic Research. GitHub repository. https://github.com/pornin/crrl

  Pornin’s library: the $\mathrm{GF}(2^{127})$ backends (field::gf2_127) and the GLS254 code from which curve::binary127::map and the $\mathrm{GF}(2^{122})$ tower are adapted.

Binary curve models and addition formulas

• [pornin-2022] T. Pornin. Efficient and Complete Formulas for Binary Curves. Cryptology ePrint Archive, Paper 2022/1325. https://eprint.iacr.org/2022/1325

  Complete formulas for ordinary binary curves with $|E|=2r$ in $(x,s)$ coordinates, the extended $(X:S:Z:T)$ accumulators of curve::binary::extended, the $w$ encoding of wcodec, and the mixed addition that unscaled reduces to $7M+2S$ by moving the curve constant into the addend, against $8M+2S$ for the implemented incomplete $\lambda$ formula.

• [pornin-2023] T. Pornin. Faster Complete Formulas for the GLS254 Binary Curve. Cryptology ePrint Archive, Paper 2023/1688. https://eprint.iacr.org/2023/1688

  The same formulas over $\mathrm{GF}(2^{254})=\mathrm{GF}(2^{127})[u]$ (GLS254) and the map to the curve. The $\mathrm{GF}(2^{122})=\mathrm{GF}(2^{61})[u]$ tower and the GLS family (binary.122-gls) test whether this shape transfers at half the size.

• [pornin-2024] T. Pornin. A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves. IACR Communications in Cryptology 1(1), 2024. https://doi.org/10.62056/akmp-4c2h

  The general method: a prime-order group abstraction with complete formulas from any curve of even order, most efficient for $|E|\equiv 2(\mathrm{mod}4)$. Both characteristics are covered, so it states once the structure the binary families ($E[r]=2E$) and the twisted quotient use.

• [oliveira-et-al-2014] T. Oliveira, J. López, D. F. Aranha, F. Rodríguez-Henríquez. Two Is the Fastest Prime: Lambda Coordinates for Binary Elliptic Curves. Journal of Cryptographic Engineering 4(1), pp. 3–17, 2014. https://doi.org/10.1007/s13389-013-0069-z
  [oliveira-et-al-2013] T. Oliveira, J. López, D. F. Aranha, F. Rodríguez-Henríquez. Lambda Coordinates for Binary Elliptic Curves. Cryptographic Hardware and Embedded Systems – CHES 2013, LNCS 8086, pp. 311–330. ePrint 2013/131, version of 2013-07-31; later versions of 2013/131 are the journal version, [oliveira-et-al-2014]. https://doi.org/10.1007/978-3-642-40349-1_18

  $\lambda$-projective coordinates, with mixed addition $8M+2S$ and no curve constant: the curve::binary::lambda accumulators. On curves with a dense $B$, where Pornin’s extended formulas need two full multiplications by $\beta =B^{1/4}$, this costs less than the extended accumulator, at the price of incompleteness; the unscaled formulas, at $7M+2S$, move $\beta$ into the addend and cost less than $\lambda$’s $8M+2S$ for the addition itself.

• [kim-kim-2007] K. H. Kim, S. I. Kim. A New Method for Speeding Up Arithmetic on Elliptic Curves over Binary Fields. Cryptology ePrint Archive, Paper 2007/181. https://eprint.iacr.org/2007/181

  PL-coordinates: López–Dahab $(X,Y,Z,T=Z^2)$ with $Y$ kept unreduced. Mixed addition of an affine and a PL point costs $8M+1S$ on curves $y^2+xy=x^3+x^2+b$ (Theorem 2), in an accounting that counts a reduction modulo the field polynomial as a squaring and defers it. Not implemented: a comparison with the $7M+2S$ of the unscaled formulas requires the same accounting; the formulas as written cover the $a=1$ families ($\mathrm{GF}(2^{127})$, $\mathrm{GF}(2^{109})$) and not the $a=u$ families over $\mathrm{GF}(2^{122})$, where $a=1$ has trace 0.

• [lopez-dahab-1998] J. López, R. Dahab. Improved Algorithms for Elliptic Curve Arithmetic in GF(2^n). Selected Areas in Cryptography – SAC ’98, LNCS 1556, pp. 201–212, 1999. https://doi.org/10.1007/3-540-48892-8_16

  López–Dahab projective coordinates, the earlier standard that $\lambda$-coordinates improve on; not implemented, and dominated by lambda for mixed addition.

• [galbraith-lin-scott-2009] S. D. Galbraith, X. Lin, M. Scott. Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves. Advances in Cryptology – EUROCRYPT 2009, LNCS 5479, pp. 518–535. https://doi.org/10.1007/978-3-642-01001-9_30

  GLS curves: over $\mathrm{GF}(q^2)$, quadratic twists of curves defined over $\mathrm{GF}(q)$, with an endomorphism $\psi$, ${\psi }^2=-1$. For binary curves, $a=u$ and $B$ in $\mathrm{GF}(2^{61})$, as in binary.122-gls. The endomorphism speeds scalar multiplication, which this workload does not perform; what the family gains here is a curve constant in $\mathrm{GF}(2^{61})$, so each multiplication by it costs two word products instead of three. Its rho penalty is in the security section.

• [bernstein-lange-farashahi-2008] D. J. Bernstein, T. Lange, R. Rezaeian Farashahi. Binary Edwards Curves. Cryptographic Hardware and Embedded Systems – CHES 2008, LNCS 5154, pp. 244–265. https://doi.org/10.1007/978-3-540-85053-3_16

  Binary Edwards curves: the complete model in characteristic 2. For $n\ge 3$ every ordinary curve over $\mathrm{GF}(2^n)$ is birationally equivalent to a complete binary Edwards curve (Theorem 4.3), so the model is available for every certified binary curve and the exclusion is one of cost. Mixed addition costs $13M+3S+3D$ (projective $21M+1S+4D$; $16M+1S+4D$ for $d_1=d_2$, with no mixed variant of lower cost) against $7M+2S$ for the unscaled formulas of pornin-2022. No direct map to the model with a demonstrated advantage was found, and generic projective equality costs about $4M$ against $1M$ to $3M$ on the $(x,s)$ representations; neither is a lower bound for a cached or quotient representation. Excluded on these inspected operation counts under equal field arithmetic; not implemented or measured, so the exclusion is a prioritization, not a lower bound. The $d_1=d_2$ forms, of lower cost, have $\mathrm{Tr}(d_1^2+d_2)=0$ in the birational Weierstrass model, and so $4\mid |E|$; the certified binary curves, with $|E|=2r$ and $r$ odd, require $d_1\ne d_2$.

• [kim-lee-negre-2014] K. H. Kim, C. O. Lee, C. Negre. Binary Edwards Curves Revisited. Progress in Cryptology – INDOCRYPT 2014, LNCS 8885, pp. 393–408. https://doi.org/10.1007/978-3-319-13039-2_23

  Revisits binary Edwards arithmetic and keeps completeness on complete curves ($\mathrm{Tr}(d_2)=1$). For general $d_1,d_2$, projective addition costs $15M+2S+4D$ (the paper’s baseline for the 2008 formulas, from the EFD, is $18M+3S+6D$), mixed addition $13M+2S+2D$ and doubling $2M+5S+3D$. The $d_1=d_2$ forms (projective addition $14M+1S+2D$, mixed $13M+1S+2D$) and the complete differential addition-and-doubling at $5M+4S+D$ exist exactly when the curve has a rational point of order 4 (Lemma 1), so not on the certified curves; the differential formulas also assume a fixed difference ${\omega }_0\ne 0$ (and ${\omega }_0\ne 1$ when $d_1=d_2$). Mixed addition stays near twice the $7M+2S$ of pornin-2022 with dense constants, and the differential result does not implement an arbitrary cell update.

• [bernstein-2009] D. J. Bernstein. Batch Binary Edwards. Advances in Cryptology – CRYPTO 2009, LNCS 5677, pp. 317–336. https://doi.org/10.1007/978-3-642-03356-8_19
  [koziel-azarderakhsh-mozaffari-2015] B. Koziel, R. Azarderakhsh, M. Mozaffari-Kermani. Low-Resource and Fast Binary Edwards Curves Cryptography. Progress in Cryptology – INDOCRYPT 2015, LNCS 9462, pp. 347–369. https://doi.org/10.1007/978-3-319-26617-6_19
  [koziel-bec-small] B. Koziel, R. Azarderakhsh, M. Mozaffari-Kermani. BEC_Small: SageMath Verification of Binary Edwards Differential Addition. GitHub repository, commit f252fd653354466abfc36416dbf74379f11fce05. Companion to [koziel-azarderakhsh-mozaffari-2015]. https://github.com/briankoziel/BEC_Small
  [farias-albertini-barreto-2018] L. A. Farias, B. C. Albertini, P. S. L. M. Barreto. A Class of Safe and Efficient Binary Edwards Curves. Journal of Cryptographic Engineering 8(4), pp. 271–283, 2018. https://doi.org/10.1007/s13389-017-0174-5
  [loiseau-fournier-2018] A. Loiseau, J. J. A. Fournier. Binary Edwards Curves for Intrinsically Secure ECC Implementations for the IoT. Proceedings of the 15th International Joint Conference on e-Business and Telecommunications (SECRYPT 2018), pp. 625–631. https://doi.org/10.5220/0006831506250631
  [hajra-karati-sen-2026] R. Hajra, S. Karati, T. Sen. Binary Kummer Lines and Binary Edwards Curves: Efficient Two-way Vectorizations. ACM Asia Conference on Computer and Communications Security (ASIA CCS ’26), pp. 519–532, 2026. https://doi.org/10.1145/3779208.3807491

  The fast binary Edwards formulas are differential, in the coordinate $w=x+y$, which identifies $P$ with $-P$: $w(Q+P)$ is computed from $w(P)$, $w(Q)$ and $w(Q-P)$, as a Montgomery ladder supplies it. Batch Binary Edwards gives the $d_1=d_2$ mixed form at $5M+2D+4S$ with $d$ chosen sparse so that multiplication by $d$ reduces to a few shifts and additions (bernstein-2009, section “Differential addition and doubling”); the later papers correct and re-cost these $w$-formulas ($5M+1D+4S$ mixed, koziel-azarderakhsh-mozaffari-2015; koziel-bec-small is its Sage check), apply them with $d_1=d_2$ (farias-albertini-barreto-2018, Section 4), add the co-Z technique (loiseau-fournier-2018, Algorithm 2), and vectorize the ladder step with VPCLMULQDQ on a $d_1=d_2$ curve with sparse $d$ and cofactor 4 (hajra-karati-sen-2026, Table 2). A cell update adds an independent hashed point with no known difference, so none of these formulas applies to it; for generic dense parameters $D$ counts as a full $M$, and the sparse-parameter specialization they rely on is not established for seed-derived curves.

• [moloney-omahony-laurent-2010] R. Moloney, A. O’Mahony, P. Laurent. Efficient Implementation of Elliptic Curve Point Operations Using Binary Edwards Curves. Cryptology ePrint Archive, Paper 2010/208. https://eprint.iacr.org/2010/208

  The explicit birational maps between a Weierstrass curve and its complete binary Edwards curve, with their exceptional points (Section 3): the conversion a hashed Weierstrass or $(x,s)$ point would need to enter the model. The affine conversion uses rational functions; their denominators may be inverted in a batch or retained in projective coordinates. No conversion cost has been measured here.

• [hirschfeld-batten-amain-2018] S. T. E. Hirschfeld, L. M. Batten, M. K. I. Amain. Efficiencies in Binary Elliptic Curves. Computational Science and Its Applications – ICCSA 2018, LNCS 10964, pp. 246–260. https://doi.org/10.1007/978-3-319-95174-4_21
  [li-et-al-2019] J. Li, S. Zhong, Z. Li, S. Cao, J. Zhang, W. Wang. Speed-Oriented Architecture for Binary Field Point Multiplication on Elliptic Curves. IEEE Access 7, pp. 32048–32060, 2019. https://doi.org/10.1109/ACCESS.2019.2903170

  A survey of binary-curve implementation choices that restates Theorem 4.3 and the operation-count comparison, and an FPGA Montgomery-ladder architecture for binary curves: the hardware side of the differential results, with no arbitrary-addition formula.

• [kohel-2012] D. Kohel. Efficient Arithmetic on Elliptic Curves in Characteristic 2. Progress in Cryptology – INDOCRYPT 2012, LNCS 7668, pp. 378–398. https://doi.org/10.1007/978-3-642-34931-7_22
  [wu-tang-feng-2012] H. Wu, C. Tang, R. Feng. A New Model of Binary Elliptic Curves. Progress in Cryptology – INDOCRYPT 2012, LNCS 7668, pp. 399–411. https://doi.org/10.1007/978-3-642-34931-7_23
  [wu-2026] H. Wu. A New Characteristic-Uniform Model for Elliptic Curves – Theory, Arithmetic, and Applications. arXiv:2608.01675 [math.NT], 2026. https://doi.org/10.48550/arXiv.2608.01675

  Other binary normal forms considered: Kohel’s ${\mu }_4$ form (addition $7M+2S$) requires a rational 4-torsion point, which the certified curves of order $2r$ lack; the Wu–Tang–Feng model is unified, not complete, at $12M+2D$. The Wu 2026 preprint proposes a characteristic-uniform model; its addition counts were not evaluated here.

Odd-characteristic curve models and addition formulas

• [edwards-2007] H. M. Edwards. A Normal Form for Elliptic Curves. Bulletin of the American Mathematical Society 44(3), pp. 393–422, 2007. https://doi.org/10.1090/S0273-0979-07-01153-6
  [bernstein-lange-2007] D. J. Bernstein, T. Lange. Faster Addition and Doubling on Elliptic Curves. Advances in Cryptology – ASIACRYPT 2007, LNCS 4833, pp. 29–50. https://doi.org/10.1007/978-3-540-76900-2_3

  The Edwards normal form and its complete addition law when $d$ is a non-square: the edwards family, with $d$ drawn per salt.

• [bernstein-et-al-2008] D. J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters. Twisted Edwards Curves. Progress in Cryptology – AFRICACRYPT 2008, LNCS 5023, pp. 389–405. https://doi.org/10.1007/978-3-540-68164-9_26
  [hisil-et-al-2008] H. Hisil, K. K.-H. Wong, G. Carter, E. Dawson. Twisted Edwards Curves Revisited. Advances in Cryptology – ASIACRYPT 2008, LNCS 5350, pp. 326–343. https://doi.org/10.1007/978-3-540-89255-7_20

  Twisted Edwards curves and extended coordinates. With $a=-1$ a square, the addition is complete and a cached addend costs $7M$; this is the twisted family’s accumulator, and the reason it requires $q\equiv 1(\mathrm{mod}4)$.

• [renes-costello-batina-2016] J. Renes, C. Costello, L. Batina. Complete Addition Formulas for Prime Order Elliptic Curves. Advances in Cryptology – EUROCRYPT 2016, LNCS 9665, pp. 403–428. https://doi.org/10.1007/978-3-662-49890-3_16

  Complete projective formulas for prime-order short Weierstrass curves, $11M+2m_b$ for mixed addition: the weier family’s accumulator, and the cost of completeness when the order has no cofactor to quotient away.

• [efd] D. J. Bernstein, T. Lange. Explicit-Formulas Database. https://hyperelliptic.org/EFD/

  The Explicit-Formulas Database: the named formulas (madd-2007-bl, dbl-2001-b) in curve::weier::jacobian and the operation counts quoted in the module documentation.

• [montgomery-1987] P. L. Montgomery. Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation 48(177), pp. 243–264, 1987. https://doi.org/10.1090/S0025-5718-1987-0866113-7

  Montgomery curves and simultaneous inversion. The inversion method is field::batch, which every batch sum and batch normalization uses; the Montgomery model is the form in which edwards points travel and are summed in batches by the affine chord law.

• [farashahi-fadavi-sabbaghian-2024] R. Rezaeian Farashahi, M. Fadavi, S. Sabbaghian. Faster Complete Addition Laws for Montgomery Curves. IACR Transactions on Cryptographic Hardware and Embedded Systems 2024(4), pp. 737–762, 2024. https://doi.org/10.46586/tches.v2024.i4.737-762
  [kim-et-al-2019] J. Kim, J. H. Park, D.-C. Kim, W.-H. Kim. Complete Addition Law for Montgomery Curves. Information Security and Cryptology – ICISC 2019, LNCS 11975, pp. 260–277, 2020. https://doi.org/10.1007/978-3-030-40921-0_16

  Complete addition on Montgomery curves: $15M+2m_c$ in 2019, then extended Montgomery coordinates with multiplication-free maps to and from extended twisted Edwards coordinates. The extended Montgomery laws correspond to twisted Edwards laws through these maps, so the model change alone gives no field-multiplication saving for the corresponding full additions. The remaining practical comparisons concern cached operands, preparation and conversion, and implementation scheduling.

• [bernstein-lange-2007-inverted] D. J. Bernstein, T. Lange. Inverted Edwards Coordinates. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-17), LNCS 4851, pp. 20–27, 2007. https://doi.org/10.1007/978-3-540-77224-8_4

  Inverted Edwards coordinates, superseded for addition by the extended coordinates of hisil-et-al-2008.

• [goundar-joye-miyaji-2010] R. R. Goundar, M. Joye, A. Miyaji. Co-Z Addition Formulæ and Binary Ladders on Elliptic Curves. Cryptographic Hardware and Embedded Systems – CHES 2010, LNCS 6225, pp. 65–79. https://doi.org/10.1007/978-3-642-15031-9_5
  [kim-et-al-2020] K. H. Kim, J. Choe, S. Y. Kim, N. Kim, S. Hong. Speeding Up Regular Elliptic Curve Scalar Multiplication without Precomputation. Advances in Mathematics of Communications 14(4), pp. 703–726, 2020. https://doi.org/10.3934/amc.2020090

  Co-Z Jacobian formulas and Montgomery-ladder scalar multiplication on short Weierstrass curves over fields of characteristic other than 2 and 3, built on differential addition-and-doubling. Scalar multiplication, which the workload does not perform.

Prime fields

• [scott-2024] M. Scott. Elliptic Curve Cryptography for the Masses: Simple and Fast Finite Field Arithmetic. Cryptology ePrint Archive, Paper 2024/779. https://eprint.iacr.org/2024/779

  Reduction for shaped primes: Mersenne ($2^{61}-1$, $2^{107}-1$, $2^{127}-1$), pseudo-Mersenne ($2^{64}-59$, $2^{128}-275$) and generalized Mersenne (Goldilocks). Every odd field here has one of these shapes; the paper indicates what generated or assembly code could gain over the portable implementations timed.

• [polygon-zero-2022] Polygon Zero Team. Plonky2: Fast Recursive Arguments with PLONK and FRI. Draft, plonky2 repository. 7 September 2022. https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/plonky2.pdf
  [plonky3] Polygon. Plonky3: A Toolkit for Polynomial IOPs. GitHub repository. https://github.com/Plonky3/Plonky3

  The Goldilocks prime $2^{64}-2^{32}+1$ and the implementation field::goldilocks2 uses for its base field and binomial extension. Its 2-adicity of 32, chosen for FFTs, makes square roots slower than over $2^{64}-59$; the goldilocks2 rows measure that cost.

• [bruestle-gafni-2023] J. Bruestle, P. Gafni, RISC Zero Team. RISC Zero zkVM: Scalable, Transparent Arguments of RISC-V Integrity. RISC Zero, draft. 11 August 2023. https://dev.risczero.com/proof-system-in-detail.pdf
  [haboeck-levit-papini-2024] U. Haböck, D. Levit, S. Papini. Circle STARKs. Cryptology ePrint Archive, Paper 2024/278. https://eprint.iacr.org/2024/278

  BabyBear and the Mersenne prime $2^{31}-1$, the 31-bit fields of current STARK systems. Reaching $2^{122}$ points over a 31-bit prime needs an extension of degree 4, which admits the heuristic index-calculus asymptotic $\tilde{O}(q^{3/2})$ of gaudry-2009, below the generic $q^2$. Group size alone therefore does not justify the target security, and these fields are excluded from the comparison.