翻訳: Verifiable Random Functions (VRFs)

Abstract

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

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 暗号スイートを指定する単一のゼロ以外のオクテット。

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

型変換:

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

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 から得ている。

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