^(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. In the case of supersingular elliptic curves, we let G_1 = G_2, P = P', so

is a generator of G_3.
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
^(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 particular families
of elliptic curves, which are 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.
. In the supersingular case, P = P', so we have g =
. Having this pre-computed value allows the Verifier to
only perform one pairing operation to verify a signature.
. There are
certain cases when the Cheon attack [Cheon] can be applied to this
problem, though still at exponential cost, and choosing p such that
both of p+1 and p-1 have no small divisor greater than (log p)^2 can
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:
```
/* 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
```

```
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
Method:
1) Let A = hashfn( s )
2) Let h_0 = 00...00, a string of null bits of length hashlen
bits
3) Let l = Ceiling(lg(n)/hashlen)
```

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
E(F_p^12), we can use Q' in E'(F_p^2), where E' is the twist under
the twisting isomorphism described in the section above, so
psi(Q')=Q. This allows us to use a compact representation of the
point and to avoid F_p^12 arithmetic when computing the pairing.
Thus, let us consider G_1 = E(F_p)[q] and G_2 = E'(F_p^2)[q]. We
note that if Q=(Q_x,Q_y) and Q'=(Q_x',Q_y'), then (Q_x,Q_y)=
((z^2)Q_x',(z^3)Q_y'). The version of the Ate pairing used in this
document is given by

= 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
```

:

```
Appendix C. Example Data
This appendix provides example data for the ZSS short signature
scheme with the public parameters (n, p, q, E, P, P', g, H). The
```