< draft-yonezawa-pairing-friendly-curves-01.txt   draft-yonezawa-pairing-friendly-curves-02.txt >
Network Working Group S. Yonezawa Network Working Group S. Yonezawa
Internet-Draft Lepidum Internet-Draft Lepidum
Intended status: Experimental Intended status: Experimental T. Kobayashi
Expires: January 9, 2020 T. Saito
T. Kobayashi
T. Saito
NTT NTT
, 2019 July 08, 2019
Pairing-Friendly Curves Pairing-Friendly Curves
draft-yonezawa-pairing-friendly-curves-0 draft-yonezawa-pairing-friendly-curves-02
Abstract Abstract
This memo introduces pairing-friendly curves used for constructing This memo introduces pairing-friendly curves used for constructing
pairing-based cryptography. It describes recommended parameters for pairing-based cryptography. It describes recommended parameters for
each security level and recent implementations of pairing-friendly each security level and recent implementations of pairing-friendly
curves. curves.
Status of This Memo Status of This Memo
skipping to change at page 1, line 37 skipping to change at page 1, line 35
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on . This Internet-Draft will expire on January 9, 2020.
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 18 skipping to change at page 2, line 17
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Pairing-Based Cryptography . . . . . . . . . . . . . . . 2 1.1. Pairing-Based Cryptography . . . . . . . . . . . . . . . 2
1.2. Applications of Pairing-Based Cryptography . . . . . . . 3 1.2. Applications of Pairing-Based Cryptography . . . . . . . 3
1.3. Goal . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Goal . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Requirements Terminology . . . . . . . . . . . . . . . . 4 1.4. Requirements Terminology . . . . . . . . . . . . . . . . 4
2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 4 2.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 4
2.2. Pairing . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Pairing . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3. Barreto-Naehrig Curve . . . . . . . . . . . . . . . . . . 2.3. Barreto-Naehrig Curve . . . . . . . . . . . . . . . . . . 6
2.4. Barreto-Lynn-Scott Curve . . . . . . . . . . . . . . . . 6 2.4. Barreto-Lynn-Scott Curve . . . . . . . . . . . . . . . . 6
2.5. Representation Convention for an Extension Field . . . . 2.5. Representation Convention for an Extension Field . . . . 7
3. Security of Pairing-Friendly Curves . . . . . . . . . . . . . 3. Security of Pairing-Friendly Curves . . . . . . . . . . . . . 8
3.1. Evaluating the Security of Pairing-Friendly Curves . . . 3.1. Evaluating the Security of Pairing-Friendly Curves . . . 8
3.2. Impact of the Recent Attack . . . . . . . . . . . . . . . 3.2. Impact of the Recent Attack . . . . . . . . . . . . . . . 9
4. Security Evaluation of Pairing-Friendly Curves . . . . . . . 4. Security Evaluation of Pairing-Friendly Curves . . . . . . . 9
4.1. For 100 Bits of Security . . . . . . . . . . . . . . . . 4.1. For 100 Bits of Security . . . . . . . . . . . . . . . . 9
4.2. For 128 Bits of Security . . . . . . . . . . . . . . . . 4.2. For 128 Bits of Security . . . . . . . . . . . . . . . . 10
4.3. For 256 Bits of Security . . . . . . . . . . . . . . . . 4.2.1. BN Curves . . . . . . . . . . . . . . . . . . . . . . 10
5. Implementations of Pairing-Friendly Curves . . . . . . . . . 4.2.2. BLS Curves . . . . . . . . . . . . . . . . . . . . . 12
6. Security Considerations . . . . . . . . . . . . . . . . . . . 4.3. For 192 Bits of Security . . . . . . . . . . . . . . . . 14
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 4.4. For 256 Bits of Security . . . . . . . . . . . . . . . . 15
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5. Implementations of Pairing-Friendly Curves . . . . . . . . . 19
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 6. Security Considerations . . . . . . . . . . . . . . . . . . . 21
9.1. Normative References . . . . . . . . . . . . . . . . . . 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
9.2. Informative References . . . . . . . . . . . . . . . . . 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21
Appendix A. Computing Optimal Ate Pairing . . . . . . . . . . . 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
A.1. Optimal Ate Pairings over Barreto-Naehrig Curves . . . . 9.1. Normative References . . . . . . . . . . . . . . . . . . 21
A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves . . . 9.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix B. Test Vectors of Optimal Ate Pairing . . . . . . . . Appendix A. Computing Optimal Ate Pairing . . . . . . . . . . . 26
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . A.1. Optimal Ate Pairings over Barreto-Naehrig Curves . . . . 27
A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves . . . 27
Appendix B. Test Vectors of Optimal Ate Pairing . . . . . . . . 28
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 35
1. Introduction 1. Introduction
1.1. Pairing-Based Cryptography 1.1. Pairing-Based Cryptography
Elliptic curve cryptography is one of the important areas in recent Elliptic curve cryptography is one of the important areas in recent
cryptography. The cryptographic algorithms based on elliptic curve cryptography. The cryptographic algorithms based on elliptic curve
cryptography, such as widely used in many applications. cryptography, such as ECDSA (Elliptic Curve Digital Signature
Algorithm), are widely used in many applications.
Pairing-based cryptography, a variant of elliptic curve cryptography, Pairing-based cryptography, a variant of elliptic curve cryptography,
s attracted the attention for its flexible and applicable has attracted the attention for its flexible and applicable
functionality. Pairing is a special map defined over elliptic functionality. Pairing is a special map defined over elliptic
curves. curves. Thanks to the characteristics of pairing, it can be applied
to construct several cryptographic algorithms and protocols such as
Thanks to the characteristics of pairing, it can be applied to
construct several cryptographic algorithms and protocols such as
identity-based encryption (IBE), attribute-based encryption (ABE), identity-based encryption (IBE), attribute-based encryption (ABE),
authenticated key exchange (AKE), short signatures and so on. authenticated key exchange (AKE), short signatures and so on.
Several applications of pairing-based cryptography now in Several applications of pairing-based cryptography are now in
practical use. practical use.
As the importance of pairing grows, elliptic curves where pairing is
efficiently computable are studied and the special curves called
pairing-friendly curves are proposed.
1.2. Applications of Pairing-Based Cryptography 1.2. Applications of Pairing-Based Cryptography
Several applications using pairing-based cryptography are Several applications using pairing-based cryptography are
standardized and implemented. We show example applications available standardized and implemented. We show example applications available
in the real world. in the real world.
IETF RFCs for pairing-based cryptography such as IETF publishes RFCs for pairing-based cryptography such as Identity-
Sakai-Kasahara Key Encryption (SAKKE) Based Cryptography [RFC5091], Sakai-Kasahara Key Encryption (SAKKE)
and Identity-Based Authenticated Key Exchange (IBAKE) SAKKE is [RFC6508], and Identity-Based Authenticated Key Exchange (IBAKE)
applied to Multimedia Internet KEYing (MIKEY) and used in 3GPP [RFC6539]. SAKKE is applied to Multimedia Internet KEYing (MIKEY)
[RFC6509] and used in 3GPP [SAKKE].
Pairing-based key agreement protocols are standardized in ISO/IEC Pairing-based key agreement protocols are standardized in ISO/IEC
In a key agreement scheme by Joux identity-based [ISOIEC11770-3]. In [ISOIEC11770-3], a key agreement scheme by Joux
key agreement schemes by Smart-Chen-Cheng and by [Joux00], identity-based key agreement schemes by Smart-Chen-Cheng
are specified. [CCS07] and by Fujioka-Suzuki-Ustaoglu [FSU10] are specified.
MIRACL implements M-Pin, a multi-factor authentication protocol MIRACL implements M-Pin, a multi-factor authentication protocol
M-Pin protocol includes a kind of zero-knowledge proof, where pairing [M-Pin]. M-Pin protocol includes a kind of zero-knowledge proof,
is used for its construction. where pairing is used for its construction.
Trusted Computing Group (TCG) specifies ECDAA (Elliptic Curve Direct Trusted Computing Group (TCG) specifies ECDAA (Elliptic Curve Direct
Anonymous Attestation) in the specification of Trusted Platform Anonymous Attestation) in the specification of Trusted Platform
Module (TPM) []. ECDAA is a protocol for proving the attestation Module (TPM) [TPM]. ECDAA is a protocol for proving the attestation
held by a TPM to a verifier without revealing the attestation held by held by a TPM to a verifier without revealing the attestation held by
that TPM. Pairing is used for constructing ECDAA. FIDO Alliance that TPM. Pairing is used for constructing ECDAA. FIDO Alliance
and W3C also published ECDAA algorithm similar to TCG. [FIDO] and W3C [W3C] also published ECDAA algorithm similar to TCG.
Intel introduces Intel Enhanced Privacy ID (EPID) which enables
remote attestation of a hardware device while preserving the privacy
of the device as a functionality of Intel Software Guard Extensions
(SGX) [EPID]. They extend TPM ECDAA to realize such functionality.
A pairing-based EPID has been proposed [BL10] and distributed along
with Intel SGX applications.
Zcash implements their own zero-knowledge proof algorithm named zk- Zcash implements their own zero-knowledge proof algorithm named zk-
SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of
Knowledge) []. zk-SNARKs is used for protecting privacy of Knowledge) [Zcash]. zk-SNARKs is used for protecting privacy of
transactions of Zcash. They use pairing for constructing zk-SNARKS. transactions of Zcash. They use pairing for constructing zk-SNARKS.
Cloudflare Geo Key Manager to restrict distribution Cloudflare introduces Geo Key Manager [Cloudflare] to restrict
of customers' private keys to the subset of their data centers. To distribution of customers' private keys to the subset of their data
achieve this functionality, attribute-based encryption is used and centers. To achieve this functionality, attribute-based encryption
pairing takes a role as a building block. is used and pairing takes a role as a building block.
Recently, Boneh-Lynn-Shacham (BLS) signature schemes are being Recently, Boneh-Lynn-Shacham (BLS) signature schemes are being
standardized and utilized in several blockchain projects such as standardized [I-D.boneh-bls-signature] and utilized in several
Ethereum Algorand Chia Network and DFINITY blockchain projects such as Ethereum [Ethereum], Algorand [Algorand],
The aggregation functionality of BLS Chia Network [Chia] and DFINITY [DFINITY]. The aggregation
signatures effective for their applications of decentralization functionality of BLS signatures is effective for their applications
and scalability. of decentralization and scalability.
1.3. Goal 1.3. Goal
The goal of this memo is to consider the security of pairing-friendly The goal of this memo is to consider the security of pairing-friendly
curves used in pairing-based cryptography and introduce secure curves used in pairing-based cryptography and introduce secure
parameters of pairing-frindly curves. Specifically, we explain the parameters of pairing-friendly curves. Specifically, we explain the
recent attack against pairing-friendly curves and how much the recent attack against pairing-friendly curves and how much the
security of the curves is reduced. We show how to evaluate the security of the curves is reduced. We show how to evaluate the
security of pairing-friendly curves and give the parameters for 100 security of pairing-friendly curves and give the parameters for 100
bits of security, which is no longer secure, 128 and 256 bits of bits of security, which is no longer secure, 128, 192 and 256 bits of
security. security.
1.4. Requirements Terminology 1.4. Requirements Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"MAY", and "OPTIONAL" in this document are to be interpreted as "OPTIONAL" in this document are to be interpreted as described in BCP
described in 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
2. Preliminaries 2. Preliminaries
2.1. Elliptic Curve 2.1. Elliptic Curve
Let p > 3 be a prime and be a finite field. The curve defined by Let p > 3 be a prime and q = p^n for a natural number n. Let F_q be
the following equation E is called an elliptic curve. a finite field. The curve defined by the following equation E is
called an elliptic curve.
E : y^2 = x^3 + A * x + B, E : y^2 = x^3 + A * x + B,
where are in and 4 * A^3 + 27 * B^2 != 0 mod where x and y are in F_q, and A and B in F_q satisfy the discriminant
inequality 4 * A^3 + 27 * B^2 != 0 mod q. This is called Weierstrass
normal form of an elliptic curve.
Solutions (x, y) for an elliptic curve E, as well as the point at Solutions (x, y) for an elliptic curve E, as well as the point at
infinity, O_E, are called F_-rational points. If P and Q are two infinity, O_E, are called F_q-rational points. If P and Q are two
points on the curve E, we can define R = P + Q as the opposite point points on the curve E, we can define R = P + Q as the opposite point
of the intersection between the curve E and the line that of the intersection between the curve E and the line that passes
P and Q. We can define P + O_E = P = O_E + P as well. through P and Q.
We can define P + O_E = P = O_E + P as well. Similarly, we can
Similarly, a scalar multiplication S = [a]P for a define 2P = P + P and a scalar multiplication S = [a]P for a positive
positive integer a can be defined as an a-time addition of P. integer a can be defined as an a-time addition of P.
the cyclic additive group with a prime order r The additive group, denoted by E(F_q), is constructed by the set of
base point in group is used for the elliptic curve F_q-rational points and the addition law described above. We can
cryptography. define terminology used in this memo define the cyclic additive group with a prime order r by taking a
as follows. base point BP in E(F_q) as a generator. This group is used for the
elliptic curve cryptography.
We define terminology used in this memo as follows.
O_E: the point at infinity over an elliptic curve E. O_E: the point at infinity over an elliptic curve E.
. E(F_q): a group constructed by F_q-rational points of E.
h: a cofactor such that h = #E(F_q): the number of F_q-rational points of E.
h: a cofactor such that h = #E(F_q) / r.
k: an embedding degree, a minimum integer such that r is a divisor of k: an embedding degree, a minimum integer such that r is a divisor of
^k - 1. q^k - 1.
2.2. Pairing 2.2. Pairing
Pairing is a kind of the bilinear map defined over elliptic Pairing is a kind of the bilinear map defined over two elliptic
Examples include Weil pairing, Tate pairing, optimal Ate pairing curves E and E'. Examples include Weil pairing, Tate pairing,
and so on. Especially, optimal Ate pairing is considered to be optimal Ate pairing [Ver09] and so on. Especially, optimal Ate
efficient to compute and mainly used for practical implementation. pairing is considered to be efficient to compute and mainly used for
practical implementation.
Let E be an elliptic curve defined over prime field F_p. Let G_1 Let E be an elliptic curve defined over a prime field F_p and E' be
be a cyclic subgroup on E with order r, an elliptic curve defined over an extension field of F_p. Let G_1 be
and G_2 be a cyclic subgroup curve E' a cyclic subgroup on the elliptic curve E with order r, and G_2 be a
with order r. Let G_T be an order r subgroup of a where cyclic subgroup on the elliptic curve E' with order r. Let G_T be an
k is an embedded order r subgroup of a multiplicative group F_pk^*, where k is an
embedded degree of E.
1. Bilinearity: for any S in G_1, T in G_2, Pairing is defined as a bilinear map e: (G_1, G_2) -> G_T satisfying
e([a]S, [b]T) = e(S, T)^{a * b}. the following properties:
1. Bilinearity: for any S in G_1, T in G_2, and integers a and b,
e([a]S, [b]T) = e(S, T)^{a * b}.
2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = 2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S =
O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T =
O_E. O_E.
3. Computability: for any S in G_1 and T in G_2, the bilinear map is 3. Computability: for any S in G_1 and T in G_2, the bilinear map is
efficiently computable. efficiently computable.
2.3. Barreto-Naehrig Curve 2.3. Barreto-Naehrig Curve
A BN curve [] is one of the instantiations of pairing-friendly A BN curve [BN05] is one of the instantiations of pairing-friendly
curves proposed in 2005. A pairing over BN curves constructs optimal curves proposed in 2005. A pairing over BN curves constructs optimal
Ate pairings. Ate pairings.
A BN curve is elliptic E defined over F_p, A BN curve is defined by elliptic curves E and E' parameterized by a
where p is more than or equal to 5, p and order r are well chosen integer t. E is defined over F_p, where p is a prime
parameterized by more than or equal to 5, and E(F_p) has a subgroup of prime order r.
The characteristic p and the order r are parameterized by
p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1 p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1
r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1 r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1
for integer t. The elliptic curve has an equation for an integer t.
of the form E: y^2 = x^3 + b, where b is an element of multiplicative
group of order p. The elliptic curve E has an equation of the form E: y^2 = x^3 + b,
where b is an element of multiplicative group of order p.
BN curves always have order 6 twists. If m is an element which is BN curves always have order 6 twists. If m is an element which is
neither a square nor a cube in field F_p2, the twisted curve neither a square nor a cube in an extension field F_p2, the twisted
E' of E is defined over field F_p2 by the equation E': y^2 = curve E' of E is defined over an extension field F_p2 by the equation
x^3 + b' with b' = b / m or b' = b * m. The embedded degree k is 12. E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN curves are
called D-type if b' = b / m, and M-type if b' = b * m. The embedded
degree k is 12.
A pairing e is defined by taking G_1 as a A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order
G_2 as a r, G_2 as a subgroup of E'(F_p2), and G_T as a subgroup of a
and G_T as a multiplicative group F_p12^* of order r.
multiplicative group of order
2.4. Barreto-Lynn-Scott Curve 2.4. Barreto-Lynn-Scott Curve
A BLS curve [] is another instantiations of pairings proposed in A BLS curve [BLS02] is another instantiations of pairings proposed in
2002. Similar to BN curves, a pairing over BLS curves constructs 2002. Similar to BN curves, a pairing over BLS curves constructs
optimal Ate pairings. optimal Ate pairings.
A BLS curve is elliptic E defined over a finite field F_p by A BLS curve is elliptic curves E and E' parameterized by a well
an equation of the form E: y^2 = x^3 + and chosen integer t. E is defined over a finite field F_p by an
defined in the same way as BN curves. In contrast to BN curves, equation of the form E: y^2 = x^3 + b, and its twisted curve, E': y^2
does not have a prime its order is divisible by a = x^3 + b', is defined in the same way as BN curves. In contrast to
large parameterized prime r and pairing will be defined on the BN curves, E(F_p) does not have a prime order. Instead, its order is
r-torsions points. divisible by a large parameterized prime r and denoted by h * r with
cofactor h. The pairing will be defined on the r-torsions points.
In the same way as BN curves, BLS curves can be categorized into
D-type and M-type.
BLS curves vary according to different embedding degrees. In this BLS curves vary according to different embedding degrees. In this
memo, we deal with BLS12 and BLS48 families with embedding degrees 12 memo, we deal with BLS12 and BLS48 families with embedding degrees 12
and 48 with respect to r, respectively. and 48 with respect to r, respectively.
In BLS curves, parameterized p and r are given by the following In BLS curves, parameterized p and r are given by the following
equations: equations:
BLS12: BLS12:
p = (t - 1)^2 * (t^4 - t^2 + 1) / 3 + t p = (t - 1)^2 * (t^4 - t^2 + 1) / 3 + t
r = t^4 - t^2 + 1 r = t^4 - t^2 + 1
BLS48: BLS48:
p = (t - 1)^2 * (t^16 - t^8 + 1) / 3 + t p = (t - 1)^2 * (t^16 - t^8 + 1) / 3 + t
r = t^16 - t^8 + 1 r = t^16 - t^8 + 1
for well chosen integer t. for a well chosen integer t.
A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order
r, G_2 as an order r subgroup of E'(F_p2) for BLS12 and of E'(F_p8)
for BLS48, and G_T as an order r subgroup of a multiplicative group
F_p12^* for BLS12 and of a multiplicative group F_p48^* for BLS48.
2.5. Representation Convention for an Extension Field 2.5. Representation Convention for an Extension Field
Pairing-friendly curves some extension fields. In order to Pairing-friendly curves use a tower of some extension fields. In
encode an element of an extension field, we adopt the convention order to encode an element of an extension field, we adopt the
shown in representation convention shown in [IEEE-1363a-2004].
of an extension field of degree d such that s = s_0 Let F_p be a finite field of characteristic p and F_p^d be an
+ s_1 * + ... + * for extension field of F_p of degree d and an indeterminate i. For an
s is represented by element s in F_p^d such that s = s_0 + s_1 * p + ... + s_{d - 1} *
i^{d - 1} for s_0, s_1, ... , s_{d - 1} in a basefield F_p, s is
represented as integer by
= s_0 + s_1 * p + * + ... + * int(s) = s_0 + s_1 * p + ... + s_{d - 1} * p^{d - 1}.
Let F_p^d' be an extension field of F_p^d of degree d' / d and an
indeterminate j. For an element s' in F_p^d' such that s' = s'_0 +
s'_1 * j + ... + s'_{d' / d - 1} * j^{d' / d - 1} for s'_0, s'_1, ...
, s'_{d' / d - 1} in a basefield F_p^d, s' is represented as integer
by
int(s') = int(s'_0) + int(s'_1) * p^{d' / d} +
... + int(s'_{d' / d - 1}) * p^{d' / d * (d' - 1)},
where int(s'_0), ... , int(s'_{d' / d - 1}) are integers encoded by
above convention.
In general, one can define encoding between integer and an element of
any finite field tower by inductively applying the above convention.
The parameters and test vectors of extension fields described in this The parameters and test vectors of extension fields described in this
memo are encoded by this convention and represented in octet stream. memo are encoded by this convention and represented in octet stream.
3. Security of Pairing-Friendly Curves 3. Security of Pairing-Friendly Curves
3.1. Evaluating the Security of Pairing-Friendly Curves 3.1. Evaluating the Security of Pairing-Friendly Curves
The security of pairing-friendly curves is evaluated by the hardness The security of pairing-friendly curves is evaluated by the hardness
of the following discrete logarithm problems. of the following discrete logarithm problems.
- The elliptic curve discrete logarithm problem (ECDLP) in G_1 and - The elliptic curve discrete logarithm problem (ECDLP) in G_1 and
G_2 G_2
- The finite field discrete logarithm problem (FFDLP) in G_T - The finite field discrete logarithm problem (FFDLP) in G_T
There are other hard problems over pairing-friendly There are other hard problems over pairing-friendly curves used for
used for proving the security of pairing-based cryptography. Such proving the security of pairing-based cryptography. Such problems
problems include computational bilinear Diffie-Hellman (CBDH) problem include computational bilinear Diffie-Hellman (CBDH) problem and
bilinear Diffie-Hellman (BDH) Problem, decision bilinear Diffie- bilinear Diffie-Hellman (BDH) Problem, decision bilinear Diffie-
Hellman (DBDH) problem, gap DBDH problem, etc Almost all of Hellman (DBDH) problem, gap DBDH problem, etc [ECRYPT]. Almost all
these variants are reduced to the hardness of discrete logarithm of these variants are reduced to the hardness of discrete logarithm
problems described above and believed to be easier than the discrete problems described above and believed to be easier than the discrete
logarithm problems. logarithm problems.
There would be the case where the attacker solves these reduced There would be the case where the attacker solves these reduced
problems to break pairing-based cryptography. Since such attacks problems to break pairing-based cryptography. Since such attacks
have not been discovered yet, we discuss the hardness of the discrete have not been discovered yet, we discuss the hardness of the discrete
logarithm problems in this memo. logarithm problems in this memo.
The security level of pairing-friendly curves is estimated by the The security level of pairing-friendly curves is estimated by the
computational cost of the most efficient algorithm to solve the above computational cost of the most efficient algorithm to solve the above
discrete logarithm problems. The well-known algorithms for solving discrete logarithm problems. The well-known algorithms for solving
the discrete logarithm problems Pollard's rho algorithm the discrete logarithm problems include Pollard's rho algorithm
Index Calculus and so on. In order to make index calculus [Pollard78], Index Calculus [HR83] and so on. In order to make index
algorithms more efficient, number field sieve (NFS) algorithms are calculus algorithms more efficient, number field sieve (NFS)
utilized. algorithms are utilized.
3.2. Impact of the Recent Attack 3.2. Impact of the Recent Attack
In 2016, Kim and Barbulescu proposed a new variant of the NFS In 2016, Kim and Barbulescu proposed a new variant of the NFS
algorithms, the extended number field sieve (exTNFS), which algorithms, the extended tower number field sieve (exTNFS), which
drastically reduces the complexity of solving FFDLP Due to drastically reduces the complexity of solving FFDLP [KB16]. Due to
exTNFS, the security level of pairing-friendly curves asymptotically exTNFS, the security level of pairing-friendly curves asymptotically
dropped down. For instance, Barbulescu and Duquesne that dropped down. For instance, Barbulescu and Duquesne estimated that
the security of the BN curves which believed to provide 128 bits the security of the BN curves which had been believed to provide 128
of security (BN256, for example) dropped down to approximately 100 bits of security (BN256, for example) dropped down to approximately
bits 100 bits [BD18].
Some papers the minimum of the parameters of Some papers showed the minimum bit length of the parameters of
curves for each security level when applying exTNFS as an pairing-friendly curves for each security level when applying exTNFS
attacking method for FFDLP. For 128 bits of security, Menezes, as an attacking method for FFDLP. For 128 bits of security, Menezes,
Sarkar and Singh estimated the minimum of p of BN curves Sarkar and Singh estimated the minimum bit length of p of BN curves
after exTNFS as 383 bits, and that of BLS12 curves as 384 bits after exTNFS as 383 bits, and that of BLS12 curves as 384 bits
For 256 bits of security, Kiyomura et al. estimated the minimum [MSS17]. For 256 bits of security, Kiyomura et al. estimated the
of p^k of BLS48 curves as 27,410 bits, which implied 572 minimum bit length of p^k of BLS48 curves as 27,410 bits, which
bits of p implied 572 bits of p [KIK17].
4. Security Evaluation of Pairing-Friendly Curves 4. Security Evaluation of Pairing-Friendly Curves
We give security evaluation for pairing-friendly curves based on the We give security evaluation for pairing-friendly curves based on the
evaluating method presented in Section 3. We also introduce secure evaluating method presented in Section 3. We also introduce secure
parameters of pairing-friendly curves for each security level. The parameters of pairing-friendly curves for each security level. The
parameters introduced here are chosen with the consideration of parameters introduced here are chosen with the consideration of
security, efficiency and global acceptance. security, efficiency and global acceptance.
For security, we introduce 100 bits, 128 bits and 256 bits of For security, we introduce the parameters with 100 bits, 128 bits,
security. We note that 100 bits of security is no longer secure and 192 bits and 256 bits of security. We note that 100 bits of security
recommend 128 bits and 256 bits of security for secure applications. is no longer secure and recommend 128 bits, 192 bits and 256 bits of
We follow TLS 1.3 which specifies the cipher suites with 128 security for secure applications. We follow TLS 1.3 [RFC8446] which
bits and 256 bits of security as mandatory-to-implement for the specifies the cipher suites with 128 bits and 256 bits of security as
choice of the security level. mandatory-to-implement for the choice of the security level.
mplementers of the applications have to choose the parameters with Implementers of the applications have to choose the parameters with
appropriate security level according to the security requirements of appropriate security level according to the security requirements of
the applications. For efficiency, we refer to the benchmark by mcl the applications. For efficiency, we refer to the benchmark by mcl
for 128 bits of security, and by Kiyomura et al. for 256 [mcl] for 128 bits of security, and by Kiyomura et al. [KIK17] for
bits of and choose sufficiently efficient parameters. For 256 bits of security, and then choose sufficiently efficient
global acceptance, we give the implementations of pairing-friendly parameters. For global acceptance, we give the implementations of
curves in Section 5. pairing-friendly curves in Section 5.
4.1. For 100 Bits of Security 4.1. For 100 Bits of Security
Before exTNFS, BN curves with 256-bit size of underlying finite field Before exTNFS, BN curves with 256-bit size of underlying finite field
(so-called BN256) were considered to ve 128 bits of security. (so-called BN256) were considered to achieve 128 bits of security.
After exTNFS, however, the security level of BN curves with 256-bit After exTNFS, however, the security level of BN curves with 256-bit
size of underlying finite field fell into 100 bits. size of underlying finite field fell into 100 bits.
who will newly develop the applications of pairing-based Implementers who will newly develop the applications of pairing-based
cryptography SHOULD NOT use pairing-friendly cryptography SHOULD NOT use pairing-friendly curves with 100 bits of
security (i.e. BN256).
100 bits of security (i.e. implementers There exists applications which already implemented pairing-based
MAY use cryptography with 100-bit secure pairing-friendly curves. In such a
case, implementers MAY use 100 bits of security only if they need to
keep interoperability with the existing applications.
4.2. For 128 Bits of Security 4.2. For 128 Bits of Security
A BN curve with 128 bits of security is shown in which we call 4.2.1. BN Curves
BN462. BN462 is defined by a parameter t = 2^114 + 2^101 - 2^14 - 1
for the definition in Section 2.3. A BN curve with 128 bits of security is shown in [BD18], which we
call BN462. BN462 is defined by a parameter
t = 2^114 + 2^101 - 2^14 - 1
for the definition in Section 2.3.
For the finite field F_p, the towers of extension field F_p2, F_p6 For the finite field F_p, the towers of extension field F_p2, F_p6
and F_p12 are defined by indeterminas u, v, w as follows: and F_p12 are defined by indeterminates u, v, w as follows:
F_p2 = F_p[u] / (u^2 + 1) F_p2 = F_p[u] / (u^2 + 1)
F_p6 = F_p2[v] / (v^3 - u - 2) F_p6 = F_p2[v] / (v^3 - u - 2)
F_p12 = F_p6[w] / (w^2 - v). F_p12 = F_p6[w] / (w^2 - v).
the a order Defined by t, the elliptic curve E and its twisted curve E' are
a base point = (x, a of E: y^2 = represented by E: y^2 = x^3 + 5 and E': y^2 = x^3 - u + 2,
x^3 + an order a base point a cofactor respectively. The size of p becomes 462-bit length. A pairing e is
of E': y^2 = x^3 + defined by taking G_1 as a cyclic group of order r generated by a
base point BP = (x, y) in F_p, G_2 as a cyclic group of order r
generated by a based point BP' = (x', y') in F_p2, and G_T as a
subgroup of a multiplicative group F_p12^* of order r. BN462 is
D-type.
We give the following parameters for BN462.
- G_1 defined over E: y^2 = x^3 + b
o p : a characteristic
o r : an order
o BP = (x, y) : a base point
o h : a cofactor
o b : a coefficient of E
- G_2 defined over E': y^2 = x^3 + b'
o r' : an order
o BP' = (x', y') : a base point (encoded with [IEEE-1363a-2004])
* x' = x'0 + x'1 * u (x'0, x'1 in F_p)
* y' = y'0 + y'1 * u (y'0, y'1 in F_p)
o h' : a cofactor
o b' : a coefficient of E'
p: 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8 p: 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8
12908f41 c8020fff fffffff6 ff66fc6f f687f640 00000000 2401b008 12908f41 c8020fff fffffff6 ff66fc6f f687f640 00000000 2401b008
40138013 40138013
r: 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8 r: 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8
12908ee1 c201f7ff fffffff6 ff66fc7b f717f7c0 00000000 2401b007 12908ee1 c201f7ff fffffff6 ff66fc7b f717f7c0 00000000 2401b007
e010800d e010800d
x: 0x21a6 d67ef250 191fadba 34a0a301 60b9ac92 64b6f95f 63b3edbe x: 0x21a6 d67ef250 191fadba 34a0a301 60b9ac92 64b6f95f 63b3edbe
skipping to change at page 10, line 4 skipping to change at page 11, line 39
x: 0x21a6 d67ef250 191fadba 34a0a301 60b9ac92 64b6f95f 63b3edbe x: 0x21a6 d67ef250 191fadba 34a0a301 60b9ac92 64b6f95f 63b3edbe
c3cf4b2e 689db1bb b4e69a41 6a0b1e79 239c0372 e5cd7011 3c98d91f c3cf4b2e 689db1bb b4e69a41 6a0b1e79 239c0372 e5cd7011 3c98d91f
36b6980d 36b6980d
y: 0x0118 ea0460f7 f7abb82b 33676a74 32a490ee da842ccc fa7d788c y: 0x0118 ea0460f7 f7abb82b 33676a74 32a490ee da842ccc fa7d788c
65965042 6e6af77d f11b8ae4 0eb80f47 5432c666 00622eca a8a5734d 65965042 6e6af77d f11b8ae4 0eb80f47 5432c666 00622eca a8a5734d
36fb03de 36fb03de
h: 1 h: 1
b: 5 b: 5
r': 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8 r': 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8
12908ee1 c201f7ff fffffff6 ff66fc7b f717f7c0 00000000 2401b007 12908ee1 c201f7ff fffffff6 ff66fc7b f717f7c0 00000000 2401b007
e010800d e010800d
x'0: 0x0257 ccc85b58 dda0dfb3 8e3a8cbd c5482e03 37e7c1cd 96ed61c9
4ae1e4df
x'1: 0x1d2e 4343e859 9102af8e dca84956 6ba3c98e 2a354730 cbed9176
884058b1 8134dd86 bae555b7 83718f50 af8b59bf 7e850e9b 73108ba6
aa8cd283
y'0: 0x0a06 50439da2 2c197951 7427a208 09eca035 634706e2 3c3fa7a6
bb42fe81 0f1399a1 f41c9dda e32e0369 5a140e7b 11d7c337 6e5b68df
0db7154e
y'1: 0x073e f0cbd438 cbe0172c 8ae37306 324d44d5 e6b0c69a c57b393f
1ab370fd 725cc647 692444a0 4ef87387 aa68d537 43493b9e ba14cc55
2ca2a93a
x': 0x041b04cb e3413297 c49d8129 7eed0759 47d86135 c4abf0be 9d5b64be x': 0x041b04cb e3413297 c49d8129 7eed0759 47d86135 c4abf0be 9d5b64be
02d6ae78 34047ea4 079cd30f e28a68ba 0cb8f7b7 2836437d c75b2567 02d6ae78 34047ea4 079cd30f e28a68ba 0cb8f7b7 2836437d c75b2567
ff2b98db b93f68fa c828d822 1e4e1d89 475e2d85 f2063cbc 4a74f6f6 ff2b98db b93f68fa c828d822 1e4e1d89 475e2d85 f2063cbc 4a74f6f6
6268b6e6 da1162ee 055365bb 30283bde 614a17f6 1a255d68 82417164 6268b6e6 da1162ee 055365bb 30283bde 614a17f6 1a255d68 82417164
bc500498 bc500498
y': 0x0104fa79 6cbc2989 0f9a3798 2c353da1 3b299391 be45ddb1 c15ca42a y': 0x0104fa79 6cbc2989 0f9a3798 2c353da1 3b299391 be45ddb1 c15ca42a
bdf8bf50 2a5dd7ac 0a3d351a 859980e8 9be676d0 0e92c128 714d6f3c bdf8bf50 2a5dd7ac 0a3d351a 859980e8 9be676d0 0e92c128 714d6f3c
6aba56ca 6e0fc6a5 468c12d4 2762b29d 840f13ce 5c3323ff 016233ec 6aba56ca 6e0fc6a5 468c12d4 2762b29d 840f13ce 5c3323ff 016233ec
7d76d4a8 12e25bbe b2c25024 3f2cbd27 80527ec5 ad208d72 24334db3 7d76d4a8 12e25bbe b2c25024 3f2cbd27 80527ec5 ad208d72 24334db3
c1b4a49c c1b4a49c
h': 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8 h': 0x2404 80360120 023fffff fffff6ff 0cf6b7d9 bfca0000 000000d8
12908fa1 ce0227ff fffffff6 ff66fc63 f5f7f4c0 00000000 2401b008 12908fa1 ce0227ff fffffff6 ff66fc63 f5f7f4c0 00000000 2401b008
a0168019 a0168019
b': -u + 2 b': -u + 2
A BLS12 curve with 128 bits of security shown in BLS12-381, is 4.2.2. BLS Curves
defined by a parameter t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16
and the size of p becomes 381-bit length. A BLS12 curve with 128 bits of security shown in [BLS12-381],
BLS12-381, is defined by a parameter
t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16
and the size of p becomes 381-bit length.
For the finite field F_p, the towers of extension field F_p2, F_p6 For the finite field F_p, the towers of extension field F_p2, F_p6
and F_p12 are defined by indeterminas u, v, w as follows: and F_p12 are defined by indeterminates u, v, w as follows:
F_p2 = F_p[u] / (u^2 + 1) F_p2 = F_p[u] / (u^2 + 1)
F_p6 = F_p2[v] / (v^3 - u - 1) F_p6 = F_p2[v] / (v^3 - u - 1)
F_p12 = F_p6[w] / (w^2 - v). F_p12 = F_p6[w] / (w^2 - v).
the Defined by t, the elliptic curve E and its twisted curve E' are
and represented by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1).
by
and
We the for BLS12-381 as A pairing e is defined by taking G_1 as a cyclic group of order r
generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group
of order r generated by a based point BP' = (x', y') in F_p2, and G_T
as a subgroup of a multiplicative group F_p12^* of order r.
BLS12-381 is M-type.
We have to note that, according to [MSS17], the bit length of p for
BLS12 to achieve 128 bits of security is calculated as 384 bits and
more, which BLS12-381 does not satisfy. They state that BLS12-381
achieves 127-bit security level evaluated by the computational cost
of Pollard's rho, whereas NCC group estimated that the security level
of BLS12-381 is between 117 and 120 bits at most [NCCG]. Therefore,
we regard BN462 as a "conservative" parameter, and BLS12-381 as an
"optimistic" parameter.
We give the following parameters for BLS12-381.
- G_1 defined over E: y^2 = x^3 + b
o p : a characteristic
o r : an order
o BP = (x, y) : a base point
o h : a cofactor
o b : a coefficient of E
- G_2 defined over E': y^2 = x^3 + b'
o r' : an order
o BP' = (x', y') : a base point (encoded with [IEEE-1363a-2004])
* x' = x'0 + x'1 * u (x'0, x'1 in F_p)
* y' = y'0 + y'1 * u (y'0, y'1 in F_p)
o h' : a cofactor
o b' : a coefficient of E'
p: 0x1a0111ea 397fe69a 4b1ba7b6 434bacd7 64774b84 f38512bf 6730d2a0 p: 0x1a0111ea 397fe69a 4b1ba7b6 434bacd7 64774b84 f38512bf 6730d2a0
f6b0f624 1eabfffe b153ffff b9feffff ffffaaab f6b0f624 1eabfffe b153ffff b9feffff ffffaaab
r: 0x73eda753 299d7d48 3339d808 09a1d805 53bda402 fffe5bfe ffffffff r: 0x73eda753 299d7d48 3339d808 09a1d805 53bda402 fffe5bfe ffffffff
00000001 00000001
x: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f 9774b905 a14e3a3f x: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f 9774b905 a14e3a3f
171bac58 6c55e83f f97a1aef fb3af00a db22c6bb 171bac58 6c55e83f f97a1aef fb3af00a db22c6bb
y: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095 d5d00af6 00db18cb y: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095 d5d00af6 00db18cb
2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1 2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1
h: 0x396c8c00 5555e156 8c00aaab 0000aaab h: 0x396c8c00 5555e156 8c00aaab 0000aaab
b: 4 b: 4
r': 0x1a0111ea 397fe69a 4b1ba7b6 434bacd7 64774b84 f38512bf 6730d2a0 r': 0x1a0111ea 397fe69a 4b1ba7b6 434bacd7 64774b84 f38512bf 6730d2a0
f6b0f624 1eabfffe b153ffff b9feffff ffffaaab f6b0f624 1eabfffe b153ffff b9feffff ffffaaab
x'0: 0x24aa2b2 f08f0a91 26080527 2dc51051 c6e47ad4 fa403b02 b4510b64
7ae3d177 0bac0326 a805bbef d48056c8 c121bdb8
x'1: 0x13e02b60 52719f60 7dacd3a0 88274f65 596bd0d0 9920b61a
b5da61bb dc7f5049 334cf112 13945d57 e5ac7d05 5d042b7e
y'0: 0xce5d527 727d6e11 8cc9cdc6 da2e351a adfd9baa 8cbdd3a7 6d429a69
5160d12c 923ac9cc 3baca289 e1935486 08b82801
y'1: 0x606c4a0 2ea734cc 32acd2b0 2bc28b99 cb3e287e 85a763af 267492ab
572e99ab 3f370d27 5cec1da1 aaa9075f f05f79be
x': 0x204d9ac 05ffbfeb ac60c8f3 e4143831 567c7063 d38b0595 9c12ec06 x': 0x204d9ac 05ffbfeb ac60c8f3 e4143831 567c7063 d38b0595 9c12ec06
3fd7b99a b4541ece faa3f0ec 1a0a33da 0ff56d7b 45b2ca9f f8adbac4 3fd7b99a b4541ece faa3f0ec 1a0a33da 0ff56d7b 45b2ca9f f8adbac4
78790d52 dc45216b 3e272dce a7571e71 81b20335 695608a3 0ea1f83e 78790d52 dc45216b 3e272dce a7571e71 81b20335 695608a3 0ea1f83e
y': 0x09cb66a fff60c18 9da2c655 d4eccad1 5dba53e8 a3c89101 aba0838c y': 0x09cb66a fff60c18 9da2c655 d4eccad1 5dba53e8 a3c89101 aba0838c
17ad69cd 096844ba 7ec246ea 99be5c24 9aea2f05 c14385e9 c53df5fb 17ad69cd 096844ba 7ec246ea 99be5c24 9aea2f05 c14385e9 c53df5fb
63ddecfe f1067e73 5cc17763 97138d4c b2ccdfbe 45b5343e eadf6637 63ddecfe f1067e73 5cc17763 97138d4c b2ccdfbe 45b5343e eadf6637
08ae1288 aa4306db 8598a5eb 08ae1288 aa4306db 8598a5eb
h': 0x5d543a9 5414e7f1 091d5079 2876a202 cd91de45 47085aba a68a205b h': 0x5d543a9 5414e7f1 091d5079 2876a202 cd91de45 47085aba a68a205b
2e5a7ddf a628f1cb 4d9e82ef 21537e29 3a6691ae 1616ec6e 786f0c70 2e5a7ddf a628f1cb 4d9e82ef 21537e29 3a6691ae 1616ec6e 786f0c70
cf1c38e3 1c7238e5 cf1c38e3 1c7238e5
b': 4 * (u + 1) b': 4 * (u + 1)
4.3. For 256 Bits of Security 4.3. For 192 Bits of Security
(TBD)
4.4. For 256 Bits of Security
As shown in Section 3.2, it is unrealistic to achieve 256 bits of As shown in Section 3.2, it is unrealistic to achieve 256 bits of
security by BN curves since the minimum size of p becomes too large security by BN curves since the minimum size of p becomes too large
to implement. Hence, we consider BLS48 for 256 bits of security. to implement. Hence, we consider BLS48 for 256 bits of security.
A BLS48 curve with 256 bits of security is shown in which we A BLS48 curve with 256 bits of security is shown in [KIK17], which we
call BLS48-581. It is defined by a parameter t = -1 + 2^7 - 2^10 - call BLS48-581. It is defined by a parameter
2^30 -
t = -1 + 2^7 - 2^10 - 2^30 - 2^32.
For the finite field F_p, the towers of extension field F_p2, F_p4, For the finite field F_p, the towers of extension field F_p2, F_p4,
F_p8, F_p24 and F_p48 are defined by indeterminas u, v, w, z, s as F_p8, F_p24 and F_p48 are defined by indeterminates u, v, w, z, s as
follows: follows:
F_p2 = F_p[u] / (u^2 + 1) F_p2 = F_p[u] / (u^2 + 1)
F_p4 = F_p2[v] / (v^2 + u + 1) F_p4 = F_p2[v] / (v^2 + u + 1)
F_p8 = F_p4[w] / (w^2 + v) F_p8 = F_p4[w] / (w^2 + v)
F_p24 = F_p8[z] / (z^3 + w) F_p24 = F_p8[z] / (z^3 + w)
F_p48 = Fp24[s] / (s^2 + F_p48 = Fp24[s] / (s^2 + z).
The elliptic curve E and its twisted curve E' are represented by E:
y^2 = x^3 + 1 and E': y^2 = x^3 - 1 / w. A pairing e is defined by
taking G_1 as a cyclic group of order r generated by a base point BP
= (x, y) in F_p, G_2 as a cyclic group of order r generated by a
based point BP' = (x', y') in F_p8, and G_T as a subgroup of a
multiplicative group F_p48^* of order r. The size of p becomes
581-bit length. BLS48-581 is D-type.
We then give the parameters for BLS48-581 as follows. We then give the parameters for BLS48-581 as follows.
- G_1 defined over E: y^2 = x^3 + b
o p : a characteristic
o r : a prime which divides an order of G_1
o BP = (x, y) : a base point
o h : a cofactor
o b : a coefficient of E
- G_2 defined over E': y^2 = x^3 + b'
o r' : an order
o BP' = (x', y') : a base point (encoded with [IEEE-1363a-2004])
* x' = x'0 + x'1 * u + x'2 * v + x'3 * u * v + x'4 * w + x'5 *
u * w + x'6 * v * w + x'7 * u * v * w (x'0, ..., x'7 in F_p)
* y' = y'0 + y'1 * u + y'2 * v + y'3 * u * v + y'4 * w + y'5 *
u * w + y'6 * v * w + y'7 * u * v * w (y'0, ..., y'7 in F_p)
o h' : a cofactor
o b' : a coefficient of E'
p: 0x12 80f73ff3 476f3138 24e31d47 012a0056 e84f8d12 2131bb3b p: 0x12 80f73ff3 476f3138 24e31d47 012a0056 e84f8d12 2131bb3b
e6c0f1f3 975444a4 8ae43af6 e082acd9 cd30394f 4736daf6 8367a551 e6c0f1f3 975444a4 8ae43af6 e082acd9 cd30394f 4736daf6 8367a551
3170ee0a 578fdf72 1a4a48ac 3edc154e 6565912b 3170ee0a 578fdf72 1a4a48ac 3edc154e 6565912b
r: 0x23 86f8a925 e2885e23 3a9ccc16 15c0d6c6 35387a3f 0b3cbe00 r: 0x23 86f8a925 e2885e23 3a9ccc16 15c0d6c6 35387a3f 0b3cbe00
3fad6bc9 72c2e6e7 41969d34 c4c92016 a85c7cd0 562303c4 ccbe5994 3fad6bc9 72c2e6e7 41969d34 c4c92016 a85c7cd0 562303c4 ccbe5994
67c24da1 18a5fe6f cd671c01 67c24da1 18a5fe6f cd671c01
x: 0x02 af59b7ac 340f2baf 2b73df1e 93f860de 3f257e0e 86868cf6 x: 0x02 af59b7ac 340f2baf 2b73df1e 93f860de 3f257e0e 86868cf6
1abdbaed ffb9f754 4550546a 9df6f964 5847665d 859236eb dbc57db3 1abdbaed ffb9f754 4550546a 9df6f964 5847665d 859236eb dbc57db3
skipping to change at page 12, line 43 skipping to change at page 16, line 38
876d1b2e 35f37aef 7b926b57 6dbb5de3 e2587a70 876d1b2e 35f37aef 7b926b57 6dbb5de3 e2587a70
h: 0x85555841 aaaec4ac h: 0x85555841 aaaec4ac
b: 1 b: 1
r': 0x23 86f8a925 e2885e23 3a9ccc16 15c0d6c6 35387a3f 0b3cbe00 r': 0x23 86f8a925 e2885e23 3a9ccc16 15c0d6c6 35387a3f 0b3cbe00
3fad6bc9 72c2e6e7 41969d34 c4c92016 a85c7cd0 562303c4 ccbe5994 3fad6bc9 72c2e6e7 41969d34 c4c92016 a85c7cd0 562303c4 ccbe5994
67c24da1 18a5fe6f cd671c01 67c24da1 18a5fe6f cd671c01
x': 0x5 d615d9a7 871e4a38 237fa45a 2775deba bbefc703 44dbccb7
de64db3a 2ef156c4 6ff79baa d1a8c422 81a63ca0 612f4005 03004d80
491f5103 17b79766 322154de c34fd0b4 ace8bfab + 0x7 c4973ece
22585120 69b0e86a bc07e8b2 2bb6d980 e1623e95 26f6da12 307f4e1c
3943a00a bfedf162 14a76aff a62504f0 c3c7630d 979630ff d75556a0
1afa143f 1669b366 76b47c57 * u + 0x1 fccc7019 8f1334e1 b2ea1853
ad83bc73 a8a6ca9a e237ca7a 6d6957cc bab5ab68 60161c1d bd19242f
fae766f0 d2a6d55f 028cbdfb b879d5fe a8ef4cde d6b3f0b4 6488156c
a55a3e6a * v + 0xb e2218c25 ceb6185c 78d80129 54d4bfe8 f5985ac6
2f3e5821 b7b92a39 3f8be0cc 218a95f6 3e1c776e 6ec143b1 b279b946
8c31c525 7c200ca5 2310b8cb 4e80bc3f 09a7033c bb7feafe * u * v +
0x3 8b91c600 b35913a3 c598e4ca a9dd6300 7c675d0b 1642b567 5ff0e7c5
80538669 9981f9e4 8199d5ac 10b2ef49 2ae58927 4fad55fc 1889aa80
c65b5f74 6c9d4cbb 739c3a1c 53f8cce5 * w + 0xc 96c7797e b0738603
f1311e4e cda088f7 b8f35dce f0977a3d 1a58677b b0374181 81df6383
5d28997e b57b40b9 c0b15dd7 595a9f17 7612f097 fc796091 0fce3370
f2004d91 4a3c093a * u * w + 0xb 9b7951c6 061ee3f0 197a4989
08aee660 dea41b39 d13852b6 db908ba2 c0b7a449 cef11f29 3b13ced0
fd0caa5e fcf3432a ad1cbe43 24c22d63 334b5b0e 205c3354 e41607e6
0750e057 * v * w + 0x8 27d5c22f b2bdec52 82624c4f 4aaa2b1e
5d7a9def af47b521 1cf74171 9728a7f9 f8cfca93 f29cff36 4a7190b7
e2b0d458 5479bd6a ebf9fc44 e56af2fc 9e97c3f8 4e19da00 fbc6ae34 * u
* v * w
y': 0x0 eb53356c 375b5dfa 49721645 2f3024b9 18b42380 59a577e6
f3b39ebf c435faab 0906235a fa27748d 90f7336d 8ae5163c 1599abf7
7eea6d65 9045012a b12c0ff3 23edd3fe 4d2d7971 + 0x2 84dc7597
9e0ff144 da653181 5fcadc2b 75a422ba 325e6fba 01d72964 732fcbf3
afb096b2 43b1f192 c5c3d189 2ab24e1d d212fa09 7d760e2e 588b4235
25ffc7b1 11471db9 36cd5665 * u + 0xb 36a201dd 008523e4 21efb703
67669ef2 c2fc5030 216d5b11 9d3a480d 37051447 5f7d5c99 d0e90411
515536ca 3295e5e2 f0c1d35d 51a65226 9cbc7c46 fc3b8fde 68332a52
6a2a8474 * v + 0xa ec25a462 1edc0688 223fbbd4 78762b1c 2cded336
0dcee23d d8b0e710 e122d274 2c89b224 333fa40d ced28177 42770ba1
0d67bda5 03ee5e57 8fb3d8b8 a1e53373 16213da9 2841589d * u * v +
0xd 209d5a22 3a9c4691 6503fa5a 88325a25 54dc541b 43dd93b5 a959805f
1129857e d85c77fa 238cdce8 a1e2ca4e 512b64f5 9f430135 945d137b
08857fdd dfcf7a43 f47831f9 82e50137 * w + 0x7 d0d03745 736b7a51
3d339d5a d537b904 21ad66eb 16722b58 9d82e205 5ab7504f a83420e8
c270841f 6824f47c 180d139e 3aafc198 caa72b67 9da59ed8 226cf3a5
94eedc58 cf90bee4 * u * w + 0x8 96767811 be65ea25 c2d05dfd
d17af8a0 06f364fc 0841b064 155f14e4 c819a6df 98f425ae 3a2864f2
2c1fab8c 74b2618b 5bb40fa6 39f53dcc c9e88401 7d9aa62b 3d41faea
feb23986 * v * w + 0x3 5e2524ff 89029d39 3a5c07e8 4f981b5e
068f1406 be8e50c8 7549b6ef 8eca9a95 33a3f8e6 9c31e97e 1ad0333e
c7192054 17300d8c 4ab33f74 8e5ac66e 84069c55 d667ffcb 732718b6 * u
* v * w
x': 0x01 690ae060 61530e31 64040ce6 e7466974 a0865edb 6d5b825d x': 0x01 690ae060 61530e31 64040ce6 e7466974 a0865edb 6d5b825d
f11e5db6 b724681c 2b5a805a f2c7c45f 60300c3c 4238a1f5 f6d3b644 f11e5db6 b724681c 2b5a805a f2c7c45f 60300c3c 4238a1f5 f6d3b644
29f5b655 a4709a8b ddf790ec 477b5fb1 ed4a0156 dec43f7f 6c401164 29f5b655 a4709a8b ddf790ec 477b5fb1 ed4a0156 dec43f7f 6c401164
da6b6f9a f79b9fc2 c0e09d2c d4b65900 d2394b61 aa3bb48c 7c731a14 da6b6f9a f79b9fc2 c0e09d2c d4b65900 d2394b61 aa3bb48c 7c731a14
68de0a17 346e34e1 7d58d870 7f845fac e35202bb 9d64b5ef f29cbfc8 68de0a17 346e34e1 7d58d870 7f845fac e35202bb 9d64b5ef f29cbfc8
5f5c6d60 1d794c87 96c20e67 81dffed3 36fc1ff6 d3ae3193 dec00603 5f5c6d60 1d794c87 96c20e67 81dffed3 36fc1ff6 d3ae3193 dec00603
91acb681 1f1fbde3 8027a0ef 591e6b21 c6e31c5f 1fda66eb 05582b6b 91acb681 1f1fbde3 8027a0ef 591e6b21 c6e31c5f 1fda66eb 05582b6b
0399c6a2 459cb2ab fd0d5d95 3447a927 86e194b2 89588e63 ef1b8b61 0399c6a2 459cb2ab fd0d5d95 3447a927 86e194b2 89588e63 ef1b8b61
ad354bed 299b5a49 7c549d7a 56a74879 b7665a70 42fbcaf1 190d915f ad354bed 299b5a49 7c549d7a 56a74879 b7665a70 42fbcaf1 190d915f
945fef6c 0fcec14b 4afc403f 50774720 4d810c57 00de1692 6309352f 945fef6c 0fcec14b 4afc403f 50774720 4d810c57 00de1692 6309352f
skipping to change at page 14, line 16 skipping to change at page 19, line 12
a1b695f9 54af10e9 a78e40ac ffc13b06 540aae9d a5287fc4 429485d4 a1b695f9 54af10e9 a78e40ac ffc13b06 540aae9d a5287fc4 429485d4
4e6289d8 c0d6a3eb 2ece3501 24527518 39fb48bc 14b51547 8e2ff412 4e6289d8 c0d6a3eb 2ece3501 24527518 39fb48bc 14b51547 8e2ff412
d930ac20 307561f3 a5c998e6 bcbfebd9 7effc643 3033a236 1bfcdc4f d930ac20 307561f3 a5c998e6 bcbfebd9 7effc643 3033a236 1bfcdc4f
b': -1 / w b': -1 / w
5. Implementations of Pairing-Friendly Curves 5. Implementations of Pairing-Friendly Curves
We show the pairing-friendly curves selected by existing standards, We show the pairing-friendly curves selected by existing standards,
s. cryptographic libraries and applications.
ISO/IEC 15946-5 shows examples of BN curves with the size of ISO/IEC 15946-5 [ISOIEC15946-5] shows examples of BN curves with the
160, 192, 224, 256, 384 and 512 bits of p. There is no action so far size of 160, 192, 224, 256, 384 and 512 bits of p. There is no
after the proposal of exTNFS. action so far after the proposal of exTNFS.
TCG adopts an BN curve of 256 bits specified in ISO/IEC 15946-5 TCG adopts an BN curve of 256 bits specified in ISO/IEC 15946-5
(TPM_ECC_BN_P256) and of 638 bits specified by their own (TPM_ECC_BN_P256) and that of 638 bits specified by their own
(TPM_ECC_BN_P638). FIDO Alliance and W3C adopt the BN (TPM_ECC_BN_P638). FIDO Alliance [FIDO] and W3C [W3C] adopt the same
curves TCG, a 512-bit BN curve shown in ISO/IEC 15946-5 BN curves as TCG, a 512-bit BN curve shown in ISO/IEC 15946-5 and
and another 256-bit BN curve. another 256-bit BN curve.
and Cryptographic libraries which implement pairings include PBC [PBC],
mcl [mcl], RELIC [RELIC], TEPLA [TEPLA], AMCL [AMCL], Intel IPP
[Intel-IPP] and a library by Kyushu University [BLS48].
Cloudflare published a new cryptographic library CIRCL (Cloudflare
a new Interoperable, Reusable Cryptographic Library) in 2019 [CIRCL]. The
implementation plan for the implementation of secure pairing-friendly curves is
implements a BN curve MIRACL implements BN curves and BLS12 curves [MIRACL].
Zcash implements a BN curve (named BN128) in their library libsnark
[libsnark]. After exTNFS, they propose a new parameter of BLS12 as
BLS12-381 [BLS12-381] and publish its experimental implementation
[zkcrypto].
Ethereum 2.0 adopts BLS12-381 (BLS12_381), BN curves with 254 bits of Ethereum 2.0 adopts BLS12-381 (BLS12_381), BN curves with 254 bits of
p (CurveFp254BNb) and 382 bits of p (CurveFp382_1 and CurveFp382_2) p (CurveFp254BNb) and 382 bits of p (CurveFp382_1 and CurveFp382_2)
Their implementation calls mcl for pairing computation. [go-bls]. Their implementation calls mcl [mcl] for pairing
Chia Network publishs their implementation by integrating the computation. Chia Network publishs their implementation [Chia] by
RELIC toolkit integrating the RELIC toolkit [RELIC].
Table 1 shows the adoption of pairing-friendly curves in existing Table 1 shows the adoption of pairing-friendly curves in existing
standards, and In this table, the curves standards, cryptographic libraries and applications. In this table,
marked as (*) indicate that the the curves marked as (*) indicate that the security level is
security the evaluated less than the one labeld in the table.
+------------+--------------+-----------------------+-------+-------+
| Name | 100 bit | 128 bit | | | Name | 100 bit | 128 bit | 192 | 256 |
| | | | | bit | | | | | bit | bit |
+------------+--------------+-----------------------+-------+-------+
| | ISO/IEC | BN256 | BN384 | | | ISO/IEC | BN256 | BN384 | | |
| | 15946-5 | | | | | 15946-5 | | | | |
| | | | | | | | | | | |
| | TCG | BN256 | | | | TCG | BN256 | | | |
| | | | | | | | | | | |
| | FIDO/W3C | BN256 | | | | FIDO/W3C | BN256 | | | |
| | | | | | | | | | | |
| | | | | | | PBC | BN | | | |
| | | | | | | | | | | |
| | | | | | | mcl | BN254 / | BN381_1 (*) / BN462 / | | |
| | | | | | | | BN_SNARK1 | BLS12-381 | | |
| | | | | | | | | | | |
| | | | | | | RELIC | BN254 / | BLS12-381 / BLS12-455 | | |
| | | | | | | | BN256 | | | |
| | | | | | | | | | | |
| | | | | | | TEPLA | BN254 | | | |
| | | | | | | | | | | |
| | | | BLS12-381 (*) | | | AMCL | BN254 / | BLS12-381 (*) / | | BLS48 |
| | | | | | | | BN256 | BLS12-383 (*) / | | |
| | | | | | | | | BLS12-461 | | |
| | | | | | | | | | | |
| | | | | | | Intel IPP | BN256 | | | |
| | | | | | | | | | | |
| | | | | | | Kyushu | | | | BLS48 |
| | | | | | | Univ. | | | | |
| | | | | | | | | | | |
| | | BN254 | | | | MIRACL | BN254 | BLS12 | | |
| | | | | | | | | | | |
| | | | | | | Zcash | BN128 | BLS12-381 | | |
| | | | | | | | (CurveSNARK) | | | |
| | | | | | | | | | | |
| | | BN254 | (*) | Ethereum | BN254 | BN382 (*) / BLS12-381 | | |
/ | | | | | (*) | | |
| | | | (*) | | | | | |
| Chia | | BLS12-381 (*) | | |
| Network | | | | |
| | | +------------+--------------+-----------------------+-------+-------+
| | | | | |
| | | | | |
| | | | | |
Table 1: Adoption of Pairing-Friendly Curves Table 1: Adoption of Pairing-Friendly Curves
6. Security Considerations 6. Security Considerations
This memo entirely describes the security of pairing-friendly curves, This memo entirely describes the security of pairing-friendly curves,
and introduces secure parameters of pairing-friendly curves. We give and introduces secure parameters of pairing-friendly curves. We give
these parameters in terms of security, efficiency and global these parameters in terms of security, efficiency and global
acceptance. The parameters for 100, and 256 bits of security are acceptance. The parameters for 100, 128, 192 and 256 bits of
introduced since the security level will different in the security are introduced since the security level will different in
requirements of the pairing-based applications. the requirements of the pairing-based applications. Implementers can
select these parameters according to their security requirements.
7. IANA Considerations 7. IANA Considerations
This document has no actions for IANA. This document has no actions for IANA.
8. Acknowledgements 8. Acknowledgements
The authors would like to thank Akihiro Kato for his significant The authors would like to thank Akihiro Kato for his significant
contribution to the early version of this memo. contribution to the early version of this memo. The authors would
also like to acknowledge Sakae Chikara, Hoeteck Wee, Sergey Gorbunov
and Michael Scott for their valuable comments.
9. References 9. References
9.1. Normative References 9.1. Normative References
for [BD18] Barbulescu, R. and S. Duquesne, "Updating Key Size
Estimations for Pairings", Journal of Cryptology,
DOI 10.1007/s00145-018-9280-5, January 2018.
Pairings",
of
DOI
[ Barreto, P., Lynn, B., and M. Scott, "Constructing [BLS02] Barreto, P., Lynn, B., and M. Scott, "Constructing
Elliptic Curves with Prescribed Embedding Degrees", Elliptic Curves with Prescribed Embedding Degrees",
Security in Communication Networks pp. 257-267, Security in Communication Networks pp. 257-267,
DOI 10.1007/3-540-36413-7_19, 2003. DOI 10.1007/3-540-36413-7_19, 2003.
Kim, T. and R. Barbulescu, "Extended Tower Number Field [BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic
Curves of Prime Order", Selected Areas in Cryptography pp.
319-331, DOI 10.1007/11693383_22, 2006.
[KB16] Kim, T. and R. Barbulescu, "Extended Tower Number Field
Sieve: A New Complexity for the Medium Prime Case", Sieve: A New Complexity for the Medium Prime Case",
Advances in Cryptology - CRYPTO 2016 pp. 543-571, Advances in Cryptology - CRYPTO 2016 pp. 543-571,
DOI 10.1007/978-3-662-53018-4_20, 2016. DOI 10.1007/978-3-662-53018-4_20, 2016.
and [KIK17] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi,
T., and T. Kobayashi, "Secure and Efficient Pairing at
DOI 256-Bit Security Level", Applied Cryptography and Network
Security pp. 59-79, DOI 10.1007/978-3-319-61204-1_4, 2017.
[ Menezes, A., Sarkar, P., and S. Singh, "Challenges with [MSS17] Menezes, A., Sarkar, P., and S. Singh, "Challenges with
Assessing the Impact of NFS Advances on the Security of Assessing the Impact of NFS Advances on the Security of
Pairing-Based Cryptography", Lecture Notes in Computer Pairing-Based Cryptography", Lecture Notes in Computer
Science pp. 83-108, DOI 10.1007/978-3-319-61273-7_5, 2017. Science pp. 83-108, DOI 10.1007/978-3-319-61273-7_5, 2017.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
DOI <https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[Ver09] Vercauteren, F., "Optimal Pairings", IEEE Transactions on
Information Theory Vol. 56, pp. 455-461,
DOI 10.1109/tit.2009.2034881, January 2010.
DOI
9.2. Informative References
and [Algorand]
Gorbunov, S., "Efficient and Secure Digital Signatures for
Proof-of-Stake Blockchains", <https://medium.com/algorand/
digital-signatures-for-blockchains-5820e15fbe95>.
[AMCL] The Apache Software Foundation, "The Apache Milagro
Cryptographic Library (AMCL)", 2016,
<https://github.com/apache/incubator-milagro-crypto>.
[BL10] Brickell, E. and J. Li, "Enhanced Privacy ID from Bilinear
Pairing for Hardware Authentication and Attestation", 2010
IEEE Second International Conference on Social Computing,
DOI 10.1109/socialcom.2010.118, August 2010.
[BLS12-381]
Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve
Construction",
<https://electriccoin.co/blog/new-snark-curve/>.
for [BLS48] Kyushu University, "bls48 - C++ library for Optimal Ate
Pairing on BLS48", 2017,
<https://github.com/mk-math-kyushu/bls48>.
[ Chen, L., Cheng, Z., and N. Smart, "Identity-based key [CCS07] Chen, L., Cheng, Z., and N. Smart, "Identity-based key
agreement protocols from pairings", International Journal agreement protocols from pairings", International Journal
of Information Security Vol. 6, pp. 213-241, of Information Security Vol. 6, pp. 213-241,
DOI 10.1007/s10207-006-0011-9, January 2007. DOI 10.1007/s10207-006-0011-9, January 2007.
[Chia] Chia Network, "BLS signatures in C++, using the relic
toolkit",
in <https://github.com/Chia-Network/bls-signatures>.
[CIRCL] Cloudflare, "CIRCL: Cloudflare Interoperable, Reusable
Cryptographic Library", 2019,
<https://github.com/cloudflare/circl>.
Sullivan, N., "Geo Key Manager: How It Works", [Cloudflare]
Sullivan, N., "Geo Key Manager: How It Works",
<https://blog.cloudflare.com/ <https://blog.cloudflare.com/
geo-key-manager-how-it-works/>. geo-key-manager-how-it-works/>.
D., [DFINITY] Williams, D., "DFINITY Technology Overview Series
Consensus System Rev. 1", n.d., <https://dfinity.org/pdf-
viewer/library/dfinity-consensus.pdf>.
Jordan, R., "Ethereum 2.0 Development Update #17 - [ECRYPT] ECRYPT, "Final Report on Main Computational Assumptions in
Cryptography".
[EPID] Intel Corporation, "Intel (R) SGX: Intel (R) EPID
Provisioning and Attestation Services",
intel-epid-provisioning-and-attestation-services>.
[Ethereum]
Jordan, R., "Ethereum 2.0 Development Update #17 -
Prysmatic Labs", <https://medium.com/prysmatic-labs/ Prysmatic Labs", <https://medium.com/prysmatic-labs/
ethereum-2-0-development-update-17-prysmatic-labs- ethereum-2-0-development-update-17-prysmatic-labs-
ed5bcf82ec00>. ed5bcf82ec00>.
[FIDO] Lindemann, R., "FIDO ECDAA Algorithm - FIDO Alliance
Review Draft 02", <https://fidoalliance.org/specs/
fido-v2.0-rd-20180702/
fido-ecdaa-algorithm-v2.0-rd-20180702.html>.
-
in [FSU10] Fujioka, A., Suzuki, K., and B. Ustaoglu, "Ephemeral Key
Leakage Resilient and Efficient ID-AKEs That Can Share
Identities, Private and Master Keys", Lecture Notes in
Computer Science pp. 187-205,
DOI 10.1007/978-3-642-17455-1_12, 2010.
for [go-bls] Prysmatic Labs, "go-bls - Go wrapper for a BLS12-381
Signature Aggregation implementation in C++", 2018,
<https://godoc.org/github.com/prysmaticlabs/go-bls>.
[ Hellman, M. and J. Reyneri, "Fast Computation of Discrete [HR83] Hellman, M. and J. Reyneri, "Fast Computation of Discrete
Logarithms in GF (q)", Advances in Cryptology pp. 3-13, Logarithms in GF (q)", Advances in Cryptology pp. 3-13,
DOI 10.1007/978-1-4757-0602-4_1, 1983. DOI 10.1007/978-1-4757-0602-4_1, 1983.
[I-D.boneh-bls-signature]
and in Boneh, D., Gorbunov, S., Wee, H., and Z. Zhang, "BLS
Signature Scheme", draft-boneh-bls-signature-00 (work in
progress), February 2019.
[IEEE-1363a-2004]
DOI "IEEE Standard Specifications for Public-Key Cryptography
- Amendment 1: Additional Techniques", IEEE standard,
DOI 10.1109/ieeestd.2004.94612, n.d..
[Intel-IPP]
Intel Corporation, "Developer Reference for Intel
Integrated Performance Primitives Cryptography 2019",
2018, <https://software.intel.com/en-us/ipp-crypto-
reference-arithmetic-of-the-group-of-elliptic-curve-
points>.
[ISOIEC11770-3]
ISO/IEC, "ISO/IEC 11770-3:2015", ISO/IEC Information
technology -- Security techniques -- Key management --
Part 3: Mechanisms using asymmetric techniques, 2015.
ISO/IEC, "ISO/IEC 15946-5:2017", ISO/IEC Information [ISOIEC15946-5]
ISO/IEC, "ISO/IEC 15946-5:2017", ISO/IEC Information
technology -- Security techniques -- Cryptographic technology -- Security techniques -- Cryptographic
techniques based on elliptic curves -- Part 5: Elliptic techniques based on elliptic curves -- Part 5: Elliptic
curve generation, 2017. curve generation, 2017.
[Joux00] Joux, A., "A One Round Protocol for Tripartite Diffie-
Hellman", Lecture Notes in Computer Science pp. 385-393,
DOI 10.1007/10722028_23, 2000.
SCIPR Lab, "libsnark: a C++ library for zkSNARK proofs", [libsnark]
SCIPR Lab, "libsnark: a C++ library for zkSNARK proofs",
2012, <https://github.com/zcash/libsnark>. 2012, <https://github.com/zcash/libsnark>.
[M-Pin] Scott, M., "M-Pin: A Multi-Factor Zero Knowledge
Authentication Protocol", July 2019,
<https://www.miracl.com/miracl-labs/m-pin-a-multi-factor-
zero-knowledge-authentication-protocol>.
[mcl] Mitsunari, S., "mcl - A portable and fast pairing-based
cryptography library", 2016,
<https://github.com/herumi/mcl>.
[MIRACL] MIRACL Ltd., "MIRACL Cryptographic SDK", 2018,
2018, <https://github.com/miracl/MIRACL>.
Lynn, B., "PBC Library - The Pairing-Based Cryptography [NCCG] NCC Group, "Zcash Overwinter Consensus and Sapling
Cryptography Review", <https://www.nccgroup.trust/us/our-
research/zcash-overwinter-consensus-and-sapling-
cryptography-review/>.
[PBC] Lynn, B., "PBC Library - The Pairing-Based Cryptography
Library", 2006, <https://crypto.stanford.edu/pbc/>. Library", 2006, <https://crypto.stanford.edu/pbc/>.
C., "RELIC is an Efficient LIbrary for [Pollard78]
Pollard, J., "Monte Carlo methods for index computation
$({\rm mod}\ p)$", Mathematics of Computation Vol. 32, pp.
918-918, DOI 10.1090/s0025-5718-1978-0491431-9, September
1978.
[RELIC] Gouvea, C., "RELIC is an Efficient LIbrary for
Cryptography", 2013, Cryptography", 2013,
<https://>. <https://github.com/relic-toolkit/relic>.
University of Tsukuba, "TEPLA: University of Tsukuba [RFC5091] Boyen, X. and L. Martin, "Identity-Based Cryptography
Standard (IBCS) #1: Supersingular Curve Implementations of
the BF and BB1 Cryptosystems", RFC 5091,
DOI 10.17487/RFC5091, December 2007,
<https://www.rfc-editor.org/info/rfc5091>.
[RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)",
RFC 6508, DOI 10.17487/RFC6508, February 2012,
<https://www.rfc-editor.org/info/rfc6508>.
[RFC6509] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key Encryption in
Multimedia Internet KEYing (MIKEY)", RFC 6509,
DOI 10.17487/RFC6509, February 2012,
<https://www.rfc-editor.org/info/rfc6509>.
[RFC6539] Cakulev, V., Sundaram, G., and I. Broustis, "IBAKE:
Identity-Based Authenticated Key Exchange", RFC 6539,
DOI 10.17487/RFC6539, March 2012,
<https://www.rfc-editor.org/info/rfc6539>.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/info/rfc8446>.
[SAKKE] 3GPP, "Security of the mission critical service (Release
15)", 3GPP TS 33.180 15.3.0, 2018.
[TEPLA] University of Tsukuba, "TEPLA: University of Tsukuba
Elliptic Curve and Pairing Library", 2013, Elliptic Curve and Pairing Library", 2013,
<http://www.cipher.risk.tsukuba.ac.jp/tepla/index_e.html>. <http://www.cipher.risk.tsukuba.ac.jp/tepla/index_e.html>.
[TPM] Trusted Computing Group (TCG), "Trusted Platform Module
Library Library Specification, Family \"2.0\", Level 00, Revision
01.38", <https://trustedcomputinggroup.org/resource/
tpm-library-specification/>.
for [W3C] Lundberg, E., "Web Authentication: An API for accessing
Public Key Credentials Level 1 - W3C Recommendation",
<https://www.w3.org/TR/webauthn/>.
- [Zcash] Lindemann, R., "What are zk-SNARKs?",
2017, <https://z.cash/technology/zksnarks.html>.
[zkcrypto]
zkcrypto, "zkcrypto - Pairing-friendly elliptic curve
library", 2017, <https://github.com/zkcrypto/pairing>.
Appendix A. Computing Optimal Ate Pairing Appendix A. Computing Optimal Ate Pairing
Before presenting the computation of optimal Ate pairing e(P, Q) Before presenting the computation of optimal Ate pairing e(P, Q)
satisfying the properties shown in Section 2.2, we give subfunctions satisfying the properties shown in Section 2.2, we give subfunctions
used for pairing computation. used for pairing computation.
The following algorithm Line_Function shows the computation of the The following algorithm Line_Function shows the computation of the
line function. It takes A = (A[1], A[2]), B = (B[1], B[2]) in G_2 line function. It takes A = (A[1], A[2]), B = (B[1], B[2]) in G_2
and P = ((P[1], P[2])) in G_1 as input and outputs an element of G_T. and P = ((P[1], P[2])) in G_1 as input and outputs an element of G_T.
if (A = B) then if (A = B) then
l := (3 * A[1]^2) / (2 * A[2]); l := (3 * A[1]^2) / (2 * A[2]);
else if (A = -B) then else if (A = -B) then
return P[1] - A[1]; return P[1] - A[1];
else else
l := (B[2] - A[2]) / (B[1] - A[1]); l := (B[2] - A[2]) / (B[1] - A[1]);
end if; end if;
return (l * (P[1] -A[1]) + A[2] -P[2]); return (l * (P[1] -A[1]) + A[2] -P[2]);
When implementing the line function, implementer should consider the When implementing the line function, implementers should consider the
isomorphism of E and its twisted curve E' so that one can reduce the isomorphism of E and its twisted curve E' so that one can reduce the
computational cost of operations in G_2. We note that the function computational cost of operations in G_2. We note that the function
Line_function does not consider such isomorphism. Line_function does not consider such isomorphism.
Computation of optimal Ate pairing for BN curves uses Frobenius map. Computation of optimal Ate pairing for BN curves uses Frobenius map.
Let a Frobenius map pi for a point Q = (x, y) over E' be pi(p, Q) = Let a Frobenius map pi for a point Q = (x, y) over E' be pi(p, Q) =
(x^p, y^p). (x^p, y^p).
A.1. Optimal Ate Pairings over Barreto-Naehrig Curves A.1. Optimal Ate Pairings over Barreto-Naehrig Curves
skipping to change at page 22, line 7 skipping to change at page 27, line 34
end if end if
end for end for
Q_1 := pi(p, Q); Q_2 := pi(p, Q_1); Q_1 := pi(p, Q); Q_2 := pi(p, Q_1);
f := f * Line_function(T, Q_1, P); T := T + Q_1; f := f * Line_function(T, Q_1, P); T := T + Q_1;
f := f * Line_function(T, -Q_2, P); f := f * Line_function(T, -Q_2, P);
f := f^{(p^k - 1) / r} f := f^{(p^k - 1) / r}
return f; return f;
A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves
Let s = t for a parameter and s_0, s_1, ... , s_L in {-1,0,1} Let s = t for a parameter t and s_0, s_1, ... , s_L in {-1,0,1} such
such that the sum of s_i * 2^i (i = 0, that the sum of s_i * 2^i (i = 0, 1, ..., L) equals to s. The
1, ..., L) equals to s. The following algorithm shows the following algorithm shows the computation of optimal Ate pairing over
computation of optimal Ate pairing over Barreto-Lynn-Scott curves. Barreto-Lynn-Scott curves. It takes P in G_1, Q in G_2, a parameter
It takes P in G_1, Q in G_2, a parameter s, s_0, s_1, ..., s_L in s, s_0, s_1, ..., s_L in {-1,0,1} such that the sum of s_i * 2^i (i =
{-1,0,1} such that the sum of s_i * 2^i (i = 0, 1, ..., L), and an 0, 1, ..., L), and an order r as input, and outputs e(P, Q).
order r as input, and outputs e(P, Q).
f := 1; T := Q; f := 1; T := Q;
if (s_L = -1) if (s_L = -1)
T := -T; T := -T;
end if end if
for i = L-1 to 0 for i = L-1 to 0
f := f^2 * Line_function(T, T, P); T := 2 * T; f := f^2 * Line_function(T, T, P); T := 2 * T;
if (s_i = 1 | s_i = -1) if (s_i = 1 | s_i = -1)
f := f * Line_function(T, s_i * Q, P); T := T + s_i * Q; f := f * Line_function(T, s_i * Q, P); T := T + s_i * Q;
end if end if
end for end for
f := f^{(p^k - 1) / r}; f := f^{(p^k - 1) / r};
return f; return f;
Appendix B. Test Vectors of Optimal Ate Pairing Appendix B. Test Vectors of Optimal Ate Pairing
We provide test vectors for Optimal Ate Pairing e(P, Q) given in We provide test vectors for Optimal Ate Pairing e(P, Q) given in
Appendix A for the curves BN462, BLS12-381 and BLS48-581 given in Appendix A for the curves BN462, BLS12-381 and BLS48-581 given in
Section 4. Here, the inputs P = (x, y) and Q = (x', y') are the Section 4. Here, the inputs P = (x, y) and Q = (x', y') are the
corresponding base points and given in corresponding base points BP and BP' given in Section 4.
For BN462 and BLS12-381, Q = (x', y') is given by
x' = x'0 + x'1 * u and
y' = y'0 + y'1 * u,
where u is a indeterminate and x'0, x'1, y'0, y'1 are elements of
F_p.
For BLS48-581, Q = (x', y') is given by
x' = x'0 + x'1 * u + x'2 * v + x'3 * u * v
+ x'4 * w + x'5 * u * w + x'6 * v * w + x'7 * u * v * w and
y' = y'0 + y'1 * u + y'2 * v + y'3 * u * v
+ y'4 * w + y'5 * u * w + y'6 * v * w + y'7 * u * v * w,
where u, v and w are indeterminates and x'0, ..., x'7 and y'0, ...,
y'7 are elements of F_p. The representation of Q = (x', y') given
below is followed by [IEEE-1363a-2004].
BN462: BN462:
Input x value: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f Input x value: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f
9774b905 a14e3a3f 171bac58 6c55e83f f97a1aef fb3af00a db22c6bb 9774b905 a14e3a3f 171bac58 6c55e83f f97a1aef fb3af00a db22c6bb
Input y value: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095 Input y value: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095
d5d00af6 00db18cb 2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1 d5d00af6 00db18cb 2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1
Input x'0 value: 0x0257 ccc85b58 dda0dfb3 8e3a8cbd c5482e03 37e7c1cd
468e3d93 4ae1e4df
Input x'1 value: 0x1d2e 4343e859 9102af8e dca84956 6ba3c98e 2a354730
cbed9176 884058b1 8134dd86 bae555b7 83718f50 af8b59bf 7e850e9b
73108ba6 aa8cd283
Input y'0 value: 0x0a06 50439da2 2c197951 7427a208 09eca035 634706e2
3c3fa7a6 bb42fe81 0f1399a1 f41c9dda e32e0369 5a140e7b 11d7c337
6e5b68df 0db7154e
Input y'1 value: 0x073e f0cbd438 cbe0172c 8ae37306 324d44d5 e6b0c69a
c57b393f 1ab370fd 725cc647 692444a0 4ef87387 aa68d537 43493b9e
ba14cc55 2ca2a93a
Input x' value: 0x041b04cb e3413297 c49d8129 7eed0759 47d86135 Input x' value: 0x041b04cb e3413297 c49d8129 7eed0759 47d86135
c4abf0be 9d5b64be 02d6ae78 34047ea4 079cd30f e28a68ba 0cb8f7b7 c4abf0be 9d5b64be 02d6ae78 34047ea4 079cd30f e28a68ba 0cb8f7b7
2836437d c75b2567 ff2b98db b93f68fa c828d822 1e4e1d89 475e2d85 2836437d c75b2567 ff2b98db b93f68fa c828d822 1e4e1d89 475e2d85
f2063cbc 4a74f6f6 6268b6e6 da1162ee 055365bb 30283bde 614a17f6 f2063cbc 4a74f6f6 6268b6e6 da1162ee 055365bb 30283bde 614a17f6
1a255d68 82417164 bc500498 1a255d68 82417164 bc500498
Input y' value: 0x0104fa79 6cbc2989 0f9a3798 2c353da1 3b299391 Input y' value: 0x0104fa79 6cbc2989 0f9a3798 2c353da1 3b299391
be45ddb1 c15ca42a bdf8bf50 2a5dd7ac 0a3d351a 859980e8 9be676d0 be45ddb1 c15ca42a bdf8bf50 2a5dd7ac 0a3d351a 859980e8 9be676d0
0e92c128 714d6f3c 6aba56ca 6e0fc6a5 468c12d4 2762b29d 840f13ce 0e92c128 714d6f3c 6aba56ca 6e0fc6a5 468c12d4 2762b29d 840f13ce
5c3323ff 016233ec 7d76d4a8 12e25bbe b2c25024 3f2cbd27 80527ec5 5c3323ff 016233ec 7d76d4a8 12e25bbe b2c25024 3f2cbd27 80527ec5
skipping to change at page 23, line 41 skipping to change at page 30, line 8
2560ddcc ad362cb9 02f79d7f 1210ddac 950bf406 d0f0c79f 299bcebd 2560ddcc ad362cb9 02f79d7f 1210ddac 950bf406 d0f0c79f 299bcebd
BLS12-381: BLS12-381:
Input x value: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f Input x value: 0x17f1d3a7 3197d794 2695638c 4fa9ac0f c3688c4f
9774b905 a14e3a3f 171bac58 6c55e83f f97a1aef fb3af00a db22c6bb 9774b905 a14e3a3f 171bac58 6c55e83f f97a1aef fb3af00a db22c6bb
Input y value: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095 Input y value: 0x08b3f481 e3aaa0f1 a09e30ed 741d8ae4 fcf5e095
d5d00af6 00db18cb 2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1 d5d00af6 00db18cb 2c04b3ed d03cc744 a2888ae4 0caa2329 46c5e7e1
Input x'0 value: 0x24aa2b2 f08f0a91 26080527 2dc51051 c6e47ad4
fa403b02 b4510b64 7ae3d177 0bac0326 a805bbef d48056c8 c121bdb8
Input x'1 value: 0x13e02b60 52719f60 7dacd3a0 88274f65 596bd0d0
9920b61a b5da61bb dc7f5049 334cf112 13945d57 e5ac7d05 5d042b7e
Input y'0 value: 0xce5d527 727d6e11 8cc9cdc6 da2e351a adfd9baa
8cbdd3a7 6d429a69 5160d12c 923ac9cc 3baca289 e1935486 08b82801
Input y'1 value: 0x606c4a0 2ea734cc 32acd2b0 2bc28b99 cb3e287e
85a763af 267492ab 572e99ab 3f370d27 5cec1da1 aaa9075f f05f79be
Input x' value: 0x204d9ac 05ffbfeb ac60c8f3 e4143831 567c7063 Input x' value: 0x204d9ac 05ffbfeb ac60c8f3 e4143831 567c7063
d38b0595 9c12ec06 3fd7b99a b4541ece faa3f0ec 1a0a33da 0ff56d7b d38b0595 9c12ec06 3fd7b99a b4541ece faa3f0ec 1a0a33da 0ff56d7b
45b2ca9f f8adbac4 78790d52 dc45216b 3e272dce a7571e71 81b20335 45b2ca9f f8adbac4 78790d52 dc45216b 3e272dce a7571e71 81b20335
Input y' value: 0x09cb66a fff60c18 9da2c655 d4eccad1 5dba53e8 Input y' value: 0x09cb66a fff60c18 9da2c655 d4eccad1 5dba53e8
a3c89101 aba0838c 17ad69cd 096844ba 7ec246ea 99be5c24 9aea2f05 a3c89101 aba0838c 17ad69cd 096844ba 7ec246ea 99be5c24 9aea2f05
c14385e9 c53df5fb 63ddecfe f1067e73 5cc17763 97138d4c b2ccdfbe c14385e9 c53df5fb 63ddecfe f1067e73 5cc17763 97138d4c b2ccdfbe
skipping to change at page 24, line 37 skipping to change at page 31, line 13
BLS48-581: BLS48-581:
Input x value: 0x02 af59b7ac 340f2baf 2b73df1e 93f860de 3f257e0e Input x value: 0x02 af59b7ac 340f2baf 2b73df1e 93f860de 3f257e0e
86868cf6 1abdbaed ffb9f754 4550546a 9df6f964 5847665d 859236eb 86868cf6 1abdbaed ffb9f754 4550546a 9df6f964 5847665d 859236eb
dbc57db3 68b11786 cb74da5d 3a1e6d8c 3bce8732 315af640 dbc57db3 68b11786 cb74da5d 3a1e6d8c 3bce8732 315af640
Input y value: 0x0c efda44f6 531f91f8 6b3a2d1f b398a488 a553c9ef Input y value: 0x0c efda44f6 531f91f8 6b3a2d1f b398a488 a553c9ef
eb8a52e9 91279dd4 1b720ef7 bb7beffb 98aee53e 80f67858 4c3ef22f eb8a52e9 91279dd4 1b720ef7 bb7beffb 98aee53e 80f67858 4c3ef22f
487f77c2 876d1b2e 35f37aef 7b926b57 6dbb5de3 e2587a70 487f77c2 876d1b2e 35f37aef 7b926b57 6dbb5de3 e2587a70
Input x' value: 0x5 d615d9a7 871e4a38 237fa45a 2775deba bbefc703
44dbccb7 de64db3a 2ef156c4 6ff79baa d1a8c422 81a63ca0 612f4005
03004d80 491f5103 17b79766 322154de c34fd0b4 ace8bfab + 0x7
c4973ece 22585120 69b0e86a bc07e8b2 2bb6d980 e1623e95 26f6da12
307f4e1c 3943a00a bfedf162 14a76aff a62504f0 c3c7630d 979630ff
d75556a0 1afa143f 1669b366 76b47c57 * u + 0x1 fccc7019 8f1334e1
b2ea1853 ad83bc73 a8a6ca9a e237ca7a 6d6957cc bab5ab68 60161c1d
bd19242f fae766f0 d2a6d55f 028cbdfb b879d5fe a8ef4cde d6b3f0b4
6488156c a55a3e6a * v + 0xb e2218c25 ceb6185c 78d80129 54d4bfe8
f5985ac6 2f3e5821 b7b92a39 3f8be0cc 218a95f6 3e1c776e 6ec143b1
b279b946 8c31c525 7c200ca5 2310b8cb 4e80bc3f 09a7033c bb7feafe * u
* v + 0x3 8b91c600 b35913a3 c598e4ca a9dd6300 7c675d0b 1642b567
5ff0e7c5 80538669 9981f9e4 8199d5ac 10b2ef49 2ae58927 4fad55fc
1889aa80 c65b5f74 6c9d4cbb 739c3a1c 53f8cce5 * w + 0xc 96c7797e
b0738603 f1311e4e cda088f7 b8f35dce f0977a3d 1a58677b b0374181
81df6383 5d28997e b57b40b9 c0b15dd7 595a9f17 7612f097 fc796091
0fce3370 f2004d91 4a3c093a * u * w + 0xb 9b7951c6 061ee3f0
197a4989 08aee660 dea41b39 d13852b6 db908ba2 c0b7a449 cef11f29
3b13ced0 fd0caa5e fcf3432a ad1cbe43 24c22d63 334b5b0e 205c3354
e41607e6 0750e057 * v * w + 0x8 27d5c22f b2bdec52 82624c4f
4aaa2b1e 5d7a9def af47b521 1cf74171 9728a7f9 f8cfca93 f29cff36
4a7190b7 e2b0d458 5479bd6a ebf9fc44 e56af2fc 9e97c3f8 4e19da00
fbc6ae34 * u * v * w
Input y' value: 0x0 eb53356c 375b5dfa 49721645 2f3024b9 18b42380
59a577e6 f3b39ebf c435faab 0906235a fa27748d 90f7336d 8ae5163c
1599abf7 7eea6d65 9045012a b12c0ff3 23edd3fe 4d2d7971 + 0x2
84dc7597 9e0ff144 da653181 5fcadc2b 75a422ba 325e6fba 01d72964
732fcbf3 afb096b2 43b1f192 c5c3d189 2ab24e1d d212fa09 7d760e2e
588b4235 25ffc7b1 11471db9 36cd5665 * u + 0xb 36a201dd 008523e4
21efb703 67669ef2 c2fc5030 216d5b11 9d3a480d 37051447 5f7d5c99
d0e90411 515536ca 3295e5e2 f0c1d35d 51a65226 9cbc7c46 fc3b8fde
68332a52 6a2a8474 * v + 0xa ec25a462 1edc0688 223fbbd4 78762b1c
2cded336 0dcee23d d8b0e710 e122d274 2c89b224 333fa40d ced28177
42770ba1 0d67bda5 03ee5e57 8fb3d8b8 a1e53373 16213da9 2841589d * u
* v + 0xd 209d5a22 3a9c4691 6503fa5a 88325a25 54dc541b 43dd93b5
a959805f 1129857e d85c77fa 238cdce8 a1e2ca4e 512b64f5 9f430135
945d137b 08857fdd dfcf7a43 f47831f9 82e50137 * w + 0x7 d0d03745
736b7a51 3d339d5a d537b904 21ad66eb 16722b58 9d82e205 5ab7504f
a83420e8 c270841f 6824f47c 180d139e 3aafc198 caa72b67 9da59ed8
226cf3a5 94eedc58 cf90bee4 * u * w + 0x8 96767811 be65ea25
c2d05dfd d17af8a0 06f364fc 0841b064 155f14e4 c819a6df 98f425ae
3a2864f2 2c1fab8c 74b2618b 5bb40fa6 39f53dcc c9e88401 7d9aa62b
3d41faea feb23986 * v * w + 0x3 5e2524ff 89029d39 3a5c07e8
4f981b5e 068f1406 be8e50c8 7549b6ef 8eca9a95 33a3f8e6 9c31e97e
1ad0333e c7192054 17300d8c 4ab33f74 8e5ac66e 84069c55 d667ffcb
732718b6 * u * v * w
Input x' value: 0x01 690ae060 61530e31 64040ce6 e7466974 a0865edb Input x' value: 0x01 690ae060 61530e31 64040ce6 e7466974 a0865edb
6d5b825d f11e5db6 b724681c 2b5a805a f2c7c45f 60300c3c 4238a1f5 6d5b825d f11e5db6 b724681c 2b5a805a f2c7c45f 60300c3c 4238a1f5
f6d3b644 29f5b655 a4709a8b ddf790ec 477b5fb1 ed4a0156 dec43f7f f6d3b644 29f5b655 a4709a8b ddf790ec 477b5fb1 ed4a0156 dec43f7f
6c401164 da6b6f9a f79b9fc2 c0e09d2c d4b65900 d2394b61 aa3bb48c 6c401164 da6b6f9a f79b9fc2 c0e09d2c d4b65900 d2394b61 aa3bb48c
7c731a14 68de0a17 346e34e1 7d58d870 7f845fac e35202bb 9d64b5ef 7c731a14 68de0a17 346e34e1 7d58d870 7f845fac e35202bb 9d64b5ef
f29cbfc8 5f5c6d60 1d794c87 96c20e67 81dffed3 36fc1ff6 d3ae3193 f29cbfc8 5f5c6d60 1d794c87 96c20e67 81dffed3 36fc1ff6 d3ae3193
dec00603 91acb681 1f1fbde3 8027a0ef 591e6b21 c6e31c5f 1fda66eb dec00603 91acb681 1f1fbde3 8027a0ef 591e6b21 c6e31c5f 1fda66eb
05582b6b 0399c6a2 459cb2ab fd0d5d95 3447a927 86e194b2 89588e63 05582b6b 0399c6a2 459cb2ab fd0d5d95 3447a927 86e194b2 89588e63
ef1b8b61 ad354bed 299b5a49 7c549d7a 56a74879 b7665a70 42fbcaf1 ef1b8b61 ad354bed 299b5a49 7c549d7a 56a74879 b7665a70 42fbcaf1
190d915f 945fef6c 0fcec14b 4afc403f 50774720 4d810c57 00de1692 190d915f 945fef6c 0fcec14b 4afc403f 50774720 4d810c57 00de1692
skipping to change at page 28, line 21 skipping to change at page 35, line 45
fc0bc8a3 eed01024 ddffe6fc 75d8e8ee 2fc302d4 aa3f556d c16852cb fc0bc8a3 eed01024 ddffe6fc 75d8e8ee 2fc302d4 aa3f556d c16852cb
53a373a7 555b99a1 e914cbf8 55da764c 53a373a7 555b99a1 e914cbf8 55da764c