[要約] RFC 8235は、Schnorr非対話型ゼロ知識証明に関する標準化文書であり、非対話型証明のプロトコルとアルゴリズムを提供しています。このRFCの目的は、セキュリティとプライバシーを向上させるために、非対話型ゼロ知識証明の実装と利用を促進することです。
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）の証明、3パスのSchnorr識別スキームの非対話型の変形について説明します。 Schnorr NIZK証明により、その値に関する情報を漏らすことなく、離散対数の知識を証明できます。これは、参加者がプロトコル仕様に正直に従うことを保証するために、多くの暗号プロトコルの有用なビルディングブロックとして機能します。このドキュメントでは、有限体と楕円曲線の両方の設定でSchnorr NIZKの証明を指定します。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for informational purposes.
このドキュメントはInternet Standards Trackの仕様ではありません。情報提供を目的として公開されています。
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 Editorによって公開が承認されたドキュメントは、どのレベルのインターネット標準の候補にもなりません。 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.
Copyright（c）2017 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
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
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].
堅牢な公開鍵プロトコルを設計するためのよく知られている原理は次のとおりです。「受信したメッセージが特定の形式（既知のrの場合はg ^ rなど）であると確認できない限り、想定しないでください」[AN95]。これは、Crypto '95でロスアンダーソンとロジャーニーダムが定義した8つの原則の6番目です。したがって、「第6原則」とも呼ばれます。過去30年間、多くの公開鍵プロトコルが攻撃を防止できませんでした。これは、この原則の違反によって説明できます[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).
6番目の原則を満たすいくつかの方法があるかもしれませんが、このドキュメントでは、値を明らかにせずに離散対数（たとえば、g ^ rの場合はr）の知識を証明できるようにする1つの手法について説明します。この手法は、Schnorr NIZK証明と呼ばれ、3パスSchnorr識別スキームの非インタラクティブな変形です[Stinson06]。安全な暗号化ハッシュ関数（いわゆるランダムオラクルモデル）が存在することを前提として、元のシュノーア識別スキームは、フィアットシャミル変換[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.
キーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「NOT RECOMMENDED」、「MAY」、「OPTIONALこのドキュメントの「」は、BCP 14 [RFC2119] [RFC8174]で説明されているように解釈されます。
The following notation is used in this document:
このドキュメントでは、次の表記法を使用しています。
o Alice: the assumed identity of the prover in the protocol
o アリス：プロトコルにおける証明者の想定されるアイデンティティ
o Bob: the assumed identity of the verifier in the protocol
o Bob：プロトコルでの検証者の想定されるアイデンティティ
o a | b: a divides b
o a | b：aはbを分割します
o a || b: concatenation of a and b
o || b：aとbの連結
o [a, b]: the interval of integers between and including a and b
o [a、b]：aとbの間の整数の間隔
o t: the bit length of the challenge chosen by Bob
o t：ボブが選択したチャレンジのビット長
o H: a secure cryptographic hash function
o H：安全な暗号化ハッシュ関数
o p: a large prime
o p：大きな素数
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 mod b：a modulo b
o Fp: a finite field of p elements, where p is a prime o E(Fp): an elliptic curve defined over Fp
o Fp：p要素の有限体、pは素数o E（Fp）：Fpで定義された楕円曲線
o G: a generator of the subgroup over E(Fp) with prime order n
o G：素数次数がnのE（Fp）上のサブグループのジェネレーター
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 P x [b]：E（Fp）上の点Pとスカラーbの乗算
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を持つ2つの大きな素数とする| p-1。 Gqを素数次数qのZp *のサブグループとし、gをサブグループのジェネレーターとします。異なるセキュリティレベルを提供する（p、q、g）の値については、NIST暗号化ツールキット[NIST_DSA]のDSAの例を参照してください。 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（検証者）の間で対話的に実行されます。スキームのセットアップで、アリスは彼女の公開鍵A = g ^ a mod pを公開します。ここで、aは[0、q-1]からランダムに一様に選択された秘密鍵です。
The protocol works in three passes:
プロトコルは3つのパスで機能します。
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. アリスは、[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. ボブは[0、2 ^ t-1]からランダムに一様にチャレンジcを選択します。ここで、tはチャレンジのビット長です（たとえば、t = 160）。ボブはcをアリスに送信します。
3. Alice computes r = v - a * c mod q and sends it to Bob.
3. アリスはr = v-a * c mod qを計算し、それをボブに送信します。
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;
1. Aが[1、p-1]内にあり、A ^ q = 1 mod 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が有効な公開鍵であることを確認します。したがって、底gに関するAの離散対数が実際に存在します。アプリケーションによっては、アイデンティティ要素を有効な公開鍵として明確に除外する場合があることに注意してください。その場合、Aが[1、p-1]ではなく[2、p-1]内にあることを確認する必要があります。
The process is summarized in the following diagram.
このプロセスは、次の図に要約されています。
Alice Bob
------- -----
choose random v from [0, q-1]
[0、q-1]からランダムなvを選択
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
有限体上の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証明は、フィアット-シャミル変換[FS86]を介した対話型Schnorr識別スキームから取得されます。この変換では、安全な暗号化ハッシュ関数を使用してチャレンジを発行します。より具体的には、チャレンジは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 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は、Schnorr NIZKプルーフにコンテキスト情報（[ABM15]では「ラベル」とも呼ばれます）を柔軟に含めることができるように定義されているため、このドキュメントで定義されている手法は一般的に役立ちます。たとえば、Schnorr NIZKプルーフに基づいて構築された一部のセキュリティプロトコルは、プロトコル名、タイムスタンプなどのよりコンテキスト情報を含めたい場合があります。 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.
ハッシュ関数内では、2つの連結されたアイテムの間に明確な境界がなければなりません。各アイテムの先頭に、そのアイテムのバイト長を表す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の指数の知識を証明するために、アリスは次を含む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証明を生成するためのコストは、およそ1つのモジュラ指数です。つまり、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証明を検証するには、コストは約2のべき乗です。1つはA ^ q mod pの計算用で、もう1つはg ^ r * A ^ c mod pの計算用です。 （[MOV96]で説明されているように、同時べき乗法を使用して後者を計算するには、約1つのべき乗が必要です。）
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 [FIPS186-4]と同じEC設定を使用する場合があります。説明のために、ここでは素数フィールド（たとえば、NIST P-256）上の曲線のみを説明します。 ECDSAに適したバイナリフィールド上の他の曲線（[FIPS186-4]を参照）も、Schnorr NIZK証明の実装に使用できます。 E（Fp）を有限体Fpで定義される楕円曲線とします。ここで、pは大きな素数です。 Gを、素数次数の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曲線は例としてのみ使用されています。 Curve25519などの他の安全な曲線も、楕円曲線の離散対数問題（ECDLP）が扱いにくいままである限り、実装に適しています。
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].
スキームの設定で、アリスは彼女の公開鍵A = G x [a]を公開します。ここで、aは[1、n-1]からランダムに一様に選択された秘密鍵です。
The protocol works in three passes:
プロトコルは3つのパスで機能します。
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. アリスは[1、n-1]からランダムに一様に数値vを選択し、V = G x [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. ボブは[0、2 ^ t-1]からランダムに一様にチャレンジcを選択します。ここで、tはチャレンジのビット長です（たとえば、t = 80）。ボブはcをアリスに送信します。
3. Alice computes r = v - a * c mod n and sends it to Bob.
3. アリスはr = v-a * c mod nを計算し、それをボブに送信します。
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;
1. Aが曲線上の有効な点であり、A x [h]が無限遠の点ではないことを確認します。
2. To verify V = G x [r] + A x [c].
2. 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).
最初のチェックでは、Aが有効な公開鍵であることを確認します。したがって、底Gに関するAの離散対数が実際に存在します。公開鍵を検証するために完全なモジュラー累乗が必要なDSAのようなグループ設定とは異なり、ECDSAのような設定では、補因子が小さいため（1、2、または4）。
The process is summarized in the following diagram.
このプロセスは、次の図に要約されています。
Alice Bob
------- -----
choose random v from [1, n-1]
[1、n-1]からランダムなvを選択
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
楕円曲線上の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.
以前と同じように、非インタラクティブバリアントは、代わりに安全な暗号化ハッシュ関数を使用してチャレンジを発行することにより、フィアットシャミル変換[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).
要約すると、楕円曲線上の基底Gに関してA = G x [a]の離散対数の知識を証明するために、アリスは次の内容を含むSchnorr NIZK証明を生成します：{UserID、OtherInfo、V = G x [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証明を生成するためのコストは、1つのスカラー乗算です。つまり、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.
EC設定でSchnorr NIZKの証明を検証するためのコストは、楕円曲線の約1倍の乗算です。つまり、G x [r] + A x [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.
有限フィールド設定では、証明者は（UserIDおよびOtherInfoとともに）（V、r）を送信し、検証者は最初にcを計算してから、V = g ^ r * A ^ c mod pをチェックします。これには、サイズが通常2048〜3072ビットのZpの要素Vと、サイズが通常224〜256ビットのZqの要素rの送信が必要です。以下のように、送信データ量をZqの2つの要素に減らすことができます。
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.
変更されたバリアントでは、証明者は（V、r）ではなく（c、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）を送信することと同じです。したがって、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の証明は一般的に有用であり、幅広いアプリケーションに対応できる柔軟性を備えています。例えば、記載された技術は、ユーザが公開鍵登録フレーズの間に認証局（ＣＡ）に長期秘密鍵の所有の証明（ＰｏＰ）を示すことを可能にするために使用され得る。ハッシュには、証明を1つの特定のキー登録手順に関連付けるデータが含まれていることを確認する必要があります（たとえば、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. 正直な検証者のゼロ知識-証明者は、正直な検証者に1ビット以下の情報を漏らします：証明者が離散対数を知っているかどうか。
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.
フィアットシャミア変換は、3パスのインタラクティブなゼロ知識証明プロトコル（検証者がランダムなチャレンジを選択する）を非インタラクティブなプロトコルに変換する標準的な手法です。ただし、安全な暗号化ハッシュ関数が存在することが前提です。ハッシュ関数は公に定義されているため、証明者はそれ自体でチャレンジを計算できるため、プロトコルは非インタラクティブになります。この場合、ハッシュ関数（より正確には、セキュリティ証明のランダムオラクル）は、証明者から送信された各コミットメント（g ^ vまたはG x [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が証明者によって2回使用された（たとえば、乱数ジェネレータが失敗したため）が、検証者が異なるチャレンジcとc 'を選択するとします（または、ハッシュ関数が2つの異なるOtherInfoデータ、2つの異なる値cおよびc '）を生成します。攻撃者は2つの証明筆記録（V、c、r）と（V、c '、r'）を観察します。これに基づいて、次の方法で秘密鍵aを計算できます。
(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' 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:
より一般的には、このような攻撃は、値vが繰り返されない少し優れた（しかしまだ悪い）乱数ジェネレータでも機能する可能性がありますが、攻撃者はv '= v +のような2つの値vとv'の関係を知っています。 wは既知の値wです。攻撃者が2つの証明筆記録（V、c、r）と（V '、c'、r '）を観察するとします。彼は次の方法で秘密鍵を計算できます：
(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.
この例では、安全な乱数ジェネレータを使用して、シュノーのスキームで一時的な秘密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の証明は証明者自体に再生される可能性があります（暗号化プロトコルのアイテム間に望ましくない相関関係を導入するため）。この特定の攻撃は、ハッシュに一意のユーザーIDを含めることで防止されます。検証者は、証明者のUserIDが有効な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、「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.
[AN95]アンダーソン、R.、R。ニーダム、「公開鍵プロトコルのロバスト性の原則」、第15回年次国際暗号学会議、暗号学の進歩に関する議事録、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.
[FS86]フィアット、A。およびA.シャミール、「自分を証明する方法：識別および署名の問題に対する実際的な解決策」、第6回年次国際暗号化学会、暗号学の進歩に関する議事録、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]「効率的な暗号化の標準。SEC1：楕円曲線暗号化」、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。、「Cryptography：Theory and Practice」、第3版、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-4、2013年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 Cryptographic Toolkit、「DSA Examples」、<http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/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).
このドキュメントの編集者は、ディランクラーク、ロバートランソム、シャマックシャハンダシュティ、ロバートクラギー、スタニスラフスミシュライエフ、およびティボールイェーガーに役立つコメントを多数ありがとうございました。 Tibor Jagerは、一時的な秘密vがランダムに生成されない場合の最適化手法と脆弱性の問題を指摘しました。この作品は、EPSRC First Grant（EP / J011541 / 1）と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
Feng Hao（編集者）ニューカッスル大学（イギリス）ニューカッスル大学スクールオブコンピューティング、ニューカッスルアポンタインイギリス
Phone: +44 (0)191-208-6384
Email: feng.hao@ncl.ac.uk