RFC 8235

Schnorr Non-interactive Zero-Knowledge Proof

📅 published September 2017, from ietf

RFC 8235: Schnorr Non-interactive Zero-Knowledge Proof ✨

Okay bestie, this is RFC 8235, and the title block tells us the whole vibe 🎀. It's an Independent Submission (so it's not from an IETF stream), it was written by F. Hao, Ed. from Newcastle University (UK), and it's marked Category: Informational. It was published in September 2017 with ISSN 2070-1721. It doesn't obsolete or update anything, since the title block doesn't list any RFCs that it replaces or changes 🦋.

Abstract 🌸

Okay so this doc describes the Schnorr NIZK proof, which is basically a non-interactive version of the three-pass Schnorr identification scheme 💖. It lets you prove you know a discrete logarithm without leaking anything about its value 🤫. It's a seriously useful building block for lots of crypto protocols, because it helps make sure everyone is actually following the protocol rules 💅. The spec covers both the finite field and elliptic curve versions ✨.

Status of This Memo 🧚

This document is not an Internet Standards Track specification. It's published for informational purposes.

This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor chose to publish this document at its discretion, and they make 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 Section 2 of RFC 7841.

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

Copyright (c) 2017 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.

Table of Contents 📖

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

1. Introduction 🌸

Okay so there's a well-known principle for designing robust public key protocols, and it goes like this: "Do not assume that a message you receive has a particular form (such as g^r for known r) unless you can check this" [AN95]. This is the sixth of the eight principles defined by Ross Anderson and Roger Needham at Crypto '95, which is why people also call it the "sixth principle" 👑. In the past thirty years, lots of public key protocols failed to prevent attacks, and that can be explained by violating this principle [Hao10] 😭.

There are probably several ways to satisfy the sixth principle, but this doc describes one technique that lets you prove you know a discrete logarithm (for example, r for g^r) without revealing its value 🦋. It's called the Schnorr NIZK proof, and it's a non-interactive variant of the three-pass Schnorr identification scheme [Stinson06]. The original Schnorr identification scheme is made non-interactive through a Fiat-Shamir transformation [FS86], assuming there's a secure cryptographic hash function (the so-called random oracle model) ✨.

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

1.1. Requirements Language 💅

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 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

1.2. Notation 🍓

Here's the notation used in this document, so you can keep up:

  • Alice: the assumed identity of the prover in the protocol
  • Bob: the assumed identity of the verifier in the protocol
  • a | b: a divides b
  • a || b: concatenation of a and b
  • [a, b]: the interval of integers between and including a and b
  • t: the bit length of the challenge chosen by Bob
  • H: a secure cryptographic hash function
  • p: a large prime
  • q: a large prime divisor of p-1, i.e., q | p-1
  • Zp*: a multiplicative group of integers modulo p
  • Gq: a subgroup of Zp* with prime order q
  • g: a generator of Gq
  • g^d: g raised to the power of d
  • a mod b: a modulo b
  • Fp: a finite field of p elements, where p is a prime
  • E(Fp): an elliptic curve defined over Fp
  • G: a generator of the subgroup over E(Fp) with prime order n
  • n: the order of G
  • h: the cofactor of the subgroup generated by G, which is equal to the order of the elliptic curve divided by n
  • P x [b]: multiplication of a point P with a scalar b over E(Fp)

2. Schnorr NIZK Proof over Finite Field 🦋

2.1. Group Parameters 🌷

When it's implemented over a finite field, the Schnorr NIZK proof may use the same group setting as DSA [FIPS186-4]. Let p and q be two large primes with q | p-1. Let Gq denote the subgroup of Zp* of prime order q, and let g be a generator for the subgroup. Refer to the DSA examples in the NIST Cryptographic Toolkit [NIST_DSA] 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 implementing the Schnorr NIZK proof 🧚.

2.2. Schnorr Identification Scheme 🎀

The Schnorr identification scheme runs interactively between Alice (prover) and Bob (verifier). In the setup, 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.

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 makes sure that A is a valid public key, so the discrete logarithm of A with respect to the base g actually exists. It's 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] 👀.

Here's the process summarized in a diagram 🍓:

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

   choose random v from [0, q-1]

   compute V = g^v mod p    -- V ->

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

                            -- b -> 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

2.3. Non-interactive Zero-Knowledge Proof 💖

The Schnorr NIZK proof is obtained from the interactive Schnorr identification scheme through a Fiat-Shamir transformation [FS86]. This transformation uses 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 so you can flexibly include contextual information (also known as "labels" in [ABM15]) in the Schnorr NIZK proof, which makes the technique in this document generally useful 🌈. For example, security protocols built on top of the Schnorr NIZK proof may want to include more context, like the protocol name, a 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 make sure there's a clear boundary between adjacent subitems 🫶.

2.4. Computation Cost 🧮

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, which is computing 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 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 [MOV96].) 🔥

3. Schnorr NIZK Proof over Elliptic Curve 🦋

3.1. Group Parameters 💖

okay so when you run the Schnorr NIZK proof over an elliptic curve, it can use the same EC setup that ECDSA [FIPS186-4] uses. 🦋 For illustration, this doc only walks through curves over prime fields (like NIST P-256), but curves over binary fields (also in [FIPS186-4]) that work for ECDSA can totally be used here too. ✨

Here's the setup: let E(Fp) be an elliptic curve over a finite field Fp, where p is a large prime. G is a base point on the curve that acts as a generator for the subgroup of E(Fp) with prime order n. The cofactor of that subgroup is h, and it's usually small (not more than 4). 🌸

If you need the nitty-gritty on EC operations like addition, negation, and scalar multiplication, check [MOV96]. For data types and conversions, like going from an elliptic-curve point to an octet string and back, look at Section 2.3 of [SEC1]. 🧚

Also, the NIST curves are just an example! Other secure curves like Curve25519 are fair game too, as long as the elliptic curve discrete logarithm problem (ECDLP) stays intractable. 💅

3.2. Schnorr Identification Scheme 🎀

So, in the setup, Alice publishes her public key A = G x [a], where a is her private key, picked uniformly at random from [1, n-1]. 🔑

The protocol is a three-pass thing:

  1. Alice picks a number v uniformly at random from [1, n-1] and computes V = G x [v]. She sends V to Bob. 📨
  2. Bob picks 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, Bob runs some checks. If any check fails, the verification is unsuccessful. 🙈

  1. Verify that A is a valid point on the curve, and that A x [h] is not the point at infinity.
  2. Verify that V = G x [r] + A x [c].

The first check makes sure A is a valid public key, so the discrete logarithm of A with respect to the base G actually exists. Honestly, this is giving efficiency 🧠: in the DSA-like group setting you need a full modular exponentiation to validate a public key, but in the ECDSA-like setting, public key validation costs almost nothing, because the cofactor is small (e.g., 1, 2, or 4). 😭

Here's the whole vibe in one diagram:

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

   choose random v from [1, n-1]

   compute V = G x [v]          -- V ->

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

                                -- b -> 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

3.3. Non-interactive Zero-Knowledge Proof 🌈

Same energy as before, but now the non-interactive version comes from a Fiat-Shamir transformation [FS86]. ✨ Instead of Bob sending a challenge, you use a secure cryptographic hash function to produce the challenge. 🔮

The challenge is c = H(G || V || A || UserID || OtherInfo). The UserID is a unique identifier for the prover, and OtherInfo is OPTIONAL data, which is explained earlier in the doc. 🫶

3.4. Computation Cost 🧮

Okay, the big summary! To prove you know the discrete logarithm for A = G x [a] with respect to base G over the elliptic curve, Alice makes 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 the proof, the cost is just one scalar multiplication, which is computing G x [v]. Easy. 💅

To verify the proof in the EC setting, the cost is about one elliptic curve multiplication: computing G x [r] + A x [c], using the same simultaneous computation trick as before. And the cost of public key validation in the EC setting is essentially free. 🤑

4. Variants of Schnorr NIZK proof 🦋

In the finite field setting, the prover sends (V, r) (along with UserID and OtherInfo), and the verifier first computes c, then checks V = g^r * A^c mod p. The catch is that this means sending an element V of Zp, which is typically between 2048 and 3072 bits, plus an element r of Zq, which is typically between 224 and 256 bits. That's a lot of data, bestie. 😳 But it's possible to shrink it down to two elements of Zq, like so. ✨

In the modified variant, the prover does everything exactly the same, except 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. 🧠

Why is this still secure? Because you can compute V from (c, r), and you can compute c from (V, r). So sending (c, r) is equivalent to sending (V, c, r), which is in turn equivalent to sending (V, r). Thus, the size of the Schnorr NIZK proof is significantly reduced. 📉 The catch is that the computation costs for both the prover and the verifier stay the same. 💀

The same trick works in the elliptic curve setting by swapping (V, r) for (c, r), but the payoff is extremely limited. When V is encoded in the compressed form, this only saves 1 bit. 🙃 The computation costs for generating and verifying the NIZK proof stay the same as before.

5. Applications of Schnorr NIZK proof 🍓

Some key exchange protocols, like J-PAKE [HR08] and YAK [Hao10], rely on the Schnorr NIZK proof to make sure participants know their discrete logarithms, which means they're following the protocol spec honestly. 🤝 The technique in this doc can be applied directly to those protocols. 👑

Also, the inclusion of OtherInfo makes the Schnorr NIZK proof generally useful and flexible for a wide range of applications. 🌸 For example, you can use this technique to show a 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). This part is NOT optional, bestie! 🚨

In this case, the Schnorr NIZK proof is functionally equivalent to a self-signed Certificate Signing Request generated by using DSA or ECDSA. 🎀

6. Security Considerations 🚨

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 [Stinson06]). 🔥

  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, which is whether the prover knows the discrete logarithm. 🤫

The Fiat-Shamir transformation is a standard technique for turning a three-pass interactive Zero-Knowledge Proof protocol (where the verifier picks a random challenge) into a non-interactive one, assuming a secure cryptographic hash function exists. 🔮 Since the hash function is publicly defined, the prover can compute the challenge by itself, which is what makes the protocol non-interactive. In this case, the hash function (more precisely, the random oracle in the security proof) acts as an honest verifier, because it assigns a uniformly random challenge c to each commitment (g^v or G x [v]) sent by the prover. That's 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. 🚨🚨 Like, seriously. 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'), and from those they can compute the secret key a by:

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

It gets worse, honestly. Even a slightly better (but still bad) random number generator can cause trouble, where the value v isn't repeated, but the adversary knows a relation between two values v and 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'). They 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 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, which could introduce some undesirable correlation between items in a cryptographic protocol. The good news is that this particular attack is prevented by including the unique UserID in the hash. ✅ The verifier shall check that 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 should be included in OtherInfo whenever necessary. 🧚

7. IANA Considerations 🌷

This document does not require any IANA actions. 🎀

8. References ✨

8.1. Normative References 🎀

okay bestie, this is the references section and it's giving "where did the author get their receipts" 📚 ✨ Every single one of these is a source the spec leans on, so I'm keeping the exact citations, DOIs, dates and links so nobody has to go hunting. no cap, they are all here 💅

  • [ABM15] 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. 🔐
  • [AN95] 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. 🧠
  • [FS86] 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. 🦋 this one is literally the OG Fiat-Shamir paper, iconic
  • [MOV96] Menezes, A., Oorschot, P., and S. Vanstone, "Handbook of Applied Cryptography", 1996. 📖
  • [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>. 💜 the MUST/SHOULD vocab lives here, it's the foundation of the whole vibe
  • [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>. 🌸 it's the follow-up that says the capitals are the whole point
  • [SEC1] "Standards for Efficient Cryptography. SEC 1: Elliptic Curve Cryptography", SECG SEC1-v2, May 2009, <http://www.secg.org/sec1-v2.pdf>. 🧚 the elliptic curve bible
  • [Stinson06] Stinson, D., "Cryptography: Theory and Practice", 3rd Edition, CRC, 2006. 🍓

8.2. Informative References 🌈

these ones are the extra reading, not required to implement, but they're so good for going deeper 🫶

  • [FIPS186-4] National Institute of Standards and Technology, "Digital Signature Standard (DSS)", FIPS PUB 186-4, DOI 10.6028/NIST.FIPS.186-4, July 2013, <http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>. ✨
  • [Hao10] 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. 💅
  • [HR08] 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. 🎀
  • [NIST_DSA] NIST Cryptographic Toolkit, "DSA Examples", <http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/DSA2_All.pdf>. 🔥

Acknowledgements 🫶

okay the shoutout section, and it's SO deserved. the editor thanks Dylan Clarke, Robert Ransom, Siamak Shahandashti, Robert Cragie, Stanislav Smyshlyaev, and Tibor Jager for many useful comments 💖 Tibor Jager is the real MVP here because he pointed out the optimization technique and the vulnerability issue when the ephemeral secret v is not generated randomly 😭🔥 this is also funded 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

that's the whole doc bestie, the editor's contact info is right here if you have questions 💜🧚

📦 where this page comes from