Botan 3.14.1
Crypto and TLS for C&
bls12_381_pairing.cpp
Go to the documentation of this file.
1/*
2* (C) 2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/bls12_381.h>
8
9#include <botan/exceptn.h>
10#include <botan/mem_ops.h>
11#include <botan/internal/bls12_381_point_mul.h>
12#include <botan/internal/bls12_381_tower.h>
13#include <botan/internal/ct_utils.h>
14#include <vector>
15
16namespace Botan::BLS12_381 {
17
18namespace {
19
20/**
21* The Miller loop accumulator point, in Jacobian coordinates
22*/
23struct MillerG2 {
24 FieldElement2 x;
25 FieldElement2 y;
26 FieldElement2 z;
27};
28
29struct LineEval {
30 FieldElement2 c0;
31 FieldElement2 c1;
32 FieldElement2 c2;
33};
34
35struct PairingTerm {
36 FieldElement px;
37 FieldElement py;
38 FieldElement2 qx;
39 FieldElement2 qy;
40 MillerG2 cur;
41};
42
43LineEval doubling_step(MillerG2& r) {
44 // Adaptation of Algorithm 26, https://eprint.iacr.org/2010/354.pdf
45 const auto tmp0 = r.x.square();
46 const auto tmp1 = r.y.square();
47 const auto tmp2 = tmp1.square();
48 auto tmp3 = (tmp1 + r.x).square() - tmp0 - tmp2;
49 tmp3 = tmp3 + tmp3;
50 const auto tmp4 = tmp0 + tmp0 + tmp0;
51 auto tmp6 = r.x + tmp4;
52 const auto tmp5 = tmp4.square();
53 const auto zsquared = r.z.square();
54 r.x = tmp5 - tmp3 - tmp3;
55 r.z = (r.z + r.y).square() - tmp1 - zsquared;
56 r.y = (tmp3 - r.x) * tmp4;
57 auto tmp2_8 = tmp2 + tmp2;
58 tmp2_8 = tmp2_8 + tmp2_8;
59 tmp2_8 = tmp2_8 + tmp2_8;
60 r.y = r.y - tmp2_8;
61 auto ltmp3 = tmp4 * zsquared;
62 ltmp3 = ltmp3 + ltmp3;
63 ltmp3 = ltmp3.negate();
64 tmp6 = tmp6.square() - tmp0 - tmp5;
65 auto tmp1_4 = tmp1 + tmp1;
66 tmp1_4 = tmp1_4 + tmp1_4;
67 tmp6 = tmp6 - tmp1_4;
68 auto ltmp0 = r.z * zsquared;
69 ltmp0 = ltmp0 + ltmp0;
70
71 return LineEval{ltmp0, ltmp3, tmp6};
72}
73
74LineEval addition_step(MillerG2& r, const FieldElement2& qx, const FieldElement2& qy) {
75 // Adaptation of Algorithm 27, https://eprint.iacr.org/2010/354.pdf
76 const auto zsquared = r.z.square();
77 const auto ysquared = qy.square();
78 const auto t0 = zsquared * qx;
79 const auto t1 = ((qy + r.z).square() - ysquared - zsquared) * zsquared;
80 const auto t2 = t0 - r.x;
81 const auto t3 = t2.square();
82 auto t4 = t3 + t3;
83 t4 = t4 + t4;
84 const auto t5 = t4 * t2;
85 const auto t6 = t1 - r.y - r.y;
86 auto t9 = t6 * qx;
87 const auto t7 = t4 * r.x;
88 r.x = t6.square() - t5 - t7 - t7;
89 r.z = (r.z + t2).square() - zsquared - t3;
90 auto t10 = qy + r.z;
91 const auto t8 = (t7 - r.x) * t6;
92 auto t0y = r.y * t5;
93 t0y = t0y + t0y;
94 r.y = t8 - t0y;
95 t10 = t10.square() - ysquared;
96 const auto ztsquared = r.z.square();
97 t10 = t10 - ztsquared;
98 t9 = t9 + t9 - t10;
99 const auto lt10 = r.z + r.z;
100 const auto t6neg = t6.negate();
101 const auto lt1 = t6neg + t6neg;
102
103 return LineEval{lt10, lt1, t9};
104}
105
106Fp12 ell(const Fp12& f, const LineEval& line, const FieldElement& px, const FieldElement& py) {
107 const auto c0 = FieldElement2(line.c0.c0() * py, line.c0.c1() * py);
108 const auto c1 = FieldElement2(line.c1.c0() * px, line.c1.c1() * px);
109
110 return f.mul_by_014(line.c2, c1, c0);
111}
112
113Fp12 multi_miller_loop(std::span<PairingTerm> terms) {
114 auto f = Fp12::one();
115
116 bool found_one = false;
117 for(size_t b = 64; b > 0; --b) {
118 const bool i = (((BLS_Z_ABS >> 1) >> (b - 1)) & 1) == 1;
119 if(!found_one) {
120 found_one = i;
121 continue;
122 }
123
124 for(auto& term : terms) {
125 f = ell(f, doubling_step(term.cur), term.px, term.py);
126 }
127
128 if(i) {
129 for(auto& term : terms) {
130 f = ell(f, addition_step(term.cur, term.qx, term.qy), term.px, term.py);
131 }
132 }
133
134 f = f.square();
135 }
136
137 for(auto& term : terms) {
138 f = ell(f, doubling_step(term.cur), term.px, term.py);
139 }
140
141 // z is negative
142 return f.conjugate();
143}
144
145Fp12 cyclotomic_exp(const Fp12& f) {
146 // Exponentiation by |z|, in the cyclotomic subgroup, negated by
147 // conjugation since z is negative
148 auto tmp = Fp12::one();
149 bool found_one = false;
150 for(size_t b = 64; b > 0; --b) {
151 const bool i = ((BLS_Z_ABS >> (b - 1)) & 1) == 1;
152 if(found_one) {
153 tmp = tmp.cyclotomic_square();
154 } else {
155 found_one = i;
156 }
157
158 if(i) {
159 tmp = tmp * f;
160 }
161 }
162
163 return tmp.conjugate();
164}
165
166Fp12 final_exponentiation(const Fp12& ml) {
167 auto f = ml;
168 // Possible optimization: f^(p^6) equals f.conjugate() for any Fp12
169 // element, and the chained p^2/p^3 Frobenius uses below could be
170 // dedicated maps with precomputed coefficients
172 auto t1 = f.invert();
173 auto t2 = t0 * t1;
174 t1 = t2;
175 t2 = t2.frobenius_map().frobenius_map();
176 t2 = t2 * t1;
177 t1 = t2.cyclotomic_square().conjugate();
178 auto t3 = cyclotomic_exp(t2);
179 auto t4 = t3.cyclotomic_square();
180 auto t5 = t1 * t3;
181 t1 = cyclotomic_exp(t5);
182 t0 = cyclotomic_exp(t1);
183 auto t6 = cyclotomic_exp(t0);
184 t6 = t6 * t4;
185 t4 = cyclotomic_exp(t6);
186 t5 = t5.conjugate();
187 t4 = t4 * t5 * t2;
188 t5 = t2.conjugate();
189 t1 = t1 * t2;
190 t1 = t1.frobenius_map().frobenius_map().frobenius_map();
191 t6 = t6 * t5;
192 t6 = t6.frobenius_map();
193 t3 = t3 * t0;
194 t3 = t3.frobenius_map().frobenius_map();
195 t3 = t3 * t1;
196 t3 = t3 * t6;
197 f = t3 * t4;
198
199 return f;
200}
201
202PairingTerm make_term(const G1Affine& p, const G2Affine& q) {
203 const auto qx = q._x();
204 const auto qy = q._y();
205 return PairingTerm{p._x(), p._y(), qx, qy, MillerG2{qx, qy, FieldElement2::one()}};
206}
207
208} // namespace
209
210Gt::Gt(const Fp12& v) : m_coeffs{} {
211 constexpr size_t N = FieldElement::N;
212
213 const std::array<const FieldElement2*, 6> c = {
214 &v.c0().c0(), &v.c0().c1(), &v.c0().c2(), &v.c1().c0(), &v.c1().c1(), &v.c1().c2()};
215
216 for(size_t i = 0; i != c.size(); ++i) {
217 copy_mem(m_coeffs.data() + (2 * i) * N, c[i]->c0()._words().data(), N);
218 copy_mem(m_coeffs.data() + (2 * i + 1) * N, c[i]->c1()._words().data(), N);
219 }
220}
221
222Fp12 Gt::_to_fp12() const {
223 constexpr size_t N = FieldElement::N;
224
225 std::array<FieldElement2, 6> c;
226 for(size_t i = 0; i != c.size(); ++i) {
227 std::array<word, N> c0{};
228 std::array<word, N> c1{};
229 copy_mem(c0.data(), m_coeffs.data() + (2 * i) * N, N);
230 copy_mem(c1.data(), m_coeffs.data() + (2 * i + 1) * N, N);
231 c[i] = FieldElement2::_unchecked_from_words(c0, c1);
232 }
233
234 return Fp12(Fp6(c[0], c[1], c[2]), Fp6(c[3], c[4], c[5]));
235}
236
237//static
239 return Gt(Fp12::one());
240}
241
242bool Gt::is_identity() const {
243 return (*this) == Gt::identity();
244}
245
246bool Gt::operator==(const Gt& other) const {
247 // The Montgomery representation of a reduced element is unique
248 return CT::is_equal(m_coeffs.data(), other.m_coeffs.data(), m_coeffs.size()).as_bool();
249}
250
251std::array<uint8_t, Gt::BYTES> Gt::serialize() const {
252 return this->_to_fp12().serialize();
253}
254
255Gt Gt::pairing(const G1Affine& p, const G2Affine& q) {
256 if(p.is_identity() || q.is_identity()) {
257 return Gt::identity();
258 }
259
260 std::array<PairingTerm, 1> terms = {make_term(p, q)};
261
262 return Gt(final_exponentiation(multi_miller_loop(terms)));
263}
264
265Gt Gt::multi_pairing(std::span<const G1Affine> p, std::span<const G2Affine> q) {
266 if(p.size() != q.size()) {
267 throw Invalid_Argument("BLS12_381::multi_pairing spans must have equal length");
268 }
269
270 std::vector<PairingTerm> terms;
271 terms.reserve(p.size());
272
273 for(size_t i = 0; i != p.size(); ++i) {
274 // By bilinearity e(I,Q) = e(P,I) = I, contributing nothing to the product
275 if(p[i].is_identity() || q[i].is_identity()) {
276 continue;
277 }
278 terms.push_back(make_term(p[i], q[i]));
279 }
280
281 if(terms.empty()) {
282 return Gt::identity();
283 }
284
285 return Gt(final_exponentiation(multi_miller_loop(terms)));
286}
287
288} // namespace Botan::BLS12_381
std::array< uint8_t, BYTES > serialize() const
static Gt pairing(const G1Affine &p, const G2Affine &q)
static Gt multi_pairing(std::span< const G1Affine > p, std::span< const G2Affine > q)
bool operator==(const Gt &other) const
constexpr uint64_t BLS_Z_ABS
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
BigInt square(const BigInt &x)
Definition numthry.cpp:184
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144