Schnorr Non-interactive Zero-Knowledge Proof
RFC 8235

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 00
• 01
• 02
• 03
• 04
• 05
• 06

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

              Schnorr Non-interactive Zero-Knowledge Proof

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

   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.

Hao                           Informational                     [Page 1]
RFC 8235                   Schnorr NIZK Proof             September 2017

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

   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"
   [AN95].  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 [Hao10].

   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 [Stinson06].  The original Schnorr identification scheme is
   made non-interactive through a Fiat-Shamir transformation [FS86],
   assuming that there exists a secure cryptographic hash function
   (i.e., the so-called random oracle model).

Hao                           Informational                     [Page 2]