翻訳: Verifiable Random Functions (VRFs)

Takami Torao 2019年 IETF Draft 4 #VRF #IETF
  • このエントリーをはてなブックマークに追加
CFRG
Internet-Draft
Intended status: Standards Track
Expires: August 12, 2019
S. Goldberg
L. Reyzin
Boston University
D. Papadopoulos
Hong Kong University of Science and Technology
J.Vcelak NS1
February 8, 2019

Abstract

Verifiable Random Functions (VRF) は公開鍵をキーとする暗号化ハッシュのバージョンである。秘密鍵の所有者のみがハッシュを算出できるが、公開鍵を持つ人であれば誰でもハッシュの正当性を検証できる。VRF はハッシュに基づくデータ構造の列挙を防ぐのに役に立つ。このドキュメントは暗号的乱数オラクルモデルで安全であるいくつかの VRF 構造を特定する。一方の VRF は RSA を使用し、もう一方の VRF は楕円曲線 (EC) を使用する。

Status of This Memo

この Internet-Draft は BCP 78 および BCP 79 の規定に完全に準拠して提出される。

Internet-Draft は Internet Engineering Task Force (IETF) の作業文書である。他のグループでも作業文書を Internet-Draft として配布する可能性があることに注意。現在の Internet-Draft のリストは https://datatracker.ietf.org/drafts/current/ に存在する。

Internet-Draft は最大 6 ヶ月間有効なドラフト文書であり、いつでも更新、置換または他の文書に置き換えられる可能性がある。Internet-Draft を参考資料として使用したり、「進行中の作業」以外として引用することは適切ではない。

この Internet-Draft は 2019 年 8 月 12 日に期限切れとなる。

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

この文書はこの文書の日付で発効される BCP 78 および IEFT’s Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) の対象となる。これらの文書は、この文書に関する権利と制限を説明しているため慎重に検討すること。本書から抽出されたコードコンポーネントには Trust Legal Provisions のセクション 4e に記載されている Simplified BSD License のテキストが含まれており、Simplified BSD License に記載されているとおり無保証で提供される。

1. Introduction

1.1 Rationale

Verifiable Random Functions (VRF) [MRV99] は公開鍵をキーとする暗号的ハッシュである。VRF 秘密鍵の所有者のみがハッシュを算出できるが、対応する公開鍵を持つ人は誰でもハッシュの正当性を検証することができる。

VRF の主な用途はハッシュに基づくデータ構造に格納されているデータのオフライン列挙 (例えば辞書攻撃) に対するプライバシーを保護することである。この用途では、Prover は VRF 秘密鍵を保持しており、入力データに対してハッシュに基づくデータ構造を構築するために VRF ハッシュを使用する。VRF の性質上、あるデータがデータ構造に格納されているかどうかについてのクエリーに答えることができるのは Prover のみである。VRF 公開鍵を知っている者であれば誰でも Prover がクエリーに正しく答えたかを検証することができる。しかしながら、データ構造に格納されているデータについてオフライン推論 (すなはち Prover に問い合わせることのない推論) を行うことはできない。

1.2 Requirements

この文書において "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", そして "OPTIONAL" は [RFC2119] に記載されているように解釈される。

1.3 Terminology

この文書では以下の用語を使用している。

  • \(S_k\): VRF の秘密鍵
  • \(P_k\): VRF の公開鍵
  • \(\alpha\) または \({\tt alpha\_string}\): VRF によってハッシュ化される入力
  • \(\beta\) または \({\tt beta\_string}\): VRF ハッシュ出力
  • \(\pi\) または \({\tt pi\_string}\): VRF 証明
  • Prover: VRF 秘密鍵 \(S_k\) と VRF 公開鍵 \(P_k\) を所有する Prover
  • Verifier: VRF 公開鍵 \(P_k\) を所有する Verifier

VRF Algorithms

VRF には VRF 公開鍵 \(P_k\) と VRF 秘密鍵 \(S_k\) を生成するキー生成アルゴリズムが付属している。

Prover は VRF 秘密鍵 \(S_k\) を使用して入力 \(\alpha\) をハッシュ化し、VRF ハッシュ出力 \(\beta\) を取得する。\[ \beta = {\rm VRF\_hash}(S_k, \alpha) \] \({\rm VRF\_hash}\) アルゴリズムは与えられた入力ペア \((S_k, \alpha)\) に対して同じ出力 \(\beta\) を生成するという意味で確定的である。Prover は \(\beta\) が正しいハッシュ出力であるという証明 \(\pi\) を生成するためにも秘密鍵 \(S_k\) を使用する。\[ \pi = {\rm VRF\_prove}(S_k, \alpha) \] この文書で定義されている VRF によって、証明 \(\pi\) から直接 VRF ハッシュ出力 \(\beta\) を以下のように決定することができる。\[ \beta = {\rm VRF\_proof\_to\_hash}(\pi) \] これは \[ {\rm VRF\_hash}(S_k, \alpha) = {\rm VRF\_proof\_to\_hash}({\rm VRF\_prove}(S_k, \alpha)) \] であることに注意。従って、この文書では \({\rm VRF\_hash}\) ではなく \({\rm VRF\_prove}\) と \({\rm VRF\_proof\_to\_hash}\) を使用する。

証明 \(\pi\) により、公開鍵 \(P_k\) を持つ Verifier は \(\beta\) が鍵 \(P_k\) による入力 \(\alpha\) の正しい VRF ハッシュであることの検証が可能となる。従って VRF には \(\pi\) が有効な場合は \(({\rm VALID}, \beta = {\rm VRF\_proof\_to\_hash}(\pi))\) を出力し、それ以外の場合は \({\rm INVALID}\) を出力するアルゴリズム \[ {\rm VRF\_verify}(P_k, \alpha, \pi) \] も付属している。

3. VRF Security Properties

VRF は次のセキュリティ特性を保証するように設計されている。

3.1 Full Uniqueness or Trusted Uniqueness

一意性 (uniqueness) とは、どのような VRF 公開鍵とどのような入力 \(\alpha\) に対しても、有効性を証明することのできる一意な VRF 出力 \(\beta\) が存在することを意味している。一意性は VRF 秘密鍵 \(S_k\) を知っている敵対的な Prover に対しても成り立たなければならない。

より正確に "完全な一意性" (full uniqueness) とは、計算上の制限を持つ敵対者は VRF 公開鍵 \(P_k\)、VRF 入力 \(\alpha\)、および、\(\beta_1 \ne \beta_2\) で \({\rm VRF\_verify}(P_k, \alpha, \pi_1)\) が \(({\rm VALID}, \beta_1)\) を出力し \({\rm VRF\_verify}(P_k, \alpha, \pi_2)\) が \(({\rm VALID}, \beta_2)\) を出力する 2 つの証明 \(\pi_1\) と\(\pi_2\) を選択することができない。

"信頼できる一意性" (trusted uniqueness) と呼ばれるわずかに弱いセキュリティ特性は多くのアプリケーションにとって十分である。信頼できる一意性は完全な一意性と同じだが、VRF 鍵 \(P_k\) と \(S_k\) が信頼できる方法で生成された場合にのみ有効である。言い換えれば、鍵が無効な方法で生成された場合やランダム性が悪い場合には一意性が保持されない可能性がある。

3.2 Full Collision Resistance or Trusted Collision Resistance

他の暗号ハッシュ関数と同様に VRF も衝突耐性が必要である。VRF 秘密鍵 \(S_k\) を知っている敵対的な Prover でさえも衝突に対する耐性は成り立たなければならない。

より正確に "完全衝突耐性" full collision resistance) とは、例えてきた医者が VRF 秘密鍵 \(S_k\) を知っていたとしても、敵対者が同じ VRF ハッシュ \(\beta\) となる 2 つの異なる VRF 入力 \(\alpha_1\) および \(\alpha_2\) を見つけることは計算上不可能であるべきである。

ほとんどのアプリケーションでは "信頼された衝突耐性" (trusted collision resistance) と呼ばれるわずかに弱いセキュリティ特性で十分である。信頼できる衝突耐性は衝突耐性と同じだが \(P_k\) と \(S_k\) が信頼できる方法で生成された場合にのみ有効である。

3.3 Full Pseudorandomness or Selective Pseudorandomness

擬似ランダム性は、敵対的 Verifier が VRF 証明 \(\pi\) なしで VRF ハッシュ出力 \(\beta\) を見かけても、その \(\beta\) がランダム値と区別が付かない事を保証する。

より正確には、VRF 公開および秘密鍵 \((P_k,S_k)\) が信頼できる方法で生成されたとすると、擬似ランダム性は、敵対的に選択された任意の "target" VRF 入力 \(\alpha\) の VRF ハッシュ出力 \(\beta\) (対応する VRF 証明 \(\pi\) のない) が、VRF 秘密鍵 \(S_k\) を知らない計算上の限界がある敵対者に対して乱数と見分けが付かないことを保証する。敵対者が他の VRF 入力 \(\alpha'\) を選択して、それらに対応する VRF ハッシュ出力 \(\beta'\) および証明 \(\pi'\) も得たとしてもこれは成立する。

"完全な疑似乱数性" により敵対者は VRF 出力 \(\beta'\) を観察し、選択された様々な入力 \(\alpha'\) に対する証明 \(\pi'\) を得た後でも、いつでも "target" VRF 入力 \(\alpha\) を選択することもできる。

"選択的疑似乱数性" は弱いが多くのアプリケーションで十分なセキュリティ特性である。ここで敵対者は VRF 公開鍵 \(P_k\) と無関係、かつ、その選択の入力 \(\alpha'\) に対して VRF 出力 \(\beta'\) と証明 \(\pi'\) を観察する前に VRF 入力 \(\alpha\) を選択しなければならない。

VRF 出力 \(\beta\) が Prover または VRF 秘密鍵 \(S_k\) を知っている他の当事者にとってランダムには見えていないことを注意しておくことが重要である。そのような当事者は \(\beta\) を \({\rm VRF\_hash}(S_k, \alpha)\) の結果と比較することによって \(\beta\) をランダムな値から容易に区別することができる。

また VRF 鍵の生成が信頼できる方法で行われていない場合、VRF 出力 \(\beta\) はランダムに見えないかも知れない。(例えば VRF 鍵が質の悪い乱数によって生成された場合。)

3.4 A random-oracle-like unpredictability property

VRF 鍵が敵対的に生成された場合、セクション 3.3 で定義されているように疑似乱数は成立しない。例えば敵対者が決定論的に生成された (またはハードコードされ公に知られている) VRF 鍵を出力した場合、その出力は誰でも容易に導き出すことができる。

しかし、特定の VRF アプリケーションには異なる種類の予測不可能性がある ([GHMVZ17] や [KRDO17] など)。この性質は (通常の鍵なしの) 暗号ハッシュ関数によってもたらされる予測不可能性に似ている。入力が十分なエントロピーを持っている (すなはち予測できない) 場合、正しい出力は一様乱数と区別が付かない。

この特性は正式な定義も証明も暗号文献には現れていないが、公開鍵が信頼できる方法で生成されればこの仕様で提示された VRF スキームはこのプロパティを満たすと信じられている。さらに ECFRV は公開鍵が信頼できる方法で生成されなかったとしても、その公開鍵がセクション 5.6 の鍵検証手順を満たしている限りこの特性も満たしている。

4. RSA Full Domain Hash VRF (RSA-FDH-VRF)

5. Elliptic Curve VRF (ECVRF)

楕円曲線 Verifiable Random Function (ECVRF) はセクション 3 で定義されている信頼できる一意性、信頼できる衝突耐性、完全な疑似乱数特性を持っている。この VRF のセキュリティはランダムオラクルモデルにおける決定論的 Diffie-Hellman (DDH) 仮定から得られる。正式なセキュリティ証明は [PWHVNRG17] である。

さらなる "完全な一意性" と "完全な衝突耐性" を満たすために、Verifier は VRF 公開鍵の受信したときにセクション 5.6 で指定されている検証手順をさらに実行する必要がある。

固定オプション (セクション 5.5 で詳述):

  • \(F\) - 有限フィールド。
  • \(2n\) - \(F\) のフィールド要素の長さ(オクテット単位)。最も近い偶数の整数に切り上げ。
  • \(E\) - \(F\) 上で定義された楕円曲線 (EC)。
  • \({\rm ptLen}\) - オクテット文字列としてエンコードされた EC ポイントの長さ (オクテット)。
  • \(G\) - 大きな素数次の \(E\) の部分群。
  • \(q\) - \(G\) 群の素数。
  • \({\rm qLen}\) - オクテット単位の \(q\) の長さ、すなはち \(2^{8{\rm qLen}} \gt q\) となるような最小の整数 (通常 \({\rm qLen}\) は \(2n\) に等しいか \(2n\) に近いことに注意)。
  • cofactor - \(E\) 上の点の数を \(q\) で割ったもの。
  • \(B\) - \(G\) 群のジェネレータ。
  • \({\rm hash}\) - 暗号化ハッシュ関数。
  • \({\rm hLen}\) - \({\rm hash}\) のオクテット単位の出力長。\(2n\) 以上でなければならない。
  • suite_string - 上記のオプションを決定する ECVRF 暗号スイートを指定する単一のゼロ以外のオクテット。

使用される表記とプリミティブ:

楕円曲線演算は加法的表記で記述され、\(P + Q\) は点の加算を表し \(x \times P\) は点 \(P\) とスカラー \(x\) とのスカラー倍を表す。

  • \(x^y\) - \(x\) の \(y\) 乗。
  • \(x\times y\) - \(x\) の \(y\) 倍。
  • || - オクテット文字列の連結。
  • \({\rm ECVRF\_hash\_to\_curve}\) - EC 点への文字列の衝突耐性ハッシュ; セクション 5.4.1 で説明されセクション 5.5 で指定されたオプション。
  • \({\rm ECVRF\_nonce\_generation}\) - \(S_k\) と ECVRF 証明の一部として入力から疑似乱数 nonce を導く。セクション 5.5 で詳述
  • \({\rm ECVRF\_hash\_points}\) - 整数で表された EC 点の衝突耐性ハッシュ。セクション 5.4.3 で詳述。

型変換:

  • int_to_string(a, len) - セクション5.5で詳述する、非負整数 a を長さ len のオクテット文字列へ変換する。
  • string_to_int(a_string) - セクション 5.5 で詳述する、オクテット文字列 a_string を非負整数に変換する。
  • point_to_string - EC 点を \({\rm ptLen}\) のオクテット文字列に変換する。セクション 5.5 で詳述。
  • string_to_point - \({\rm ptLen}\) のオクテット文字列を EC 点に変換する。セクション5.5 で詳述。string_to_point はオクテット文字列が正しい EC 点に変換できない場合に INVALID を返す。
  • arbitrary_string_to_point - 任意長オクテット文字列を EC 点に変換する。セクション 5.5 で詳述。

(big integer と楕円曲線演算用の) 特定のソフトウェアライブラリでは int_to_string および point_to_string 変換は不要である。例えばいくつかの実装では、個別に楕円曲線点タイプを導入することはせず、EC 点演算は入力としてオクテット文字列を取り、出力としてオクテット文字列を生成する。

使用されるパラメータ (これらのパラメータの生成はセクション 5.5 で詳述する):

  • \(S_k\) - VRF 秘密鍵。
  • \(x\) - 整数としての VRF 秘密スカラー値。

    注意: 使用される暗号スイートに応じて VRF 秘密スカラー値は \(S_k\) に等しい場合がある; そうでなければ \(S_k\) から派生する。

  • \(Y = x \times B\) - VRF 公開鍵で EC 点。

5.1 ECVRF Proving

\({\rm ECVRF\_prove}(S_k, {\tt alpha\_string})\)

Input:
  • \(S_k\) - VRF 秘密鍵。
  • \({\tt alpha\_string}\) - オクテット文字列としての入力値 \(\alpha\)。
Output:
  • \({\tt pi\_string}\) - 長さ \({\rm ptLen} + n + {\rm qLen}\) のオクテット文字列。
Steps:
  1. \(S_k\) を使用して VRF 秘密スカラー値 \(x\) と VRF 公開鍵 \(Y = x \times B\) を導出する (この導出はセクション 5.5 のように暗号スイートに依存する。これらの値は鍵生成後などにキャッシュでき毎回再導出する必要はない)。
  2. \(H = {\rm ECVRF\_hash\_to\_curve}({\tt suite\_string}, Y, {\tt alpha\_string})\)
  3. \({\tt h\_string} = {\rm point\_to\_string}(H)\)
  4. \(\Gamma = x \times H\)
  5. \(k = {\rm ECVRF\_nonce\_generation}(S_k, {\tt h\_string})\)
  6. \(c = {\rm ECVRF\_hash\_points}(H, \Gamma, k \times B, k \times H)\)
  7. \(s = (k + c \times x) \mod q\)
  8. \({\tt pi\_string} = {\rm point\_to\_string}(\Gamma)\ ||\ {\rm int\_to\_string}(c, n)\ ||\ {\rm int\_to\_string}(s, {\rm qLen})\)
  9. \({\tt pi\_string}\) を出力

5.2 ECVRF Proof To Hash

\({\rm ECVRF\_proof\_to\_hash}({\tt pi\_string})\)

Input:
  • \({\tt pi\_string}\) - VRF 証明。長さ \({\rm ptLen} + n + {\rm qLen}\) のオクテット文字列。
Output:
  • "INVALID" または
  • \({\tt beta\_string}\) - VRF ハッシュ出力。長さ \({\rm hLen}\) のオクテット文字列。
Important note:

\({\rm ECVRF\_proof\_to\_hash}\) は \({\rm ECVRF\_prove}\) によって生成されたことが分かっている \({\tt pi\_string}\)、またはセクション 5.3 で指定されている \({\rm ECVRV\_verify}\) 内からのみ実行されるべきである。

Steps:
  1. \(D = {\rm ECVRF\_decode\_proof}({\tt pi\_string})\)
  2. もし \(D\) が "INVALID" であれば "INVALID" を出力して停止。
  3. \((\Gamma, c, s) = D\)
  4. \({\tt three\_string} = {\tt 0x03} = {\rm int\_to\_string}(3, 1)\)、値 3 の 1 文字オクテット。
  5. \({\tt beta\_string} = {\rm Hash}({\tt suite\_string}\ ||\ {\tt three\_string}\ ||\ {\rm point\_to\_string}({\rm cofactor} \times \Gamma)\)
  6. \({\tt beta\_string}\) を出力

5.3 ECVRF Verifying

\({\rm ECVRF\_verify}(Y, {\tt pi\_string}, {\tt alpha\_string})\)

Input:
  • \(Y\) - EC 点の公開鍵。
  • \({\tt pi\_string}\) - VRF 証明。長さ \({\rm ptLen} + n + {\rm qLen}\) のオクテット文字列。
  • \({\tt alpha\_string}\) - VRF 入力。オクテット文字列。
Output:
  • \((\)"VALID"\(, {\tt beta\_string})\)。ここで \({\tt beta\_string}\) は VRF ハッシュ出力で長さ \({\rm hLen}\) のオクテット文字列; または "INVALID"
Steps:
  1. \(D = {\rm ECVRF\_decode\_proof}({\tt pi\_string})\)
  2. もし \(D\) が "INVALID" なら "INVALID" を出力して停止。
  3. \((\Gamma, c, s) = D\)
  4. \(H = {\rm ECVRF\_hash\_to\_curve}({\tt suite\_string}, Y, {\tt alpha\_string})\)
  5. \(U = s \times B - c \times Y\)
  6. \(c' = {\rm ECVRF\_hash\_points}(H, \Gamma, U, V)\)
  7. もし \(c\) と \(c'\) が同じであれば \((\)"VALID"\(, {\rm ECVRF\_proof\_to\_hash}({\tt pi\_string})\) を出力; そうでなければ "INVALID" を出力。

5.4 ECVRF Auxiliary Functions

6. Implementation Status

ECVRF-P256-SHA256-TAI, ECVRF-P256-SHA256-SWU, ECVRF-ED25519-SHA512-TAI, ECVRF-ED25519-SHA512-Elligator2 の参照実装は <https://github.com/reyzin/ecvrf> から利用できる。この実装はセキュアでも特別に効率的でもないがテストベクトルの生成に使用することはできる。

ECVRF-ED25519-SHA512-Elligator2 の実装は <https://github.com/algorand/libsodium/tree/draft-irtf-cfrg-vrf-03/src/libsodium/crypto_vrf/ietfdraft03> から利用できる。

RSA-FDH-VRF (SHA-256) および ECVRF-P256-SHA256-TAI の earlier でわずかに異なるバージョンは NSEC5 プロジェクト[I-D.vcelak-nsec5]の一部として最初に開発され、<http://github.com/fcelda/nsec5-crypto> から利用することができる。

Google の Key Transparency プロジェクトでは ECVRF-P256-SHA256-TAI に似た VRF 実装を使用しているが、SHA-256 の代わりに SHA-512 を使用するなどいくつかの小さな変更が加えられている。この実装は <https://github.com/google/keytransparency/blob/master/core/vrf/vrf.go> から利用することができる。

ECVRF と似た Yahoo! による実装は <https://github.com/r2ishiguro/vrf> から利用することができる。

ECVRF に似た実装は Golan による CONIKS 実装の一部として <https://github.com/coniks-sys/coniks-go/tree/master/crypto/vrf> で利用することができる。

Open Whisper Systems は VXEdDSA と呼ばれる ECVRF-ED25519-SHA512-Elligator にとても似た VRF も使用しておりここで詳述されている: <https://whispersystems.org/docs/specifications/xeddsa/>

7. Security Considerations

7.1 Key Generation

この文書で定義されている VRF を使用するアプリケーションは VRF 鍵が良質な乱数を使って正しく生成されていることを保証しなければならない。

7.1.1 Uniqueness and collision resistance with untrusted keys

7.1.2 Pseudorandomness with untrusted keys

7.2 Selective vs Full Pseudorandomness

7.3 Proper pseudorandom nonce for ECVRF

7.4 Side-channel attacks

7.5 Proofs Provide No Secrecy for VRF Input

7.6 Prehashing

7.7 Hash function domain separation and future-proofing

8. Change Log

9. Contributors

10. References

10.1 Normative References

  1. [FIPS-186-4] National Institute for Standards and Technology, "Digital Signature Standard (DSS)", FIPS PUB 186-4, July 2013, <https://csrc.nist.gov/publications/detail/fips/186/4/final>.
  2. [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>.
  3. [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman Groups for Use with IETF Standards", RFC 5114, DOI 10.17487/RFC5114, January 2008, <https://www.rfc-editor.org/info/rfc5114>.
  4. [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, May 2011, <https://www.rfc-editor.org/info/rfc6234>.
  5. [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 2013, <https://www.rfc-editor.org/info/rfc6979>.
  6. [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, <https://www.rfc-editor.org/info/rfc8017>.
  7. [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, <https://www.rfc-editor.org/info/rfc8032>.
  8. [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: Elliptic Curve Cryptography", Version 2.0, May 2009, <http://www.secg.org/sec1-v2.pdf>.

10.1 Normative References

  1. [ANSI.X9-62-2005] American National Standards Institute, "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", ANSI X9.62, 2005.
  2. [BCIMRT10] Brier, E., Coron, J., Icart, T., Madore, D., Randriam, H., and M. Tibouchi, "Efficient Indifferentiable Hashing into Ordinary Elliptic Curves", in Advances in Cryptology - CRYPTO, 2010, <https://eprint.iacr.org/2009/340>.
  3. [BHKT13] Bernstein, D., Hamburg, M., Krasnova, A., and T. Lange, "Elligator: elliptic-curve points indistinguishable from uniform random strings", in ACM SIGSAC Conference on Computer and Communications Security (CCS), 2013, <https://elligator.cr.yp.to/elligator-20130828.pdf>.
  4. [GHMVZ17] Gilad, Y., Hemo, R., Micali, Y., Vlachos, Y., and Y. Zeldovich, "Algorand: Scaling Byzantine Agreements for Cryptocurrencies", in Proceedings of the 26th Symposium on Operating Systems Principles (SOSP), 2017, <https://eprint.iacr.org/2017/454>.
  5. [I-D.irtf-cfrg-hash-to-curve] Scott, S., Sullivan, N., and C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg-hash-to-curve-01 (work in progress), July 2018.
  6. [I-D.vcelak-nsec5] Vcelak, J., Goldberg, S., Papadopoulos, D., Huque, S., and D. Lawrence, "NSEC5, DNSSEC Authenticated Denial of Existence", draft-vcelak-nsec5-08 (work in progress), December 2018.
  7. [KRDO17] Kiayias, A., Russell, A., David, B., and R. Oliynykov, "Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol", in Advances in Cryptology - CRYPTO, 2017, <https://eprint.iacr.org/2016/889>.
  8. [MRV99] Michali, S., Rabin, M., and S. Vadhan, "Verifiable Random Functions", in FOCS, 1999, <https://dash.harvard.edu/handle/1/5028196>.
  9. [ntb] Shoup, V., "A Computational Introduction to Number Theory and Algebra", 2008, <http://www.shoup.net/ntb/ntb-v2.pdf>.
  10. [PWHVNRG17] Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J., Naor, M., Reyzin, L., and S. Goldberg, "Making NSEC5 Practical for DNSSEC", in ePrint Cryptology Archive 2017/099, February 2017, <https://eprint.iacr.org/2017/099.pdf>.
  11. [SW06] Shallue, A. and C. van de Woestijne, "Construction of rational points on elliptic curves over finite fields", in Algorithmic Number Theory - ANTS, 2006, <https://works.bepress.com/andrew_shallue/1/>.
  12. [Ulas07] Ulas, M., "Rational points on certain hyperelliptic curves over finite fields", in Bull. Polish Acad. Sci. Math., 2007, <https://arxiv.org/abs/0706.1448>.
  13. [X25519] Bernstein, D., "How do I validate Curve25519 public keys?", 2006, <https://cr.yp.to/ecdh.html#validate>.

Appendix A. Test Vectors for the ECVRFs

A.1 ECVRF-P256-SHA256-TAI

A.2 ECVRF-P256-SHA256-SWU

A.3 ECVRF-ED25519-SHA512-TAI

A.3 ECVRF-ED25519-SHA512-Elligator2

これらの 3 つの秘密鍵とメッセージの例は [RFC8032] のセクション 7.1 から得ている。

\(S_k\) = 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60
\(P_k\) = d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a
\(\alpha\) = (the empty string)
\(x\) = 307c83864f2833cb427a2ef1c00a013cfdff2768d980c0a3a520f006904de94f
In Elligator: \(r\) = 9ddd071cd5837e591a3a40c57a46701bb7f49b1b53c670d490c2766a08fa6e3d
In Elligator: \(w\) = c7b5d6239e52a473a2b57a92825e0e5de4656e349bb198de5afd6a76e5a07066
In Elligator: \(e\) = -1
\(H\) = 1c5672d919cc0a800970cd7e05cb36ed27ed354c33519948e5a9eaf89aee12b7
\(k\) = 868b56b8b3faf5fc7e276ff0a65aaa896aa927294d768d0966277d94599b7afe4a6330770da5fdc2875121e0cbecbffbd4ea5e491eb35be53fa7511d9f5a61f2
\(U\) = \(k\times B\) = c4743a22340131a2323174bfc397a6585cbe0cc521bfad09f34b11dd4bcf5936
\(V\) = \(k\times H\) = e309cf5272f0af2f54d9dc4a6bad6998a9d097264e17ae6fce2b25dcbdd10e8b
\(\pi\) = b6b4699f87d56126c9117a7da55bd0085246f4c56dbc95d20172612e9d38e8d7ca65e573a126ed88d4e30a46f80a666854d675cf3ba81de0de043c3774f061560f55edc256a787afe701677c0f602900
\(\beta\) = 5b49b554d05c0cd5a5325376b3387de59d924fd1e13ded44648ab33c21349a603f25b84ec5ed887995b33da5e3bfcb87cd2f64521c4c62cf825cffabbe5d31cc

\(S_k\) = 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb
\(P_k\) = 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c
\(\alpha\) = 72 (1 byte)
\(x\) = 68bd9ed75882d52815a97585caf4790a7f6c6b3b7f821c5e259a24b02e502e51
In Elligator: \(r\) = 92181bd612695e464049590eb1f9746750d6057441789c9759af8308ac77fd4a In Elligator: \(w\) = 7ff6d8b773bfbae57b2ab9d49f9d3cb7d9af40a03d3ed3c6beaaf2d486b1fe6e
In Elligator: e = 1
\(H\) = 86725262c971bf064168bca2a87f593d425a49835bd52beb9f52ea59352d80fa
\(k\) = fd919e9d43c61203c4cd948cdaea0ad4488060db105d25b8fb4a5da2bd40e4b8330ca44a0538cc275ac7d568686660ccfd6323c805b917e91e28a4ab352b9575
\(U\) = \(k\times B\) = 04b1ba4d8129f0d4cec522b0fd0dff84283401df791dcc9b93a219c51cf27324
\(V\) = \(k\times H\) = ca8a97ce1947d2a0aaa280f03153388fa7aa754eedfca2b4a7ad405707599ba5
\(\pi\) = ae5b66bdf04b4c010bfe32b2fc126ead2107b697634f6f7337b9bff8785ee111200095ece87dde4dbe87343f6df3b107d91798c8a7eb1245d3bb9c5aafb093358c13e6ae1111a55717e895fd15f99f07
\(\beta\) = 94f4487e1b2fec954309ef1289ecb2e15043a2461ecc7b2ae7d4470607ef82eb1cfa97d84991fe4a7bfdfd715606bc27e2967a6c557cfb5875879b671740b7d8

SK = c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7
PK = fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025
alpha = af82 (2 bytes)
x = 909a8b755ed902849023a55b15c23d11ba4d7f4ec5c2f51b1325a181991ea95c
In Elligator: r = dcd7cda88d6798599e07216de5a48a27dcd1cde197ab39ccaf6a906ae6b25c7f
In Elligator: w = 2ceaa2c2ff3028c34f9fbe076ff99520b925f18d652285b4daad5ccc467e523b
In Elligator: e = -1
H = 9d8663faeb6ab14a239bfc652648b34f783c2e99f758c0e1b6f4f863f9419b56
k = 8f675784cdc984effc459e1054f8d386050ec400dc09d08d2372c6fe0850eaaa5 0defd02d965b79930dcbca5ba9222a3d99510411894e63f66bbd5d13d25db4b
U = k*B = d6f8a95a4ce86812e3e50febd9d48196b3bc5d1d9fa7b6dfa33072641b45d029
V = k*H = f77cd4ce0b49b386e80c3ce404185f93bb07463600dc14c31b0a09beaff4d592
pi = dfa2cba34b611cc8c833a6ea83b8eb1bb5e2ef2dd1b0c481bc42ff36ae7847f6 ab52b976cfd5def172fa412defde270c8b8bdfbaae1c7ece17d9833b1bcf31064fff7 8ef493f820055b561ece45e1009
beta = 2031837f582cd17a9af9e0c7ef5a6540e3453ed894b62c293686ca3c1e319d de9d0aa489a4b59a9594fc2328bc3deff3c8a0929a369a72b1180a596e016b5ded

Authors' Addresses

Sharon Goldberg
Boston University
111 Cummington St, MCS135
Boston, MA 02215
USA

EMail: goldbe@cs.bu.edu

Leonid Reyzin
Boston University
111 Cummington St, MCS135
Boston, MA 02215
USA

EMail: reyzin@bu.edu

Dimitrios Papadopoulos
Hong Kong University of Science and Techology
Clearwater Bay
Hong Kong

EMail: dipapado@cse.ust.hkbu.edu

Jan Vcelak
NS1
16 Beaver St
New York, NY 10004
USA

EMail: jvcelak@ns1.com

参考文献

  1. Verifiable Random Functions (VRFs) draft-irtf-cfrg-vrf-04
F