1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
import React from "react";
import Entry from "../../components/entry";
import Link from "../../components/Link";
import CodeBlock from "../../components/CodeBlock";
import { Styled } from "theme-ui";
import { BlockMath, InlineMath } from "react-katex";
export default ({ data, location }) => {
let blsCode = `class BLS(object):
@classmethod
def generate_prime_order(cls, zbits):
while True:
z = randint(2^(zbits - 1), 2^zbits)
pz = int(cls.p(z))
if not is_prime(pz):
continue
rz = int(cls.r(z))
if not is_prime(rz):
continue
break
K = GF(pz)
b = 1
while True:
curve = EllipticCurve(K, [0, b])
card = curve.cardinality()
if card % rz == 0:
break
b += 1
return curve
class BLS12(BLS):
@staticmethod
def p(z):
return (z - 1)^2 * (z^4 - z^2 + 1)/3 + z
@staticmethod
def r(z):
return z^4 - z^2 + 1
@staticmethod
def t(z):
return z + 1
class BLS24(BLS):
@staticmethod
def p(z):
return (z - 1)^2 * (z^8 - z^4 + 1)/3 + z
@staticmethod
def r(z):
return z^8 - z^4 + 1
@staticmethod
def t(z):
return z + 1`;
return (
<Entry data={data} location={location} title={"BLS"}>
<Styled.h2>Barreto-Lynn-Scott curves</Styled.h2>
<Styled.p>
A class of pairing-friendly curves with embedding degree{" "}
<InlineMath>{`k \\in \\{12, 24\\}`}</InlineMath>.
</Styled.p>
<Styled.h3>BLS12</Styled.h3>
<Styled.p>
Given an integer <InlineMath>{`z \\in \\mathbb{N}`}</InlineMath> the BLS
curve with embedding degree <InlineMath>12</InlineMath> can be
constructed over a prime field{" "}
<InlineMath>{`\\mathbb{F}_p`}</InlineMath> with the number of points{" "}
<InlineMath>r</InlineMath> and a trace of Frobenius{" "}
<InlineMath>t</InlineMath>.
</Styled.p>
<BlockMath>
{`\\begin{aligned}
p(z) &= (z - 1)^2 (z^4 - z^2 + 1)/3 + z\\\\
r(z) &= z^4 - z^2 + 1\\\\
t(z) &= z + 1
\\end{aligned}`}
</BlockMath>
<Styled.h3>BLS24</Styled.h3>
<Styled.p>
Given an integer <InlineMath>{`z \\in \\mathbb{N}`}</InlineMath> the BLS
curve with embedding degree <InlineMath>24</InlineMath> can be
constructed over a prime field{" "}
<InlineMath>{`\\mathbb{F}_p`}</InlineMath> with the number of points{" "}
<InlineMath>r</InlineMath> and a trace of Frobenius{" "}
<InlineMath>t</InlineMath>.
</Styled.p>
<BlockMath>
{`\\begin{aligned}
p(z) &= (z - 1)^2 (z^8 - z^4 + 1)/3 + z\\\\
r(z) &= z^8 - z^4 + 1\\\\
t(z) &= z + 1
\\end{aligned}`}
</BlockMath>
<Styled.p>The class of curves has the Short-Weierstrass form:</Styled.p>
<BlockMath>y^2 \equiv x^3 + b</BlockMath>
<Styled.p>
where given <InlineMath>z</InlineMath> such that{" "}
<InlineMath>p(z)</InlineMath> is prime, a curve with a prime order
subgroup of <InlineMath>r(z)</InlineMath> points can be found either via
complex multiplication or by exhaustively trying small coefficients{" "}
<InlineMath>b</InlineMath> until a curve is found. Some generate curves
can be found in the <Link to={"/bls/"}>BLS</Link> category.
</Styled.p>
<Styled.p>
The following SageMath code generates BLS curves with embedding degree{" "}
<InlineMath>12</InlineMath> and <InlineMath>24</InlineMath>.
</Styled.p>
<CodeBlock code={blsCode} language="python" />
<Styled.h4>References</Styled.h4>
<ul>
<li>
Paulo S. L. M. Barreto, Ben Lynn, Michael Scott:{" "}
<Link to="https://eprint.iacr.org/2002/088.pdf">
Constructing Elliptic Curves with Prescribed Embedding Degrees
</Link>
</li>
<li>
Diego F. Aranha, Laura Fuentes-Castaneda, Edward Knapp, Alfred
Menezes, Francisco Rodríguez-Henríquez:{" "}
<Link to="https://eprint.iacr.org/2012/232.pdf">
Implementing Pairings at the 192-bit Security Level
</Link>
</li>
</ul>
</Entry>
);
};
|
