Independent Submission F. Hao, Ed.
Request for Comments: 8235 Newcastle University (UK)
Category: Informational September 2017
ISSN: 2070-1721
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
Schnorr非交互式零知识证明
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.
本文档描述了Schnorr非交互式零知识（NIZK）证明，这是三通Schnorr识别方案的非交互式变体。Schnorr-NIZK证明允许人们证明离散对数的知识，而不会泄露有关其值的任何信息。它可以作为许多加密协议的有用构建块，以确保参与者诚实地遵守协议规范。本文档指定了有限域和椭圆曲线设置中的Schnorr-NIZK证明。
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.
这是对RFC系列的贡献，独立于任何其他RFC流。RFC编辑器已选择自行发布此文档，并且未声明其对实现或部署的价值。RFC编辑批准发布的文件不适用于任何级别的互联网标准；见RFC 7841第2节。
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.
有关本文件当前状态、任何勘误表以及如何提供反馈的信息，请访问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.
版权所有（c）2017 IETF信托基金和确定为文件作者的人员。版权所有。
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.
本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件，因为它们描述了您对本文件的权利和限制。
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 . . . . . . . . . . . . . . . . . . . . . . . . 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
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].
设计健壮的公钥协议的一个众所周知的原则如下：“不要假设您收到的消息具有特定的形式（例如，g^r表示已知的r），除非您可以对此进行检查”[AN95]。这是罗斯·安德森（Ross Anderson）和罗杰·李约瑟（Roger Needham）在95年的Crypto大会上定义的八项原则中的第六项。因此，它也被称为“第六原则”。在过去的三十年中，许多公钥协议未能阻止攻击，这可以解释为违反了这一原则[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).
虽然有几种方法可以满足第六条原则，但本文件描述了一种技术，该技术允许证明离散对数的知识（例如，r代表g^r），而不显示其值。这种技术称为Schnorr-NIZK证明，它是三通Schnorr识别方案的非交互式变体[Stinson06]。假设存在安全的加密散列函数（即所谓的随机预言模型），原始Schnorr识别方案通过Fiat-Shamir变换[FS86]实现非交互式。
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.
Schnorr-NIZK证明可以在有限域或椭圆曲线（EC）上实现。技术规范基本相同，只是基础循环组不同。为完整起见，本文档描述了有限域和EC设置中的Schnorr-NIZK证明。
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.
本文件中的关键词“必须”、“不得”、“必需”、“应”、“不应”、“建议”、“不建议”、“可”和“可选”在所有大写字母出现时（如图所示）应按照BCP 14[RFC2119][RFC8174]所述进行解释。
The following notation is used in this document:
本文件中使用了以下符号：
o Alice: the assumed identity of the prover in the protocol
o Alice：协议中验证人的假定身份
o Bob: the assumed identity of the verifier in the protocol
o 协议中验证器的假定身份
o a | b: a divides b
o a | b:a除以b
o a || b: concatenation of a and b
o a | | b：a和b的串联
o [a, b]: the interval of integers between and including a and b
o [a，b]：介于a和b之间且包括a和b的整数的间隔
o t: the bit length of the challenge chosen by Bob
o t:由Bob选择的挑战的位长度
o H: a secure cryptographic hash function
o H：一个安全的加密散列函数
o p: a large prime
o 大素数
o q: a large prime divisor of p-1, i.e., q | p-1
o q:p-1的大素因子，即q | p-1
o Zp*: a multiplicative group of integers modulo p
o Zp*：模p的整数的乘法群
o Gq: a subgroup of Zp* with prime order q
o Gq：具有素数阶q的Zp*的子群
o g: a generator of Gq
o g:Gq的发生器
o g^d: g raised to the power of d
o g^d:g提升到d的幂
o a mod b: a modulo b
o a模b:a模b
o Fp: a finite field of p elements, where p is a prime
o Fp：p元素的有限域，其中p是素数
o E(Fp): an elliptic curve defined over Fp
o E（Fp）：定义在Fp上的椭圆曲线
o G: a generator of the subgroup over E(Fp) with prime order n
o G:E（Fp）上素数阶为n的子群的生成元
o n: the order of G
o n：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 h：G生成的子群的余因子，等于椭圆曲线的阶数除以n
o P x [b]: multiplication of a point P with a scalar b over E(Fp)
o px[b]：点P与标量b乘以E（Fp）
When 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 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 the implementation of the Schnorr NIZK proof.
当在有限域上实现时，Schnorr-NIZK证明可以使用与DSA相同的组设置[FIPS186-4]。设p和q是q | p-1的两个大素数。设Gq表示素数阶q的Zp*的子群，g是该子群的生成元。参考NIST加密工具包[NIST_DSA]中的DSA示例，了解提供不同安全级别的（p，q，g）值。建议使用128位或更高级别的安全性。这里，DSA组仅用作示例。离散对数问题（DLP）难以解决的其他乘法群也适用于Schnorr-NIZK证明的实现。
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].
Schnorr识别方案在Alice（验证者）和Bob（验证者）之间交互运行。在方案的设置中，Alice发布了她的公钥A=g^A mod p，其中A是从[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.
1. Alice从[0，q-1]中均匀随机地选择一个数字v，并计算v=g^v mod p。她把V发给鲍勃。
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.
2. Bob从[0，2^t-1]中均匀随机地选择质询c，其中t是质询的位长度（例如，t=160）。鲍勃把c寄给爱丽丝。
3. Alice computes r = v - a * c mod q and sends it to Bob.
3. Alice计算r=v-a*c mod q并将其发送给Bob。
At the end of the protocol, Bob performs the following checks. If any check fails, the identification is unsuccessful.
在协议结束时，Bob执行以下检查。如果任何检查失败，则标识不成功。
1. To verify A is within [1, p-1] and A^q = 1 mod p;
1. 验证A在[1，p-1]范围内且A^q=1模p；
2. To verify V = g^r * A^c mod p.
2. 验证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].
第一个检查确保A是有效的公钥，因此A相对于基g的离散对数实际上存在。值得注意的是，一些应用程序可能会明确地将identity元素排除为有效的公钥。在这种情况下，应检查A是否在[2，p-1]范围内，而不是[1，p-1]。
The process is summarized in the following diagram.
下图总结了该过程。
Alice Bob
------- -----
Alice Bob
------- -----
choose random v from [0, q-1]
从[0，q-1]中选择随机v
compute V = g^v mod p -- V ->
compute V = g^v mod p -- V ->
compute r = v-a*c mod q <- c -- choose random c from [0, 2^t-1]
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
-- 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
有限域上Schnorr识别方案的信息流
The Schnorr NIZK proof is obtained from the interactive Schnorr identification scheme through a Fiat-Shamir transformation [FS86]. 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.
Schnorr-NIZK证明是通过Fiat-Shamir变换从交互式Schnorr识别方案中获得的[FS86]。此转换涉及使用安全加密哈希函数来发出质询。更具体地说，挑战被重新定义为c=H（g | | V | | | A | | UserID | | OtherInfo），其中UserID是验证程序的唯一标识符，OtherInfo是可选数据。这里，散列函数H应当是安全的加密散列函数，例如，SHA-256、SHA-384、SHA-512、SHA3-256、SHA3-384或SHA3-512。散列输出的位长度应至少等于所考虑的子组的顺序q的位长度。
OtherInfo is defined to allow flexible inclusion of contextual information (also known as "labels" in [ABM15]) 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
OtherInfo的定义允许在Schnorr-NIZK证明中灵活地包含上下文信息（在[ABM15]中也称为“标签”），因此本文档中定义的技术通常是有用的。例如，一些建立在Schnorr-NIZK证明之上的安全协议可能希望包含更多上下文信息
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.
例如协议名、时间戳等。OtherInfo中的确切项目（如有）应留给特定的协议来定义。但是，任何特定协议中的OtherInfo格式都必须固定，并在协议规范中明确定义。
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.
在散列函数中，任何两个连接项之间必须有明确的边界。建议始终使用表示该项字节长度的4字节整数作为每个项的前缀。OtherInfo可能包含多个子项。在这种情况下，同样的规则应适用于确保相邻子项之间的清晰边界。
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).
总之，为了证明A=g^A指数的知识，Alice生成了一个Schnorr-NIZK证明，其中包含：{UserID，OtherInfo，V=g^V mod p，r=V-A*c mod q}，其中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.
要生成Schnorr-NIZK证明，代价大约是一次模幂运算：即计算g^v mod p。在实践中，可以以离线方式预先计算此指数运算以优化效率。与模幂运算相比，剩余运算（随机数生成、模乘和散列）的成本可以忽略不计。
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].)
为了验证Schnorr-NIZK证明，代价大约是两个指数：一个用于计算A^q mod p，另一个用于计算g^r*A^c mod p。（使用[MOV96]中所述的同时求幂技术计算后者大约需要一次求幂。）
When implemented over an elliptic curve, the Schnorr NIZK proof may use the same EC setting as ECDSA [FIPS186-4]. 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 [FIPS186-4]) 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 [MOV96]. Data types and conversions including
当在椭圆曲线上实现时，Schnorr-NIZK证明可以使用与ECDSA相同的EC设置[FIPS186-4]。出于说明目的，此处仅描述基本场（如NIST P-256）上的曲线。适用于ECDSA的二进制字段上的其他曲线（参见[FIPS186-4]）也可用于实现Schnorr-NIZK证明。设E（Fp）是有限域Fp上定义的椭圆曲线，其中p是大素数。设G是曲线上的一个基点，作为素数阶n的E（Fp）上的子群的生成元。子群的辅因子表示为h，通常是一个小值（不超过4）。有关EC操作的详细信息，如加法、求反和标量乘法，请参见[MOV96]。数据类型和转换，包括
elliptic-curve-point-to-octet-string and vice versa can be found in Section 2.3 of [SEC1]. 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.
椭圆曲线指向八进制字符串，反之亦然，见[SEC1]第2.3节。这里，NIST曲线仅用作示例。只要椭圆曲线离散对数问题（ECDLP）仍然难以解决，其他安全曲线（如Curve25519）也适用于实现。
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].
在方案的设置中，Alice发布了她的公钥A=Gx[A]，其中A是从[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.
1. Alice从[1，n-1]中均匀随机地选择一个数字v，并计算v=Gx[v]。她把V发给鲍勃。
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.
2. Bob从[0，2^t-1]中均匀随机地选择质询c，其中t是质询的位长度（例如，t=80）。鲍勃把c寄给爱丽丝。
3. Alice computes r = v - a * c mod n and sends it to Bob.
3. Alice计算r=v-a*c mod n并将其发送给Bob。
At the end of the protocol, Bob performs the following checks. If any check fails, the verification is unsuccessful.
在协议结束时，Bob执行以下检查。如果任何检查失败，则验证不成功。
1. To verify A is a valid point on the curve and A x [h] is not the point at infinity;
1. 验证A是曲线上的有效点，且A x[h]不是无穷远处的点；
2. To verify V = G x [r] + A x [c].
2. 验证V=gx[r]+ax[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).
第一个检查确保A是有效的公钥，因此A相对于基G的离散对数实际上存在。与类似DSA的组设置不同，在类似ECDSA的组设置中，验证公钥需要完全模幂运算，而在类似ECDSA的设置中，由于辅因子较小（例如，1、2或4），公钥验证产生的成本几乎可以忽略不计。
The process is summarized in the following diagram.
下图总结了该过程。
Alice Bob
------- -----
Alice Bob
------- -----
choose random v from [1, n-1]
从[1，n-1]中选择随机v
compute V = G x [v] -- V ->
compute V = G x [v] -- V ->
compute r = v - a * c mod n <- c -- choose random c from [0, 2^t-1]
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]
-- 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
椭圆曲线上Schnorr识别方案的信息流
Same as before, the non-interactive variant is obtained through a Fiat-Shamir transformation [FS86], 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.
与之前一样，非交互变体是通过Fiat-Shamir转换[FS86]获得的，使用安全加密哈希函数来发出质询。质询c被定义为c=H（G | | V | | | | | A | | | UserID | | OtherInfo），其中UserID是验证者的唯一标识符，OtherInfo是可选数据，如前所述。
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).
总之，为了证明A=gx[A]关于椭圆曲线上基G的离散对数的知识，Alice生成了一个Schnorr-NIZK证明，其中包含：{UserID，OtherInfo，V=gx[V]，r=V-A*c mod n}，其中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].
要生成Schnorr-NIZK证明，代价是一个标量乘法：即计算gx[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.
为了验证EC设置中的Schnorr-NIZK证明，成本约为椭圆曲线上的一次乘法：即，计算gx[r]+ax[c]（使用与之前相同的同时计算技术）。在EC环境中，公钥验证的成本基本上是免费的。
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.
在有限域设置中，验证程序发送（V，r）（连同UserID和OtherInfo），验证程序首先计算c，然后检查V=g^r*A^c mod p。这需要传输Zp的元素V（其大小通常在2048和3072位之间）和Zq的元素r（其大小通常在224和256位之间）。可以将传输的数据量减少到Zq的两个元素，如下所示。
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.
在修改后的变体中，校准器的工作原理与以前完全相同，只是它发送（c，r）而不是（V，r）。验证器计算V=g^r*A^c mod p，然后检查H（g | V | A | UserID | OtherInfo）=c。这个修改过的变体的安全性来自这样一个事实：可以从（c，r）计算V，从（V，r）计算c。因此，发送（c，r）等价于发送（V，c，r），而发送（V，r）又等价于发送（V，r）。因此，Schnorr-NIZK证明的尺寸显著减小。然而，验证方和验证方的计算成本保持不变。
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.
通过将（V，r）替换为（c，r），同样的优化技术也适用于椭圆曲线设置，但其好处非常有限。当V以压缩形式编码时，此优化仅节省1位。生成和验证NIZK证明的计算成本与以前相同。
Some key exchange protocols, such as J-PAKE [HR08] and YAK [Hao10], 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.
一些密钥交换协议，如J-PAKE[HR08]和YAK[Hao10]，依靠Schnorr-NIZK证明来确保参与者了解离散对数，因此诚实地遵循协议规范。本文档中描述的技术可直接应用于这些协议。
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.
OtherInfo的加入也使得Schnorr-NIZK证明通常有用且灵活，以满足广泛的应用。例如，所述技术可用于允许用户在公钥注册阶段向证书颁发机构（CA）证明长期私钥的拥有证明（PoP）。必须确保哈希包含将证明链接到一个特定密钥注册过程的数据（例如，通过在OtherInfo中包括CA名称、到期日期、申请人的电子邮件联系人等）。在这种情况下，Schnorr-NIZK证明在功能上等同于使用DSA或ECDSA生成的自签名证书签名请求。
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]).
Schnorr识别协议已被证明满足以下属性，假设验证者诚实且离散对数问题难以解决（见[Stinson06]）。
1. Completeness -- a prover who knows the discrete logarithm is always able to pass the verification challenge.
1. 完整性——知道离散对数的证明者总是能够通过验证挑战。
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.
2. 可靠性——不知道离散对数的对手通过验证挑战的概率可以忽略不计（即2^（-t））。
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.
3. 诚实验证者零知识——验证者向诚实验证者泄露的信息不超过一位：验证者是否知道离散对数。
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.
Fiat-Shamir变换是一种标准技术，用于将三次通过的交互式零知识证明协议（验证者在其中选择随机质询）转换为非交互式协议，前提是存在安全的加密哈希函数。由于散列函数是公开定义的，验证程序能够自己计算质询，因此使协议非交互式。在这种情况下，散列函数（更准确地说，安全证明中的随机预言机）实现了一个诚实的验证器，因为它为验证器发送的每个承诺（g^v或gx[v]）分配了一个统一的随机质询c。这正是一个诚实的验证者会做的。
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:
需要注意的是，在Schnorr的识别方案及其非交互式变体中，需要一个安全的随机数生成器。特别是，v中的坏随机性可能会揭示秘密的离散对数。例如，假设验证程序两次使用相同的随机值V=g^V mod p（例如，因为其随机数生成器失败），但验证程序选择不同的质询c和c’（或者对两个不同的OtherInfo数据使用哈希函数，产生两个不同的值c和c’）。对手现在观察两个证明记录（V，c，r）和（V，c'，r'），根据这两个记录，他可以通过以下方式计算密钥a：
(r-r')/(c'-c) = (v-a*c-v+a*c')/(c'-c) = a mod q.
(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
更一般地说，这种攻击甚至可能适用于稍好（但仍然不好）的随机数生成器，其中值v不会重复，但对手知道两个值v和之间的关系
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:
例如，对于某些已知值w，v'=v+w。假设对手观察到两个证明文本（V，c，r）和（V'，c'，r'）。他可以通过以下方式计算密钥a：
(r-r'+w)/(c'-c) = (v-a*c-v-w+a*c'+w)/(c'-c) = a mod q.
(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.
这个例子强调了在Schnorr的方案中使用安全随机数生成器生成短暂秘密v的重要性。
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.
最后，当安全协议依赖Schnorr-NIZK证明以非交互方式证明离散对数知识时，应考虑重放攻击的威胁。例如，Schnorr-NIZK证明可能会重放回验证程序本身（以便在加密协议中的项之间引入一些不希望的关联）。通过在散列中包含唯一的UserID，可以防止这种特定的攻击。验证人应检查验证人的用户ID是否有效，是否与自己的用户ID不同。根据特定协议的上下文，应考虑其他形式的重播攻击，并在必要时在OtherInfo中包含适当的上下文信息。
This document does not require any IANA actions.
本文件不要求IANA采取任何行动。
[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.
[ABM15]Abdalla，M.，Benhamouda，F.，和P.MacKenzie，“J-PAKE密码认证密钥交换协议的安全性”，2015年IEEE安全与隐私研讨会，DOI 10.1109/sp.2015.412015年5月。
[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.
[AN95]Anderson，R.和R.Needham，“公钥协议的鲁棒性原则”，第15届国际密码学年度会议论文集，密码学进展，DOI 10.1007/3-540-44750-4䴇，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.
[FS86]Fiat，A.和A.Shamir，“如何证明自己：识别和签名问题的实际解决方案”，第六届国际密码学年度会议论文集，密码学进展，DOI 10.1007/3-540-47721-7_12，1986年。
[MOV96] Menezes, A., Oorschot, P., and S. Vanstone, "Handbook of Applied Cryptography", 1996.
[MOV96]Menezes，A.，Oorschot，P.，和S.Vanstone，“应用密码学手册”，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>.
[RFC2119]Bradner，S.，“RFC中用于表示需求水平的关键词”，BCP 14，RFC 2119，DOI 10.17487/RFC2119，1997年3月<https://www.rfc-editor.org/info/rfc2119>.
[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>.
[RFC8174]Leiba，B.，“RFC 2119关键词中大写与小写的歧义”，BCP 14，RFC 8174，DOI 10.17487/RFC8174，2017年5月<https://www.rfc-editor.org/info/rfc8174>.
[SEC1] "Standards for Efficient Cryptography. SEC 1: Elliptic Curve Cryptography", SECG SEC1-v2, May 2009, <http://www.secg.org/sec1-v2.pdf>.
[SEC1]“高效密码标准。第1节：椭圆曲线密码术”，SECG SEC1-v2，2009年5月<http://www.secg.org/sec1-v2.pdf>.
[Stinson06] Stinson, D., "Cryptography: Theory and Practice", 3rd Edition, CRC, 2006.
[Stinson06]Stinson，D.，“密码学：理论与实践”，第三版，CRC，2006年。
[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>.
[FIPS186-4]国家标准与技术研究所，“数字签名标准（DSS）”，FIPS PUB 186-4，DOI 10.6028/NIST.FIPS.186-42013年7月<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.
[Hao10]Hao，F.，“基于公钥认证的鲁棒密钥协议”，第14届金融加密和数据安全国际会议，DOI 10.1007/978-3-642-14577-3!33，2010年2月。
[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.
[HR08]Hao，F.和P.Ryan，“通过变戏法进行密码验证的密钥交换”，《计算机科学》课堂讲稿，第159-171页，摘自第16届安全协议研讨会（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>.
[NIST_DSA]NIST加密工具包，“DSA示例”<http://csrc.nist.gov/groups/ST/toolkit/documents/ 示例/DSA2_All.pdf>。
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).
本文件的编辑要感谢Dylan Clarke、Robert Ransom、Siamak Shahandashti、Robert Cragie、Stanislav Smyshlyaev和Tibor Jager的许多有用评论。Tibor Jager指出了当短暂秘密v不是随机生成时的优化技术和漏洞问题。这项工作得到了EPSRC首次拨款（EP/J011541/1）和ERC启动拨款（编号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
Phone: +44 (0)191-208-6384
Email: feng.hao@ncl.ac.uk