[CFRG] Re: Feedback on draft-irtf-cfrg-pairing-friendly-curves-12

[Emil Lundberg <[e-mail]>]

Hi Yumi,

Thank you for this, and apologies for not replying earlier. I agree with
your proposed (and performed) changes, and with leaving point 3
(intermediate test vectors) out of scope. Indeed, if there are multiple
equivalent ways to compute the same pairing, we should not mandate or
favour a particular one by providing test vectors for only one of them.

The explicit definition of psi^-1 helps a lot (I had found it in "Pairings
for Beginners", but it's a great help to have it inline), as does pointing
out that E' points must be untwisted before calling Line_function on them.
With these clarifications, my (very slow) "optimal" ate pairing
implementation at least doesn't always return 1 as the result anymore. :)

I've also confirmed that the pairing test vectors agree with noble-curves
given the exponentiation cofactors (e =
bls12_381.pairing(bls12_381.G1.Point.BASE, bls12_381.G2.Point.BASE); e2 =
bls12_381.fields.Fp12.fromBigTwelve([e_0, e_1, ...,
e_11]); assert(bls12_381.fields.Fp12.eql(e, bls12_381.fields.Fp12.pow(e2,
3n)))). That's a great help in verifying that one is using a library and
the test vectors together correctly.

I'm still not quite sure about the notation e_0, e_1, ..., e_11 for the
pairing test vectors, though. You state that "the extension field that e(P,
Q) belongs is constructed according to
[I-D.ietf-lwig-curve-representations]", but as far as I can tell
lwig-curve-representations
never mentions towered extension field constructions. As you said earlier
(and as I can now verify), these test vectors are formulated in a towered
representation - as I understand, the GF(p^12) element is ((e_0 + e_1 * u)
+ (e_2 + e_3 * u) * v + (e_4 + e_5 * u) * v^2) + ((e_6 + e_7 * u) + (e_8 +
e_9 * u) * v + (e_10 + e_11 * u) * v^2) * w = e_0 + e_1 * u + e_2 * v + e_3
* uv + e_4 * v^2 + e_5 * uv^2 + e_6 * w + e_7 * uw + e_8 * vw + e_9 * uvw +
e_10 * v^2w + e_11 * uv^2w (this pattern agrees with the GF(p^8)
polynomials written out for x' and y' in section 4.3). But I can't find
anything in lwig-curve-representations that suggests any representation
other than e_11 * t^11 + ... + e_1 * t + e_0. Am I missing something, or is
this reference to lwig-curve-representations inaccurate (perhaps left over
from an earlier draft version, which later versions diverged from)?

Finally, even with these clarifications I am sadly still unable to
reproduce the pairing test vectors. The only non-unity pairing e(BP1, BP2)
I've managed to produce is this (with the notation e_0 + e_1 * u + ... +
e_11 * uv^2w above):

e_0  =
0x07002b9494e5c5feddd7fdc1860cb5c9ca9ebc68d4b413a463e8c080e00b17c6710fd99e6112e1c61babfdec952dc785
e_1  =
0x1967896bc3d369a693abde4af9737fac3519651073a989ee3080cce0a9d722edce352251aef6c63ec532e72bd5a6a80c
e_2  =
0x12a1b1d275fdd03bc8439d2c83869a68a3b1457944dd9c4cd594c35951ac779840f0094a1a794560db2160ed7434a7c8
e_3  =
0x169ecce6c0853f902c801d8fa5f335f9d40420aca0790fce94986397c01d507615e05a9ae994699c090d0067c7228a24
e_4  =
0x12122bf46976fe1cc707ef899c256ef45ae71167688fcf6fb368d606aa6c3105b9bd1fcbade856ade9dade08502bcd11
e_5  =
0x11742c94cb0f25bab9233f39365752c697fab540ba429c1d8aeb581cd7d813092f695f2b1507a5226c872af20f5bfd63
e_6  =
0x004dbbdd3a96bf70ac681d8e4834a9fb9df69eee8518e162a15a00e3a3f201eb314a9b7fbf5e9495d5e054f98380fe39
e_7  =
0x007a0a27e3c1f62bd259c8fdeb794dd8634816f948aedef0c56dd3b4037f1e3c272af3640f0a9eda97e305da0b7d4701
e_8  =
0x06e06c9b7b9a89b6e280eb1e06ee4fa559639ab4ce0281905a9802addd3bd33c5f7f90b89a1b4e9d3e733c21ea441202
e_9  =
0x028071cf8fa524472cb0a28c5ad3cb58b927545a8eabe3f9356838088eb170b727ca64d15aa19eef4ced24a877b715cc
e_10 =
0x0cad8523d8f93b37d8e904067b62811fc488e2894efd9e35929ac27f50dab7725fba0707c5d086297182fcb66744f895
e_11 =
0x066daa4f2dfd8f33b4ac5f5cde897c977f554e640007a311f458a841feef28ed49a4705a3d77cb4b5c3614e2976a3bde

It's almost certainly my implementation that's incorrect, especially as I'm
getting distinct values for all three of e(BP1, BP2)^2, e(BP1 * 2, BP2) and
e(BP1, BP2 * 2). I've tried to implement the pairing pseudocode quite
literally. Thank you for your earlier offer to review my code - please do
so if you'd like:
https://github.com/emlun/python-fido2/blob/d733c3cff32e395c6ab3540b67f8dc1ebfcb9f55/fido2/bls12_381.py#L1344-L1387
 . This implementation is mostly for my own learning, not for any practical
use, so I'm sorry if much of the code is hard to read, and I don't mind if
you don't want to or have time to look much into it. If you do, you can run
the code using `python -i fido2/bls12_381.py` and then running `e =
opt_ate_pairing(gfp12, CRV_BLS_G1.generator, CRV_BLS_G2.generator, c, t,
k)` at the REPL prompt to compute the pairing. It takes about 2 minutes to
run on my machines. I'm fairly certain that at least the GF(p^2) math is
correct, as I get identical results as noble-curves for BP2*2, BP2*1234 and
BP2*((r - 1)/2), but I'm not as confident about the higher-order towered
polynomials.

Thanks again for your work on the draft and for taking the time to respond
to my issues! And again my apologies for not in turn replying sooner.

Emil Lundberg

Staff Engineer | Yubico <http://www.yubico.com/>




Den sön 19 apr. 2026 kl 16:55 skrev Yumi Sakemi <sakemi-yumi=
[e-mail]>:

> Hi Emil, all,
>
> Quick follow-up to my earlier reply: the two GitHub issues I mentioned
> are now filed.
>
> - #77 — Add explicit untwist isomorphism ψ to Section 4.x and clarify
>   Appendix B G2 representation (normative editorial)
>
> https://github.com/cfrg/draft-irtf-cfrg-pairing-friendly-curves/issues/77
>
> - #78 — Add an informative "Implementation Notes" Appendix
>   (production library cofactors, final exponentiation decomposition)
>
> https://github.com/cfrg/draft-irtf-cfrg-pairing-friendly-curves/issues/78
>
> Best regards,
> Yumi
>
> 2026年4月19日(日) 19:11 Yumi Sakemi <[e-mail]>:
>
>> Hi Emil, and CFRG members,
>>
>> Thank you for the detailed and constructive feedback. Your
>> scratch-implementation perspective is exactly the kind of input we
>> have been hoping to receive ahead of the crypto-panel review and IETF
>> 126 RGLC.
>>
>> We worked through your four points; here is what we found, including,
>> on #4, a finding that revised our own understanding.
>>
>> ---
>>
>> Point 4 - e(P, Q) parsing and cross-implementation mismatch
>>
>> The most consequential first. The reason you could not reproduce the
>> Appendix B values via noble-curves is not a parsing error: the draft
>> test vectors and the production-library outputs follow different
>> conventions.
>>
>> The tower spec is identical across the draft, mcl, and our independent
>> reimplementation (we verified this layer by layer with unit tests).
>> Implementing the Appendix A pseudocode literally exactly reproduces
>> the Appendix B test vectors for BLS12-381 (12/12) and BN462. After
>> reading mcl's source (pairing_impl.hpp) and verifying numerically, we
>> found that production libraries return the literal pseudocode value
>> raised to a curve-specific exponent - 3 for BLS12-381, a different
>> polynomial in u for BN462. The exponents and references will be in
>> Issue A-2.
>>
>> These cofactors are coprime to r, so bilinearity is preserved and
>> verification equations hold on either side. The two are mathematically
>> valid representations of the same pairing, just normalized
>> differently. Because noble-curves agrees with mcl, your value is most
>> likely the cofactor-multiplied form. To match Appendix B
>> byte-for-byte, the Appendix A pseudocode must be evaluated literally,
>> without the cofactor optimization.
>>
>> ---
>>
>> Points 1 and 2 - Twist isomorphism and Frobenius endomorphism
>>
>> We agree there is editorial room for improvement on #1 and #2. The
>> pseudocode in Appendix A defines Line_function on points of the
>> untwisted curve, but the G2 base points in Appendix B are given in
>> twisted form (for compactness), and the explicit untwist isomorphism
>> psi that bridges the two is not written in the body.
>>
>> The overall posture for the draft was discussed at IETF 124 and
>> reached rough consensus on a parameter-centric specification - we
>> deliberately do not aim to standardize implementation algorithms
>> themselves. Picking up Hannes's IETF 124 remark that "this is not a
>> binary choice between parameters-only and full tutorial - context is
>> valuable", we propose:
>>
>> - Issue A-1 (normative editorial): add the explicit psi to each
>> curve's Section 4.x, and a short note in the introduction of Appendix
>> B about the twisted-form representation. psi is a structural fact
>> derived from the parameters (twist coefficient + tower spec), not an
>> algorithmic choice, so it sits naturally inside the parameter-centric
>> scope.
>> - Issue A-2 (informative): add an Implementation Notes appendix
>> documenting the cofactor relationship in #4, and pointing to the
>> standard literature for the easy/hard split of the final
>> exponentiation and the construction of the signed binary expansion.
>>
>> ---
>>
>> Point 3 - Including intermediate values in test vectors
>>
>> We took your suggestion seriously, but on reflection we believe
>> intermediate values are not actually well-suited as a
>> cross-implementation consistency check.
>>
>> Most standard pairing optimizations (twist isomorphism, NAF and
>> signed-binary representations, Miller-loop post-correction, the
>> addition chain in the final exponentiation) rely on a structural
>> property of the pairing: differences in intermediate state are
>> absorbed by the final exponentiation. In our verification work, our
>> naive implementation and mcl produced completely different
>> 12-coefficient outputs at the end of the Miller loop but converged to
>> a cofactor-related pair afterwards. Published intermediate values
>> would therefore only match implementations that follow one specific
>> Miller-loop variant literally, effectively pinning down a particular
>> reference implementation - outside the parameter-centric scope.
>>
>> We very much understand the implementer's desire to bisect a
>> divergence with intermediate diagnostics. We suggest covering this
>> through the literature pointers in the Implementation Notes appendix
>> instead.
>>
>> ---
>>
>> An offer
>>
>> If it would be useful, we would be glad to support your scratch
>> implementation more directly - for example by reviewing your code if
>> you point us at a repo, or by joining a repo as a collaborator. Please
>> treat this as an open offer rather than a push, and feel free to
>> ignore if it isn't helpful.
>>
>> ---
>>
>> We will open Issues A-1 and A-2 shortly and post the URLs back on this
>> thread. We would be very grateful if you could continue to engage
>> during the discussion phase (1-22 May); this kind of implementer
>> feedback genuinely strengthens the draft.
>>
>> Thank you again for the thoughtful and constructive review.
>>
>> Best regards,
>> Yumi
>>
>> 2026年4月18日(土) 3:04 Emil Lundberg <emil=[e-mail]>:
>>
>>> Hi CFRG and draft authors,
>>>
>>> I'd like to share some feedback on
>>> draft-irtf-cfrg-pairing-friendly-curves-12
>>> <https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-12.html> [1],
>>> or primarily Appendix A: Computing the Optimal Ate Pairing. I've been
>>> trying on and off for a few months (in between other work) to implement
>>> this pairing function and reproduce the test vectors, but have not been
>>> able to do so. I'm sorry to say that for a reader (me) not already deeply
>>> familiar with elliptic curve pairings, Appendix A is not nearly enough to
>>> successfully implement the pairing. I've been working through Craig
>>> Costello's "Pairings for beginners
>>> <https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf>"
>>> [2] to learn the underlying math and have successfully reproduced many of
>>> its examples, but I've not yet been able to take the final step to a
>>> working optimal ate pairing.
>>>
>>> Some concrete points of feedback on the draft:
>>>
>>> - It's not clear to me if the G2 input (Q) should be in twisted form or
>>> not. The introduction of Appendix A reads "[...] implementers should
>>> consider the isomorphism of E and its twist curve E' [...]. We note that
>>> Line_function does not consider such an isomorphism.". *How* should
>>> implementers consider the twist isomorphism? Does Line_function work with
>>> and without the twist, and just makes the computation faster, or (since it
>>> "does not consider such an isomorphism") does this formulation only work
>>> for Q on the untwisted curve? (Line_function directly extracts the
>>> coordinate values, so surely it matters if the coordinates are in twisted
>>> form or not?)
>>>
>>> - The same section also reads "The computation of the optimal Ate
>>> pairing uses the Frobenius endomorphism. [...]". I cannot see this mapping
>>> appear anywhere in the pairing algorithms, so how is it used? I gather
>>> vaguely from "Pairings for beginners" that it seems to be used primarily
>>> for the final exponentiation, but that's in GT while this paragraph seems
>>> to describe the endomorphism only for points on E'(G2). This Frobenius
>>> optimizaion seems necessary to compute the final exponentiation in
>>> reasonable time, right? Yet the draft doesn't seem to help implementers at
>>> all in implementing this optimization.
>>>
>>> - I think it might greatly help implementers to include a few
>>> intermediate values in the test vectors, like maybe the results of
>>> Line_function evaluations in the first loop iteration, maybe the value of f
>>> before and after the first loop iteration, and maybe the value of f before
>>> the final exponentiation. This would help determine whether one has the
>>> points in the correct twisted/untwisted form, and whether one is performing
>>> the GT operations on f correctly.
>>>
>>> - Lastly, I've also tried to reproduce the test vectors using existing
>>> pairing implementations, with no luck either, so I'm not even sure if I'm
>>> correctly parsing the pairing value `e` in the test vectors. The draft says
>>> "the extension field that e(P, Q) belongs is constructed according to
>>> [I-D.ietf-lwig-curve-representations]." (a more precise section reference
>>> would be helpful here), and that along with the 12 (for BLS12-381) linearly
>>> numbered limbs seems to me like it's using the direct representation of the
>>> coefficients of an 11-degree polynomial over GF(p)? But the implementations
>>> I've seen (including my own) work with the towered extension field
>>> representation, and the draft too seems to assume this given the
>>> definitions in sections 2.5, 4.2 and 4.3. The encoding in section 2.5 is
>>> described as generating a single octet stream, but the test vectors are
>>> given as a sequence of elements - what gives? This is all to say I haven't
>>> managed to parse `e` in a way that it matches the pairing result computed
>>> by the noble-curves <https://github.com/paulmillr/noble-curves> [3]
>>> library (`e = bls12_381.pairing(bls12_381.G1.Point.BASE,
>>> bls12_381.G2.Point.BASE)`). I don't suppose this library would implement
>>> some other pairing than the optimal ate pairing?
>>>
>>> Thank you for your work on the draft and for your patience reading this.
>>> I'm happy to help clarify these things, if there's some way I can with my
>>> limited experience - please let me know if I can help!
>>>
>>> [1]:
>>> https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-12.html
>>> [2]:
>>> https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf
>>> [3]: https://github.com/paulmillr/noble-curves
>>>
>>> Cheers,
>>>
>>> Emil Lundberg
>>>
>>> Staff Engineer | Yubico <http://www.yubico.com/>
>>>
>>>
>>> _______________________________________________
>>> CFRG mailing list -- [e-mail]
>>> To unsubscribe send an email to [e-mail]
>>>
>>