<pre>Independent Submission                                       F. Hao, Ed.
Request for Comments: 8235                     Newcastle University (UK)
Category: Informational                                   September 2017
ISSN: 2070-1721


              <span class="h1">Schnorr Non-interactive Zero-Knowledge Proof</span>

Abstract

   This document describes the Schnorr non-interactive zero-knowledge
   (NIZK) proof, a non-interactive variant of the three-pass Schnorr
   identification scheme.  The Schnorr NIZK proof allows one to prove
   the knowledge of a discrete logarithm without leaking any information
   about its value.  It can serve as a useful building block for many
   cryptographic protocols to ensure that participants follow the
   protocol specification honestly.  This document specifies the Schnorr
   NIZK proof in both the finite field and the elliptic curve settings.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This is a contribution to the RFC Series, independently of any other
   RFC stream.  The RFC Editor has chosen to publish this document at
   its discretion and makes no statement about its value for
   implementation or deployment.  Documents approved for publication by
   the RFC Editor are not a candidate for any level of Internet
   Standard; see <a href="./rfc7841#section-2">Section&nbsp;2 of RFC 7841</a>.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   <a href="http://www.rfc-editor.org/info/rfc8235">http://www.rfc-editor.org/info/rfc8235</a>.

Copyright Notice

   Copyright (c) 2017 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) 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.





<span class="grey">Hao                           Informational                     [Page 1]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


Table of Contents

   <a href="#section-1">1</a>.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   <a href="#page-2">2</a>
     <a href="#section-1.1">1.1</a>.  Requirements Language . . . . . . . . . . . . . . . . . .   <a href="#page-3">3</a>
     <a href="#section-1.2">1.2</a>.  Notation  . . . . . . . . . . . . . . . . . . . . . . . .   <a href="#page-3">3</a>
   <a href="#section-2">2</a>.  Schnorr NIZK Proof over Finite Field  . . . . . . . . . . . .   <a href="#page-4">4</a>
     <a href="#section-2.1">2.1</a>.  Group Parameters  . . . . . . . . . . . . . . . . . . . .   <a href="#page-4">4</a>
     <a href="#section-2.2">2.2</a>.  Schnorr Identification Scheme . . . . . . . . . . . . . .   <a href="#page-4">4</a>
     <a href="#section-2.3">2.3</a>.  Non-interactive Zero-Knowledge Proof  . . . . . . . . . .   <a href="#page-5">5</a>
     <a href="#section-2.4">2.4</a>.  Computation Cost  . . . . . . . . . . . . . . . . . . . .   <a href="#page-6">6</a>
   <a href="#section-3">3</a>.  Schnorr NIZK Proof over Elliptic Curve  . . . . . . . . . . .   <a href="#page-6">6</a>
     <a href="#section-3.1">3.1</a>.  Group Parameters  . . . . . . . . . . . . . . . . . . . .   <a href="#page-6">6</a>
     <a href="#section-3.2">3.2</a>.  Schnorr Identification Scheme . . . . . . . . . . . . . .   <a href="#page-7">7</a>
     <a href="#section-3.3">3.3</a>.  Non-interactive Zero-Knowledge Proof  . . . . . . . . . .   <a href="#page-8">8</a>
     <a href="#section-3.4">3.4</a>.  Computation Cost  . . . . . . . . . . . . . . . . . . . .   <a href="#page-8">8</a>
   <a href="#section-4">4</a>.  Variants of Schnorr NIZK proof  . . . . . . . . . . . . . . .   <a href="#page-9">9</a>
   <a href="#section-5">5</a>.  Applications of Schnorr NIZK proof  . . . . . . . . . . . . .   <a href="#page-9">9</a>
   <a href="#section-6">6</a>.  Security Considerations . . . . . . . . . . . . . . . . . . .  <a href="#page-10">10</a>
   <a href="#section-7">7</a>.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  <a href="#page-11">11</a>
   <a href="#section-8">8</a>.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  <a href="#page-11">11</a>
     <a href="#section-8.1">8.1</a>.  Normative References  . . . . . . . . . . . . . . . . . .  <a href="#page-11">11</a>
     <a href="#section-8.2">8.2</a>.  Informative References  . . . . . . . . . . . . . . . . .  <a href="#page-12">12</a>
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  <a href="#page-13">13</a>
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  <a href="#page-13">13</a>

<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>.  Introduction</span>

   A well-known principle for designing robust public key protocols is
   as follows: "Do not assume that a message you receive has a
   particular form (such as g^r for known r) unless you can check this"
   [<a href="#ref-AN95" title="&quot;Robustness principles for public key protocols&quot;">AN95</a>].  This is the sixth of the eight principles defined by Ross
   Anderson and Roger Needham at Crypto '95.  Hence, it is also known as
   the "sixth principle".  In the past thirty years, many public key
   protocols failed to prevent attacks, which can be explained by the
   violation of this principle [<a href="#ref-Hao10" title="&quot;On Robust Key Agreement Based on Public Key Authentication&quot;">Hao10</a>].

   While there may be several ways to satisfy the sixth principle, this
   document describes one technique that allows one to prove the
   knowledge of a discrete logarithm (e.g., r for g^r) without revealing
   its value.  This technique is called the Schnorr NIZK proof, which is
   a non-interactive variant of the three-pass Schnorr identification
   scheme [<a href="#ref-Stinson06">Stinson06</a>].  The original Schnorr identification scheme is
   made non-interactive through a Fiat-Shamir transformation [<a href="#ref-FS86" title="&quot;How to Prove Yourself: Practical Solutions to Identification and Signature Problems&quot;">FS86</a>],
   assuming that there exists a secure cryptographic hash function
   (i.e., the so-called random oracle model).






<span class="grey">Hao                           Informational                     [Page 2]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   The Schnorr NIZK proof can be implemented over a finite field or an
   elliptic curve (EC).  The technical specification is basically the
   same, except that the underlying cyclic group is different.  For
   completeness, this document describes the Schnorr NIZK proof in both
   the finite field and the EC settings.

<span class="h3"><a class="selflink" id="section-1.1" href="#section-1.1">1.1</a>.  Requirements Language</span>

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a> [<a href="./rfc2119" title="&quot;Key words for use in RFCs to Indicate Requirement Levels&quot;">RFC2119</a>] [<a href="./rfc8174" title="&quot;Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words&quot;">RFC8174</a>] when, and only when, they appear in all
   capitals, as shown here.

<span class="h3"><a class="selflink" id="section-1.2" href="#section-1.2">1.2</a>.  Notation</span>

   The following notation is used in this document:

   o  Alice: the assumed identity of the prover in the protocol

   o  Bob: the assumed identity of the verifier in the protocol

   o  a | b: a divides b

   o  a || b: concatenation of a and b

   o  [a, b]: the interval of integers between and including a and b

   o  t: the bit length of the challenge chosen by Bob

   o  H: a secure cryptographic hash function

   o  p: a large prime

   o  q: a large prime divisor of p-1, i.e., q | p-1

   o  Zp*: a multiplicative group of integers modulo p

   o  Gq: a subgroup of Zp* with prime order q

   o  g: a generator of Gq

   o  g^d: g raised to the power of d

   o  a mod b: a modulo b

   o  Fp: a finite field of p elements, where p is a prime




<span class="grey">Hao                           Informational                     [Page 3]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   o  E(Fp): an elliptic curve defined over Fp

   o  G: a generator of the subgroup over E(Fp) with prime order n

   o  n: the order of G

   o  h: the cofactor of the subgroup generated by G, which is equal to
      the order of the elliptic curve divided by n

   o  P x [b]: multiplication of a point P with a scalar b over E(Fp)

<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>.  Schnorr NIZK Proof over Finite Field</span>

<span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a>.  Group Parameters</span>

   When implemented over a finite field, the Schnorr NIZK proof may use
   the same group setting as DSA [<a href="#ref-FIPS186-4">FIPS186-4</a>].  Let p and q be two large
   primes with q | p-1.  Let Gq denote the subgroup of Zp* of prime
   order q, and g be a generator for the subgroup.  Refer to the DSA
   examples in the NIST Cryptographic Toolkit [<a href="#ref-NIST_DSA" title="&quot;DSA Examples&quot;">NIST_DSA</a>] for values of
   (p, q, g) that provide different security levels.  A level of 128-bit
   security or above is recommended.  Here, DSA groups are used only as
   an example.  Other multiplicative groups where the discrete logarithm
   problem (DLP) is intractable are also suitable for the implementation
   of the Schnorr NIZK proof.

<span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a>.  Schnorr Identification Scheme</span>

   The Schnorr identification scheme runs interactively between Alice
   (prover) and Bob (verifier).  In the setup of the scheme, Alice
   publishes her public key A = g^a mod p, where a is the private key
   chosen uniformly at random from [0, q-1].

   The protocol works in three passes:

   1.  Alice chooses a number v uniformly at random from [0, q-1] and
       computes V = g^v mod p.  She sends V to Bob.

   2.  Bob chooses a challenge c uniformly at random from [0, 2^t-1],
       where t is the bit length of the challenge (say, t = 160).  Bob
       sends c to Alice.

   3.  Alice computes r = v - a * c mod q and sends it to Bob.








<span class="grey">Hao                           Informational                     [Page 4]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   At the end of the protocol, Bob performs the following checks.  If
   any check fails, the identification is unsuccessful.

   1.  To verify A is within [1, p-1] and A^q = 1 mod p;

   2.  To verify V = g^r * A^c mod p.

   The first check ensures that A is a valid public key, hence the
   discrete logarithm of A with respect to the base g actually exists.
   It is worth noting that some applications may specifically exclude
   the identity element as a valid public key.  In that case, one shall
   check A is within [2, p-1] instead of [1, p-1].

   The process is summarized in the following diagram.

          Alice                               Bob
         -------                             -----

   choose random v from [0, q-1]

   compute V = g^v mod p    -- V -&gt;

   compute r = v-a*c mod q  &lt;- c -- choose random c from [0, 2^t-1]

                            -- b -&gt; check 1) A is a valid public key
                                          2) V = g^r * A^c mod p

   Information Flows in Schnorr Identification Scheme over Finite Field

<span class="h3"><a class="selflink" id="section-2.3" href="#section-2.3">2.3</a>.  Non-interactive Zero-Knowledge Proof</span>

   The Schnorr NIZK proof is obtained from the interactive Schnorr
   identification scheme through a Fiat-Shamir transformation [<a href="#ref-FS86" title="&quot;How to Prove Yourself: Practical Solutions to Identification and Signature Problems&quot;">FS86</a>].
   This transformation involves using a secure cryptographic hash
   function to issue the challenge instead.  More specifically, the
   challenge is redefined as c = H(g || V || A || UserID || OtherInfo),
   where UserID is a unique identifier for the prover and OtherInfo is
   OPTIONAL data.  Here, the hash function H SHALL be a secure
   cryptographic hash function, e.g., SHA-256, SHA-384, SHA-512,
   SHA3-256, SHA3-384, or SHA3-512.  The bit length of the hash output
   should be at least equal to that of the order q of the considered
   subgroup.

   OtherInfo is defined to allow flexible inclusion of contextual
   information (also known as "labels" in [<a href="#ref-ABM15" title="&quot;Security of the J-PAKE Password-Authenticated Key Exchange Protocol&quot;">ABM15</a>]) in the Schnorr NIZK
   proof so that the technique defined in this document can be generally
   useful.  For example, some security protocols built on top of the
   Schnorr NIZK proof may wish to include more contextual information



<span class="grey">Hao                           Informational                     [Page 5]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   such as the protocol name, timestamp, and so on.  The exact items (if
   any) in OtherInfo shall be left to specific protocols to define.
   However, the format of OtherInfo in any specific protocol must be
   fixed and explicitly defined in the protocol specification.

   Within the hash function, there must be a clear boundary between any
   two concatenated items.  It is RECOMMENDED that one should always
   prepend each item with a 4-byte integer that represents the byte
   length of that item.  OtherInfo may contain multiple subitems.  In
   that case, the same rule shall apply to ensure a clear boundary
   between adjacent subitems.

<span class="h3"><a class="selflink" id="section-2.4" href="#section-2.4">2.4</a>.  Computation Cost</span>

   In summary, to prove the knowledge of the exponent for A = g^a, Alice
   generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V =
   g^v mod p, r = v - a*c mod q}, where c = H(g || V || A || UserID ||
   OtherInfo).

   To generate a Schnorr NIZK proof, the cost is roughly one modular
   exponentiation: that is to compute g^v mod p.  In practice, this
   exponentiation may be precomputed in the offline manner to optimize
   efficiency.  The cost of the remaining operations (random number
   generation, modular multiplication, and hashing) is negligible as
   compared with the modular exponentiation.

   To verify the Schnorr NIZK proof, the cost is approximately two
   exponentiations: one for computing A^q mod p and the other for
   computing g^r * A^c mod p.  (It takes roughly one exponentiation to
   compute the latter using a simultaneous exponentiation technique as
   described in [<a href="#ref-MOV96" title="&quot;Handbook of Applied Cryptography&quot;">MOV96</a>].)

<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>.  Schnorr NIZK Proof over Elliptic Curve</span>

<span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a>.  Group Parameters</span>

   When implemented over an elliptic curve, the Schnorr NIZK proof may
   use the same EC setting as ECDSA [<a href="#ref-FIPS186-4">FIPS186-4</a>].  For the illustration
   purpose, only curves over the prime fields (e.g., NIST P-256) are
   described here.  Other curves over the binary fields (see
   [<a href="#ref-FIPS186-4">FIPS186-4</a>]) that are suitable for ECDSA can also be used for
   implementing the Schnorr NIZK proof.  Let E(Fp) be an elliptic curve
   defined over a finite field Fp, where p is a large prime.  Let G be a
   base point on the curve that serves as a generator for the subgroup
   over E(Fp) of prime order n.  The cofactor of the subgroup is denoted
   h, which is usually a small value (not more than 4).  Details on EC
   operations, such as addition, negation and scalar multiplications,
   can be found in [<a href="#ref-MOV96" title="&quot;Handbook of Applied Cryptography&quot;">MOV96</a>].  Data types and conversions including



<span class="grey">Hao                           Informational                     [Page 6]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   elliptic-curve-point-to-octet-string and vice versa can be found in
   Section 2.3 of [<a href="#ref-SEC1" title="&quot;Standards for Efficient Cryptography. SEC 1: Elliptic Curve Cryptography&quot;">SEC1</a>].  Here, the NIST curves are used only as an
   example.  Other secure curves such as Curve25519 are also suitable
   for the implementation as long as the elliptic curve discrete
   logarithm problem (ECDLP) remains intractable.

<span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a>.  Schnorr Identification Scheme</span>

   In the setup of the scheme, Alice publishes her public key
   A = G x [a], where a is the private key chosen uniformly at random
   from [1, n-1].

   The protocol works in three passes:

   1.  Alice chooses a number v uniformly at random from [1, n-1] and
       computes V = G x [v].  She sends V to Bob.

   2.  Bob chooses a challenge c uniformly at random from [0, 2^t-1],
       where t is the bit length of the challenge (say, t = 80).  Bob
       sends c to Alice.

   3.  Alice computes r = v - a * c mod n and sends it to Bob.

   At the end of the protocol, Bob performs the following checks.  If
   any check fails, the verification is unsuccessful.

   1.  To verify A is a valid point on the curve and A x [h] is not the
       point at infinity;

   2.  To verify V = G x [r] + A x [c].

   The first check ensures that A is a valid public key, hence the
   discrete logarithm of A with respect to the base G actually exists.
   Unlike in the DSA-like group setting where a full modular
   exponentiation is required to validate a public key, in the ECDSA-
   like setting, the public key validation incurs almost negligible cost
   due to the cofactor being small (e.g., 1, 2, or 4).














<span class="grey">Hao                           Informational                     [Page 7]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   The process is summarized in the following diagram.

   Alice                               Bob
   -------                             -----

   choose random v from [1, n-1]

   compute V = G x [v]          -- V -&gt;

   compute r = v - a * c mod n  &lt;- c -- choose random c from [0, 2^t-1]

                                -- b -&gt; check 1) A is a valid public key
                                              2) V = G x [r] + A x [c]

            Information Flows in Schnorr Identification Scheme
                            over Elliptic Curve

<span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a>.  Non-interactive Zero-Knowledge Proof</span>

   Same as before, the non-interactive variant is obtained through a
   Fiat-Shamir transformation [<a href="#ref-FS86" title="&quot;How to Prove Yourself: Practical Solutions to Identification and Signature Problems&quot;">FS86</a>], by using a secure cryptographic
   hash function to issue the challenge instead.  The challenge c is
   defined as c = H(G || V || A || UserID || OtherInfo), where UserID is
   a unique identifier for the prover and OtherInfo is OPTIONAL data as
   explained earlier.

<span class="h3"><a class="selflink" id="section-3.4" href="#section-3.4">3.4</a>.  Computation Cost</span>

   In summary, to prove the knowledge of the discrete logarithm for A =
   G x [a] with respect to base G over the elliptic curve, Alice
   generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V =
   G x [v], r = v - a*c mod n}, where c = H(G || V || A || UserID ||
   OtherInfo).

   To generate a Schnorr NIZK proof, the cost is one scalar
   multiplication: that is to compute G x [v].

   To verify the Schnorr NIZK proof in the EC setting, the cost is
   approximately one multiplication over the elliptic curve: i.e.,
   computing G x [r] + A x [c] (using the same simultaneous computation
   technique as before).  The cost of public key validation in the EC
   setting is essentially free.









<span class="grey">Hao                           Informational                     [Page 8]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>.  Variants of Schnorr NIZK proof</span>

   In the finite field setting, the prover sends (V, r) (along with
   UserID and OtherInfo), and the verifier first computes c, and then
   checks for V = g^r * A^c mod p.  This requires the transmission of an
   element V of Zp, whose size is typically between 2048 and 3072 bits,
   and an element r of Zq whose size is typically between 224 and 256
   bits.  It is possible to reduce the amount of transmitted data to two
   elements of Zq as below.

   In the modified variant, the prover works exactly the same as before,
   except that it sends (c, r) instead of (V, r).  The verifier computes
   V = g^r * A^c mod p and then checks whether H(g || V || A || UserID
   || OtherInfo) = c.  The security of this modified variant follows
   from the fact that one can compute V from (c, r) and c from (V, r).
   Therefore, sending (c, r) is equivalent to sending (V, c, r), which
   in turn is equivalent to sending (V, r).  Thus, the size of the
   Schnorr NIZK proof is significantly reduced.  However, the
   computation costs for both the prover and the verifier stay the same.

   The same optimization technique also applies to the elliptic curve
   setting by replacing (V, r) with (c, r), but the benefit is extremely
   limited.  When V is encoded in the compressed form, this optimization
   only saves 1 bit.  The computation costs for generating and verifying
   the NIZK proof remain the same as before.

<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>.  Applications of Schnorr NIZK proof</span>

   Some key exchange protocols, such as J-PAKE [<a href="#ref-HR08" title="&quot;Password Authenticated Key Exchange by Juggling&quot;">HR08</a>] and YAK [<a href="#ref-Hao10" title="&quot;On Robust Key Agreement Based on Public Key Authentication&quot;">Hao10</a>],
   rely on the Schnorr NIZK proof to ensure participants have the
   knowledge of discrete logarithms, hence following the protocol
   specification honestly.  The technique described in this document can
   be directly applied to those protocols.

   The inclusion of OtherInfo also makes the Schnorr NIZK proof
   generally useful and flexible to cater for a wide range of
   applications.  For example, the described technique may be used to
   allow a user to demonstrate the proof of possession (PoP) of a long-
   term private key to a Certification Authority (CA) during the public
   key registration phrase.  It must be ensured that the hash contains
   data that links the proof to one particular key registration
   procedure (e.g., by including the CA name, the expiry date, the
   applicant's email contact, and so on, in OtherInfo).  In this case,
   the Schnorr NIZK proof is functionally equivalent to a self-signed
   Certificate Signing Request generated by using DSA or ECDSA.






<span class="grey">Hao                           Informational                     [Page 9]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>.  Security Considerations</span>

   The Schnorr identification protocol has been proven to satisfy the
   following properties, assuming that the verifier is honest and the
   discrete logarithm problem is intractable (see [<a href="#ref-Stinson06">Stinson06</a>]).

   1.  Completeness -- a prover who knows the discrete logarithm is
       always able to pass the verification challenge.

   2.  Soundness -- an adversary who does not know the discrete
       logarithm has only a negligible probability (i.e., 2^(-t)) to
       pass the verification challenge.

   3.  Honest verifier zero-knowledge -- a prover leaks no more than one
       bit of information to the honest verifier: whether the prover
       knows the discrete logarithm.

   The Fiat-Shamir transformation is a standard technique to transform a
   three-pass interactive Zero-Knowledge Proof protocol (in which the
   verifier chooses a random challenge) to a non-interactive one,
   assuming that there exists a secure cryptographic hash function.
   Since the hash function is publicly defined, the prover is able to
   compute the challenge by itself, hence making the protocol non-
   interactive.  In this case, the hash function (more precisely, the
   random oracle in the security proof) implements an honest verifier,
   because it assigns a uniformly random challenge c to each commitment
   (g^v or G x [v]) sent by the prover.  This is exactly what an honest
   verifier would do.

   It is important to note that in Schnorr's identification scheme and
   its non-interactive variant, a secure random number generator is
   REQUIRED.  In particular, bad randomness in v may reveal the secret
   discrete logarithm.  For example, suppose the same random value V =
   g^v mod p is used twice by the prover (e.g., because its random
   number generator failed), but the verifier chooses different
   challenges c and c' (or the hash function is used on two different
   OtherInfo data, producing two different values c and c').  The
   adversary now observes two proof transcripts (V, c, r) and (V, c',
   r'), based on which he can compute the secret key a by:

   (r-r')/(c'-c) = (v-a*c-v+a*c')/(c'-c) = a mod q.

   More generally, such an attack may even work for a slightly better
   (but still bad) random number generator, where the value v is not
   repeated, but the adversary knows a relation between two values v and






<span class="grey">Hao                           Informational                    [Page 10]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   v' such as v' = v + w for some known value w.  Suppose the adversary
   observes two proof transcripts (V, c, r) and (V', c', r').  He can
   compute the secret key a by:

   (r-r'+w)/(c'-c) = (v-a*c-v-w+a*c'+w)/(c'-c) = a mod q.

   This example reinforces the importance of using a secure random
   number generator to generate the ephemeral secret v in Schnorr's
   schemes.

   Finally, when a security protocol relies on the Schnorr NIZK proof
   for proving the knowledge of a discrete logarithm in a non-
   interactive way, the threat of replay attacks shall be considered.
   For example, the Schnorr NIZK proof might be replayed back to the
   prover itself (to introduce some undesirable correlation between
   items in a cryptographic protocol).  This particular attack is
   prevented by the inclusion of the unique UserID in the hash.  The
   verifier shall check the prover's UserID is a valid identity and is
   different from its own.  Depending on the context of specific
   protocols, other forms of replay attacks should be considered, and
   appropriate contextual information included in OtherInfo whenever
   necessary.

<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>.  IANA Considerations</span>

   This document does not require any IANA actions.

<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>.  References</span>

<span class="h3"><a class="selflink" id="section-8.1" href="#section-8.1">8.1</a>.  Normative References</span>

   [<a id="ref-ABM15">ABM15</a>]    Abdalla, M., Benhamouda, F., and P. MacKenzie, "Security
              of the J-PAKE Password-Authenticated Key Exchange
              Protocol", 2015 IEEE Symposium on Security and Privacy,
              DOI 10.1109/sp.2015.41, May 2015.

   [<a id="ref-AN95">AN95</a>]     Anderson, R. and R. Needham, "Robustness principles for
              public key protocols", Proceedings of the 15th Annual
              International Cryptology Conference on Advances in
              Cryptology, DOI 10.1007/3-540-44750-4_19, 1995.

   [<a id="ref-FS86">FS86</a>]     Fiat, A. and A. Shamir, "How to Prove Yourself: Practical
              Solutions to Identification and Signature Problems",
              Proceedings of the 6th Annual International Cryptology
              Conference on Advances in Cryptology,
              DOI 10.1007/3-540-47721-7_12, 1986.





<span class="grey">Hao                           Informational                    [Page 11]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


   [<a id="ref-MOV96">MOV96</a>]    Menezes, A., Oorschot, P., and S. Vanstone, "Handbook of
              Applied Cryptography", 1996.

   [<a id="ref-RFC2119">RFC2119</a>]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>,
              DOI 10.17487/RFC2119, March 1997,
              &lt;<a href="https://www.rfc-editor.org/info/rfc2119">https://www.rfc-editor.org/info/rfc2119</a>&gt;.

   [<a id="ref-RFC8174">RFC8174</a>]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in <a href="./rfc2119">RFC</a>
              <a href="./rfc2119">2119</a> Key Words", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc8174">RFC 8174</a>, DOI 10.17487/RFC8174,
              May 2017, &lt;<a href="https://www.rfc-editor.org/info/rfc8174">https://www.rfc-editor.org/info/rfc8174</a>&gt;.

   [<a id="ref-SEC1">SEC1</a>]     "Standards for Efficient Cryptography. SEC 1: Elliptic
              Curve Cryptography", SECG SEC1-v2, May 2009,
              &lt;<a href="http://www.secg.org/sec1-v2.pdf">http://www.secg.org/sec1-v2.pdf</a>&gt;.

   [<a id="ref-Stinson06">Stinson06</a>]
              Stinson, D., "Cryptography: Theory and Practice", 3rd
              Edition, CRC, 2006.

<span class="h3"><a class="selflink" id="section-8.2" href="#section-8.2">8.2</a>.  Informative References</span>

   [<a id="ref-FIPS186-4">FIPS186-4</a>]
              National Institute of Standards and Technology, "Digital
              Signature Standard (DSS)", FIPS PUB 186-4,
              DOI 10.6028/NIST.FIPS.186-4, July 2013,
              &lt;<a href="http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf">http://nvlpubs.nist.gov/nistpubs/FIPS/</a>
              <a href="http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf">NIST.FIPS.186-4.pdf</a>&gt;.

   [<a id="ref-Hao10">Hao10</a>]    Hao, F., "On Robust Key Agreement Based on Public Key
              Authentication", 14th International Conference on
              Financial Cryptography and Data Security,
              DOI 10.1007/978-3-642-14577-3_33, February 2010.

   [<a id="ref-HR08">HR08</a>]     Hao, F. and P. Ryan, "Password Authenticated Key Exchange
              by Juggling", Lecture Notes in Computer Science, pp.
              159-171, from 16th Security Protocols Workshop (SPW'08),
              DOI 10.1007/978-3-642-22137-8_23, 2011.

   [<a id="ref-NIST_DSA">NIST_DSA</a>] NIST Cryptographic Toolkit, "DSA Examples",
              &lt;<a href="http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/DSA2_All.pdf">http://csrc.nist.gov/groups/ST/toolkit/documents/</a>
              <a href="http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/DSA2_All.pdf">Examples/DSA2_All.pdf</a>&gt;.









<span class="grey">Hao                           Informational                    [Page 12]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
<span class="grey"><a href="./rfc8235">RFC 8235</a>                   Schnorr NIZK Proof             September 2017</span>


Acknowledgements

   The editor of this document would like to thank Dylan Clarke, Robert
   Ransom, Siamak Shahandashti, Robert Cragie, Stanislav Smyshlyaev, and
   Tibor Jager for many useful comments.  Tibor Jager pointed out the
   optimization technique and the vulnerability issue when the ephemeral
   secret v is not generated randomly.  This work is supported by the
   EPSRC First Grant (EP/J011541/1) and the ERC Starting Grant (No.
   306994).

Author's Address

   Feng Hao (editor)
   Newcastle University (UK)
   Urban Sciences Building, School of Computing, Newcastle University
   Newcastle Upon Tyne
   United Kingdom

   Phone: +44 (0)191-208-6384
   Email: feng.hao@ncl.ac.uk































Hao                           Informational                    [Page 13]
</pre>