Internet DRAFT - draft-irtf-cfrg-zss
draft-irtf-cfrg-zss
INTERNET-DRAFT L. Hitt
Intended Status: Informational 21CT, Inc.
Expires: June 13, 2014 December 10, 2013
ZSS Short Signature Scheme for Supersingular and BN Curves
draft-irtf-cfrg-zss-02
Abstract
This document describes the ZSS Short Signature Scheme for
implementation from bilinear pairings on supersingular elliptic
curves and Barreto-Naerhig (BN) ordinary elliptic curves. The ZSS
Short Signature Scheme uses general cryptographic hash functions such
as SHA-1 or SHA-2 and is efficient in terms of pairing operations.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Copyright and License Notice
Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
<L. Hitt> Expires June 13, 2014 [Page 1]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Bilinear Pairings . . . . . . . . . . . . . . . . . . . . . 4
1.2 Discrete Logarithm Problem and Diffie-Hellman Problems . . . 4
1.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Notation, Definitions and Parameters . . . . . . . . . . . . . . 6
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Representations . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 The ZSS Cryptosystem . . . . . . . . . . . . . . . . . . . . . 10
4.1 Parameter Generation . . . . . . . . . . . . . . . . . . . . 10
4.2 Key Generation . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Signature Generation . . . . . . . . . . . . . . . . . . . . 11
4.4 Signature Verification . . . . . . . . . . . . . . . . . . . 11
5 Security Considerations . . . . . . . . . . . . . . . . . . . . 11
6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 13
7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.1 Normative References . . . . . . . . . . . . . . . . . . . . 13
7.2 Informative References . . . . . . . . . . . . . . . . . . . 14
Appendix A. Supersingular Elliptic Curves, Pairings and
Supporting Algorithms . . . . . . . . . . . . . . . . . . 16
A.1 Supersingular Elliptic Curves . . . . . . . . . . . . . . . 16
A.2. E(F_p^2) and the Distortion Map for Supersingular Curves . 16
A.3. The Tate-Lichtenbaum Pairings for Supersingular Curves . . 16
A.4. Hashing to an Integer Range . . . . . . . . . . . . . . . . 18
Appendix B. BN Elliptic Curves, Pairings and Supporting
Algorithms . . . . . . . . . . . . . . . . . . . . . . . 19
B.1. BN Elliptic Curves . . . . . . . . . . . . . . . . . . . . 19
B.2. Sextic Twists of BN Curves . . . . . . . . . . . . . . . . 19
B.3. The Ate Pairing for BN Curves . . . . . . . . . . . . . . . 19
Appendix C. Example Data . . . . . . . . . . . . . . . . . . . . . 21
C.1 Example 1 (Supersingular) . . . . . . . . . . . . . . . . . 22
C.2 Example 2 (BN) . . . . . . . . . . . . . . . . . . . . . . . 24
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 26
<L. Hitt> Expires June 13, 2014 [Page 2]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
1 Introduction
This document describes the ZSS Short Signature Scheme (designed by
Zhang, Safavi-Naini, and Susilo) for implementation from bilinear
pairings [ZSS]. It does not require any special hash function such
as MapToPoint [B-F], which is still probabilistic and generally
inefficient, but rather can use cryptographic hash functions such as
SHA-1 or SHA-2.
This document is restricted to implementation of ZSS on a particular
family of supersingular elliptic curves and a particular family of
Barreto-Naerhig (BN) elliptic curves, though the scheme is valid on
other elliptic curve groups. The supersingular family offers
efficiency and simplicity advantages when computing the pairing,
which is the most time consuming procedure in pairing-based
cryptography. These advantages are important since short signatures
are needed in low-bandwidth communication environments.
BN curves are a family of non-supersingular (i.e., ordinary) curves
that are attractive for pairing-based cryptography for a variety of
other reasons. These curves are plentiful and easily found and they
support a sextic twist, which allows pairing arguments to be defined
over relatively small finite fields. BN curves are amenable to
twofold or threefold pairing compression and attain high efficiency
for all pairing computation algorithms known (e.g., Tate, ate, eil,
R-ate, Xate). These curves are also suitable for software and
hardware implementations on a wide range of platforms.
The specific subclass of BN curves that we choose for this document
is discussed in [Pereira], and offers many additional efficiency
advantages. The subclass automatically yields the right sextic twist
(thus entirely avoiding curve arithmetic for that purpose) and
provides simple and obvious generators for the curve and its twist
(removing the need for extra processing and storage). It allows for
pairing efficiency, uniform finite field arithmetic, choice of
suitable field sizes, and enables virtually all optimizations
currently proposed in the literature for involved algebraic
structures.
The scheme is constructed from the Inverse Computational Diffie-
Hellman Problem (Inv-CDHP) on bilinear pairings (see Section 1.2
below for a discussion of Inv-CDHP). The security of the scheme is
based on the assumed hardness of this problem (which is widely
accepted), which means there is no polynomial time algorithm to solve
it with non-negligible probability. Bilinear pairings have been used
to construct Identity (ID)-Based cryptosystems [B-F], so that the
identity information of a user functions as his public key. The
signing process in a short signature scheme can be regarded as the
<L. Hitt> Expires June 13, 2014 [Page 3]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
private key extract process in the ID-based public key setting from
bilinear pairings. Therefore, the ZSS signature scheme can be
regarded as being derived from Sakai-Kasahara's ID-based encryption
scheme with pairing [S-K, RFC6508].
The algorithm is for use in the following context:
* where there are two parties, a Signer and a Verifier;
* where a message is to be signed and then verified (e.g., for
authenticating the initiating party during key establishment);
* where a Certificate Authority (CA) or Trusted Third Party (TTP)
within a traditional Public Key Infrastructure (PKI) provides a
root of trust for both parties.
1.1 Bilinear Pairings
Let G_1 and G_2 be cyclic additive groups generated by P and P',
respectively, both of whose order is a prime q. Let G_3 be a
cyclic multiplicative group with the same order q. Let Z_q be the
additive group of integers modulo q.
Let <,>: G_1 X G_2 --> G_3 be a map with the following properties.
1. Bilinearity: <aP,bQ>=<P,Q>^(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 <P,Q> != 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 <P,Q>
for all P in G_1 and Q in G_2.
In our setting of prime order groups, non-degeneracy is equivalent to
<P,Q> != 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 <P,Q> 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 <P,P> 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
<L. Hitt> Expires June 13, 2014 [Page 4]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
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_3 such that v = <P,P>^(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.
<L. Hitt> Expires June 13, 2014 [Page 5]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
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.
During the signing process, once the Signer has formed its message,
it signs the message using its Signer Secret Key (SSK). It transmits
the Signature with the message. The Verifier MUST then use the
message, Signature, and SPK in verification.
This document specifies
* an algorithm for creating a Signature from a message, using an
SSK;
* an algorithm for verifying a Signature for a message, using an
SPK.
This document does not specify (but comments on)
* how to choose a valid and secure elliptic curve;
* which hash function to use.
3 Notation, Definitions and Parameters
3.1 Notation
n A security parameter; n should be at most half the bit size of
q.
p A prime, of size at least 2n bits, which is the order of the
finite field F_p. In this document, p is always congruent to 3
modulo 4.
F_p The finite field of order p (i.e., field with p elements).
F* The multiplicative group of the non-zero elements in the field
F; e.g., (F_p)* is the multiplicative group of the finite field
F_p.
q An odd prime. In the case of supersingular curves, q divides
p+1 and is the order of a subgroup of E(F_p). For BN curves, q
is the order of E(F_p). To provide the desired level of
security, lg(q) MUST be greater than 2*n.
E An elliptic curve defined over F_p. In this document, for the
case of supersingular curves, E(F_p) has a subgroup of prime
<L. Hitt> Expires June 13, 2014 [Page 6]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
order q, and for the case of BN curves, E(F_p) has prime order
q. In this document, we use supersingular curves with equation
y^2 = x^3 - 3 * x modulo p and BN elliptic curves with equation
y^2 = x^3 + 2 modulo p.
E' A sextic twist of the elliptic curve E. For the family of BN
curves in this document, E':y^2 = x^3 + (1-i) over F_p^12, and
the order of E' over F_{p^2} is q(2p-q).
E(F) The additive group of points of affine coordinates (x,y) with
x, y in the field F, that satisfy the curve equation for E.
P A point of E(F_p) that generates the cyclic (sub)group of order
q. In the case of supersingular curves, P generates a subgroup
of order q and in the case of BN curves, P is a generator of
the full group E(F_p) and has order q.
P' A point of E'(F_p^2) that generates the cyclic subgroup of
order q.
0 The null element of any additive group of points on an elliptic
curve, also called the point at infinity.
F_p^2 The extension field of degree 2 of the field F_p. In this
document, we use a particular instantiation of this field;
F_p^2 = F_p[i], where i^2 + 1 = 0. It is for this reason that
we choose p congruent to 3 modulo 4.
PF_p The projectivization of F_p. We define this to be
(F_p^2)*/(F_p)*. Note that PF_p is cyclic and has order p + 1,
which is divisible by q.
G[q] The q-torsion of a group G. This is the subgroup generated by
points of order q in G.
< , > A bilinear pairing. We use < , > to represent a version of the
Tate-Lichtenbaum pairing for supersingular curves and the ate
pairing for BN curves. In this document, the Tate-Lichtenbaum
pairing is a bilinear map from E(F_p)[q] x E(F_p)[q] onto the
subgroup of order q in PF_p, and the ate pairing is a bilinear
map from E'(F_p^2)[q] X E(F_p)[q] onto the subgroup of order q
in (F_p^12)*. A full definition for each of these is given in
Appendix A.3 and Appendix B.3.
g g = <P,P'>. In the supersingular case, P = P', so we have g =
<P,P>. Having this pre-computed value allows the Verifier to
only perform one pairing operation to verify a signature.
<L. Hitt> Expires June 13, 2014 [Page 7]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
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. In the
supersingular case, P' = P.
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
the range 0 to p-1 using the octet string
representation defined above. Such octet strings
<L. Hitt> Expires June 13, 2014 [Page 8]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
MUST have length L = Ceiling(lg(p)/8).
F_p^2 elements The elements of F_p^2 = F_p[i] are represented as
x_1 + i * x_2, where x_1 and x_2 are elements of
F_p. It is for this reason that we choose p
congruent to 3 modulo 4.
PF_p elements Elements of PF_p are cosets of (F_p)* in (F_p^2)*.
Every element of F_p^2 can be written unambiguously
in the form x_1 + i * x_2, where x_1 and x_2 are
elements of F_p. Thus, elements of PF_p (except the
unique element of order 2) can be represented
unambiguously by x_2/x_1 in F_p. Since q is odd,
every element of PF_p[q] can be represented by an
element of F_p in this manner.
Elements of PF_p MUST be represented as an element
of F_p using the algorithm in Appendix A.2. They
are therefore represented as octet strings as
defined above and are L octets in length.
Representation of the unique element of order 2 in
PF_p will not be required.
This representation of elements in PF_p[q] allows
efficient implementation of PF_p[q] group
operations, as these can be defined using arithmetic
in F_p. If a and b are elements of F_p representing
elements A and B of PF_p[q], respectively, then A *
B in PF_p[q] is represented by (a + b)/(1 - a * b)
in F_p.
Points on E, E' Elliptic curve points MUST be represented in
uncompressed form as defined in Section 2.2 of
[RFC5480]. For an elliptic curve point (x,y) with x
and y in F_p, this representation is given by 0x04
|| x' || y', where x' is the octet string
representing x, y' is the octet string representing
y, and || denotes concatenation. The representation
is 2*L+1 octets in length.
3.4 Arithmetic
ZSS relies on elliptic curve arithmetic. The coordinates of a point
P on the elliptic curve are given by P = (P_x,P_y), where Px and Py
are the affine coordinates in F_p satisfying the curve equation.
The following conventions are assumed for curve operations:
<L. Hitt> Expires June 13, 2014 [Page 9]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
Point addition - If P and Q are two points on a curve E, their sum is
denoted as P + Q.
Scalar multiplication - If P is a point on a curve, and k an integer,
the result of adding P to itself a total of k times
is denoted [k]P.
In this document, we use either supersingular curves with equation
y^2 = x^3 - 3 * x modulo p, or BN curves with equation y^2 = x^3 + 2
modulo p. These curves are chosen because of the efficiency and
simplicity advantages they offer. The choice of -3 for the
coefficient of x in the supersingular curve provides advantages for
elliptic curve arithmetic that are explained in [P1363]. Barreto's
trick [Barreto] of eliminating the computation of the denominators
when calculating the pairing also applies to these supersingular
curves. Advantages for the BN curves are discussed in Section 1 and
in [Pereira]. For example, one advantage is an easy determination of
a generator P of E(F_p), namely P = (-1,1).
4 The ZSS Cryptosystem
This section describes the ZSS short signature scheme [ZSS].
4.1 Parameter Generation
The following static parameters are fixed for each implementation.
They are not intended to change frequently, and MUST be specified for
each user community.
The system parameters to be generated for a given security parameter
n are {p, q, E, P, P', <,>, g, H}. These are known by the Sender and
the Verifier. In the supersingular case, P' = P.
4.2 Key Generation
To create signatures, each Signer requires an SSK and SPK. The SSK
is an integer, and the SPK is an elliptic curve point. The SSK MUST
be kept secret (to the Signer and possibly the CA), but the SPK need
not be kept secret.
The Signer (or CA) MUST randomly select a value in the range 2 to q-
1, and assigns this value to x, which is the SSK.
The Signer MUST derive its SPK, X, by performing the calculation X
=[x]P.
If the signer generated the SPK, then it must be registered with a
CA.
<L. Hitt> Expires June 13, 2014 [Page 10]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
4.3 Signature Generation
Given the SSK x, and a message m, the Signer computes the signature S
by performing the following steps:
1) Compute the hash of the message as a mod q value using the hash
algorithm specified in the public parameters.
2) Compute (H(m)+x)^-1, where the inversion is performed modulo q.
3) Compute S = [(H(m)+x)^-1]P'. (Recall that in the supersingular
case, P' = P.) The signature is S, and this is a point on the
curve E in the supersingular case, and E' in the BN case.
The Signer sends m and S.
4.4 Signature Verification
Given the SPK X, a message m, and a signature S, the Receiver
verifies that <[H(m)]P + X, S> = g, to ensure that the Signer is
authentic and the message was not altered in transit. This is
achieved by the Verifier performing the following steps:
1) Check that S is a point on the curve E in the supersingular
case and E' in the BN case, otherwise reject the signature.
2) Compute the hash of the message as a mod q value using the hash
algorithm specified in the public parameters.
3) Compute the elliptic curve point [H(m)]P + X.
4) Compute the pairing <[H(m)]P + X, S>.
5) Verify that <[H(m)]P + X, S> = g; if not, reject the signature.
5 Security Considerations
This document describes the ZSS Short Signature Scheme. We assume
that the security provided by this algorithm depends entirely on the
secrecy of the secret keys it uses, and that for an adversary to
defeat this security, he will need to perform computationally
intensive cryptanalytic attacks to recover a secret key. Note that a
security proof exists for ZSS in the Random Oracle Model [ZSS].
Security rests on the (k+1)-Exponent Problem, which is to compute
y^(k+1)P when given k+1 values <P,xP, x^2P, ..., x^kP>. 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
<L. Hitt> Expires June 13, 2014 [Page 11]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
prevent the possibility of this attack.
When defining public parameters, guidance on parameter sizes from
[RFC4492] SHOULD be followed. For lower security levels (e.g., less
than 128 bit security), the parameter sizes must be determined based
on the elliptic curve discrete logarithm problem over F_p, and for
the higher security levels the parameter sizes are based on the
finite field size (e.g., 2*lg(p) for the supersingular curve family,
12*lg(p) for the BN curve family).
Table 1 and Table 2 show bits of security afforded by various sizes
of p for the case of supersingular curves and BN curves,
respectively.
Security (bits) | EC size (lg(p) | finite field size (2*lg(p))
---------------------------------------------------------------
80 | 512 | 1024
112 | 1024 | 2048
128 | 1536 | 3072
192 | 3840 | 7680
256 | 7680 | 15360
Table 1: For supersingular curves, comparable strengths, taken from
[RFC4492]
Security (bits) | EC size (lg(p) | finite field size (12*lg(p))
---------------------------------------------------------------
80 | 160 | 1920
112 | 224 | 2688
128 | 256 | 3072
192 | 640 | 7680
256 | 1280 | 15360
Table 2: For BN curves, comparable strengths, taken from [RFC4492]
The order of the base point P used in ZSS (and hence the order of
E(F_p) for BN curves), MUST be a large prime q. If n bits of security
are needed, then lg(q) SHOULD be chosen to be at least 2*n.
Similarly, if n bits of security are needed, then a hash with output
size at least 2*n SHOULD be chosen.
Randomizing the messages that are signed is a way to enhance the
security of the cryptographic hash function. [SP800-106] provides a
technique to randomize messages that are input to a cryptographic
hash function during the signature generation step. The intent of
this method is to strengthen the collision resistance provided by the
hash functions without any changes to the core hash functions and
signature algorithms. If the message is randomized with a different
<L. Hitt> Expires June 13, 2014 [Page 12]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
random value each time it is signed, it will result in the message
having a different digital signature each time.
Each user's SSK protects the ZSS communications it receives. This
key MUST NOT be revealed to any entity other than the authorized user
and possibly the CA (if the CA generated the key pair).
In order to ensure that the SSK is received only by an authorized
entity, it MUST be transported through a secure channel. The
security offered by this signature scheme is no greater than the
security provided by this delivery channel.
The randomness of values stipulated to be selected at random, as
described in this document, is essential to the security provided by
ZSS. If the value of x used by a user is predictable, then the value
of his SSK could be recovered. This would allow that user's
signatures to be forged. Guidance on the generation of random values
for security can be found in [RFC4086].
6 IANA Considerations
This memo includes no request to IANA.
7 References
7.1 Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and
B. Moeller, "Elliptic Curve Cryptography (ECC) Cipher
Suites for Transport Layer Security (TLS)", RFC 4492, May
2006.
[RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk,
"Elliptic Curve Cryptography Subject Public Key
Information", RFC 5480, March 2009.
[RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental
Elliptic Curve Cryptography Algorithms", RFC 6090,
February 2011.
[ZSS] Zhang, F., Safavi-Naini, R., and Susilo, W., "An
Efficient Signature Scheme from Bilinear Pairings and Its
Applications", PKC 2004, LNCS 2947, Springer-Verlag
(2004), pp. 277-290.
<L. Hitt> Expires June 13, 2014 [Page 13]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
7.2 Informative References
[Barreto] Barreto, P., Kim, H., Lynn, B., and Scott, M., "Efficient
Algorithms for Pairing-Based Cryptosystems", Advances in
Cryptology - Crypto 2002, LNCS 2442, Springer-Verlag
(2002), pp. 354-369.
[B-F] Boneh, D., Franklin, M., "Identity-based encryption from
the Weil pairing", Advances in Cryptology - Crypto 2001,
LNCS 2139, Springer-Verlag (2001), pp. 213-229.
[Cha-Cheon] Cha, J.C., Cheon, J.H., "An identity-based signature from
gap Diffie-Hellman groups", Public Key Cryptography - PKC
2003, LNCS 2139, Springer-Verlag (2003), pp. 18-3.
[Cheon] Cheon, J.H., "Discrete Logarithm Problems with Auxiliary
Inputs", J. Cryptology 23 (2010), pp. 457-476.
[Devegili] Devegili, A.J., Scott, M., Dahab, R., "Implementing
Cryptographic Pairings over Barreto-Naehrig Curves",
Pairing 2007, pp. 197-207.
[FIPS180-3] Federal Information Processing Standards Publication
(FIPS PUB) 180-3, "Secure Hash Standard (SHS)", October
2008.
[Hess] Hess, F., "Efficient identity based signature schemes
based on pairings", SAC 2002, LNCS 2595, Springer-Verlag
(2002), pp. 310-324.
[Miller] Miller, V., "The Weil pairing, and its efficient
calculation", J. Cryptology 17 (2004), pp. 235-261.
[P1363] IEEE P1363-2000, "Standard Specifications for Public-Key
Cryptography", 2001.
[Pereira] Pereira, G. C., et al. "A Family of Implementation-
Friendly BN Elliptic Curves", J. Systems and Software,
Volume 84, Issue 8, Elsevier (2011), pp. 1319-1326.
[RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106,
RFC 4086, June 2005.
[RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)",
RFC 6508, February 2012.
[S-K] Sakai, R., Ohgishi, K., and M. Kasahara, "ID based
<L. Hitt> Expires June 13, 2014 [Page 14]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
cryptosystem based on pairing on elliptic curves",
Symposium on Cryptography and Information Security -
SCIS, 2001.
[SP800-106] Dang, Q., "Randomized Hashing for Digital Signatures",
NIST Special Publication 800-106, February 2009.
<L. Hitt> Expires June 13, 2014 [Page 15]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
Appendix A. Supersingular Elliptic Curves, Pairings and Supporting
Algorithms
A.1 Supersingular Elliptic Curves
When E is a supersingular elliptic curve (of j-invariant 1728), we
consider the family such that E: y^2 = x^3 - 3 * x modulo p. E(F_p)
contains a cyclic subgroup of order q, denoted E(F_p)[q], whereas the
larger object E(F_p^2) contains the direct product of two cyclic
subgroups of order q, denoted E(F_p^2)[q].
P is a generator of E(F_p)[q]. It is specified by the (affine)
coordinates (P_x,P_y) in F_p, satisfying the curve equation.
Routines for point addition and doubling on E(F_p) can be found in
Appendix A.10 of [P1363].
A.2. E(F_p^2) and the Distortion Map for Supersingular Curves
If (Q_x,Q_y) are (affine) coordinates in F_p for some point (denoted
Q) in E(F_p)[q], then (-Q_x,iQ_y) are (affine) coordinates in F_p^2
for some point in E(F_p^2)[q]. This latter point is denoted [i]Q, by
analogy with the definition for scalar multiplication. The two
points P and [i]P together generate E(F_p^2)[q]. The map [i]:
E(F_p)-> E(F_p^2) is sometimes termed the distortion map. This map is
used to ensure the pairing is applied to independent points so that
the pairing is not equal to 1.
A.3. The Tate-Lichtenbaum Pairings for Supersingular Curves
As in [RFC6508], we describe the pairing < , > to be used in ZSS for
supersingular elliptic curves. We will need to evaluate polynomials
f_R that depend on points on E(F_p)[q]. Miller's algorithm [Miller]
provides a method for evaluation of f_R(X), where X is some element
of E(F_p^2)[q] and R is some element of E(F_p)[q] and f_R is some
polynomial over F_p whose divisor is (q)(R) - (q)(0). Note that f_R
is defined only up to scalars of F_p.
The version of the Tate-Lichtenbaum pairing used in this document is
given by <R,Q> = f_R([i]Q)^c / (F_p)*. It satisfies the bilinear
relation <[x]R,Q> = <R,[x]Q> = <R,Q>^x for all Q, R in E(F_p)[q], for
all integers x. Note that the domain of definition is restricted to
E(F_p)[q] x E(F_p)[q] so that certain optimizations are natural.
We provide pseudocode for computing <R,Q> with elliptic curve
arithmetic expressed in affine coordinates. We make use of Barreto's
trick [Barreto] for avoiding the calculation of denominators. Note
that this section does not fully describe the most efficient way of
computing the pairing; it is possible to compute the pairing without
<L. Hitt> Expires June 13, 2014 [Page 16]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
any explicit reference to the extension field F_p^2. This reduces
the number and complexity of the operations needed to compute the
pairing.
<CODE BEGINS>
/* 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 <R,Q>:
Input R, Q points on E(F_p)[q];
Initialize variables:
v = (F_p)*; // An element of PF_p[q]
C = R; // An element of E(F_p)[q]
c = (p+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.
l = 3*( C_x^2 - 1 ) / ( 2*C_y );
//accumulate line evaluated at [i]Q into v
v = v^2 * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) );
C = [2]C;
if bit is 1, then
// gradient of line through C, R, -C-R.
l = ( C_y - R_y )/( C_x - R_x );
//accumulate line evaluated at [i]Q into v
v = v * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) );
C = C+R;
<L. Hitt> Expires June 13, 2014 [Page 17]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
end if;
end for;
t = v^c;
return representative in F_p of t;
End of routine;
Routine for computing representative in F_p of elements of
PF_p:
Input t, in F_p^2, representing an element of PF_p;
Represent t as a + i*b, with a,b in F_p; return b/a;
End of routine;
<CODE ENDS>
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)
<L. Hitt> Expires June 13, 2014 [Page 18]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
4) For each i in 1 to l, do:
a) Let h_i = hashfn(h_(i - 1))
b) Let v_i = hashfn(h_i || A), where || denotes concatenation
5) Let v' = v_1 || ... || v_l
6) Let v = v' mod n
Appendix B. BN Elliptic Curves, Pairings and Supporting Algorithms
B.1. BN Elliptic Curves
When E is an ordinary elliptic curve known as a BN curve (of j-
invariant 0), we consider the family such that E: y^2=x^3+b, defined
over a finite prime field F_p. In this document, we let b = 2. We
require that p is congruent to 3 modulo 4, for efficiency reasons. E
has prime order q = #E(F_p), and for BN curves, the primes p and q
are given by p = p(u) = 36u^4+36u^3+24u^2+6u+1 and q = q(u) =
36u^4+36u^3+18u^2+6u+1, for some integer u. The BN curve in this
document has a generator P = (-1,1). BN curves have embedding degree
k = 12 and admit a sextic twist, which allows for an optimal ate
pairing on the groups, as we discuss below.
Routines for point addition and doubling on E(F_p) can be found in
Appendix A.10 of [P1363].
B.2. Sextic Twists of BN Curves
Since p is a prime congruent to 3 modulo 4, the finite field F_p^2
can be represented as F_p[i]/(i^2+1). So i^2+1 = 0 and elements of
F_p^2 are represented as x_1 + i * x_2, where x_1 and x_2 are
elements of F_p. We may view F_p^12 as F_p^2[x]/(x^6-z), where x^6-z
is irreducible over F_p^2.
Consider the twisting isomorphism, psi: E'(F_p^2) --> E(F_p), where
(x',y') is mapped to (x'z^2),y'z^3) for some z in the multiplicative
group of F_p^12. It can be shown that E':y^2 = x^3 +b/z over F_p^2,
where z is not a cube nor square in F_p^2. E' is called the sextic
twist of E over F_p^2. E'(F_p^2)[q] has a generator P' = [h](-i,1)
where h=2p-q. So in the case of E: y^2=x^3+2 over F_p, we have E':
y^2=x^3+(1-i) over F_p^2.
B.3. The Ate Pairing for BN Curves
The Tate, Ate or R-ate pairings can be used with BN curves in ZSS,
but we describe the Ate pairing in this document The Ate pairing for
<L. Hitt> Expires June 13, 2014 [Page 19]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
BN curves uses roughly half the number of iterations of the Miller
loop needed to compute the Tate pairing.
In general, the Ate pairing is from G_2 X G1 onto the subgroup of
order q in (F_p^12)*, where G_2 = E(F_p^12)[q] and G_1 = E(F_p)[q].
Thus, the Ate pairing <Q,R> 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 <Q',R> = f_Q'(R)^c in (F_p^12)*, where c=(p^12-
1)/q. It satisfies the bilinear relation <[x]Q',R> = <Q',[x]R> =
<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 <Q',R> 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.
<CODE BEGINS>
/* 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 <Q,R>:
<L. Hitt> Expires June 13, 2014 [Page 20]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
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.
l = 3*( C_x^2 ) / ( 2*C_y );
//accumulate line evaluated at R into f
f = f^2 * ( l*( - R_x + C_x ) + ( R_y - C_y ) );
C = [2]C;
if bit is 1, then
// gradient of line through C, Q, -C-Q.
l = ( C_y - Q_y )/( C_x - Q_x );
//accumulate line evaluated at R into f
f = f * ( l*( - R_x + C_x ) + ( R_y - C_y ) );
C = C+Q;
end if;
end for;
t = f^c;
return representative in (F_p^12)* of t;
<CODE ENDS>
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
<L. Hitt> Expires June 13, 2014 [Page 21]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
supersingular curve parameters are also found in [RFC6808,RFC6809].
We denote elements of Fp_2 by (alpha, beta) for alpha + i*beta, where
i in Fp_2 is a root of X^2+1. We denote elements of Fp_12 by
((gamma_0), (gamma_1), (gamma_2), (gamma_3), (gamma_4), (gamma_5))
for gamma_0 + gamma_1*Z + gamma_2*Z^2 + gamma_3*Z^3 + gamma_4*Z^4 +
gamma_5*Z^5, where Z in Fp_12 is a root of x^6-z and
gamma_j=(alpha_j, beta_j) are elements of Fp_2.
C.1 Example 1 (Supersingular)
n = 128
p = 997ABB1F 0A563FDA 65C61198 DAD0657A
416C0CE1 9CB48261 BE9AE358 B3E01A2E
F40AAB27 E2FC0F1B 228730D5 31A59CB0
E791B39F F7C88A19 356D27F4 A666A6D0
E26C6487 326B4CD4 512AC5CD 65681CE1
B6AFF4A8 31852A82 A7CF3C52 1C3C09AA
9F94D6AF 56971F1F FCE3E823 89857DB0
80C5DF10 AC7ACE87 666D807A FEA85FEB
q = 265EAEC7 C2958FF6 99718466 36B4195E
905B0338 672D2098 6FA6B8D6 2CF8068B
BD02AAC9 F8BF03C6 C8A1CC35 4C69672C
39E46CE7 FDF22286 4D5B49FD 2999A9B4
389B1921 CC9AD335 144AB173 595A0738
6DABFD2A 0C614AA0 A9F3CF14 870F026A
A7E535AB D5A5C7C7 FF38FA08 E2615F6C
203177C4 2B1EB3A1 D99B601E BFAA17FB
E: y^2 = x^3 -3x
P = P' = (Px,Py) where
Px = 53FC09EE 332C29AD 0A799005 3ED9B52A
2B1A2FD6 0AEC69C6 98B2F204 B6FF7CBF
B5EDB6C0 F6CE2308 AB10DB90 30B09E10
43D5F22C DB9DFA55 718BD9E7 406CE890
9760AF76 5DD5BCCB 337C8654 8B72F2E1
A702C339 7A60DE74 A7C1514D BA66910D
D5CFB4CC 80728D87 EE9163A5 B63F73EC
80EC46C4 967E0979 880DC8AB EAE63895
Py = 0A824906 3F6009F1 F9F1F053 3634A135
D3E82016 02990696 3D778D82 1E141178
F5EA69F4 654EC2B9 E7F7F5E5 F0DE55F6
6B598CCF 9A140B2E 416CFF0C A9E032B9
<L. Hitt> Expires June 13, 2014 [Page 22]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
70DAE117 AD547C6C CAD696B5 B7652FE0
AC6F1E80 164AA989 492D979F C5A4D5F2
13515AD7 E9CB99A9 80BDAD5A D5BB4636
ADB9B570 6A67DCDE 75573FD7 1BEF16D7
g = 66FC2A43 2B6EA392 148F1586 7D623068
C6A87BD1 FB94C41E 27FABE65 8E015A87
371E9474 4C96FEDA 449AE956 3F8BC446
CBFDA85D 5D00EF57 7072DA8F 541721BE
EE0FAED1 828EAB90 B99DFB01 38C78433
55DF0460 B4A9FD74 B4F1A32B CAFA1FFA
D682C033 A7942BCC E3720F20 B9B7B040
3C8CAE87 B7A0042A CDE0FAB3 6461EA46
H = SHA-256 (defined in [FIPS180-3]).
The SSK is:
x = AFF429D3 5F84B110 D094803B 3595A6E2 998BC99F
The SPK is:
X = (Xx,Xy) where
Xx = 5958EF1B 1679BF09 9B3A030D F255AA6A
23C1D8F1 43D4D23F 753E69BD 27A832F3
8CB4AD53 DDEF4260 B0FE8BB4 5C4C1FF5
10EFFE30 0367A37B 61F701D9 14AEF097
24825FA0 707D61A6 DFF4FBD7 273566CD
DE352A0B 04B7C16A 78309BE6 40697DE7
47613A5F C195E8B9 F328852A 579DB8F9
9B1D0034 479EA9C5 595F47C4 B2F54FF2
Xy = 1508D375 14DCF7A8 E143A605 8C09A6BF
2C9858CA 37C25806 5AE6BF75 32BC8B5B
63383866 E0753C5A C0E72709 F8445F2E
6178E065 857E0EDA 10F68206 B63505ED
87E534FB 2831FF95 7FB7DC61 9DAE6130
1EEACC2F DA3680EA 4999258A 833CEA8F
C67C6D19 487FB449 059F26CC 8AAB655A
B58B7CC7 96E24E9A 39409575 4F5F8BAE
Suppose H(m) = 3230 31312D30 32007465 6C3A2B34
34373730 30393030 31323300
Signature S = (Sx,Sy) where
Sx = 93AF67E5 007BA6E6 A80DA793 DA300FA4
B52D0A74 E25E6E7B 2B3D6EE9 D18A9B5C
5023597B D82D8062 D3401956 3BA1D25C
0DC56B7B 979D74AA 50F29FBF 11CC2C93
<L. Hitt> Expires June 13, 2014 [Page 23]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
F5DFCA61 5E609279 F6175CEA DB00B58C
6BEE1E7A 2A47C4F0 C456F052 59A6FA94
A634A40D AE1DF593 D4FECF68 8D5FC678
BE7EFC6D F3D68353 25B83B2C 6E69036B
Sy = 155F0A27 241094B0 4BFB0BDF AC6C670A
65C325D3 9A069F03 659D44CA 27D3BE8D
F311172B 55416018 1CBE94A2 A783320C
ED590BC4 2644702C F371271E 496BF20F
588B78A1 BC01ECBB 6559934B DD2FB65D
2884318A 33D1A42A DF5E33CC 5800280B
28356497 F87135BA B9612A17 26042440
9AC15FEE 996B744C 33215123 5DECB0F5
For verification of the signature:
<H(m)P + X, S> = g
C.2 Example 2 (BN)
n = 127 and lg(p) = 254
p = p(u) = p(-4647714815446351873)
= 1679810873101583228494080414223173390988918712143906984893371542
6072753864723
q = q(u) = q(-4647714815446351873)
= 16798108731015832284940804142231733909759579603404752749028378864
165570215949
E: y^2 = x^3 + 2
Thus, E': y'^2 = x'^3 + (1, 16798108731015832284940804142231733909
889187121439069848933715426072753864722)
P = (-1,1)
= (1679810873101583228494080414223173390988918712143906984893371542
6072753864722, 1)
P' = [h](-i,1) = (P'x,P'y), where P'x and P'y are elements of Fp_2
P'x =
(2759930593230997547690248631365636073479225314645471320757910281
674905877291, 230161490788271857374524411062025673221233257170073
7603512907075120331574515)
P'y =
(9480765153516887970576068394945041092622478388406602889697250323
02618946458, 6663077446927392079224045631425291036692402823802663
<L. Hitt> Expires June 13, 2014 [Page 24]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
947112913140121004068507)
g = <P, P'> 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:
<L. Hitt> Expires June 13, 2014 [Page 25]
INTERNET DRAFT draft-irtf-cfrg-zss-02 December 10, 2013
<H(m)P + X, S> = g
Author's Address
Laura Hitt
6011 W Courtyard Dr.
Building 5, Suite 300
Austin, TX 78730
EMail: LHitt@21CT.com
<L. Hitt> Expires June 13, 2014 [Page 26]
