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

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

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

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

is a generator of G_2. 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)*, given P, aP, bP, compute abP. Inverse Computational Diffie-Hellman Problem (Inv-CDHP): For a in (Z_q)*, given P, aP, compute [a^(-1)]P. Square Computational Diffie-Hellman Problem (Squ-CDHP): For a in (Z_q)*, given P, aP, compute [a^2]P. Bilinear Diffie-Hellman problem (BDHP): Given (P, aP, bP, cP) for some a,b,c in (Z_q)*, compute v in G_2 such that v =

^(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 supersingular elliptic curves or hyperelliptic
. 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 p,
q, E, P, < , >, g, H, and n.
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.
Signer Secret Key (SSK) - The Signer's Secret Key is used to generate
a signature and must not be revealed to any entity
other than the trusted third party and the
authorized signer. It is a value between 2 and q-1.
3.3 Representations
This section provides canonical representations of values that MUST
be used to ensure interoperability of implementations. The following
representations MUST be used for input into hash functions and for
transmission. In this document, concatenation of octet strings s and
t is denoted s || t.
Integers Integers MUST be represented as an octet string,
with bit length a multiple of 8. To achieve this,
the integer is represented most significant bit
first, and padded with zero bits on the left until
an octet string of the necessary length is obtained.
This is the octet string representation described in
Section 6 of [RFC6090].
F_p elements Elements of F_p MUST be represented as integers in
```
/* 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.3. 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)
4) For each i in 1 to l, do:
a) Let h_i = hashfn(h_(i - 1))
```