^(ab) for all P, Q elements of G_1 and G_2, respectively, and a, b elements of Z_q. 2. Non-degeneracy: There exists P, Q elements of G_1 and G_2, respectively, such that

!= 1. In other words, the map does not send all pairs in G_1 X G_2 to the identity in G_3. 3. Computability: There is an efficient algorithm to compute

for all P in G_1 and Q in G_2. In our setting of prime order groups, non-degeneracy is equivalent to

!= 1 for all nontrivial P, Q elements in G_1 and G_2, respectively. So, when P is a generator of G_1 and Q is a generator of G_2, then

is a generator of G_3. Such a bilinear map is
called a bilinear pairing.
1.2 Discrete Logarithm Problem and Diffie-Hellman Problems
We consider the following problems in the additive group (G_1;+).
Discrete Logarithm Problem (DLP): Given two group elements P and
Q, find an integer n in (Z_q)*, such that Q=nP whenever such an
integer exists.
Decision Diffie-Hellman Problem (DDHP): For a,b,c in (Z_q)*, given
P, aP, bP, cP decide whether c is congruent to ab mod q.
Computational Diffie-Hellman Problem (CDHP): For a,b in (Z_q)*,
^(abc).
The CDHP, Inv-CDHP, and Squ-CDHP are polynomial time equivalent. The
DLP, CDHP, Inv-CDHP, Squ-CDHP, and BDHP are assumed to be hard, which
means there is no polynomial time algorithm to solve any of them with
non-negligible probability. Therefore, the security of pairing based
cryptosystems are typically based on these problems. A Gap Diffie-
Hellman (GDH) group is a group in which the DDHP can be efficiently
solved but the CDHP is intractable. The bilinear pairing gives us
such a group, found on elliptic curves or hyperelliptic curves over
finite fields. The bilinear pairings can be derived from the Weil or
Tate pairing, as in [B-F, Cha-Cheon, Hess]. The ZSS scheme works on
any GDH group, but in this document we focus on a particular family
of ordinary (i.e., non-supersingular) elliptic curves, known as BN
curves, described in Section 3.4 and the pairing described in
Appendix A.2.
1.3 Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
2 Architecture
We consider the situation where one entity (the Signer) wishes to
sign a message that it is sending to another entity (the Verifier).
As in a traditional Public Key Infrastructure (PKI), a Certificate
Authority (CA) or Trusted Third Party (TTP) provides assurance of a
signer's identity, which is bound to the signer's public key. The CA
may generate a public key and private key (a key pair) or the signer
may generate their own key pair and register the Signer Public Key
(SPK) with a CA.
The mechanism by which a secret key is transported MUST be secure, as
the security of the authentication provided by ZSS signatures is no
stronger than the security of this supply channel. The choice of
secret key transport mechanism is outside the scope of this document.
. Having this pre-computed value allows the Verifier
to only perform one pairing operation to verify a signature.
H A cryptographic hash function. [FIPS180-3] contains NIST
approved hash functions.
lg(x) The base 2 logarithm of the real value x.
3.2 Definitions
Certificate Authority (CA) - The Certificate Authority is a trusted
third party who provides assurance that the SPK
belongs to the signer and verified proof of the
signer's identity when the signer registered the
SPK.
Public parameters - The public parameters are a set of parameters
that are held by all users of the system. Each
application of ZSS MUST define the set of public
parameters to be used. The parameters needed are n,
p, q, E, P, P', < , >, g, and H.
Signer Public Key (SPK) - The Signer's Public key is used to verify
the signature of the entity whose SSK corresponds to
the SPK. It is a point on the elliptic curve E.
is an element of Fp_12 given by
((36699339660626669649427399393560215125019796922092031025948063026
15, 247927466780520015848965517635750695647326440402643111951301234
2995),
(53440222253683237877269791416098727648815280997704796178179123615
5, 152660447468210228523508984531632103922262052241800765770764185
1816),
(49145419234025334524484519757289516582314844784075278041512123443,
176265594691520614080041515255534401194732308979032729979138040295
4),
(23696703075178036967923154124988633199564384190798395748600577760
85, 23618404356311472082427998195066752928773113611373491721529464
37996),
(12762283628400824508803470970369296405340301501303861200304473348
06, 13459347095597820798563091367816489138601686487822582178268889
4443),
(52536691068804792250953154403977106032469644538529906910544187717
3, 111049479509897086258622292367384411180467475476136042303440990
5476))
SSK = 2121608753564392499593333521375987220574081909435960440370410
821656
SPK = (120851890594243637869885901573990997912577177623964284017952
0609651, 5156510979532175335881708985883359220634082111209944466019
22864253)
Suppose H(m) = 6104193801232612202724894323091424875875271378342228
is an element of Fp_12 given by
((13070690801249658484759892809227642840919015841299984602661540278
97835831306, 362837632692008901334341187262873478716707643732273036
6913713646023905731503),
(352778753845190583740690941014710408681261806065247837729422038997
7928485580, 1390842049595369881149037040415050751861458203097739688
0797626940316305362787),
(148957391318235038979721383575910962973602682276093210989431526351
38088456200, 154193402372256829285477206567013233448625527219699948
30027125771243100988775),
(657015345250965363244058395947686331467494595330600581669861545909
8579995196, 9246328720071559688457720607053218330889647295590139338
238624175808225962795),
(151014665406602395528454680822744016147807484038495196740696804034
7117671512, 6964231951063075324378672955330091045708301556113455379
316967754148774004530),
(132001962407792355737177261139163922637454993559842085107451833663
5435672354, 9476335168658772594045570476784073542275866387029189317
560203959549876656582))
SSK = 228064033978937665992889984775405287134161793365057496448735949
2611
SPK = (48893896735870064320433171153400539525040538030176968340812183
01282547698392, 15356945755932217528217084848811599775130985825038998
692965243198105904624442)
Suppose H(m) = 21668398097129279358779433271119370918865051659048528
91187078055077
Signature S = (Sx,Sy) where Sx and Sy are elements of Fp_2 and
Sx = (729051981497750473018989894592657769743437818459774775561224900
9723218090232, 683378059974468691645078542720737033649767207447427118
6472709797618120651615)
Sy = (157432174827386069860812184931399877857826328817373172771264166
63269695635786, 93427588866953969700345687463198658107209055412980315
33851535785638159753756)
For verification of the signature:
takes a point Q in E(F_p^12) and a point
R in E(F_p), and evaluates f_Q(R), where f_Q is some polynomial over
F_p^12 whose divisor is (q)(Q) - (q)(0). (Note that f_Q is defined
only up to scalars of F_p^12.) Miller's algorithm [Miller] provides a
method for evaluation of f_Q(R).
However, for BN curves, instead of using the full point Q in

= f_Q'(R)^c in (F_p^12)*, where c=(p^12-
1)/q. It satisfies the bilinear relation <[x]Q',R> =

=

^x for all Q' in E'(F_p^2)[q] and R in E(F_p)[q], for all
integers x.
We provide pseudocode for computing

with elliptic curve
arithmetic expressed in affine coordinates. From this point forward,
we will drop the notation of Q' and just use Q, understanding that Q
is a point on E'(F_p^2). Note that this section does not fully
describe the most efficient way of computing the pairing, as there
are further ways of reducing the number and complexity of the
operations needed to compute the pairing (e.g., [Devegili]). For
example, a common optimization is to factor c = (p^12-1)/q into three
parts: (p^6-1), (p^2+1) and (p^4-p^2+1)/q.

```
/* Copyright (c) 2012 IETF Trust and the persons identified as
authors of the code. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, is permitted pursuant to, and subject to the license
terms contained in, the Simplified BSD License set forth in Section
4.c of the IETF Trust's Legal Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info). */
Routine for computing the pairing
```

:
Input Q, a point in E'(F_p^2)[q], and R, a point on
E(F_p)[q].
Initialize variables:
f = (F_p^12)*; // An element of (F_p^12)*
C = Q; // An element of E'(F_p^2)[q]
c = (p^12-1)/q; // An integer
for bits of q-1, starting with the second most significant
bit, ending with the least significant bit, do
// gradient of line through C, C, [-2]C.

```
A.4. Hashing to an Integer Range
We use the function HashToIntegerRange( s, n, hashfn ) to hash
strings to an integer range. Given a string (s), a hash function
(hashfn), and an integer (n), this function returns a value between 0
and n - 1.
Input:
* an octet string, s
* an integer, n <= (2^hashlen)^hashlen
* a hash function, hashfn, with output length hashlen bits
Output:
* an integer, v, in the range 0 to n-1
```