bls12_381/notes/
design.rs

Help
1//! # Design of BLS12-381
2//! ## Fixed Generators
3//!
4//! Although any generator produced by hashing to $\mathbb{G}_1$ or $\mathbb{G}_2$ is
5//! safe to use in a cryptographic protocol, we specify some simple, fixed generators.
6//!
7//! In order to derive these generators, we select the lexicographically smallest
8//! valid $x$-coordinate and the lexicographically smallest corresponding $y$-coordinate,
9//! and then scale the resulting point by the cofactor, such that the result is not the
10//! identity. This results in the following fixed generators:
11//!
12//! 1. $\mathbb{G}_1$
13//!     * $x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507$
14//!     * $y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569$
15//! 2. $\mathbb{G}_2$
16//!     * $x = 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160 + 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758 u$
17//!     * $y = 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905 + 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582 u$
18//!
19//! This can be derived using the following sage script:
20//!
21//! ```text
22//! param = -0xd201000000010000
23//! def r(x):
24//!     return (x**4) - (x**2) + 1
25//! def q(x):
26//!     return (((x - 1) ** 2) * ((x**4) - (x**2) + 1) // 3) + x
27//! def g1_h(x):
28//!     return ((x-1)**2) // 3
29//! def g2_h(x):
30//!     return ((x**8) - (4 * (x**7)) + (5 * (x**6)) - (4 * (x**4)) + (6 * (x**3)) - (4 * (x**2)) - (4*x) + 13) // 9
31//! q = q(param)
32//! r = r(param)
33//! Fq = GF(q)
34//! ec = EllipticCurve(Fq, [0, 4])
35//! def psqrt(v):
36//!     assert(not v.is_zero())
37//!     a = sqrt(v)
38//!     b = -a
39//!     if a < b:
40//!         return a
41//!     else:
42//!         return b
43//! for x in range(0,100):
44//!     rhs = Fq(x)^3 + 4
45//!     if rhs.is_square():
46//!         y = psqrt(rhs)
47//!         p = ec(x, y) * g1_h(param)
48//!         if (not p.is_zero()) and (p * r).is_zero():
49//!             print("g1 generator: {}".format(p))
50//!             break
51//! Fq2.<i> = GF(q^2, modulus=[1, 0, 1])
52//! ec2 = EllipticCurve(Fq2, [0, (4 * (1 + i))])
53//! assert(ec2.order() == (r * g2_h(param)))
54//! for x in range(0,100):
55//!     rhs = (Fq2(x))^3 + (4 * (1 + i))
56//!     if rhs.is_square():
57//!         y = psqrt(rhs)
58//!         p = ec2(Fq2(x), y) * g2_h(param)
59//!         if not p.is_zero() and (p * r).is_zero():
60//!             print("g2 generator: {}".format(p))
61//!             break
62//! ```
63//!
64//! ## Nontrivial third root of unity
65//!
66//! To use the fast subgroup check algorithm for $\mathbb{G_1}$ from https://eprint.iacr.org/2019/814.pdf and
67//! https://eprint.iacr.org/2021/1130, it is necessary to find a nontrivial cube root of
68//! unity β in Fp to define the endomorphism:
69//!        $$(x, y) \rightarrow (\beta x, y)$$
70//! which is equivalent to
71//!        $$P \rightarrow \lambda P$$
72//! where $\lambda$, a nontrivial cube root of unity in Fr, satisfies $\lambda^2 + \lambda +1 = 0 \pmod{r}.
73//!
74//! $$\beta = 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350$$
75//! can be derived using the following sage commands after running the above sage script:
76//!
77//! ```text
78//! # Prints the given field element in Montgomery form.
79//! def print_fq(a):
80//!     R = 1 << 384
81//!     tmp = ZZ(Fq(a*R))
82//!     while tmp > 0:
83//!         print("0x{:_x}, ".format(tmp % (1 << 64)))
84//!         tmp >>= 64
85//! β = (Fq.multiplicative_generator() ** ((q-1)/3))
86//! print_fq(β)
87//! ```
88//!
89//! ## Psi
90//!
91//! To use the fast subgroup check algorithm for $\mathbb{G_2}$ from https://eprint.iacr.org/2019/814.pdf and
92//! https://eprint.iacr.org/2021/1130, it is necessary to find the endomorphism:
93//!
94//! $$(x, y, z) \rightarrow (x^q \psi_x, y^q \psi_y, z^q)$$
95//!
96//! where:
97//!
98//! 1. $\psi_x = 1 / ((i+1) ^ ((q-1)/3)) \in \mathbb{F}_{q^2}$, and
99//! 2. $\psi_y = 1 / ((i+1) ^ ((q-1)/2)) \in \mathbb{F}_{q^2}$
100//!
101//! can be derived using the following sage commands after running the above script and commands:
102//! ```text
103//! psi_x = (1/((i+1)**((q-1)/3)))
104//! psi_y = (1/((i+1)**((q-1)/2)))
105//! print_fq(psi_x.polynomial().coefficients()[0])
106//! print_fq(psi_y.polynomial().coefficients()[0])
107//! print_fq(psi_y.polynomial().coefficients()[1])
108//! ```
bls12_381/notes/design.rs

bls12_381/notes/
design.rs
